第3章-线性表及其链式存储

1、第第3 3章章 线性表的链式存储线性表的链式存储 链式存储链式存储单链表单链表带头结点的单链表带头结点的单链表循环单链表循环单链表双链表双链表链式栈链式栈链式队列链式队列线性表的存储方式除了常用的顺序存储外，采用线性表的存储方式除了常用的顺序存储外，采用链式方式存储也是一种常见的方式。本章将介绍一般链式方式存储也是一种常见的方式。本章将介绍一般线性表的几种链式存储实现方式，如单链表、带头结线性表的几种链式存储实现方式，如单链表、带头结点单链表、循环单链表、双链表以及特殊的线性表点单链表、循环单链表、双链表以及特殊的线性表-栈和队列的链式存储实现。栈和队列的链式存储实现。 3.1链式存储链式存储

2、 数据结构的存储方式必须体现它的逻辑关系数据结构的存储方式必须体现它的逻辑关系 。在链式存储方式下，实现中除存放一个结点的信息外，在链式存储方式下，实现中除存放一个结点的信息外，还需附设指针，用指针体现结点之间的逻辑关系。如还需附设指针，用指针体现结点之间的逻辑关系。如果一个结点有多个后继或多个前驱，那么可以附设相果一个结点有多个后继或多个前驱，那么可以附设相应个数的指针，一个结点附设的指针指向的是这个结应个数的指针，一个结点附设的指针指向的是这个结点的某个前驱或后继。点的某个前驱或后继。 线性结构中，每个结点最多只有一个前驱和一个后继，这线性结构中，每个结点最多只有一个前驱和一个后继，这里暂

3、且设定更关心它的后继，这样在存储时除了存放该结点的信里暂且设定更关心它的后继，这样在存储时除了存放该结点的信息外，只要附设一个指针即可，该指针指向它的后继结点的存放息外，只要附设一个指针即可，该指针指向它的后继结点的存放位置。每个结点的存储形式是：位置。每个结点的存储形式是： infonext例，数据的逻辑结构例，数据的逻辑结构B=（K，R）其中其中 K=k1,k2,k3,k4,k5 R=r R=,是一个线性结构，它的链式存储如图所示是一个线性结构，它的链式存储如图所示 存储地址存储地址 info nextk41006k21007k11003k5k31005为了清晰，上图可以更简洁地用下图表示

4、。为了清晰，上图可以更简洁地用下图表示。k1k5k2k3k4head3.2 单链表单链表 单链表是线性表链式存储的一种形式，其中的单链表是线性表链式存储的一种形式，其中的结点一般含有两个域，一个是存放数据信息的结点一般含有两个域，一个是存放数据信息的info域，域，另一个是指向该结点的后继结点的存放地址的指针另一个是指向该结点的后继结点的存放地址的指针域域next。一个单链表必须有一个首指针指向单链表。一个单链表必须有一个首指针指向单链表中的第一个结点。中的第一个结点。数据1指针数据2指针数据3指针数据域数据域指针域指针域节点节点直观化的描述方法：直观化的描述方法：单链表是由表头唯一确定，因此

5、单链表可以用头单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例如：若头指针名是指针的名字来命名。例如：若头指针名是head，则把链表称为表则把链表称为表head。head(a) 非空表非空表head=NULL(b) 空表空表3.2.2单链表的实现单链表的实现 单链表结构的单链表结构的C语言描述如下：语言描述如下：/ 链表实现的头文件链表实现的头文件,文件名文件名linklist.h / typedef int datatype; typedef struct link_node datatype info; struct link_node next; node; typedef

6、 node * linklist;单链表几个基本操作的具体实现：单链表几个基本操作的具体实现：建立一个空的单链表建立一个空的单链表 / 函数功能函数功能:建立一个空的单链表建立一个空的单链表 / 函数参数函数参数:无无 / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的指针 / 文件名文件名:slnklist.c,函数名函数名:init() / node init() / 建立一个空的单链表建立一个空的单链表 / return NULL; 算法算法3.1 建立一个空的单链表建立一个空的单链表 输出单链表中各个结点的值输出单链表中各个结点的值 void display(node

7、head) node p; p=head; if(!p) printf(n单链表是空的！单链表是空的！); else printf(n单链表各个结点的值为单链表各个结点的值为:n); while(p) printf(%5d,p-info);p=p-next; 算法算法3.2输出单链表中各个结点的值输出单链表中各个结点的值在单链表中查找第在单链表中查找第i个结点个结点 node find(node head,int i) int j=1; node p=head; if(inext;j+; return p; 算法算法3.3 在单链表中查找第在单链表中查找第i个结点个结点单链表的插入过程见下图所

8、示单链表的插入过程见下图所示 ： headpx(2) head=p;(1) p-next=head;(a) 在单链表的最前面插入一个值为在单链表的最前面插入一个值为x的新结点的新结点单链表的插入过程见下图所示单链表的插入过程见下图所示 ： head (2)px(2) head=p;(a) 在单链表的最前面插入一个值为在单链表的最前面插入一个值为x的新结点的新结点(1) p-next=head;单链表的插入过程见下图所示单链表的插入过程见下图所示 ：head (b) 在在q所指的结点后插入一个所指的结点后插入一个p所指的值为所指的值为x的新结点的新结点(1) p-next=q-next;x单链表

9、的插入过程见下图所示单链表的插入过程见下图所示 ：head x(b) 在在q所指的结点后插入一个所指的结点后插入一个p所指的值为所指的值为x的新结点的新结点(1) p-next=q-next;(2) q-next=p;/ 函数功能函数功能:单链表第单链表第i个结点后插入值为个结点后插入值为x的新结点的新结点 / 函数参数函数参数:指向指向node类型变量的指针类型变量的指针head / datatype 类型变量类型变量x,int型变量型变量I / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的指针 / 文件名文件名:slnklist.c,函数名函数名:insert() / n

10、ode insert(node head,datatype x,int i) node p, q; q=find(head,i);/ 查找第查找第i个结点个结点 / if(!q&i!=0) printf(n找不到第找不到第%d个结点个结点,不能插入不能插入%d！,i,x); else p=(node )malloc(sizeof(node);/ 分配空间分配空间 / p-info=x;/ 设置新结点设置新结点 /if(i=0)/* 插入的结点作为单链表的第一个结点插入的结点作为单链表的第一个结点*/ p-next=head;/ 插入插入(1) / head=p;/ 插入插入(2) /

11、else p-next=q-next;/ 插入插入(1) / q-next=p;/ 插入插入(2) / return head; 算法算法3.4 在单链表中第在单链表中第i个结点后插入一个值为个结点后插入一个值为x的新结点的新结点1、申请空间、申请空间s=malloc(.)2、填入数据域、填入数据域值值s-info=ch;单链表应用单链表应用-建立单链表建立单链表方法一：堆栈方式建立单链表（头插法）方法一：堆栈方式建立单链表（头插法）数据1数据23、新结点链入表头、新结点链入表头s-next=head;4、修改表头指针、修改表头指针head=s;数据1数据24、修改表头指针、修改表头指针hea

12、d=s;单链表应用单链表应用-建立单链表建立单链表方法一：堆栈方式建立单链表（头插法）方法一：堆栈方式建立单链表（头插法）#include “linklist.h”node * creatlistf() datatype data; node * head, *s; head=NULL; printf(nnPlease input the data of linklistn); scanf(%d,&data); while (data!=0) s=(node *) malloc(sizeof(node); s-info=data; s-next=head; head=s; scanf(

13、%d,&data); return head; 1、申请空间、申请空间s=malloc()2、填入数据域、填入数据域值值s-info=ch;3、新结点链入表尾、新结点链入表尾r-next=s;4、修改表尾指针、修改表尾指针r=s;方法二：队列方式建立单链表（尾插法）方法二：队列方式建立单链表（尾插法）数据2数据1方法二：队列方式建立单链表（尾插法）方法二：队列方式建立单链表（尾插法）数据2数据1关键一步：关键一步：设置一个链尾指针设置一个链尾指针r，每次将新的结点链在，每次将新的结点链在r的的后面，使其成为新的表尾结点。后面，使其成为新的表尾结点。node* creatlistr(vo

14、id) datatype data; node *head,*s,*r; head=NULL;r=NULL; scanf(%d,&data); while (data) s=(node *)malloc(sizeof(node); s-info=data; /*产生新结点产生新结点*/ if (head=NULL) head=s; /*新结点插入空表新结点插入空表*/ else r-next=s; r=s; scanf(%d,&data); /*处理表尾结点指针域处理表尾结点指针域*/以以0作为输入结束作为输入结束条件条件if (r!=NULL) r-next=NULL;ret

15、urn head; 删除删除操作见下图所示：操作见下图所示： headp(1) head=head-next;(a) 删除单链表的最前面的（第一个）结点删除单链表的最前面的（第一个）结点2) free(p删除删除操作见下图所示操作见下图所示 head(1) head=head-next;(a) 删除单链表的最前面的（第一个）结点删除单链表的最前面的（第一个）结点(2) free(p)(b) 删除删除p指向的结点，指向的结点，pre为为p的前驱结点的前驱结点(1) pre-next=p-next;head pre p(b) 删除删除p指向的结点，指向的结点，pre为为p的前驱结点的前驱结点(1)

16、 pre-next=p-next;head pre p(1)(b) 删除删除p指向的结点，指向的结点，pre为为p的前驱结点的前驱结点(1) pre-next=p-next;head pre(1)(2)free(p)/ 函数功能函数功能:在单链表中删除一个值为在单链表中删除一个值为x的结点的结点 / 函数参数函数参数:指向指向node类型变量的指针类型变量的指针head / datatype 类型变量类型变量x / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的指针 / 文件名文件名:slnklist.c,函数名函数名:dele() / node dele(node head,

17、datatype x) node pre=NULL, p; if(!head) printf(单链表是空的！单链表是空的！);return head; p=head; while(p&p-info!=x) / 没有找到并且没有找完没有找到并且没有找完 / pre=p;p=p-next; / pre指向指向p的前驱结点的前驱结点 / if(!pre&p-info=x) / 要删除的是第一个结点要删除的是第一个结点 / head=head-next;/ 删除删除(1) /else pre-next=p-next; free(p); return head; 算法算法3.5 在单链表

18、中删除一个值为在单链表中删除一个值为x的结点的结点3.3 带头结点单链表带头结点单链表 3.3.1带头结点单链表带头结点单链表带头结点单链表见下图所示：带头结点单链表见下图所示： 数据2数据1数据3headhead(A) 空表空表(B) 非空表非空表3.3.2带头结点单链表的实现带头结点单链表的实现 一般的单链表中，第一个结点由一般的单链表中，第一个结点由head指示，而在指示，而在带头结点单链表中，带头结点单链表中，head指示的是所谓的头结点，它指示的是所谓的头结点，它不是存储数据结构中的实际结点，第一个实际的结点是不是存储数据结构中的实际结点，第一个实际的结点是head-next指示的。

19、在带头结点单链表的操作实现时指示的。在带头结点单链表的操作实现时要注意这一点。要注意这一点。 node init() node head; head=(node )malloc(sizeof(node); head-next=NULL; return head; 算法算法3.6 建立一个空的带头结点的单链表建立一个空的带头结点的单链表请修改头插法与尾插法建表程序请修改头插法与尾插法建表程序,以建立带头以建立带头结点的单链表。结点的单链表。 void display(node head) node p; p=head-next; / 从第一个（实际）结点开始从第一个（实际）结点开始 / if(!

20、p) printf(n带头结点的单链表是空的带头结点的单链表是空的!); else printf(n带头结点的单链表各个结点的值为带头结点的单链表各个结点的值为:n); while(p) printf(%5d,p-info);p=p-next; 算法算法3.7 输出带头结点的单链表中各个结点的值输出带头结点的单链表中各个结点的值/ 函数功能函数功能:在带头结点的单链表中查找第在带头结点的单链表中查找第i个结点地址个结点地址 / 函数参数函数参数:指向指向node类型变量的指针类型变量的指针head / int类型变量类型变量i / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的

21、指针head / 文件名文件名hlnklist.c,函数名函数名find() / node find(node head,int i) int j=0; node p=head; if(inext;j+;/ 继续向后（左）查找继续向后（左）查找,计数器加计数器加1 / return p;/ 返回结果返回结果,i=0时时,p指示的是头结点指示的是头结点 / 算法算法3.8 在带头结点的单链表中查找第在带头结点的单链表中查找第i个结点个结点带头结点单链表的插入过程见图带头结点单链表的插入过程见图3.7 x (2) (1)(2)q p(b) 在在q所指的结点后插入一个所指的结点后插入一个p所指的值为

22、所指的值为x的新结点的新结点(1) p-next=q-next;(2) q-next=p;head p (2) head (2) (1)x(1) p-next=q-next;(2) q-next=p;(a) 非空带头结点单链表的最前面插入一个值为非空带头结点单链表的最前面插入一个值为x的新结点的新结点q 带头结点的单链表的插入操作的具体实现见算法带头结点的单链表的插入操作的具体实现见算法3.9。 / / 函数功能函数功能:在带头结点的单链表中第在带头结点的单链表中第i个结点后插入一个值为个结点后插入一个值为x的新结点的新结点 / 函数参数函数参数:指向指向node类型变量的指针类型变量的指针h

23、ead / datatype 类型变量类型变量x,int型变量型变量i / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的指针head / 文件名文件名:hlnklist.c,函数名函数名:insert() / node insert(node head,datatype x,int i) node p, q; q=find(head,i); / 查找带头结点的单链表中的第查找带头结点的单链表中的第i个结点个结点 / / i=0,表示新结点插入在头结点之后表示新结点插入在头结点之后,此时此时q指向的是头结点指向的是头结点 / if(!q)/ 没有找到没有找到 / printf(

24、n带头结点的单链表中不存在第带头结点的单链表中不存在第%d个结点！不能个结点！不能插入插入%d！,i,x);return head; p=(node )malloc(sizeof(node);/ 为准备插入的新结点为准备插入的新结点分配空间分配空间 / p-info=x;/ 为新结点设置值为新结点设置值x / p-next=q-next; / 插入插入(1) / q-next=p;/ 插入插入(2),当当i=0时时,由于由于q指向的是头结点指向的是头结点,本语句等价于本语句等价于headnext=p / return head; 算法算法3.9 在带头结点的单链表中第在带头结点的单链表中第i个

25、结点后插入一个值为个结点后插入一个值为x的的新结点新结点带头结点单链表的删除过程见图带头结点单链表的删除过程见图3.8。 q(1) head-next=q-next;(a) 删除带头结点单链表的最前面的（第一个）实际结点删除带头结点单链表的最前面的（第一个）实际结点 (1) (1)(b) 在带头结点单链表中删除在带头结点单链表中删除q指向的结点，指向的结点，pre为为q的前驱结点的前驱结点(1) pre-next=q-next;pre qhead node dele(node head,datatype x) node pre=head, q;/ 首先首先pre指向头结点指向头结点 / q=h

26、ead-next;/ q从带头结点的第一个实际从带头结点的第一个实际结点开始找值为结点开始找值为x的结点的结点 / while(q&q-info!=x) / 没有查找完并且还没有找到没有查找完并且还没有找到 / pre=q;q=q-next; / 继续查找继续查找,pre指向指向q的前驱的前驱 / if (q) pre-next=q-next;/ 删除删除 / free(q);/ 释放空间释放空间 / return head; 算法算法3.10 在带头结点的单链表中删除一个值为在带头结点的单链表中删除一个值为x的结点的结点算法设计题：算法设计题：1、用单链表作为存储结构，实现线性表（、

27、用单链表作为存储结构，实现线性表（a0,a1, an-1）就地逆置的操作，所谓就地指辅助空间应为）就地逆置的操作，所谓就地指辅助空间应为O(1)。2、设单链表、设单链表L是一个递减有序表，试写一算法将是一个递减有序表，试写一算法将X插插入其中后仍保持入其中后仍保持L的有序性。的有序性。3、写一算法将单链表中值重复的结点删除，使所得的、写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。结果表中各结点值均不相同。4、设计一个算法，对单链表按结点值从小到大对结点、设计一个算法，对单链表按结点值从小到大对结点进行排序。进行排序。算法设计题：算法设计题：5、设计一个算法，将两个有序单

28、链表合并成一个有序、设计一个算法，将两个有序单链表合并成一个有序的单链表。的单链表。6、设计一个算法，求两个单链表表示的集合的交集，、设计一个算法，求两个单链表表示的集合的交集，并将结果用一个新的单链表保存并返回。并将结果用一个新的单链表保存并返回。 50 40 80 10phead链表插入排序演示链表插入排序演示 50 40 80 10pheads 50 40 80 10pheadspreq=head-next while ( q & q-datadata ) pre=q; q=q-next;循环结束时，将循环结束时，将s结点加在结点加在pre与与q所指示的结点所指示的结点之间！之间

29、！ 50 40 80 10pheadspreq=head-next while ( q & q-datadata ) pre=q; q=q-next;s-next=q;pre-next=s; 50 40 80 10pheadspreq=head-next while ( q & q-datadata ) pre=q; q=q-next;s-next=q;pre-next=s; 50 40 80 10pheadspreq=head-next while ( q & q-datadata ) pre=q; q=q-next;s-next=q;pre-next=s;算法设计题

30、：算法设计题：多相式相加问题多相式相加问题:A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8ABC3.4 循环单链表循环单链表 3.4.1 循环单链表循环单链表 head 循环单链表类型的描述循环单链表类型的描述 （略）（略）3.4.2循环单链表的实现循环单链表的实现 单链表中某个结点单链表中某个结点p是表中最后一个结点的特征是表中最后一个结点的特征是是p-next=NULL。对于一个循环单链表，若首指。对于一个循环单链表，若首指针为针为head，表中的某个结点，表中的某个结点p是最后一个结点的特征是最后一个结点的特征应该是应该是p-next=head循环单链表的头文件和单

31、链表的相同。循环单链表的头文件和单链表的相同。 建立一个空的循环单链表建立一个空的循环单链表/ 函数功能函数功能:建立一个空的循环单链表建立一个空的循环单链表 / 函数参数函数参数:无无 / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的指针 / 文件名文件名:clnklist.c,函数名函数名init() / node init()/ 建立一个空的循环单链表建立一个空的循环单链表 / return NULL; 算法算法3.11 建立一个空的循环单链表建立一个空的循环单链表/ 函数功能函数功能:获得循环单链表的最后一个结点的存储地址获得循环单链表的最后一个结点的存储地址 / 函

32、数参数函数参数:指向指向node类型变量的指针变量类型变量的指针变量head / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的指针 / 文件名文件名:clnklist.c,函数名函数名:rear() / node rear(node head) node p; if(!head)/ 循环单链表为空循环单链表为空 / p=NULL; else p=head;/ 从第一个结点开始从第一个结点开始 / while( p-next!=head ) / 没有到达最后一个结点没有到达最后一个结点 / p=p-next;/ 继续向后继续向后 / return p; 算法算法3.12 获得循

33、环单链表的最后一个结点的存储地址获得循环单链表的最后一个结点的存储地址/ 函数功能函数功能:输出循环单链表中各个结点的值输出循环单链表中各个结点的值 / 函数参数函数参数:指向指向node类型变量的指针变量类型变量的指针变量head / 函数返回值函数返回值:空空 / 文件名文件名:clnklist.c,函数名函数名:display() / void display(node head) node p; if(!head) printf(n循环单链表是空的！循环单链表是空的！n); else printf(n循环单链表各个结点的值分别为循环单链表各个结点的值分别为:n); printf(%5d

34、,head-info);/ 输出非空表中第一个结点的值输出非空表中第一个结点的值 / p=head-next;/ p指向第一个结点的下一个结点指向第一个结点的下一个结点 / while( p!=head )/ 没有回到第一个结点没有回到第一个结点 / printf(%5d,p-info); p=p-next; 算法算法3.13 输出循环单链表中各个结点的值输出循环单链表中各个结点的值/ 函数功能函数功能:循环单链表中查找值为循环单链表中查找值为x的结点的存储地址的结点的存储地址 / 函数参数函数参数:指向指向node类型变量的指针变量类型变量的指针变量head / datatype类型的变量类

35、型的变量x / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的指针 / 文件名文件名:clnklist.c,函数名函数名:find() / node find(node head,datatype x) / 查找一个值为查找一个值为x的结点的结点 / node q; if(!head)/ 循环单链表是空的循环单链表是空的 / printf(n循环单链表是空的！无法找指定结点！循环单链表是空的！无法找指定结点！); return NULL; q=head;/ q指向循环单链表的第一个结点指向循环单链表的第一个结点,准备查找准备查找 / while( q-next!=head&am

36、p;q-info!=x )/ 没有查找到并且没有没有查找到并且没有查找完整个表查找完整个表 / q=q-next;/ 继续查找继续查找 / if(q-info=x) return q; else return NULL; 算法算法3.14 在循环单链表中查找一个值为在循环单链表中查找一个值为x的结点的结点循环单链表的插入过程如图循环单链表的插入过程如图 ： headpx(a) 在循环单链表的最前面插入一个值为在循环单链表的最前面插入一个值为x的新结点的新结点(1) p-next=head(2) head=p;(3) rear-next=p;head xq p(b) 循环单链表，在循环单链表，在

37、q所指的结点后插入一个所指的结点后插入一个p所指的所指的值为值为x的新结点的新结点(1) p-next=q-next;(2) q-next=p;/ 函数功能函数功能:循环单链表第循环单链表第i个结点后插入值为个结点后插入值为x的新结点的新结点 / 函数参数函数参数:指向指向node类型变量的指针变量类型变量的指针变量head / datatype类型的变量类型的变量x,int类型的变量类型的变量I / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的指针 / 文件名文件名:clnklist.c,函数名函数名:insert() / node insert(node head,dat

38、atype x,int i) /*i为为0时表示将值为时表示将值为x的结点插入作为循环单链表的第一个结点的结点插入作为循环单链表的第一个结点*/ node p, q,*myrear; int j; p=(node )malloc(sizeof(node); / 分配空间分配空间 / p-info=x;/ 设置新结点的值设置新结点的值 / if(inext=p;head=p;return head; if(i=0&head)/*在非空的循环单链表最前面插在非空的循环单链表最前面插入入*/ myrear=rear(head);/ 找到循环单链表的最后一个结点找到循环单链表的最后一个结点 /

39、 p-next=head;/ 插入插入(1) / head=p; / 插入插入(2) / myrear-next=p;/ 插入插入(3)最后一个结点的指针域指向新最后一个结点的指针域指向新插入的表中第一个结点插入的表中第一个结点 / return head; if(i0&!head) printf(n无法找到指定的插入位置！无法找到指定的插入位置！); free(p);return head; if(i0&head)/*在非空的循环单链表中插入值为在非空的循环单链表中插入值为x的结点的结点,并并且插入的结点不是第一个结点且插入的结点不是第一个结点*/ q=head;/ 准备从表

40、中第一个结点开始查找准备从表中第一个结点开始查找 / j=1;/ 计数开始计数开始 / while(i!=j&q-next!=head)/ 没有找到并且没有找遍没有找到并且没有找遍整个表整个表 / q=q-next;j+;/ 继续查找继续查找,计数器加计数器加1 / if(i!=j) / 找不到指定插入位置找不到指定插入位置,即即i的值超过表中结点的值超过表中结点的个数的个数,则不进行插入则不进行插入 / printf(n表中不存在第表中不存在第%d个结点个结点,无法进行插入无法进行插入!n,i); free(p); return head; else else / 找到了第找到了第i

41、个结点个结点,插入插入x / p-next=q-next; / 插入插入,修改指针修改指针(1) / q-next=p;/ 插入插入,修改指针修改指针(2) / return head; 算法算法3.15 在循环单链表中第在循环单链表中第i个结点后插入一个值为个结点后插入一个值为x的新结点的新结点循环单链表的删除过程如图循环单链表的删除过程如图 ： head q(1) head=head-next; (2) pre-next=head;(a) 删除循环单链表的最前面的（第一个）结点删除循环单链表的最前面的（第一个）结点 (1) (1)pre (2) (2)循环单链表的删除过程如图循环单链表的删

42、除过程如图 ： (1)(1)(b) 删除删除q指向的结点，指向的结点，pre为为q的前驱结点（的前驱结点（q指向的不是循环单指向的不是循环单链表的第一个结点）链表的第一个结点）(1) pre-next=q-next;pre qhead / 函数功能函数功能:在循环单链表中删除一个值为在循环单链表中删除一个值为x的结点的结点 / / 函数参数函数参数:指向指向node类型变量的指针变量类型变量的指针变量head / datatype类型的变量类型的变量x / 函数返回值函数返回值:指向指向node类型变量的指针类型变量的指针 / 文件名文件名:clnklist.c,函数名函数名:dele() /

43、 node dele(node head,datatype x) node pre=NULL, q;/ q用于查找值为用于查找值为x的结点的结点,pre指向指向q的的前驱结点前驱结点 / if(!head)/ 表为空表为空,则无法做删除操作则无法做删除操作 / printf(n循环单链表为空循环单链表为空,无法做删除操作！无法做删除操作！); return head; q=head;/ 从第从第1个结点开始准备查找个结点开始准备查找 / while(q-next!=head&q-info!=x)/ 没有找遍整个表并且没有找遍整个表并且没有找到没有找到 / pre=q; q=q-next

44、;/ pre为为q的前驱的前驱,继续查找继续查找 / / 循环结束后循环结束后,pre为为q的前驱的前驱 / if(q-info!=x)/ 没找到没找到 / printf(没有找到值为没有找到值为%d的结点！的结点！,x); else/ 找到了找到了,下面要删除下面要删除q / if(q!=head)pre-next=q-next;free(q); else if(head-next=head)free(q);head=NULL; else pre=head-next; while(pre-next!=q) pre=pre-next;/*找找q的前驱结的前驱结点位置点位置*/ head=hea

45、d-next; pre-next=head; free(q); return head; 算法算法3.16 在循环单链表中删除一个值为在循环单链表中删除一个值为x的结点的结点3循环单链表的整体插入与删除操作循环单链表的整体插入与删除操作图图3.12 一个循环单链表整体插入到一个单链表前部的图示一个循环单链表整体插入到一个单链表前部的图示3.5 双链表双链表 3.5.1 双链表双链表 前面的各种链式表中，一个结点的指针域是指向前面的各种链式表中，一个结点的指针域是指向它的后继结点的，如果需要找一个结点它的后继结点的，如果需要找一个结点p的前驱结点，的前驱结点，则必须从表首指针开始查找，当某个结点

46、则必须从表首指针开始查找，当某个结点pre的指针的指针域指向的是结点域指向的是结点p时，即时，即pre-next=p时，则说明时，则说明pre是是p的前驱结点。如果常常需要知道一个结点的前的前驱结点。如果常常需要知道一个结点的前驱和后继结点，上述的链式表是不适合的。既然单链驱和后继结点，上述的链式表是不适合的。既然单链表中每个结点有一个指针域指向它的后继结点，那自表中每个结点有一个指针域指向它的后继结点，那自然地想到再增设一个指针域指向它的前驱结点，这就然地想到再增设一个指针域指向它的前驱结点，这就构成了双链表。构成了双链表。 双链表的结点包括三个域，一个是存放数据信息双链表的结点包括三个域，

47、一个是存放数据信息的的info域，另外两个是指针域，这里用域，另外两个是指针域，这里用llink和和rlink表表示，示，llink指向它的前驱结点，指向它的前驱结点，rlink指向它的后继结点。指向它的后继结点。 双链表的一般情形如图所示：双链表的一般情形如图所示： 双链表类型的描述（略！）双链表类型的描述（略！）head3.5.2 双链表的实现双链表的实现 双链表结构的双链表结构的C语言描述如下：语言描述如下：/ 双链表的头文件双链表的头文件,文件名文件名dlnklist.h / typedef int datatype; typedef struct dlink_node datatyp

48、e info; struct dlink_node llink, rlink; dnode;/ 函数功能函数功能:输出双链表中各个结点的值输出双链表中各个结点的值 / 函数参数函数参数:指向指向dnode类型变量的指针类型变量的指针head / 函数返回值函数返回值:空空 / 文件名文件名:dlnklist.c,函数名函数名:display() / void display(dnode head) dnode p; printf(n); p=head; if(!p) printf(n双链表是空的双链表是空的!n); else printf(n双链表中各个结点的值为双链表中各个结点的值为:n);

49、 while(p) printf(%5d,p-info);p=p-rlink; 算法算法3.18 输出双链表中各个结点的值输出双链表中各个结点的值dnode find(dnode head,int i) int j=1; dnode p=head; if(irlink;j+;/ 继续沿着右指针向后查找继续沿着右指针向后查找,计数器加计数器加1 / if(!p)printf(n第第%d个结点不存在个结点不存在!n,i);return NULL; return p; 算法算法3.19 查找双链表中第查找双链表中第i个结点个结点双链表插入过程如下图所示：双链表插入过程如下图所示： xhead(1)

50、p-rlink=head;p(a) 在双链表的最前面插入一个值为在双链表的最前面插入一个值为x的新结点的新结点(2) p-llink=NULL;(3) head-llink=p;(4) head=p;双链表插入过程如下图所示：双链表插入过程如下图所示：head (1) p-rlink=q-rlink;qxp(b) 在双链表中在双链表中q所指结点的后面插入一个值为所指结点的后面插入一个值为x的新结点的新结点(2) p-llink=q;(3) q-rlink-llink=p;(4) q-rlink=p;双链表插入过程如下图所示：双链表插入过程如下图所示： (1) p-rlink=q-rlink;q

51、xp(c) 在双链表中在双链表中q所指结点（是最后一个结点）的后面所指结点（是最后一个结点）的后面插入一个值为插入一个值为x的新结点的新结点head (2) p-llink=q; (3) q-rlink=p;/ 函数功能函数功能:双链表第双链表第i个结点后插入值为个结点后插入值为x的新结点的新结点 / 函数参数函数参数:指向指向dnode类型变量的指针类型变量的指针head / datatype类型的变量类型的变量x, int类型的变量类型的变量 / 函数返回值函数返回值:指向指向dnode类型变量的指针类型变量的指针 / 文件名文件名:dlnklist.c,函数名函数名:insert() /

52、dnode *insert(dnode *head,datatype x,int i) dnode *p,*q; p=(dnode*)malloc(sizeof(dnode);/*分配空间分配空间*/ p-info=x;/*设置新结点的值设置新结点的值*/ if(i=0)/*在最前面插入一个值为在最前面插入一个值为x的新结点的新结点*/ p-llink=NULL;/*新插入的结点没有前驱新插入的结点没有前驱*/ p-rlink=head;/*新插入的结点的后继是原来新插入的结点的后继是原来双链表中的第一个结点双链表中的第一个结点*/ if (!head)/*原表为空原表为空*/ head=p;

53、 else head-llink=p;/*原来双链表中第一个结点的前驱是原来双链表中第一个结点的前驱是新插入的结点新插入的结点*/ head=p;/*新结点成为双链表的第一个结点新结点成为双链表的第一个结点*/ return head; q=find(head,i);/*查找第查找第i个结点个结点*/ if(!q)/*第第i个结点不存在个结点不存在*/ printf(第第%d个结点不存在个结点不存在,无法进行插入无法进行插入,i);free(p);return head; if(q-rlink=NULL)/*在最后一个结点后插入在最后一个结点后插入*/ p-rlink=q-rlink; /*即

54、为即为NULL,新插入的结点没有后继。新插入的结点没有后继。插入操作（插入操作（1）*/ p-llink=q;/*插入操作（插入操作（2）*/ q-rlink=p;/*插入操（插入操（4）*/ /*注意不能和下面的一般情况一样处理注意不能和下面的一般情况一样处理,这里如执这里如执行下面的（行下面的（3）将出错！）将出错！*/ else/*一般情况下的插入一般情况下的插入*/ p-rlink=q-rlink; /*插入操作（插入操作（1）*/ p-llink=q;/*插入操作（插入操作（2）*/ q-rlink-llink=p;/*插入操作（插入操作（3）*/ q-rlink=p;/*插入操作（

55、插入操作（4）*/ return head; 算法算法3.20 在双链表中第在双链表中第i个结点后插入一个值为个结点后插入一个值为x的新结点的新结点双链表删除操作图示双链表删除操作图示 ：head(a) 被删除的被删除的q是双链表中唯一的一个结点是双链表中唯一的一个结点qNULL(b) 被删除的被删除的q是双链表中的第一个结点（表中不只是双链表中的第一个结点（表中不只这一个结点）这一个结点）qhead(1) head=head-rlink;(2) head-llink=NULL;(1) 双链表删除操作图示双链表删除操作图示 ：head(c) 被删除的被删除的q是双链表中的最后一个结点是双链表中

56、的最后一个结点qq-llink-rlink=NULL;q(1) q-llink-rlink=q-rlink;(2) q-rlink-llink=q-llink;(1)(2)head(d) 被删除的被删除的q是双链表中既非第一也非最后的一个结点是双链表中既非第一也非最后的一个结点/ 函数功能函数功能:在双链表中删除一个值为在双链表中删除一个值为x的结点的结点 / 函数参数函数参数:指向指向dnode类型变量的指针类型变量的指针head / datatype类型的变量类型的变量x / 函数返回值函数返回值:指向指向dnode类型变量的指针类型变量的指针 / 文件名文件名:dlnklist.c,函数

57、名函数名:dele() / dnode dele(dnode head,datatype x) dnode q; if(!head)/ 双链表为空双链表为空,无法进行删除操作无法进行删除操作 / printf(双链表为空双链表为空,无法进行删除操作无法进行删除操作);return head; q=head; while(q&q-info!=x) q=q-rlink;/ 循环结束后循环结束后q指向的指向的是值为是值为x的结点的结点 / if(!q) printf(n没有找到值为没有找到值为%d的结点的结点!不做删除操作！不做删除操作！,x); if(q=head&head-rli

58、nk)/ 被删除的结点是第一个结点被删除的结点是第一个结点并且表中不只一个结点并且表中不只一个结点 / head=head-rlink; head-llink=NULL; free(q);return head; if(q=head&!head-rlink) / 被删除的结点是第一个结点被删除的结点是第一个结点并且表中只有这一个结点并且表中只有这一个结点 / free(q); return NULL; / 双链表置空双链表置空 / else if(!q-rlink) / 被删除的结点是双链表中的最后一个结点被删除的结点是双链表中的最后一个结点 / q-llink-rlink=NULL;

59、 free(q); return head; else / q是有是有2个以上结点的双链表中的一个非开始、也个以上结点的双链表中的一个非开始、也非终端结点非终端结点 / q-llink-rlink=q-rlink; q-rlink-llink=q-llink; free(q); return head; 算法算法3.21 在双链表中删除一个值为在双链表中删除一个值为x的结点的结点3.6 链式栈链式栈 3.6.1 链式栈链式栈 栈的链式存储称为链式栈。链式栈就是一个特殊栈的链式存储称为链式栈。链式栈就是一个特殊的单链表，对于这特殊的单链表，它的插入和删除规的单链表，对于这特殊的单链表，它的插入和

60、删除规定在单链表的同一端进行。链式栈的栈顶指针一般用定在单链表的同一端进行。链式栈的栈顶指针一般用top表示，链式栈如下图所示。表示，链式栈如下图所示。 top3.6.2 链式栈的实现链式栈的实现 / 函数功能函数功能:读链式栈的读链式栈的栈顶栈顶结点值结点值 / 函数参数函数参数:指向指向node类型变量的指针类型变量的指针top / 函数返回值函数返回值:datatype类型的变量类型的变量 / 文件名文件名:lnkstack.c,函数名函数名:read() / datatype read(node top) if(!top) printf(n链式栈是空的链式栈是空的!);exit(1); return (top-info); /*本函数可以调用本函数可以调用empty()函数函数*/ 算法算法3.24 取得链式栈的栈顶结点值取得链式栈的