数据结构：ch2 线性表.ppt

《数据结构：ch2 线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构：ch2 线性表.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第二章第二章 线性表线性表 2.1 线性表的类型定义线性表的类型定义 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.3 线性表的链式表示和实现线性表的链式表示和实现 2.3.1 线性链表线性链表 2.3.2 循环链表循环链表 2.3.3 双向链表双向链表 *2.4 一元多项式的表示及相加一元多项式的表示及相加12/19/2022 2.1 2.1 线性表的逻辑结构线性表的逻辑结构 线性表线性表(Linear List)：由由n(n0)个数据元素个数据元素(结点结点)a1，a2，an组成的有限序列。其中数据元素的个数组成的有限序列。其中数据元素的个数n定义定义为表的长度。当为表的长度

2、。当n=0时称为空表，常常将非空的线性表时称为空表，常常将非空的线性表(n0)记作：记作：(a1，a2，an)这里的数据元素这里的数据元素ai(1in)只是一个抽象的符号，其具只是一个抽象的符号，其具体含义在不同的情况下可以不同。体含义在不同的情况下可以不同。例例1.26个英文字母组成的字母表个英文字母组成的字母表：（A，B，C、Z）例例2.某校从某校从1978年到年到1983年各种型号的计算机拥有量的变年各种型号的计算机拥有量的变化情况：化情况：（6，17，28，50，92，188）12/19/2022例例3、学生健康情况登记表如下：、学生健康情况登记表如下：姓姓 名名学学 号号性性 别别

3、年龄年龄 健康情况健康情况王小林王小林790631 男男 18 健康健康陈陈 红红790632 女女 20 一般一般刘建平刘建平790633 男男 21 健康健康张立立张立立790634 男男 17 神经衰弱神经衰弱.12/19/2022例例4.一副扑克的点数一副扑克的点数 （2，3，4，J，Q，K，A）从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是：在非空的线性表中有且仅有一个在非空的线性表中有且仅有一个开始结点开始结点a1，它没有直它没有直接前趋，而仅有一个直接后继接前趋，而仅有一个直接后继a2；有且仅有一个有且仅有一个终端终端结点结点an，它没有直接后继，而仅有一

4、个直接前趋它没有直接后继，而仅有一个直接前趋a n-1；其余的内部结点其余的内部结点ai(2in-1)都有且仅有一个直接前都有且仅有一个直接前趋趋a i-1和一个直接后继和一个直接后继a i+1。线性表是一种典型的线性结构。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。现则是在存储结构上进行的。抽象数据类型的定义为：抽象数据类型的定义为：P1912/19/2022 算法算法 2.1 2.1例例2-1 利用两个线性表利用两个线性表LA和和LB分别表示两个集合分别表示两个集合A和和B，现要求一个新的

5、集合现要求一个新的集合A=AB。void union(List&La，List Lb)La_len=Listlength(La);Lb_len=Listlength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb，i，e);if(!LocateElem(La，e，equal)ListInsert(La，+La_en，e)12/19/2022 算法算法 2.2 2.2 例例2.2 巳知线性表巳知线性表LA和线性表和线性表LB中的数据中的数据元素按值非递减有序排列，现要求将元素按值非递减有序排列，现要求将LA和和LB归并为一个新的线性表归并为一个新的线性表LC，且且LC中的中

6、的元素仍按值非递减有序排列。元素仍按值非递减有序排列。此问题的算法如下：此问题的算法如下：12/19/2022void MergeList(List La，List Lb，List&Lc)InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La_len)&(j=Lb_len)GetElem(La，i，ai);GetElem(Lb，j，bj);if(ai=bj)ListInsert(Lc，+k，ai);+i;elseListInsert(Lc，+k，bj);+j;12/19/2022while(i=

7、La_len)GetElem(La，i+，ai);ListInsert(Lc，+k，ai);while(j=Lb_len)GetElem(Lb，j+，bj);ListInsert(Lc，+k，bi);12/19/2022 2.2 2.2 线性表的顺序存储结构线性表的顺序存储结构2.2.1 顺序表顺序表 把线性表的结点按逻辑顺序依次存放在一组地址连把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。续的存储单元里。用这种方法存储的线性表简称顺序表。假设线性表的每个元素需占用假设线性表的每个元素需占用l个存储单元，并以所个存储单元，并以所占的第一个单元的存

8、储地址作为数据元素的存储位置。占的第一个单元的存储地址作为数据元素的存储位置。则线性表中第则线性表中第i+l个数据元素的存储位置个数据元素的存储位置LOC(a i+l)和第和第i个数据元素的存储位置个数据元素的存储位置LOC(a I )之间满足下列关系：之间满足下列关系：LOC(a i+l)=LOC(a i)+l 线性表的第线性表的第i个数据元素个数据元素ai的存储位置为：的存储位置为：LOC(ai)=LOC(a1)+(i-1)*l12/19/2022 由于由于C C语言中的一维数组也是采用顺序存储表示，语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。又因为除了用故可以用数

9、组类型来描述顺序表。又因为除了用数组来存储线性表的元素之外，顺序表还应该用数组来存储线性表的元素之外，顺序表还应该用一个变量来表示线性表的长度属性，所以我们用一个变量来表示线性表的长度属性，所以我们用结构类型来定义顺序表类型。结构类型来定义顺序表类型。#define ListSize 100 typedef int DataType;typedef struc DataType dataListSize;int length;Sqlist;12/19/20222.2.2 顺序表上实现的基本操作顺序表上实现的基本操作 在顺序表存储结构中，很容易实现线性表的在顺序表存储结构中，很容易实现线性表的一

10、些操作，如构造线性表、第一些操作，如构造线性表、第i个元素的访问等。个元素的访问等。注意：注意：C语言中的数组下标从语言中的数组下标从“0”开始，开始，因此，因此，若若L是是Sqlist类型的顺序表，则表中第类型的顺序表，则表中第i个元素是个元素是L.datai-1。以下主要讨论线性表的插入和删除两种运算。以下主要讨论线性表的插入和删除两种运算。1.插入插入 线性表的插入运算是指在表的第线性表的插入运算是指在表的第i(1in+1)个位置上，插入一个新结点个位置上，插入一个新结点x，12/19/2022使长度为使长度为n的线性表的线性表(a1，a i-1，ai，an)变成变成长度为长度为n+1的

11、线性表的线性表(a1，a i-1，x，ai，an)算法算法 2.3 2.3Void InsertList(Sqlist&L，DataType x，int i)int j;if(iL-length+1)printf(“Position error”);return ERROR 12/19/2022 if(L-length=ListSize)printf(“overflow”);exit(overflow);for(j=L-length-1;j=i-1;j-)L-dataj+1=l.dataj;L-datai-1=x;L-length+;12/19/2022分析算法的复杂度分析算法的复杂度:规模是

12、表的长度，设它的值为规模是表的长度，设它的值为n。该算法的时该算法的时间主要化费在循环的结点后移语句上，该语句的间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）不仅依赖于表的执行次数（即移动结点的次数）不仅依赖于表的长度，而且还与插入位置有关。长度，而且还与插入位置有关。当当i=n+1时，由于循环变量的终值大于初值，结时，由于循环变量的终值大于初值，结点后移语句将不进行；这是最好情况，其时间复点后移语句将不进行；这是最好情况，其时间复杂度杂度O（1）；）；当当=1时，结点后移语句将循环执行时，结点后移语句将循环执行n次，需移动表次，需移动表中所有结点，这是最坏情况，中所有

13、结点，这是最坏情况，其时间复杂度为其时间复杂度为O（n）。）。12/19/2022 由于插入可能在表中任何位置上进行，因此需分析算法由于插入可能在表中任何位置上进行，因此需分析算法的平均复杂度的平均复杂度 在长度为在长度为n的线性表中第的线性表中第i个位置上插入一个结点，个位置上插入一个结点，令令Eis(n)表示移动结点的期望值（即移动的平均次数），表示移动结点的期望值（即移动的平均次数），则在第则在第i个位置上插入一个结点的移动次数为个位置上插入一个结点的移动次数为n-i+1。故故 Eis(n)=pi(n-i+1)不失不失一般性，假设在表中任何位置一般性，假设在表中任何位置(1in+1)上插

14、入上插入结点的机会是均等的，则结点的机会是均等的，则 p1=p2=p3=p n+1=1/(n+1)因此，在等概率插入的情况下，因此，在等概率插入的情况下，=n/212/19/2022 也就是说，在顺序表上做插入运算，平均要移动表上一也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长半结点。当表长 n较大时，算法的效率相当低。虽然较大时，算法的效率相当低。虽然Eis(n)中中n的的系数较小，但就数量级而言，它仍然是线的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为性阶的。因此算法的平均时间复杂度为O(n)。2.删除删除 线性表的删除运算是指将表的第线性表的删

15、除运算是指将表的第i(1in)结结点删除，使长度为点删除，使长度为n的线性表：的线性表：(a1，a i-1，ai，a i+1，an)变成长度为变成长度为n-1的线性表的线性表(a1，a i-1，a i+1，an)12/19/2022 Void DeleteList(Sqlist *L，int i)int j;if(iL-length)printf(“Position error”);return ERROR for(j=i;jlength-1;j+)L-dataj-1=L-dataj;L-length-;12/19/2022 该算法的时间分析与插入算法相似，结点的移动次数也该算法的时间分析与插

16、入算法相似，结点的移动次数也是由表长是由表长n和位置和位置i决定。决定。若若i=n，则由于循环变量的初值大于终值，前移语句则由于循环变量的初值大于终值，前移语句将不执行，无需移动结点；将不执行，无需移动结点；若若i=1，则前移语句将循环执行则前移语句将循环执行n-1次，需移动表中除次，需移动表中除开始结点外的所有结点。这两种情况下算法的时间复杂开始结点外的所有结点。这两种情况下算法的时间复杂度分别为度分别为O(1)和和O(n)。删除算法的平均性能分析与插入算法相似。在长度为删除算法的平均性能分析与插入算法相似。在长度为n的线性表中删除一个结点，令的线性表中删除一个结点，令Ede(n)表示所需移

17、动结表示所需移动结点的平均次数，删除表中第点的平均次数，删除表中第i个结点的移动次数为个结点的移动次数为n-i，故故 Ede(n)=pi(n-i)式中，式中，pi表示删除表中第表示删除表中第i个结点的概率。个结点的概率。12/19/2022在等概率的假设下，在等概率的假设下，p1=p2=p3=pn=1/n由此可得：由此可得：Ede(n)=(n-i)/n=(n-1)/2 即在顺序表上做删除运算，平均要移动表即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是中约一半的结点，平均时间复杂度也是O(n)。12/19/20222.3 2.3 线性表的链式表示和实现线性表的链式表示和实

18、现 线性表的顺序表示的特点是用物理位置线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结但它也使得插入和删除操作会移动大量的结点点.为避免大量结点的移动，我们介绍线性表为避免大量结点的移动，我们介绍线性表的另一种存储方式的另一种存储方式:链式存储结构，简称为链表链式存储结构，简称为链表(Linked List)Linked List)。12/19/20222.3.1 2.3.1 线性链表线性链表 链表是指用一组任意的存

19、储单元来依次存放链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元既可以是连续的，线性表的结点，这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的也可以是不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个储指示其后继结点的地址（或位置）信息，这个信息称为指针信息称为指针(pointer)

20、pointer)或链或链(link)link)。这两部分这两部分组成了链表中的结点结构：组成了链表中的结点结构：12/19/2022 其中：其中：datadata域是数据域，用来存放结点的域是数据域，用来存放结点的值。值。nextnext是指针域（亦称链域），用来存放结是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的过每个结点的链域将线性表的n n个结点按其逻个结点按其逻辑次序链接在一起的。由于上述链表的每一个辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为结只有一个链域，故将这种

21、链表称为单链表单链表（Single Linked)Single Linked)。显然，单链表中每个结点的存储地址是存显然，单链表中每个结点的存储地址是存放在其前趋结点放在其前趋结点nextnext域中，而开始结点无前趋，域中，而开始结点无前趋，故应设头指针故应设头指针headhead指向开始结点。指向开始结点。datanext 12/19/2022同时，由于终端结点无后继，故终同时，由于终端结点无后继，故终端结点的指针域为空，即端结点的指针域为空，即nullnull（图图示中也可用示中也可用 表示表示)。例例1 1、线性表、线性表:(:(batbat，catcat，eateat，fatfat，

22、hathat，jatjat，latlat，mat)mat)12/19/2022单链表示意图如下：110 130 135 160头指针 head 165 170 200 205 hat200.cat135eat170.matNullbat130fat110jat205lat160 16512/19/2022lheadbat cat eat mat 单链表是由表头单链表是由表头唯一确定，因此单链表可以用头唯一确定，因此单链表可以用头指针的名字来命名。指针的名字来命名。例如：若头指针名是例如：若头指针名是head，则把链表称为表则把链表称为表head。用用C语言描述的单链表如下：语言描述的单链表如下

23、：Typedef char datatype;Typedef struct node datatype data;struct node *next;Listnode;12/19/2022 typedef Listnode *Linklist;Listnode *p;Linklist head;注意区分注意区分指针变量指针变量和和结点变量结点变量这两个不同的概念。这两个不同的概念。P为动态变量，它是通过标准函数生成的，即为动态变量，它是通过标准函数生成的，即 p=(Listnode*)malloc(sizeof(Listnode);函数函数malloc分配了一个类型为分配了一个类型为Listn

24、ode的结点变量的空间，的结点变量的空间，并将其首地址放入指针变量并将其首地址放入指针变量p中。一旦中。一旦p所指的结点变量所指的结点变量不再需要了，又可通过标准函数不再需要了，又可通过标准函数 free(p)释放所指的结点变量空间。释放所指的结点变量空间。12/19/2022一、建立单链表一、建立单链表 假设线性表中结点的数据类型是字符，我们假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符逐个输入这些字符型的结点，并以换行符n为输入结束标记。动态地建立单链表的为输入结束标记。动态地建立单链表的常用方法有如下两种：常用方法有如下两种：1、头插法建表、头插法建表 该方法

25、从一个空表开始，重复读入数据，生该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。直到读入结束标志为止。12/19/2022 Linklist CreateListf(void)char ch;Linklist head;Listnode *p;head=NULL;ch=getchar();while(ch!=n p=(Listnode*)malloc(sizeof(Listnode);pdata=ch;pnext=head;

26、head=p;ch=getchar();return(head);12/19/2022 Listlink CreateList(int n)int data;Linklist head;Listnode*p head=NULL;12/19/2022 for(i=n;i0;-i)p=(Listnode*)malloc(sizeof(Listnode);scanf(%d，&pdata);pnext=head;head=p;return(head);12/19/20222、尾插法建表尾插法建表 头插法建立链表虽然算法简单，但生成头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。的

27、链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾该方法是将新结点插入到当前链表的表尾上，为此必须增加一个上，为此必须增加一个尾指针尾指针r r，使其始使其始终指向当前链表的尾结点。例：终指向当前链表的尾结点。例：12/19/2022 Linklist CreateLista()char ch;Linklist head;Listnode *p，*r;/(，*head;)head=NULL;r=NULL;while(ch=getchar()!=n)p=(Listnode*)malloc(sizeof

28、(Listnode);pdata=ch;if(head=NULL)head=p;else rnext=p;r=p;12/19/2022 if(r!=NULL)rnext=NULL;return(head);说明：第一个生成的结点是开始结点，将开始结点插入说明：第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针一样的，原因是开始结点的位置是存放在头指针（指针变量）中，

29、而其余结点的位置是在其前趋结点的指针域变量）中，而其余结点的位置是在其前趋结点的指针域中。中。12/19/2022 算法中的第一个算法中的第一个if语句就是用来对第一个位置上的语句就是用来对第一个位置上的插入操作做特殊处理。算法中的第二个插入操作做特殊处理。算法中的第二个if语句的作用是语句的作用是为了分别处理空表和非空表两种不同的情况，若读入的为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表第一个字符就是结束标志符，则链表head是空表，尾指是空表，尾指针针r亦为空，结点亦为空，结点*r不存在；否则链表不存在；否则链表head非空，最后非空，最后一个尾结点一个

30、尾结点*r是终端结点，应将其指针域置空。是终端结点，应将其指针域置空。如果我们在链表的开始结点之前附加一个结点，并如果我们在链表的开始结点之前附加一个结点，并称它为称它为头结点头结点，那么会带来以下两个优点：，那么会带来以下两个优点：a、由于开始结点的位置被存放在头结点的指针域中，由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就所以在链表的第一个位置上的操作就和在表的其它位和在表的其它位置上的操作一致，无需进行特殊处理；置上的操作一致，无需进行特殊处理；12/19/2022 b b、无论链表是否为空，其头指针是指向头结点的非空无论链表是否为空，其头指针是指向头结点的

31、非空指针（空表中头结点的指针域为空），因此空表和非指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。空表的处理也就统一了。其算法如下：其算法如下：Linklist createListr1()char ch;Linklist head；head=(Linklist)malloc(sizeof(Listnode);Listnode *p，*r 12/19/2022其算法如下：其算法如下：Linklist CreateListr1()char ch;Linklist head；head=(Linklist)malloc(sizeof(Listnode);Listnode *p，*

32、r=head;while(ch=getchar()!=n p=(Listnode*)malloc(sizeof(Listnode);pdata=ch;rnext=p;r=p;rnext=NULL;return(head);12/19/202212/19/2022上述算法里动态申请新结点空间时未加错上述算法里动态申请新结点空间时未加错误处理，可作下列处理：误处理，可作下列处理：p=(Listnode*)malloc(sizeof(Listnode)if(p=NULL)printf(No space for node can be obtained);return ERROR;以上算法的时间复杂度

33、均为以上算法的时间复杂度均为O(n)。12/19/2022二、查找运算二、查找运算 1 1、按序号查找、按序号查找 在链表中，即使知道被访问结点的序号在链表中，即使知道被访问结点的序号i i，也不能象顺序表中那样直接按序号也不能象顺序表中那样直接按序号i i访问结点，访问结点，而只能从链表的头指针出发，顺链域而只能从链表的头指针出发，顺链域nextnext逐个逐个结点往下搜索，直到搜索到第结点往下搜索，直到搜索到第i i个结点为止。个结点为止。因此，因此，链表不是随机存取结构链表不是随机存取结构。设单链表的长度为设单链表的长度为n n，要查找表中第要查找表中第i i个结个结点，仅当点，仅当11

34、inin时，时，i i的值是合法的。但有时的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是需要找头结点的位置，故我们将头结点看做是第第0 0 个结点，其算法如下：个结点，其算法如下：12/19/2022Listnode*Getnode(Linklist head，int i)int j;Listnode *p=head;j=0;while(pnext&jnext;j+;if(i=j)return p;else return NULL;12/19/2022 2 2、按值查找按值查找 按值查找是在链表中，查找是否有结点按值查找是在链表中，查找是否有结点值等于给定值值等于给定值keyke

35、y的结点，若有的话，则的结点，若有的话，则返回首次找到的其值为返回首次找到的其值为keykey的结点的存储的结点的存储位置；否则返回位置；否则返回NULLNULL。查找过程从开始结查找过程从开始结点出发，顺着链表逐个将结点的值和给定点出发，顺着链表逐个将结点的值和给定值值keykey作比较。其算法如下：作比较。其算法如下：12/19/2022Listnode*Locatenode(Linklist head，int key)Listnode*p=headnext;while(p&pdata!=key)p=pnext;return p;该算法的执行时间亦与输入实例中的的取值该算法的执行时间亦与输

36、入实例中的的取值key有关，有关，其平均时间复杂度的分析类似于按序号查找，也为其平均时间复杂度的分析类似于按序号查找，也为O(n)。12/19/2022三、插入运算三、插入运算 插入运算是将值为插入运算是将值为x x的新结点插入到的新结点插入到表的第表的第i i个结点的位置上，即插入到个结点的位置上，即插入到a ai i-1-1与与a ai i之间。因此，我们必须首先找到之间。因此，我们必须首先找到a ai i-1-1的存储的存储位置位置p p，然后生成一个数据域为然后生成一个数据域为x x的新结点的新结点*q q，并令结点并令结点*p p的指针域指向新结点，新的指针域指向新结点，新结点的指针

37、域指向结点结点的指针域指向结点a ai i。从而实现三个结从而实现三个结点点a ai i-1-1，x x和和a ai i之间的逻辑关系的变化，插入之间的逻辑关系的变化，插入过程如下：过程如下：12/19/2022具体算法如下：具体算法如下：void Insertnode(Linklist head，datetype x，int i)Listnode *p，*q;p=Getnode(head，i-1);if(p=NULL)printf(position error);q=(Listnode*)malloc(sizeof(Listnode);qdata=x;qnext=pnext;pnext=q;

38、12/19/2022 设链表的设链表的长度为长度为n，合法的插入位置是合法的插入位置是1in+1。注意当注意当i=1时，时，Getnode找找到的是头结点，当到的是头结点，当i=n+1时，时，Getnode找到的是结点找到的是结点an。因此，用因此，用i-1做实参做实参调用调用Getnode时可完成插入位置的合时可完成插入位置的合法性检查。算法的时间主要耗费在查法性检查。算法的时间主要耗费在查找操作找操作Getnode上，故时间复杂度亦上，故时间复杂度亦为为O(n)。12/19/2022四、删除运算四、删除运算 删除运算是将表的第删除运算是将表的第i个结点删去。因为个结点删去。因为在单链表中结

39、点在单链表中结点ai的存储地址是在其直接前的存储地址是在其直接前趋结点趋结点 a i-1的指针域的指针域next中，所以我们必须首中，所以我们必须首先找到先找到a i-1的存储位置的存储位置p。然后令然后令pnext指向指向ai的直接后继结点，即把的直接后继结点，即把ai从链上摘下。最后从链上摘下。最后释放结点释放结点ai的空间，将其归还给的空间，将其归还给“存储池存储池”。此过程为：此过程为：12/19/2022 12/19/2022具体算法如下具体算法如下：void DeleteList(Linklist head，int i)Listnode*p，*r;p=Getnode(head，i-

40、1);if(p=NULL|pnext=NULL)return ERROR;r=pnext;pnext=rnext;free(r);12/19/2022 设设单链表的单链表的长度为长度为n n，则删去第则删去第i i个结点仅当个结点仅当11inin时是合法的。注意，当时是合法的。注意，当i=n+1i=n+1时，虽然被时，虽然被删结点不存在，但其前趋结点却存在，它是终端删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋结点。因此被删结点的直接前趋*p p存在并不意味存在并不意味着被删结点就一定存在，仅当着被删结点就一定存在，仅当*p p存在（即存在（即p!=NULLp!=NUL

41、L）且且*p p不是终端结点不是终端结点 即即pnext!=NULLpnext!=NULL）时，才能确定被删结点存时，才能确定被删结点存在。在。显然此算法的时间复杂度也是显然此算法的时间复杂度也是O(n)O(n)。从上面的讨论可以看出，从上面的讨论可以看出，链表上实现插入和删链表上实现插入和删除运算，无须移动结点，仅需修改指针。除运算，无须移动结点，仅需修改指针。12/19/20222.3.2 2.3.2 循环链表循环链表 循环链表时一种头尾相接的链表。其特点是无循环链表时一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，须增加存储量，仅对表的链接方式稍作改变，即可使得表处

42、理更加方便灵活即可使得表处理更加方便灵活。单循环链表：单循环链表：在单链表中，将终端结点的指针域在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点，就得到改为指向表头结点或开始结点，就得到了单链形式的循环链表，并简单称为单循环链了单链形式的循环链表，并简单称为单循环链表。表。为了使空表和非空表的处理一致，循环链表为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：有一个自成循环的头结点表示。如下图所示：12/19/2022 a1 an .head 非空表 空表 在用头在用头指

43、针表示的单链表中，找开始结点指针表示的单链表中，找开始结点a1的的时间是时间是O(1)，然而要找到终端结点然而要找到终端结点an，则需则需从头指针开始遍历整个链表，其时间是从头指针开始遍历整个链表，其时间是O(n)12/19/2022 在很多实际问题中，表的操作常在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方指针表示的单循环链表就显得不够方便便.如果改用尾指针如果改用尾指针rear来表示单循环来表示单循环链表，则查找开始结点链表，则查找开始结点a1和终端结点和终端结点an都很方便，它们的存储位置分别是都很方便，它们的

44、存储位置分别是(rearnext)next和和rear，显然，显然，查找时间都是查找时间都是O(1)。因此，实际中多因此，实际中多采用尾指针表示单循环链表。采用尾指针表示单循环链表。12/19/2022由于循环链表中没有由于循环链表中没有NULL指针，故涉指针，故涉及遍历操作时，其终止条件就不再像非及遍历操作时，其终止条件就不再像非循环链表那样判断循环链表那样判断p或或pnext是否为是否为空，而是判断它们是否等于某一指定指空，而是判断它们是否等于某一指定指针，如头指针或尾指针等。针，如头指针或尾指针等。例、在链表上实现将两个线性表例、在链表上实现将两个线性表(a1，a2，a3，an)和和(b

45、1，b2，b3，bn)链接成一个链接成一个线性表的运算。线性表的运算。12/19/2022 Linklist Connect(Linklist heada，Linklist headb)Linklist p=headanext;headanext=(headbnext)next;free(headbnext);headbnext=p;return(headb);12/19/20222.3.32.3.3双链表双链表 双向链表双向链表(Double linked list):Double linked list):在单链表的在单链表的每个结点里再增加一个指向其直接前趋的指每个结点里再增加一个指向其

46、直接前趋的指针域针域priorprior。这样就形成的链表中有两个方这样就形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：向不同的链，故称为双向链表。形式描述为：typedef struct DListnode datatype data;struc DListnode*prior，*next;DListnode;typedef DListnode *DLinklist;DLinklist head;12/19/2022 和单链表类似，双链表一般也是由头指针和单链表类似，双链表一般也是由头指针唯一确定的，增加头指针也能使双链表上的某唯一确定的，增加头指针也能使双链表上的某些运算变得

47、方便，将头结点和尾结点链接起来些运算变得方便，将头结点和尾结点链接起来也能构成循环链表，并称之为也能构成循环链表，并称之为双向链表双向链表。设指针设指针p指向某一结点，则双向链表结构的对指向某一结点，则双向链表结构的对称性可用下式描述：称性可用下式描述：(pprior)next=p=(pnext)prior 即结点即结点*p的存储位置既存放在其前趋结点的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放的直接后继指针域中，也存放 在在它的后继结点它的后继结点*(pnext)的直接前趋指针域中。的直接前趋指针域中。12/19/2022双向链表的前插双向链表的前插操作算法如下：

48、操作算法如下：void Dinsertbefor(DListnode*p，datatype x)DListnode*q=malloc(sizeof(DListnode);qdata=x;qprior=pprior;qnext=p;ppriornext=q;pprior=q;12/19/2022 void ddeletenode(DListnode*p)ppriornext=pnext;pnextprior=pprior;free(p);注意：注意：与单链表的插入和删除操作不同的与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算是法的时两个方向上的指针。上述两个算是法的时间复杂度均为间复杂度均为O(1)O(1)。12/19/2022