数据结构 ch02学习.pptx

《数据结构 ch02学习.pptx》由会员分享，可在线阅读，更多相关《数据结构 ch02学习.pptx（77页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2023/3/171 线性表（LinearlistLinearlist）是最简单且最常用的一种数据结构。这种结构是最简单且最常用的一种数据结构。这种结构是最简单且最常用的一种数据结构。这种结构是最简单且最常用的一种数据结构。这种结构具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的具有下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个没有后继的（尾）数据元素；此

2、外，每一个数据元素均有一个直接前驱和一个没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。直接后继数据元素。直接后继数据元素。直接后继数据元素。通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。表的基本运算以及实现算法。表的基本运算以及实现算法。表的基本运算以及实

3、现算法。本章学习导读第1页/共77页2023/3/172 线性表由一组具有相同属性的数据元素构成。数据元素的含线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛，在不同的具体情况下，可以有不同的含义。义广泛，在不同的具体情况下，可以有不同的含义。1.1.线性表的定义线性表的定义 线线性性表表L L是是n n（n0n0）个个具具有有相相同同属属性性的的数数据据元元素素a a1 1，a a2 2，a a3 3，a an n组组成成的的有有限限序序列列，其其中中序序列列中中元元素素的的个个数数n n称称为为线线性性表表的的长度。长度。当当n=0n=0时称为空表，即不含有任何元素。时称为空表，

4、即不含有任何元素。常常将非空的线性表(n0)记作：(a1，a2，an)这里的数据元素ai(1 i n)只是一个抽象的符号，其具体含义在不同的情况下可以不同。22.1.1线性表的基本概念线性表的基本概念 第2页/共77页2023/3/173例1、26个英文字母组成的字母表（A，B，C、Z）例2、从1978年到1983年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例3、第3页/共77页2023/3/174从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一

5、个直接前趋an-1；其余的内部结点ai(2 i n-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。第4页/共77页2023/3/1752.线性表的基本运算 数据结构的运算是定义在逻辑结构层次上的，而运算的具体实数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现则是建立在存储结构上的。现则是建立在存储结构上的。(1)(1)初始化线性表初始化线性表Initlist(L)Initlist(L)将线性表将线性表L L置为空表。置为空表。(2)(2)求线性表的长度求线性表的长度Getle

6、n(L)Getlen(L)求解并返回线性表所含元素的个数求解并返回线性表所含元素的个数n n。若线性表为空，则返回若线性表为空，则返回整数整数0 0。(3)(3)按序号取元素按序号取元素Getelem(L,i)Getelem(L,i)读取线性表读取线性表L L第第i i个数据元素，要求满足个数据元素，要求满足11iGetlen(L)iGetlen(L)。第5页/共77页2023/3/176(4)4)按值查找按值查找Locate(L,x)Locate(L,x)在线性表在线性表L L L L中查找值为的数据元素，若查找成功则返中查找值为的数据元素，若查找成功则返回第一个值为回第一个值为x x x

7、x的元素的序号或地址的元素的序号或地址;否则，在否则，在L L L L中未找到值中未找到值为的数据元素，返回一特殊值（例如为的数据元素，返回一特殊值（例如0 0 0 0），表示查找失败。），表示查找失败。(5)(5)插入元素插入元素Inselem(L,i,x)Inselem(L,i,x)在线性表在线性表L L的第的第 i i 个位置上插入一个值为个位置上插入一个值为 x x 的新元素，的新元素，这样使原序号为这样使原序号为 i,i+1,i,i+1,.,n,n 的数据元素的序号变为的数据元素的序号变为 i+1,i+2,i+1,i+2,.,n+1,n+1，要求要求11iGetlen(L)+1iGe

8、tlen(L)+1，插入后原插入后原表长增表长增1 1 1 1。(6)(6)删除元素删除元素Delelem(L,i)Delelem(L,i)在线性表在线性表L L L L中删除序号为中删除序号为i i i i的数据元素，删除后使序号为的数据元素，删除后使序号为 i+1,i+2,i+1,i+2,.,.,.,.,n n 的元素变为序号的元素变为序号i,i+1,i,i+1,.,n-1,n-1，要求要求11iGetlen(L)iGetlen(L)，删除后表长减删除后表长减。第6页/共77页2023/3/1772.2 2.2 线性表的顺序结构及运算线性表的顺序结构及运算实现实现 线性表有两种基本的存储结

9、构：顺序存储结构和链式存储结构线性表有两种基本的存储结构：顺序存储结构和链式存储结构。1.线性表的顺序存储结构顺序表具有以下两个基本特点：顺序表具有以下两个基本特点：(1)(1)(1)(1)线性表的所有元素所占的存储空间是连续的。线性表的所有元素所占的存储空间是连续的。(2)(2)(2)(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。的。由于线性表的所有数据元素属于同一数据类型，所以每个元由于线性表的所有数据元素属于同一数据类型，所以每个元素在存储器中占用的空间（字节数）相同。因此，要在此结构中素在存储器中占用的空间（字节数）相同。

10、因此，要在此结构中查找某一个元素是很方便的，即只要知道顺序表首地址和每个数查找某一个元素是很方便的，即只要知道顺序表首地址和每个数据元素在内存所占字节的大小，就可求出第据元素在内存所占字节的大小，就可求出第i i i i个数据元素的地址。个数据元素的地址。第7页/共77页2023/3/178 假假设设线线性性表表中中的的第第一一个个数数据据元元素素的的存存储储地地址址（首首地地址址）为为LOCLOC(a(a1 1)，每每一一个个数数据据元元素素占占k k个个字字节节，则则各各元元素素的的存存储储地地址址有有如如下下关关系：系：LOCLOC（a a2 2）=LOC(a=LOC(a1 1)k kL

11、OCLOC（a a3 3）=LOC(a=LOC(a2 2)k kLOCLOC（a ai i）=LOC(a=LOC(ai-1i-1)k k（2in2in）因此，线性表中第因此，线性表中第i i个元素个元素a ai i在计算机中的存储地址为：在计算机中的存储地址为：LOC(aLOC(ai i)=LOC(a)=LOC(a1 1)+(i-1)k)+(i-1)k（1in1in）即即在在顺顺序序存存储储结结构构中中，线线性性表表中中每每一一个个数数据据元元素素在在计计算算机机存存储储空空间间中中的的存存储储地地址址由由该该元元素素在在线线性性表表中中的的序序号号惟惟一一确确定定。一一般般来来说说，长度为长

12、度为n n的线性表的线性表(a a1 1，a a2 2，aan n)在计算机中的结构如下：在计算机中的结构如下：第8页/共77页2023/3/179第9页/共77页2023/3/1710 在具体实现时，一般用高级语言中的在具体实现时，一般用高级语言中的数组数组来对应连续的存储来对应连续的存储空间。设最多可存储空间。设最多可存储MaxLenMaxLen个元素，在个元素，在C C语言中可用数组语言中可用数组datadataMaxLenMaxLen来存储数据元素，为保存线性表的长度需定义一来存储数据元素，为保存线性表的长度需定义一个整型变量个整型变量lengthlength。线性表的第线性表的第l

13、l，2 2，n n个元素分别存放在个元素分别存放在此数组下标为此数组下标为0 0，1 1，length-1length-1数组元素中，如下图数组元素中，如下图所示所示第10页/共77页2023/3/1711这样，一个线性表的顺序存储结构需要两个分量。为体现数组data和length之间的内在联系，通常将它们定义在一个结构类型中。此处的元素类型用ElemType来表示。综上所述，在C C语言中，可用下述类型定义来描述顺序表：#defineMaxLen100/线性表的容量typedefintElemType/在实际应用中，将ElemType定义成实际类型typedefstructElemTyped

14、ataMaxLen;/定义存储表中元素的数组intlength;/线性表的实际长度sqList;sqListL;/定义表结构的变量第11页/共77页2023/3/17122.2.22.2.2线性表在顺序存储结构下的运算实现线性表在顺序存储结构下的运算实现线性表在顺序存储结构下的运算实现线性表在顺序存储结构下的运算实现 本节将讨论采用顺序存储结构之后，如何实现线性表的基本运算，并讨论各算法时间复杂度。1初始化顺序表初始化顺序表initlist(L)的实现的实现 顺序表的初始化即构造一个空表，顺序表L是否为空取决于其元素个数是否为0，因此，只要将表L中的表长度置为0，就可以实现建空表的功能。voi

15、dinitlist(sqList*L)L-length=0;2求线性表长度求线性表长度Getlen(L)的实现的实现 求线性表的长度算法如下：int Getlen(sqList*L)return L-length;该算法的时间复杂度为O(1)第12页/共77页2023/3/17133按序号取元素按序号取元素Getelem(L,i)的实现的实现 按前面的约定，序号为i的元素存储在数组下标为i-1的数组元素中，所以可直接从该数组元素中取得值。i的有效值应大于等于1和小于等于线性表的实际长度。ElemType Getelem(sqLlist*L,int i)if(iL-length)printf(“

16、error”);exit(1);return L-datai-1;4查找运算查找运算locate(L,x)的实现的实现要 确定值为x的元素在L表中的位置，需要依次比较各元素。当查询到第一个满足条件的数据元素时，返回其序号，否则返回0，表示查找失败。第13页/共77页2023/3/1714查找操作的具体实现算法如下：int Locate(sqList*L,ElemType x)int i;i=0;while(ilength&L-datai!=x)i+;if(ilength)return i;else return 0;5顺序表的插入算法顺序表的插入算法inselem(L,i,x)的实现的实现 顺

17、序表的插入是指在表的第i个位置上插入一个值为x的新元素，插入后使原表长为n的表：(a1，a2，ai-1，ai，ai+1，an)，成为表长为 n+1n+1的表：由算法可知，对于表长为n的顺序表，在查找过程中，数据元素比较次数最少为1，最多为n，元素比较次数的平均值为(n+1)/2，时间复杂度为 O(n)。第14页/共77页2023/3/1715 (a1，a2，ai-1，x，ai，ai+1，an),i 的取值范围为1iin+1。下图表示一个顺序表中的数组在进行插入运算前后，数据元素在数组中的下标变化。序号元素0a01a12a2 i-1ai-1iaii+1ai+1i+2ai+2 numanum序号元

18、素0a01a12a2 i-1ai-1ixi+1aii+2ai+1 numanum插入x插入前插入后第15页/共77页2023/3/1716void Inselem(sqList*L,int i,Elemtype x)if(iL-length+1)printf(“Error!”);/插入位置出错 exit(1);if(L-length=MaxLen)printf(“overflow!”);/表已满 exit(1);for(j=L-length;j=i;j-)L-dataj+1=L-dataj;/数据元素后移 L-datai=x;/插入x L-length+;/表长度加1 第16页/共77页202

19、3/3/1717 假设表中任何位置插入概率是均等的,即Pi=1/(n+1),则：该算法的时间主要花费在移动数据元素上，移动个数取决于插入位置i和表的长度n。所以可以用数据元素的移动操作来估计算法的时间复杂度。在第i个位置上插入x，共需要移动n-i+1个元素，i的取值范围为：1in+1，即有n+1个位置可以插入。当i=n+1时，不需要移动结点；当i=1时需要移动n个结点。由此可以看出，算法在最好的情况下时间复杂性为O(1)，最坏的时间复杂性是O(n)。由于插入的位置是随机的，因此，需要分析执行该算法移动数据元素的平均值。设在第i个位置上作插入的概率为Pi，则平均移动数据元素的次数：第17页/共7

20、7页2023/3/1718 由此可以看出，在线性表上做插入操作需要移动表中一半的数据元素，当n较大时，算法的效率是比较低的，所以在线性表上进行插入操作的时间复杂度为(n)。6 6顺序表的删除运算顺序表的删除运算顺序表的删除运算顺序表的删除运算Delelem(L,i)Delelem(L,i)的实现的实现的实现的实现 顺序表的删除运算是指将表中第 i 个元素从线性表中去掉，原表长为 n 的线性表(a1，a2，ai-1，ai，ai+1，an)。进行删除以后的线性表表长变为 n-1的表(a1，a2，ai-1，ai+1，an)，i 的取值范围为：1in。图2-5表示一个顺序表的数组在进行删除运算前后，其

21、数据元素在数组中的下标变化。第18页/共77页2023/3/1719图2-5 线性表中的删除运算示意图第19页/共77页2023/3/1720 在线性表上完成上述运算通过以下两个操作来实现：(1)(1)线性表中第i个至第n个元素（共n-i+1个元素）依次向前移动一个位置。将所删除的元素ai覆盖掉，从而保证逻辑上相邻的元素物理位置也相邻。(2)(2)修改线性表长度，使其减1。线性表的删除算法如下：void Delelem(sqList*L,int i)/删除线性表中第i个位置上的元素 if(iL-length)/检查空表及删除位置的合法性 printf(不存在第i个元素);exit(0);for

22、(j=i;jlength-1;j+)L-dataj-1=L-dataj;/向前移动元素 L-length-;第20页/共77页2023/3/1721 删除算法的时间性能分析：与插入运算相同，删除运算的时间也主要消耗在移动表中数据元素上，删除第i个元素时，其后面的元素ai+1an都要向前移动一个位置，共移动了n-i个元素，所以在等概率的情况下，在线性表中删除数据元素所需移动数据元素的期望值，即平均移动数据元素的次数为：由此可以看出，在线性表上删除数据元素时大约需要移动表中一半的元素，显然该算法的时间复杂度为(n)。通常情况下，我们认为在线性表中任何位置删除元素是等概率的，即pi=1/n，则：第2

23、1页/共77页2023/3/1722【例2-1】利用线性表的基本运算，编写在线性表A A中删除线性表B B中出现的元素的算法。【解】本题的算法思路是：依次检查线性表B B中的每个元素，看它是否在线性表A A中。若在线性表A A中，则将其从A A中删除。本题的算法如下：void delete(sqList*A,sqList*B)int i,k;ElemType x;for(i=1;i0)Delelem(A,k);/若在线性表A中找到了，将其删除 第22页/共77页2023/3/1723【例2-2】利用线性表的基本运算，编写将线性表A A和B B中公共元素生成线性表C C的算法。【解】本题的算法思

24、路是：先初始化线性表C，然后依次检查线性表A中的每个元素，看它是否在线性表B中；若在线性表B中，则将其插入到线性表C中。本题的算法如下：void commelem(sqList*A,sqList*B,sqList*C)int i,k,j=1;ElemType x;Initlist(C);for(i=1;iO)Inselem(C,j,x);j+;/若在线性表B B中找到了，将其插入到C C中 第23页/共77页2023/3/1724【例2-3】将顺序表(a1，a2，a3，an)重新排列为以a1为界的两部分：a1前面的值均比a1小，a1后面的值都比a1大（这里假设数据元素的类型具有可比性，可设为整

25、型）。【解】基本思路：从第二个元素开始到最后一个元素，逐一向后扫描，当数据元素ai比a1大时，表明它已经在a1的后面，不必改变它与a1之间的位置，继续比较下一个；当数据元素ai比a1小时，表明它应该在a1的前面，此时将它前面的元素依次向下移动一个位置，然后将它置入最上方。算法如下：typedef int ElemType;void part(sqList*L)int i,j;ElemType x,y;x=L-data0;/将基准元素a1置入x中 for(i=1;ilength;i+)if(L-dataidatai;for(j=i-1;j=0;j-)/移动 L-dataj+1=L-dataj;L

26、-data0=y;第24页/共77页2023/3/1725即 最 坏 情 况 下 移 动 数 据 的 时 间 复 杂 性 能 为O(n2)。本算法中，有两重循环，外循环执行n-1次，内循环中元素的移动次数与当前数据的大小有关，当第i个元素小于a1时，要移动它上面的i-1个元素，再加上前面结点的保存及置入，所以移动i-1+2次，在最坏情况下，a1后面的结点都小于a1，故总的移动次数为：第25页/共77页2023/3/1726 线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。但是，顺序存储结构也有一些不方便之处，主要表现在：（1）

27、数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间；（2）插入与删除运算的效率很低。为了保持线性表中的数据元素顺序，在插入操作和删除操作时需移动大量数据。对于插入和删除操作频繁的线性表、将导致系统的运行速度难以提高。（3）存储空间不便于扩充。当一个线性表分配顺序存储空间后，若线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。第26页/共77页2023/3/17272.3 2.3 线性表的链式存储和运算实现线性表的链式存储和运算实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，故可以随机存取表中的任一结点；但在插入和删除操作

28、时需移动大量的结点。为避免大量结点的移动，介绍线性表的另一种存储方式:链式存储结构，简称链表(Linked List)Linked List)。线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。链式存储方式可用于表示线性结构，也可用于表示非线性结构。第27页/共77页2023/3/17282.3.1链表的存储结链表的存储结构构 链式存储结构是利用任意的存储单元来存放线性表中的元素，存储数据

29、的单元在内存中可以连续，也可以零散分布。由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系，在这种结构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息，除了存储每一个数据元素值以外，还需存储其后继或前驱元素所在内存的地址。两部分信息一起构成链表中的一个结点。结点的结构如下所示。第28页/共77页2023/3/1729C语言采用结构数据类型描述结点如下：typedef struct LNodeElemType data;/结点值 struct LNode*next;/

30、存储下一个结点的地址LNode,*LinkList;LNode*head;在此结构中，用数据域data存储线性表中数据元素。指针域next，它给出下一个结点的存储地址。结点的指针域将所有结点按线性表的逻辑次序链接成一个整体，形成一个链表。由于链表中第一个结点没有直接前驱，所以必须设置一个头指针head存储第一个结点的地址。最后一个结点没有直接后继，其指针域应为空指针，C语言用NULL或0来表示，在图中表示为“”。假设有一个线性表为（A,B,C,D,E），存储空间具有10个存储结点，该线性表在存储空间中的存储情况如图2-7(a)所示。第29页/共77页2023/3/1730图 2-7 链表结构示

31、意图第30页/共77页2023/3/1731 从图中可见，每个结点的存储地址存放在直接前驱的指针域中。所以要访问链表中数据元素C，必须由头指针head得到第一个结点（数据A）的地址，由该结点的指针域得到第二个结点（数据B）的地址，再由其指针域得到存储数据C的结点地址，访问该结点的数据域就可以处理数据C了。链表这种顺着指针链依次访问数据元素的特点，表明链表是一种顺序存储结构，只能顺序操作链表中元素。不能像顺序表（数组）那样可以按下标随机存取。为了提高顺序操作的速度，使操作更加灵活方便，对链表中的指针采用了不同的设置，构成了不同的链表。如只设置一个指向后继结点地址的指针域是单链表；将其首尾相接构成

32、一个环状结构，称为循环链表；增加一个指向前驱的指针就构成双向链表。在链表存储结构中，不要求存储空间的连续性，数据元素之间的逻辑关系由指针来确定。由于链式存储的灵活性，这种存储方式既可用于表示线性结构，也可以用来表示非线性结构。第31页/共77页2023/3/17322.3.2 单向链单向链表表 在图2-7所示的链表中，每个结点只有一个指向后继的指针。也就是说访问数据元素只能由链表头依次到链表尾，而不能做逆向访问。称这种链表为单向链表或线性链表。这是一种最简单的链表。单链表分为带头结点和不带头结点两种类型。对于空链表，头结点的指针域为空。图2-8是带头结点的链表示方式：图2-8（a）为带头结点的

33、空链(b)为带头结点的单链表第32页/共77页2023/3/1733 由于链表是一种动态管理的存储结构，每个结点需动态产生。1初始化链表初始化链表initlist(L)的实现的实现建立一个空的带头结点的单链表。所谓空链表就是指表长为0的表。在这种情况下，链表中没有元素结点。但应有一个头结点，其指针域为空。void initlist(LinkList*L)void initlist(LinkList*L)*L=(LNode*)malloc(sizeof(LNode);*L=(LNode*)malloc(sizeof(LNode);(*L)-next=NULL;(*L)-next=NULL;在函数

34、调用时，指针L指向的内容发生了变化，为使得调用函数中头指针变量head获得头结点地址，需传递头指针变量的地址给initlist()函数，而函数中定义二级指针变量L接受该地址值，从而返回改变后的值。第33页/共77页2023/3/17342求线性表长度求线性表长度Getlen(L)的实现的实现 设计思路：设置一个初值为0的计数器变量和一个跟踪链表结点的指针p。初始时p指向链表中的第一个结点，然后顺着next域依次指向每个结点，每指向一个结点计数器变量加1。当p为0时，结束该过程。其时间复杂度为O(n)。int Getlen(LinkList L)int Getlen(LinkList L)int

35、 num=0;int num=0;LNode*p;LNode*p;p=L-next;p=L-next;while(p!=NULL)while(p!=NULL)num+;num+;p=p-next;p=p-next;return(num);return(num);第34页/共77页2023/3/17353按序号取元素按序号取元素Getelem(L,i)的实现的实现根据前面的讨论，对单链表中的结点只能顺序存取，即访问前一个结点后才能接着访问后一个结点。所以要访问单链表中第i个元素值，必须从头指针开始遍历链表，依次访问每个结点，直到访问到第i个结点为止。同顺序表一样，也需注意存取的位置是否有效。LN

36、ode*Getelem(LinkList L,int i)LNode*Getelem(LinkList L,int i)LNode*p;int pos=1;LNode*p;int pos=1;p=L-next;p=L-next;if(iGetlen(L)exit(1);if(iGetlen(L)exit(1);while(posi)while(posnext;p=p-next;pos+;pos+;return p;return p;第35页/共77页2023/3/17364查找运算查找运算locate(L,x)的实现的实现 设计思路：设置一个跟踪链表结点的指针p，初始时p指向链表中的第一个结点

37、，然后顺着next域依次指向每个结点，每指向一个结点就判断其值是否等于x，若是则返回该结点地址。否则继续往后搜索，直到p为0，表示链表中无此元素，返回NULL。其时间复杂度为O(n)。LNode*Locate(LinkList L,int x)LNode*Locate(LinkList L,int x)LNode*p;LNode*p;p=L-next;p=L-next;while(p!=NULL&p-data!=x)while(p!=NULL&p-data!=x)p=p-next;p=p-next;return p;return p;第36页/共77页2023/3/17375链表的插入算法链表

38、的插入算法inselem(L,i,x)的实现的实现 单链表结点的插入是利用修改结点指针域的值，使其指向新的链接位置来完成的插入操作，而无需移动任何元素。假定在链表中值为ai的结点之前插入一个新结点，要完成这种插入必须首先找到所插位置的前一个结点，再进行插入。假设指针q指向待插位置的前驱结点，指针s指向新结点，则完成该操作的过程如图2-9所示。第37页/共77页2023/3/1738图 2-9 p前插入s结点过程示意图上述指针进行相互赋值的语句顺序不能颠倒。第38页/共77页2023/3/1739void Inselem(LinkList L,int i,int x)void Inselem(L

39、inkList L,int i,int x)LNode*p,*q,*s;LNode*p,*q,*s;int pos=1;int pos=1;p=L;p=L;if(iGetlen(L)+1)exit(1);if(iGetlen(L)+1)exit(1);s=(LNode*)malloc(sizeof(LNode);s=(LNode*)malloc(sizeof(LNode);s-data=x;s-data=x;while(pos=i)while(posnext;q=p;p=p-next;pos+;pos+;s-next=q-next;s-next=q-next;q-next=s;q-next=s

40、;第39页/共77页2023/3/1740若传给函数的是待插入结点的地址，可编写如下的算法：void Insnode(LinkList L,int i,LNode*s)void Insnode(LinkList L,int i,LNode*s)LNode*p,*q;LNode*p,*q;int pos=1;int pos=1;if(iGetlen(L)+1)exit(1);if(iGetlen(L)+1)exit(1);p=L;p=L;while(pos=i)while(posnext;q=p;p=p-next;pos+;pos+;s-next=q-next;s-next=q-next;q-n

41、ext=s;q-next=s;第40页/共77页2023/3/17416链表的删除运算链表的删除运算delelem(L,i)的实现的实现 要删除链表中第i个结点，首先在单链表中找到删除位置前一个结点，并用指针q指向它，指针p指向要删除的结点。将*q的指针域修改为待删除结点*p的后继结点的地址。删除后的结点需动态的释放。如下图2-10所示。假定删除的结点是值为ai的结点。图2-10(c)中虚线表示删除结点*p后的指针指向。具体算法描述为：q=q-next;q=q-next;pos+;pos+;p=q-next;p=q-next;q-next=p-next;q-next=p-next;free(p

42、);free(p);void Delelem(LinkList L,int i)void Delelem(LinkList L,int i)int pos=1;int pos=1;LNode*q=L,*p;LNode*q=L,*p;if(iGetlen(L)exit(1);if(iGetlen(L)exit(1);while(posi)while(posnext;p=L-next;while(p!=NULL)while(p!=NULL)printf(%4d,p-data);printf(%4d,p-data);p=p-next;p=p-next;printf(n);printf(n);第43页

43、/共77页2023/3/1744图2-11 单链表的倒置第44页/共77页2023/3/1745【例2-4】利用前面定义的基本运算函数，编写将一已知的单链表H倒置的程序。如图2-11的操作。(a)为倒置前，(b)为倒置后。【解】算法基本思路：不另外增加新结点，而只是修改原结点的指针。设置指针p，令其指向head-next，并将head-next置空，然后依次将p所指链表的结点顺序摘下，插入到head之后即可。具体算法如下：void reverse(LinkList L)void reverse(LinkList L)LNode*p,*q;LNode*p,*q;if(L-next!=NULL)/

44、if(L-next!=NULL)/至少有两个元素 p=L-next;p=L-next;L-next=NULL;L-next=NULL;while(p!=NULL)while(p!=NULL)第45页/共77页2023/3/1746 q=p;p=p-next;q=p;p=p-next;Insnode(L,1,q);Insnode(L,1,q);main()main()LNode*head,*p;LNode*head,*p;int i,x;int i,x;initlist(&head);initlist(&head);for(i=1;i=5;i+)for(i=1;inext=L第48页/共77页2

45、023/3/17492求求线线性性表表长长度度Getlen(L)函函数数、查查找找运运算算locate(L,x)函函数数、链链表表元元素素输输出出运运算算displist(L)函函数数中中，循循环环遍遍历历是是否否进进行行的的条件由条件由p!=NULL改为改为p!=L;其余函数运算没有变化，请自行写出相关函数的定义。在循环链表中，除了有头指针head外，有时还可加上一个尾指针tail。尾指针tail指向最后一结点，沿最后一个结点的指针又可立即找到链表的第一个结点。在实际应用中，使用尾指针来代替头指针进行某些操作往往会更简单。【例2-6】将两个循环链表首尾相接进行合并，La为第一个循环链表表尾指

46、针，Lb为第二个循环链表表尾指针，合并后Lb为新链表的尾指针，head指向整个合并后的链表。【解】算法思路：对两个单循环链表La，Lb进行的连接操作，是将Lb的第一个数据结点接到La的尾部。操作时需要从La的头指针开始找到La的尾结点，其时间复杂性为O(n)。而在循环链表中若采用尾指针La，Lb来标识，则时间性能将变为O(1)。其连接过程如图2-14所示。第49页/共77页2023/3/1750图2-14两个循环链表首尾相接进行合并 第50页/共77页2023/3/1751具体操作如下：LinkList list_merge(LinkList head,LinkList La,LinkList

47、 Lb)LNode*p,*q;p=(LNode*)malloc(sizeof(LNode);/为p申请空间q=pp=La-next;/指针p指向La链表头q=Lb-next;/指针q指向Lb链表头La-next=q-next;/使链表Lb链接到La的尾部，并去掉Lb链表中的头结点Lb-next=p;/设置Lb为链表的尾指针head=p;free(p);return head;第51页/共77页2023/3/17522.3.4双向链表双向链表 双向链表结点的定义如下：typedef struct DNode ElemType data;struct DNode*prior;struct DNod

48、e*next;Dnode,*DuLinkList;结点的结构如图2-15所示。单链表只有一个指向后继的指针来表示结点间的逻辑关系。故从任一结点开始找其后继结点很方便，但要找前驱结点则比较困难。双向链式是用两个指针表示结点间的逻辑关系。即增加了一个指向其直接前驱的指针域，这样形成的链表有两条不同方向的链，前驱和后继，因此称为双链表。在双链表中，根据已知结点查找其直接前驱结点可以和查找其直接后继结点一样方便。这里也仅讨论带头结点的双链表。仍假设数据元素的类型为ElemType。图2-15 双向链表结点结构图第52页/共77页2023/3/1753图2-16带头结点的双向链表 在图2-16中，如果某

49、指针变量p指向了一个结点，则通过该结点的指针p可以直接访问它的后继结点，即由指针p-next所指向的结点；也可以直接访问它的前驱结点，由指针p-prior指出。这样在需要查找前驱的操作中，就不必再从头开始遍历整个链表。这种结构极大地简化了某些操作。在双向链表中也可采用与单链表类似的方法，用头指针标识链表的开头，也可以带头结点。在双向链表中，每个结点都有一个指向直接前驱结点和一个指向直接后继结点的指针。链表中第一个结点的前驱指针和最后一个结点的后继指针可以为空，不做任何指向，这是简单的双向链表。第53页/共77页2023/3/1754结点的插入过程如图2-17所双向链表示：注意：在图2-17中，

50、关键语句指针操作序列既不是唯一也不是任意的。操作必须在操作之前完成，否则*p的前驱结点就丢掉了。图2-17双链表插入结点示意图第54页/共77页2023/3/1755 图2-18双链表的删除结点示意图在双向链表中找到删除位置的前一个结点，由p指向它，q指向要删除的结点。删除操作如下：将*p的next域改为指向待删结点*q的后继结点；若*q不是指向最后的结点，则将*q之后结点的prior域指向*p。注意：在双向链表中进行插入和删除时，对指针的修改需要同时修改结点的前驱指针和后继指针的指向。第55页/共77页2023/3/1756【解】算法思路：扫描双向链表DL，查找链表DL的第i个位置并在第i个