数据结构概念及顺序表精.ppt

数据结构概念及顺序表第1页，本讲稿共22页2.1 2.1 数据结构基本概念数据结构基本概念1数据（数据（data）数据是指能够输入到计算机中，并被计算机识别数据是指能够输入到计算机中，并被计算机识别和处理的符号的集合和处理的符号的集合。2数据元素（数据元素（data element）数数据据元元素素是是组组成成数数据据的的基基本本单单位位。数数据据元元素素是是一一个个数数据据整整体体中中相相对对独独立立的的单单位位。但但它它还还可可以以分分割割成成若若干干个个具具有有不不同同属属性性的的项项（字字段段），故故不不是是组组成成数数据据的的最小单位最小单位第2页，本讲稿共22页数据结构（数据结构（data structure）是是指指相相互互之之间间存存在在一一种种或或多多种种特特定定关关系系的的数数据据元元素素所所组组成成的的集集合合。数数据据结结构构包包含含三三个个方方面面的的内内容容，即即数数据据的的逻逻辑辑结结构构，数数据据的的存存贮贮结结构构和和对对数数据据所所施施加的运算加的运算。这三个方面的关系为这三个方面的关系为：数数据据的的逻逻辑辑结结构构独独立立于于计计算算机机，是是数数据据本本身身所所固固有有的的存存贮贮结结构构是是逻逻辑辑结结构构在在计计算算机机存存贮贮器器中中的的映映像像，必必须须依依赖赖于计算机。于计算机。运运算算是是指指所所施施加加的的一一组组操操作作总总称称。运运算算的的定定义义直直接接依依赖赖于逻辑结构，但运算的实现必依赖于存贮结构。于逻辑结构，但运算的实现必依赖于存贮结构。第3页，本讲稿共22页数据结构基本类型数据结构基本类型 线性结构线性结构 通迅录、成绩单、花名册通迅录、成绩单、花名册树形结构树形结构 电子字典、家谱、目录电子字典、家谱、目录图状结构图状结构 交通线路、通信网络交通线路、通信网络第4页，本讲稿共22页数据结构中常用的存贮结构数据结构中常用的存贮结构(1)顺序存贮顺序存贮所所有有元元素素存存放放在在一一片片连连续续的的存存贮贮单单元元中中，逻逻辑辑上上相相邻邻的元素存放到计算机内存仍然相邻。的元素存放到计算机内存仍然相邻。(2)链式存贮链式存贮所所有有元元素素存存放放在在可可以以不不连连续续的的存存贮贮单单元元中中，元元素素之之间间的的关关系系通通过过地地址址确确定定，逻逻辑辑上上相相邻邻的的元元素素存存放放到到计计算算机内存后不一定是相邻的。机内存后不一定是相邻的。(3)索引存贮（略）索引存贮（略）(4)散列存贮（略）散列存贮（略）第5页，本讲稿共22页算法（算法（algorithm）通通俗俗地地讲讲，算算法法就就是是一一种种解解题题的的方方法法。更更严严格格地地说说，算算法法是是由由若若干干条条指指令令组组成成的的有有穷穷序序列列，它它必必须须满满足足下下述述条件（也称为算法的五大特性）：条件（也称为算法的五大特性）：（1）输输入入：具具有有0个个或或多多个个输输入入的的外外界界量量（算算法法开开始始前前的的初初始始量）量）（2）输出：）输出：至少产生一个输出，它们是算法执行完后的结果。至少产生一个输出，它们是算法执行完后的结果。（3）有穷性：）有穷性：每条指令的执行次数必须是有限的。每条指令的执行次数必须是有限的。（4）确定性：）确定性：每条指令的含义都必须明确，无二义性。每条指令的含义都必须明确，无二义性。（5）可行性：）可行性：每条指令的执行时间都是有限的。每条指令的执行时间都是有限的。第6页，本讲稿共22页1 时间复杂度时间复杂度一个算法花费的时间与算法中语句的执行次数一个算法花费的时间与算法中语句的执行次数成正比，哪个算法中语句执行次数多，它花费时间成正比，哪个算法中语句执行次数多，它花费时间就多。就多。数据结构中数据元素个数数据结构中数据元素个数n称为问题的规模，当称为问题的规模，当n不断变化时，语句的执行次数也会变化。一个算不断变化时，语句的执行次数也会变化。一个算法中的时间复杂度一般用语句执行次数的数量级来法中的时间复杂度一般用语句执行次数的数量级来衡量。衡量。例如：例如：for(i=1;i=n;i+)for(j=1;j=i;j+)dij=dataij+1;算法分析算法分析O(n2)第7页，本讲稿共22页2 空间复杂度空间复杂度与时间复杂度类似，空间复杂度是指算法在与时间复杂度类似，空间复杂度是指算法在计算机内执行时所占用的内存开销规模。但我们计算机内执行时所占用的内存开销规模。但我们一般所讨论的是除正常占用内存开销外的辅助存一般所讨论的是除正常占用内存开销外的辅助存储单元规模。讨论方法与时间复杂度类似，不再储单元规模。讨论方法与时间复杂度类似，不再赘述。赘述。第8页，本讲稿共22页2.22.2 线性数据结构线性数据结构 线性表是由有限个同类型的数据元素组成的有序序列，一般记作（a1,a2,an）。除了a1和an之外，任意元素ai都有一个直接前趋ai-1和一个直接后继ai+1。a1无前趋，an无后继。线性表的存储结构主要有顺序存储结构和链式存储结构两种。第9页，本讲稿共22页顺序表顺序表 采用顺序存储结构的线性表称为顺序表，它的数据元素采用顺序存储结构的线性表称为顺序表，它的数据元素按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上按照逻辑顺序依次存放在一组连续的存储单元中。逻辑上相邻的数据元素，其存储位置也彼此相邻。相邻的数据元素，其存储位置也彼此相邻。假定元素假定元素a1的物理地址是的物理地址是Loc(aLoc(a1 1)，每个元素占，每个元素占d个存个存储单元，则第储单元，则第i个元素的存储位置为个元素的存储位置为：Loc(ai)=Loc(a1)+(i-1)*d length=n maxsize0 1 i-2 i-1 i n-1 a2ai-1aiai+1a1an第10页，本讲稿共22页顺序表类描述顺序表类描述const int MAXSIZE=100;/顺序表最大允许长度顺序表最大允许长度class SeqListpublic:ElemType dataMAXSIZE;/存储数据的数组存储数据的数组 int length;/顺序表当前长度顺序表当前长度 SeqList()length=0;/构造函数构造函数 void ClearList()length=0;/将顺序表置为空表将顺序表置为空表 /判断顺序表是否为空表判断顺序表是否为空表 bool IsListEmpty()return length=0;(下页下页continue.)第11页，本讲稿共22页(接上页接上页 )/判断顺序表是否为满判断顺序表是否为满 bool IsListFull()return length=MAXSIZE;/在表中删除第在表中删除第i个元素个元素 void ListDelete(int i);/在表中第在表中第 i 个位置插入新元素个位置插入新元素x void ListInsert(int i,ElemType x);int Find(ElemType x);/在表中查找元素在表中查找元素;（1）ElemType代表数组的代表数组的某种某种类型。类型。（2）length表示线性表当前长度，初始长度为表示线性表当前长度，初始长度为0（空表），最大不超过（空表），最大不超过maxsize。第12页，本讲稿共22页顺序表的主要算法顺序表的主要算法（1 1）在表中第）在表中第 i i 个位置插入新元素个位置插入新元素x x 算法实现的主要步骤是：算法实现的主要步骤是：判断插入位置的合理性以及表是否已满。判断插入位置的合理性以及表是否已满。从最后一个元素开始依次向前，将每个元从最后一个元素开始依次向前，将每个元素向后移动一个位置，直到第素向后移动一个位置，直到第i i个元素为止。个元素为止。向空出的第向空出的第i i个位置存入新元素个位置存入新元素x x。最后还要将线性表长度加一。最后还要将线性表长度加一。第13页，本讲稿共22页第14页，本讲稿共22页void SeqList:ListInsert(int i,ElemType x)if(ilength+1|length=MAXSIZE)cout=i-1;j-)dataj+1=dataj;/元素依次向后移动元素依次向后移动 datai-1=x;/向第向第i个位置存入新元素个位置存入新元素 length+;/表长度加表长度加1 第15页，本讲稿共22页（2）在表中删除第i个元素 算法实现的主要步骤是：算法实现的主要步骤是：判断删除位置的合理性。判断删除位置的合理性。从第从第i+1i+1个元素开始，依次向后直个元素开始，依次向后直到最后一个元素为止，将每个元素向到最后一个元素为止，将每个元素向前移动一个位置。这时第前移动一个位置。这时第i i个元素已个元素已经被覆盖删除。经被覆盖删除。最后还要将线性表长度减一。最后还要将线性表长度减一。第16页，本讲稿共22页第17页，本讲稿共22页void SeqList:Delete(int i)if(iL-length)cout表中没有第表中没有第i个元素个元素;else for(int j=i;j=length-1;j+)dataj-1=dataj;/元素依次向前移动元素依次向前移动 length-;第18页，本讲稿共22页（3）在表中查找某个元素 下下面面是是根根据据数数据据元元素素本本身身的的值值进进行行查查询询的的算算法法，x为为需需要要查查找找的的元元素素，算算法法返返回回元元素素的的实实际际位位置。置。int SeqList:Find(ElemType x)for(int i=0;ilength;i+)/查找成功，返回元素位置查找成功，返回元素位置 if(datai=x)return i+1;return 0;/查找失败，返回查找失败，返回 0 第19页，本讲稿共22页顺序表应用举例顺序表应用举例【例例2-1】利用顺序表表示多项式，实现两个一元利用顺序表表示多项式，实现两个一元多项式多项式L1(x)和和L2(x)相加，将结果存于多项式相加，将结果存于多项式L3(x)中。中。并计算当并计算当L1(x)=3.5+4x2+2.5x4，L2(x)=1.5x+2.6x2+1.6x3时，时，L3(x)的结果是什么。的结果是什么。一一元元多多项项式式P(x)可可以以表表示示为为(a0,0),(a1,1),(a n,n)。例如线性表例如线性表(6,1),(-5,4),(8,10)表示多项式表示多项式:P(x)=6x-5x4+8x10。第20页，本讲稿共22页用用顺顺序序表表L1和和L2存存放放需需要要相相加加的的两两个个多多项项式式L1(x)和和L2(x)，用用顺顺序序表表L3来来存存放放结结果果。多多项项式式相相加加算算法法可可按按照照下列步骤实现：下列步骤实现：设设定定两两个个位位置置变变量量i和和j指指向向顺顺序序表表L1和和L2的的第第一一个个元元素素，设设定定位位置置变变量量k表表示示L3的的插插入入位位置置，插插入入位位置置从从1开开始始。本例中本例中i、j和和k初值均为初值均为1。比比较较i和和j两两个个位位置置数数据据元元素素的的指指数数项项，如如果果L1中中第第i项项指指数数较较小小，则则将将此此项项数数据据元元素素复复制制到到L3的的位位置置k中中，并并将将位位置置变变量量i和和k后后移移；如如果果L2中中第第j项项指指数数较较小小，则则同同样样是是将将此此项项复复制制到到L3中中，并并将将位位置置变变量量j和和k后后移移；如如果果两两项项指指数数项项相相等等，则则合合并并同同类类项项后后再再将将结结果果复复制制到到L3中，并将位置变量中，并将位置变量i、j和和k同时后移同时后移。当当L1或或L2中中的的一一个个顺顺序序表表已已经经处处理理完完毕毕，则则将将另另一一个个顺顺序表的序表的剩余部分剩余部分复制到复制到L3中。中。第21页，本讲稿共22页参照程序参照程序例例2-1第22页，本讲稿共22页