第二章顺序表.ppt

《第二章顺序表.ppt》由会员分享，可在线阅读，更多相关《第二章顺序表.ppt（42页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、*1上章课要点回顾上章课要点回顾数据结构定义数据结构定义数据结构内容数据结构内容算法效率指标算法效率指标指互相有关联的数据元素的集指互相有关联的数据元素的集合，用合，用D_S=(D,S)数据的逻辑结构、存储结构和数据的逻辑结构、存储结构和运算运算时间效率和空间效率时间效率和空间效率2数据结构课程的内容数据结构课程的内容逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构3近近3周周上课上课内容内容第第2 2章章 线性表线性表第第3 3章章 栈和队列栈和队列第第4 4章章 串串第第5 5章章 数组和广义表数组和广义表线性结构线性结构若若结结构构是是

2、非非空空有有限限集集，则则有有且且仅仅有有一一个个开开始始结结点点和和一一个个终终端端结结点点，并并且且所所有有结结点点都都最最多多只只有有一一个个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a1,a2,an）线性结构的定义：线性结构的定义：（逻辑、存储（逻辑、存储和运算）和运算）4线性结构的特点：线性结构的特点：只有一个首结点和尾结点；只有一个首结点和尾结点；除除首首尾尾结结点点外外，其其他他结结点点只只有有一一个个直直接接前前驱驱和和一一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a1,a2,an）线性结构包括线性表、堆栈、队列、字符串、数线性结

3、构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最典型、最常用的是-线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是一对一一对一的的见第见第2章章5第第2章章线性表线性表2.1线性表的逻辑结构线性表的逻辑结构2.2线性表的顺序表示和实现线性表的顺序表示和实现2.3线性表的链式表示和实现线性表的链式表示和实现2.4应用举例应用举例（一元多项式的表示及相加）（一元多项式的表示及相加）作业作业6（a1,a2,ai-1，ai,ai1，,an）2.1线性表的类型定义线性表的类型定义1.线性表的定义：线性表的定义：是零个或多个元素的

4、有穷序是零个或多个元素的有穷序列，通常可以表示为：列，通常可以表示为：n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点线性表的逻辑结构可以用二元组=来表示，来表示，其中K=a0,a1,an-1R=|0in-27例子（1，2，3，4，.，9，10）8数据元素都是数字数据元素都是数字;元素间关系是线性元素间关系是线性9例例2分析分析26个英文字母组成的英文表个英文字母组成的英文表（A,B,C,D,Z）学号

5、学号姓名姓名性别性别年龄年龄班级班级2001011810205于春梅于春梅女女182001级电信级电信016班班2001011810260何仕鹏何仕鹏男男182001级电信级电信017班班2001011810284王王爽爽女女182001级通信级通信011班班2001011810360王亚武王亚武男男182001级通信级通信012班班：例例3分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录;元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母;元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性1011121314

6、（a1,a2,ai-1，ai,ai1，,an）这里的数据元素这里的数据元素ai（1in)只是一个只是一个抽象的符号，其具体含义在不同的情抽象的符号，其具体含义在不同的情况下可以不同。况下可以不同。2线性表的特征线性表的特征从线性表的定义可以看出线性表的特征：从线性表的定义可以看出线性表的特征：（1）有有且且仅仅有有一一个个开开始始结结点点(表表头头结结点点)a1，它它没有直接前驱，只有一个直接后继没有直接前驱，只有一个直接后继;（2）有有且且仅仅有有一一个个终终端端结结点点(表表尾尾结结点点)an，它它没没有直接后继，只有一个直接前驱有直接后继，只有一个直接前驱;（3）其它结点都有一个直接前驱

7、和直接后继；其它结点都有一个直接前驱和直接后继；（4）元素之间为一对一的线性关系。）元素之间为一对一的线性关系。线性表是一种典型的线性结构线性表是一种典型的线性结构线线性性表表是是一一种种典典型型的的线线性性结结构构，用用二二元组表示为：元组表示为：linear_list=(A,R)其中其中A=ai 1in,n0,aielemtypeR=rr=1in-1对应的逻辑结构图如图对应的逻辑结构图如图2-1所示。所示。线性表的运算线性表的运算常见线性表的运算有：常见线性表的运算有：1置置空空表表SETNULL（&L）将将线线性性表表L置置成成空表空表2求求长长度度LENGTH（L）求求给给定定线线性性

8、表表L的的长度长度3取取元元素素GET（L，i）若若1ilength(L),则则取取第第i个个位位置置上上的的元元素素，否否则则取取得得的的元元素素为为NULL。4求求直直接接前前趋趋PRI0R（L，X）求求线线性性表表L中中元元素素值值为为X的的直直接接前前趋趋，若若X为为第第一一个个元元素素，前前驱为驱为NULL。5求求直直接接后后继继NEXT（L，X）求求线线性性表表L中中元元素素值值为为X直直接接后后继继，若若X为为最最后一个元素，后继为后一个元素，后继为NULL。6定定位位函函数数LOCATE（L，X）在在线线性性表表L中中查查找找值值为为X的的元元素素位位置置，若若有有多多个个值值

9、为为X，则则以以第第一一个个为为准准，若若没没有有，位置为位置为0。7插插入入INSERT（&L，X，i）在在线线性表性表L中第中第i个位置上插入值为个位置上插入值为X的元素。的元素。8删删除除DELETE（&L，i）删删除除线线性表性表L中第中第i个位置上的元素。个位置上的元素。线性表的抽象数据类型描述线性表的抽象数据类型描述上述这些操作可用抽象数据类型描述为：上述这些操作可用抽象数据类型描述为：ADTLinearlistisData:一一个个线线性性表表L定定义义为为L=(a1,a2,an)，当当L=（）时时定定义义为一个空表为一个空表operation:voidsetnull(&L)/将

10、线性表将线性表L置成空表置成空表intLength(L)/求给定线性表求给定线性表L的长度的长度elemtypeGet(L,i)/取线性表取线性表L第第i个位置上的元素个位置上的元素elemtypePrior(L,x)/求线性表求线性表L中元素值为中元素值为X的直接前趋的直接前趋elemtypeNext(L,x)/求线性表求线性表L中元素值为中元素值为X的直接后继的直接后继intLocate(L,x)/在线性表在线性表L中查找值为中查找值为X的元素位置的元素位置voidInsert(&L,x,i)/在在线线性性表表L中中第第i个个位位置置上上插插入入值值为为X的元素的元素voidDelete(

11、&L,i)/删除线性表删除线性表L中第中第i个位置上的元素个位置上的元素ENDLinearlist212.2线性表的顺序表示和实现线性表的顺序表示和实现2.2.1顺序表的表示顺序表的表示2.2.2顺序表的实现顺序表的实现2.2.3顺序表的运算效率分析顺序表的运算效率分析本节小结本节小结作作 业业222.2.1顺序表的表示顺序表的表示用用一一组组地地址址连连续续的的存存储储单单元元依依次次存储线性表的元素，可通过存储线性表的元素，可通过数组数组VnVn来实现。来实现。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的存储结构。线性表

12、的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻23线性表顺序存储特点：线性表顺序存储特点：1.逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2.若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（素存放位置亦可求出（利用数组下标利用数组下标）。计算方法）。计算方法是（是（参见存储结构示意图参见存储结构示意图）：）：设首元素设首元素a1的存放地址为的存放地址为

13、LOC(a1)（称为称为首地址首地址），），设每个元素占用存储空间（地址长度）为设每个元素占用存储空间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为：LOC(ai)=LOC(a1)+L*（i-1）LOC(ai+1)=LOC(ai)+L注意：注意：C C语言中的数组的下标从语言中的数组的下标从0 0开始，开始，即：即：VnVn的有效范围是的有效范围是V0V0Vn-1Vn-124线性表的顺序存储结构示意图线性表的顺序存储结构示意图a a1 1a a2 2a ai ia ai+1i+1a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序1 1

14、i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b+L Lb+(i-1)+(i-1)L Lb+(n-1)+(n-1)L Lb+(max-1)+(max-1)L L25一个一维数组，下标的范围是一个一维数组，下标的范围是到，每个数组元素用相邻的到，每个数组元素用相邻的个字节个字节存储。存储器按字节编址，设存储数组存储。存储器按字节编址，设存储数组元素元素 的第一个字节的地址是的第一个字节的地址是，则则 的第一个字节的地址是的第一个字节的地址是 113例例1因此：因此：LOC(M3)=98+5(3-0)=113解：解：地址计算通式为：地址计算通式为：LOC(ai)=LOC(a1)+L

15、*（i-1）26用数组用数组V来存放来存放26个英文字母组成个英文字母组成的线性表（的线性表（a，b，c，z），写出在顺），写出在顺序结构上序结构上生成生成和和显示显示该表的该表的C语言程序。语言程序。voidbuild()/*字母线性表的生成，即字母线性表的生成，即建表操作建表操作*/inti;V0=a;for(i=1;i=i;j-)L.aj+1=L.aj;/元素后移L.ai=x;/插入元素L.len+;/表长度增加1核心语句：核心语句：31在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：121321242830427712132124252

16、830427712345678123456789插入插入2525插入运算插入运算Insert(&L,x,i)voidInsert(sequenlist&L,elemtypex,inti)intj;if(L.len=maxsize)cout”overflow”endl;elseif(iL.len+1)cout”positionisnotcorrect!”=i;j-)L.aj+1=L.aj;/元素后移元素后移L.ai=x;/插入元素插入元素L.len+;/表长度增加表长度增加1*33实现步骤：实现步骤：(n为表长）为表长）将第将第i至第至第n位的元素向前移动一个位置；位的元素向前移动一个位置；表长

17、减表长减1。注意：注意：事先需要判断，事先需要判断，删除位置删除位置i是否合法是否合法?应当有应当有1in或或i=1,n3)3)删除删除 删除删除线性表的第线性表的第i i个位置上的元素个位置上的元素核心语句：核心语句：for(j=i+1;j=L.len;j+)L.aj-1=L.aj;/元素前移L.len-;/表长度减134123456789121321242528304277123456781213212428304277删除顺序表中某个指定的元素的示意图如下：删除顺序表中某个指定的元素的示意图如下：删除运算删除运算Delete(&L,i)voidDelete(sequenlist&L,in

18、ti)intj;if(iL.len)cout”positionisnotcorrect!”endl;elsefor(j=i+1;j=L.len;j+)L.aj-1=L.aj;/元素前移元素前移L.len-;/表长度减表长度减1362.2.3顺序表的运算效率分析顺序表的运算效率分析算法时间主要耗费在移动元素的操作上，因此算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作（最深层语句频度）计算时间复杂度的基本操作（最深层语句频度）T(n)=O(移动元素次数移动元素次数)移动元素的个数取决于插入或删除元素的位置移动元素的个数取决于插入或删除元素的位置.思考：若插入在尾结点之后，则根本无

19、需移动（特别快）；思考：若插入在尾结点之后，则根本无需移动（特别快）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若插入在首结点之前，则表中元素全部要后移（特别慢）；若要考虑在各种位置插入（共若要考虑在各种位置插入（共n+1种可能）的平均移动次数，种可能）的平均移动次数，该如何计算？该如何计算？讨论讨论1：若在长度为若在长度为n的线性表的第的线性表的第i位前位前插入一插入一元素，则向后移动元素的次数元素，则向后移动元素的次数f(n)为为:f(n)=ni+1时间效率分析时间效率分析:37讨论讨论2：若在长度为若在长度为n n的线性表上删除第的线性表上删除第i i位元素，位元素，向前移动元

20、素的次数向前移动元素的次数f(n)f(n)为：为：f(n)=f(n)=思考：若删除尾结点，则根本无需移动（特别快）；思考：若删除尾结点，则根本无需移动（特别快）；若删除首结点，则表中元素全部要前移（特别慢）；若删除首结点，则表中元素全部要前移（特别慢）；若要考虑在各种位置删除（共若要考虑在各种位置删除（共n种可能）的平均移动次数，该种可能）的平均移动次数，该如何计算？如何计算？ni可以证明：可以证明：插入、删除操作平均需要移动一半元素插入、删除操作平均需要移动一半元素(n/2)插入、删除算法的平均插入、删除算法的平均时间时间复杂度为：复杂度为：O(n)显然，顺序表的显然，顺序表的空间空间复杂度

21、复杂度S(n)=O(1)S(n)=O(1)（没有占用辅助空间）（没有占用辅助空间）38证证明明：假假定定在在每每个个元元素素位位置置上上插插入入x x的的可可能能性性都都一一样样（即即概率概率P P相同），则应当这样来计算平均执行时间：相同），则应当这样来计算平均执行时间：将所有位置的执行时间相加，然后取平均。将所有位置的执行时间相加，然后取平均。若在首结点前插入，需要移动的元素最多，后移若在首结点前插入，需要移动的元素最多，后移n n次；次；若在若在a a1 1后面插入，要后移后面插入，要后移n-1n-1个元素，后移次数为个元素，后移次数为n-1;n-1;若在若在a an-1n-1后面插入，

22、要后移后面插入，要后移1 1个元素；个元素；若在尾结点若在尾结点a an n之后插入，则后移之后插入，则后移0 0个元素；个元素；所有可能的元素移动次数合计：所有可能的元素移动次数合计：0+1+0+1+n=n(n+1)/2+n=n(n+1)/2所以平均移动次数为：所以平均移动次数为：n(n+1)/2n(n+1)/2（n+1n+1）n/2n/2O(n)O(n)共有多少种插入形式共有多少种插入形式?连头带尾有连头带尾有n+1n+1种种同理可证：同理可证：顺序表删除一元素的时间效率为顺序表删除一元素的时间效率为:T T（n)=(n-1)/2 n)=(n-1)/2 O(n)O(n)39本节小结本节小结

23、线性表线性表顺序存储结构特点顺序存储结构特点：逻辑关系上相邻的：逻辑关系上相邻的两个元素在物理存储位置上也相邻；两个元素在物理存储位置上也相邻；优点：优点：可以随机存取表中任一元素；可以随机存取表中任一元素；缺点：缺点：在插入，删除某一元素时，需要移动大在插入，删除某一元素时，需要移动大量元素。量元素。为克服这一缺点，我们引入另一种存储形式：为克服这一缺点，我们引入另一种存储形式：链式存储结构链式存储结构见见2.3节节练习1.在顺序表中插入或删除一个元素，需要平均移动在顺序表中插入或删除一个元素，需要平均移动元素，元素，具体移动的元素个数与具体移动的元素个数与有关。有关。2.线性表中结点的集合

24、是线性表中结点的集合是的，结点间的关系是的，结点间的关系是的。的。3.向一个长度为向一个长度为n的向量的第的向量的第i个元素个元素(1in+1)之前插入一个元素之前插入一个元素时，需向后移动时，需向后移动个元素。个元素。4.向一个长度为向一个长度为n的向量中删除第的向量中删除第i个元素个元素(1in)时，需向前时，需向前移动移动个元素。个元素。5.在顺序表中访问任意一结点的时间复杂度均为在顺序表中访问任意一结点的时间复杂度均为，因此，因此，顺序表也称为顺序表也称为的数据结构。的数据结构。40表中一表中一半半表长和该元素在表中的位置表长和该元素在表中的位置有限有限一对一一对一n-i+1n-iO(

25、1)随机存取随机存取单项选择题单项选择题（）1数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（）2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（A）110（B）108（C）100（D）120（）3.在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A)访问第i个结点（1in）和求第i个结点的直接前驱(2in)(B)在第i个结点后插入一个新结点（1in）（C）删除第i个结点（1in）（D）将n个结点从小到大排序（）4.向一个有127个元素的顺序表中插入一个新元素

26、并保持原来顺序不变，平均要移动个元素（A）8（B）63.5（C）63（D）741CBAB42作业：作业：自行上机练习题：自行上机练习题：设有线性表设有线性表 LALA（3,5,8,113,5,8,11）和）和 LB=LB=（2,6,8,9,11,15,202,6,8,9,11,15,20）；）；若若LALA和和LBLB分别表示两个集合分别表示两个集合A A和和B B，求新集合，求新集合 A AA U BA U B（并并操作，相同元素不保留）；操作，相同元素不保留）；按规律插入按规律插入插入到尾部插入到尾部预测输出：预测输出：LA=LA=（3,5,8,11,3,5,8,11,2,6,9,15,202,6,9,15,20）将将LALA与与LBLB表归并，要求仍有序（相同元素要保留）表归并，要求仍有序（相同元素要保留）预测输出：预测输出：LC=LC=（2,2,3,53,5,6,8,6,8,8 8,9,11,9,11,11,11,15,2015,20）