第3章 链接表.

1、主要内容主要内容普通高等教育“十一五”国家级规划教材第3章 链接表3.1 链表链表3.2 链栈链栈3.3 链队列链队列 返回目录返回目录3.4 字符串的链式存储字符串的链式存储3.5 链表应用举例链表应用举例3.1链表链表3.1.1单链表单链表3.1.2 循环链表循环链表作业作业 线性表的顺序存储的特点是用物理位置线性表的顺序存储的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结但它也使得插入和删除操作会移动大量的结点。为避免大量结点

2、的移动，本节将介绍线点。为避免大量结点的移动，本节将介绍线性表的另一种存储方法性表的另一种存储方法链式存储结构，链式存储结构，并将这种并将这种用链式方式存储的线性表简称为链用链式方式存储的线性表简称为链表（表（Linked List）。）。概概 述述 从实现角度：从实现角度： 动态链表、静态链表动态链表、静态链表从链接方式角度：从链接方式角度： 单链表、循环链表、双链表单链表、循环链表、双链表链表的分类链表的分类 链接存储是最常用的存储方法之一，它不链接存储是最常用的存储方法之一，它不仅可以用来表示线性表，而且可以用来表示各仅可以用来表示线性表，而且可以用来表示各种非线的数据结构。种非线的数据

3、结构。 链表是用一组不连续的存储单元来存放线性表中的数据，链表是用一组不连续的存储单元来存放线性表中的数据，因此链表中结点的逻辑次序和物理次序不一定相同。因此，因此链表中结点的逻辑次序和物理次序不一定相同。因此，在存储每个数据元素值的同时，还要存储指示其后继结点的在存储每个数据元素值的同时，还要存储指示其后继结点的地址信息，这两部分信息组成的存储映象称为结点。地址信息，这两部分信息组成的存储映象称为结点。单链表：单链表：单链表又称为线性链表，是线性表的一种最简单链表又称为线性链表，是线性表的一种最简单的链式存储结构。在单链表中的每一个结点单的链式存储结构。在单链表中的每一个结点都包含两部分内容

4、：存放每一个数据元素本身都包含两部分内容：存放每一个数据元素本身的数据信息的数据域和存放其直接后继存储位的数据信息的数据域和存放其直接后继存储位置的指针域（地址域）。单链表中结点的结构置的指针域（地址域）。单链表中结点的结构如下：如下：datanext数据域指针域例例 线性表（线性表（zhao,qian,sun,li,zhou,wu,zheng,wang）LIQIANSUNWANGWUZHAOZHENGZHOU存储地址17131925313743数据域指针域43131NULL377192531H头指针ZHAOQIANSUNLIZHOUWUZHENGWANGH头结点：在单链表第一个结点前附设一个

5、结点叫头结点：在单链表第一个结点前附设一个结点叫头结点指针域为空头结点指针域为空,表示线性表为空表示线性表为空ha1a2头结点an .h空表3.1.1单链表单链表datanexttypedef struct node datatype data; struct node *next; linklist ; 1. 单链表的定义和存储结构单链表的定义和存储结构 定义：一个链表由定义：一个链表由n个结点组成个结点组成,每个结每个结点中有一个存储数据的值域和一个存储另一点中有一个存储数据的值域和一个存储另一个结点地址的指针域。由于链表的每个结点个结点地址的指针域。由于链表的每个结点只有一个链域，故将这

6、种链表称为单链表只有一个链域，故将这种链表称为单链表。 通常用头指针通常用头指针head来标识一个单链表的开来标识一个单链表的开始头结点始头结点:表的第一个结点的表的第一个结点的data域不存数据域不存数据空表空表:head-next=NULL（也可用（也可用表示空表示空NULL） 存储空间动态分配存储空间动态分配:p=malloc(sizeof(linklist) 释放释放 p 所指的结点所指的结点:free(p) a1head a2 an 单链表的链式存储结构示意图单链表的链式存储结构示意图 2. 单链表的基本操作单链表的基本操作(1)建立单链表建立单链表方法一：头插法建表方法一：头插法建

7、表该方法从一个空表开始，重复读入数据，生成该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到然后将新结点插入到当前链表的表头上，直到读入结束标志为止。读入结束标志为止。LSaSbScSdLdc头结点a b在线性表在线性表la中存放数据（中存放数据（5,4,8,6） 5head 4 6 8head head 6 8head 6 4head 8 6 6 8 5时间复杂度为时间复杂度为O(n) 4具体算法如下：具体算法如下：linklist *creatlistbefore()datat

8、ype d;linklist *p,*s,*head;head=malloc(sizeof(linklist);head-next=NULL; p=head; printf(please input the character!(enter-return);rewind(stdin);scanf(%c,&d);while (d!=n) s=malloc(sizeof(linklist); s-data=d; s-next=p-next; p-next=s; scanf(%c,&d);return head;2. 单链表的基本操作单链表的基本操作(1)建立单链表建立单链表方法二：

9、从表尾到表头逆向建立。方法二：从表尾到表头逆向建立。头插法建立链表虽然算法简单，但生成的头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针上，为此必须增加一个尾指针r，使其始，使其始终指向当前链表的尾结点。终指向当前链表的尾结点。LSaRRSbRScRlinklist *creatlistafter()datatype d;linklist *p,*s,*head;he

10、ad=malloc(sizeof(linklist);head-next=NULL; p=head; printf(please input the character!(enter-return);rewind(stdin);scanf(%c,&d);while (d!=n) s=malloc(sizeof(linklist); s-data=d; p-next=s; p=s; scanf(%c,&d);if(p!=NULL) p-next=NULL;return head;（2）插入运算）插入运算后插操作后插操作pabxss-next=p-nextp-next=sS=mal

11、loc(sizeof(linklist)前插操作前插操作xss-next=pq-next=sS=malloc(sizeof(linklist)qabbp在单链表在单链表L的第的第i个元素之前插入一个元素个元素之前插入一个元素x。实现思想：实现思想：（1）找到第）找到第i-1个元素个元素（2）在）在i-1个元素之后插入个元素之后插入x a1head a3 an a2时间复杂度为时间复杂度为O(n) void insert(linklist *head,int i,datatype x) linklist *p,*s;int j=1; p=head; while(p&jnext; if(p

12、=NULL) printf(第第i个结点不存在个结点不存在); else s=malloc(sizeof(linklist); s-data=x; s-next=p-next; p-next=s; 单链表中插入元素示意图单链表中插入元素示意图ps单链表中插入元素示意图单链表中插入元素示意图ai-1aipxs12 (3)按值查找按值查找 算法思路：从链表的第一个元素结点起，判算法思路：从链表的第一个元素结点起，判断当前结点其值是否等于断当前结点其值是否等于x，若是，返回该结点的，若是，返回该结点的地址，否则继续向后查找，直到链表结束为止。地址，否则继续向后查找，直到链表结束为止。找不到时返回空。

13、找不到时返回空。时间复杂度为时间复杂度为O(n)。linklist *search(head,x)linklist *head;datatype x;linklist *p;p=head-next;while(p!=NULL & p-data!=x) p=p-next; return p;查找运算查找运算La1a2头结点a4 a3PJ0PPPJ1J2J3(4)删除运算删除运算pabcp-next=p-next-next; 删除运算删除运算 方法一方法一:在指定位置进行删除在指定位置进行删除 。void delete1(linklist *head,int i) int j=1; lin

14、klist *q,*p; p=head; while (jnext; j+; if (p=NULL ) printf(位置参数不正确位置参数不正确!n); else q=p-next; /*q指向要删除的结点指向要删除的结点*/ p-next=q-next; /*将将p之后的结点删除之后的结点删除*/ free(q); 删除单链表的第删除单链表的第i个元素个元素实现思想实现思想:找到第找到第i-1个元素个元素删除第删除第i个元素个元素head a1 a2 a3 a4 an 算法演示算法演示 时间复杂性为时间复杂性为O(n) 。 PQQPpqai-1aiai+1 删除运算删除运算 方法二方法二:

15、根据所给条件找到位置再进行删除根据所给条件找到位置再进行删除 。void delete(head,x)linklist *head;datatype x; linklist *p,*s; p=head; while (p-next!=NULL & p-next-data!=x) p=p-next; if(p-next!=NULL) s=p-next; p-next=s-next; printf(%c has been deleted!n,x); else printf(%c isn,t in thelinklist!n,x);3.1.2 循环链表循环链表 1. 循环单链表：对于单链表而

16、言，最后一循环单链表：对于单链表而言，最后一个结点的指针域是空指针，如果将该链表头结个结点的指针域是空指针，如果将该链表头结点地址存于该指针域，则使得链表头尾结点相点地址存于该指针域，则使得链表头尾结点相连，就构成了循环单链表。连，就构成了循环单链表。head空表空表 a1head a2 an非空表非空表 2. 循环双向链表循环双向链表 prior datanexta1a2an结点结点空表空表非空表非空表 循环双向链表：将最后一个结点的空指循环双向链表：将最后一个结点的空指针域（针域（next域）用来保存头结点地址，而用域）用来保存头结点地址，而用头结点的头结点的prior域保存最后一个结点的

17、地址，域保存最后一个结点的地址，用这种结点组成的链表称为循环双向链表。用这种结点组成的链表称为循环双向链表。 3. 静态链表静态链表 对于某些高级语言若没有指针类型，就不能对于某些高级语言若没有指针类型，就不能动态生成结点，此时也可以借助一维数组来描述动态生成结点，此时也可以借助一维数组来描述线性链表。线性链表。#define MAX 链表的最大长度链表的最大长度 typedef struct datatype data; int next;snode; /*结点类型结点类型*/snode slMAX; 该数组的定义如下：该数组的定义如下： 静态链表静态链表 数组数组sl就表示一种链表，该链表

18、的结点中也有就表示一种链表，该链表的结点中也有数据域数据域data和指针域和指针域next，与前面所讲的链表中的，与前面所讲的链表中的指针不同的是，这里的指针是结点的相对地址指针不同的是，这里的指针是结点的相对地址(数数组的下标组的下标)，称之为，称之为静态指针静态指针，这种链表就称之为，这种链表就称之为静态链表静态链表，空指针用，空指针用0表示，而表示，而sl.next0中存放的中存放的是第一个结点的起始地址。是第一个结点的起始地址。静态链表如图所示静态链表如图所示 0123456789dataa4a2a3a1a4next4531207890作业作业 1.简述链表的定义和链表的分类。简述链表

19、的定义和链表的分类。 2.做教材习题中的以下题目。做教材习题中的以下题目。 单项选择题：单项选择题：(1),(2),(3),(8),(9),(10) 填空题：填空题：(1),(2) ,(3),(5),(6),(7),(9),(10) 应用题：应用题：(1) 3.试写一算法求带头结点的单链表试写一算法求带头结点的单链表L的长度。的长度。 4.已知带头结点的动态单链表已知带头结点的动态单链表L中的结点是按整数值递增中的结点是按整数值递增排列的，试写一算法将值为排列的，试写一算法将值为x的结点插人表中，使的结点插人表中，使L仍然有序。仍然有序。 5.试写一算法对带头结点的单链表实现就地逆置。试写一算

20、法对带头结点的单链表实现就地逆置。 3.2 链栈链栈 1.链栈的定义链栈的定义 链栈：用链式存储结构实现的栈。链栈：用链式存储结构实现的栈。(只允只允许在表头进行插入和删除运算的单链表许在表头进行插入和删除运算的单链表) 栈顶指针栈顶指针:单链表的头指针。单链表的头指针。hsanhsa3hsa2hs a1.链栈的类型定义如下：链栈的类型定义如下：typedef struct node datatype data; struct node *next; *linkstack ;linkstack hs; /*hs为链栈栈顶指针为链栈栈顶指针*/ 2. 链栈的运算链栈的运算 进栈进栈进栈的算法进栈

21、的算法:void push(linkstack hs, datatype x) linkstack s; s=malloc(sizeof(linkstack); s-data=x; s-next=hs; hs=s;hsana3a2 a1.sxan+1hs 出栈出栈void pop(linkstack hs, datatype *x)linkstack p; if(hs=NULL) printf(栈空栈空); else *x=hs-data; p=hs; hs=hs-next; free(p); ana3a2 a1.hsdan+1*X=dphs作业作业 1.简述链栈的定义。简述链栈的定义。 2.

22、做教材习题中的以下题目。做教材习题中的以下题目。 单项选择题：单项选择题：(4),(6) 填空题：填空题：(4) 应用题：应用题：(2)3.3 链队列链队列 1.链队列的定义链队列的定义 链队列：链式存储的队列链队列：链式存储的队列 (只允许在表尾进行插只允许在表尾进行插入和在表头进行删除运算的单链表入和在表头进行删除运算的单链表) 。 头指针：头指针：front 尾指针：尾指针：rear a1front a2 an rear a1 a2 an frontreartypedef struct node datatype data; struct node *next;linkqueue; ty

23、pedef struct linkqueue *front,*rear; lqueue;lqueue *hq; /*hq链队列指针变量链队列指针变量*/链队列的类型定义如下：链队列的类型定义如下：2.链队列的运算链队列的运算void insertq(lqueue *hq ,datatype x) linkqueue *p; p=malloc(sizeof(linkqueue); p-data=x;p-next=NULL; if(hq-rear=NULL) hq-front=p;hq-rear=p; else hq-rear-next=p; hq-rear=p; a1 a2 an frontre

24、arx php进队进队 出队出队 void deleteq(lqueue *hq ,datatype *x) linkqueue *p;if(hq-front=NULL) printf (队空队空); else p=hq-front; hq-front=p-next; *x=p-data; free(p); if(hq-front=NULL) hq-rear=hq-front; a1 a2 an frontrearhpp*X= a1作业作业 1.简述链队列的定义。简述链队列的定义。 2.做教材习题中的以下题目。做教材习题中的以下题目。 单项选择题：单项选择题：(5),(7) 填空题：填空题：(

25、8) 应用题：应用题：(3)3.4 字符串的链式存储字符串的链式存储typedef struct node char ch; struct node *next; linkstring ; bhead c t a 由于串结构的特殊性由于串结构的特殊性结构中的每个数据元结构中的每个数据元素是一个字符，所以在用链表存储字符串时，存在素是一个字符，所以在用链表存储字符串时，存在一个结点大小的问题，每个结点可以存放一个字符，一个结点大小的问题，每个结点可以存放一个字符，也可以存放多个字符。也可以存放多个字符。 块链结构块链结构:下图是结点大小为下图是结点大小为4的链表。由于字符串的长的链表。由于字符串

26、的长度不一定是结点大小的整倍数，则链表的最后一个结点不一定度不一定是结点大小的整倍数，则链表的最后一个结点不一定会占满，此时补上会占满，此时补上#或其他非串字符值（通常或其他非串字符值（通常#不属于串不属于串的字符集，是一个特殊的符号）。的字符集，是一个特殊的符号）。ThisisaBox#headtaillen尾指针尾指针tail：指示最后一个结点：指示最后一个结点len：存储串的实际长度：存储串的实际长度 #define MAX 结点块的最大值结点块的最大值typedef struct node char chMAX; struct node *next; cnode;typedef str

27、uct int len; cnode *head,*tail;lstring;块链结构的结点描述如下：块链结构的结点描述如下： 结点存储密度结点存储密度 = 结点存储密度结点存储密度 结点大小选择的是否合理，直接影响存储空结点大小选择的是否合理，直接影响存储空间的利用率。间的利用率。 串所占存储空间串所占存储空间结点实际分配的存储空间结点实际分配的存储空间作业作业 1.1个字符串用链式结构存储有几种方式？个字符串用链式结构存储有几种方式？ 2.做教材习题中的以下题目。做教材习题中的以下题目。 应用题：应用题：(5)3.5 链表应用举例链表应用举例 例例3-1 试写一算法，求带结点的单链表的试写

28、一算法，求带结点的单链表的长度长度 a1head a2 an 单链表的长度是指单链表中结点的个数。求单链表单链表的长度是指单链表中结点的个数。求单链表表长的基本操作是移动指针，将指针从表头移动到表长的基本操作是移动指针，将指针从表头移动到表尾。在指针移动过程中，累计扫描过的结点数即表尾。在指针移动过程中，累计扫描过的结点数即为表长。由此需要设一个指针为表长。由此需要设一个指针p，顺链向后移动；还，顺链向后移动；还要设一个整型变量要设一个整型变量j，作为计数器。指针，作为计数器。指针p的初始值的初始值指向头结点，计数器指向头结点，计数器j的初始值为的初始值为0。La1a2头结点a4 a3PJ0P

29、PPJ1J2J3PJ4int Length_linkList (linklist *l) linklist * p； int j=0; p=l; /* p指向头结点指向头结点*/ while (p-next) p=p-next; j+ /* p所指的是第所指的是第 j 个结点个结点*/ return j;3.5 链表应用举例链表应用举例 例例3-2有一单链表有一单链表l，其头结点指针，其头结点指针head，编写一算法将其倒置。即实现如下图的操作。编写一算法将其倒置。即实现如下图的操作。(a)为倒置前，为倒置前，(b)为倒置后。为倒置后。 a1head a2 an anhead an-1 a1

30、(a)(b) 算法思路：依次取原链表中的每个结点，将其作算法思路：依次取原链表中的每个结点，将其作为第一个结点插入到新链表中去，指针为第一个结点插入到新链表中去，指针p用来指向当用来指向当前结点，前结点，p为空时结束。为空时结束。 void reverse(linklist *head) linklist *p,*q; p=head-next; head-next=NULL; while(p) q=p; p=p-next; q-next=head-next; head-next=q; 例例3-3 已知单链表已知单链表h，写一算法，删除其，写一算法，删除其中所有重复的结点。中所有重复的结点。 算

31、法思路：用指针算法思路：用指针p指向第一个数据结点，指向第一个数据结点，从它的后继结点开始到表的结束，找与其值从它的后继结点开始到表的结束，找与其值相同的结点并删除之；相同的结点并删除之；p指向下一个；依此类指向下一个；依此类推，推，p指向最后结点时算法结束。指向最后结点时算法结束。参考算法如下：参考算法如下：void del(linklist *h) linklist *p,*q,*r; p=h-next; while(p) q=p; while (q-next) if(q-next-data=p-data) r=q-next; q-next=r-next; free(r); else q=

32、q-next; p=p-next; 例例3-4 创建一个以正序排列的链表，链创建一个以正序排列的链表，链表节点为一个整形数据，插入一个元素，删表节点为一个整形数据，插入一个元素，删除一个元素，均保持链表的正序。在执行完除一个元素，均保持链表的正序。在执行完每个操作后将其输出。每个操作后将其输出。 /*创建链表函数*/linklist *creatlist()datatype d;linklist *p,*s,*head;head=malloc(sizeof(linklist);head-next=NULL;printf(please input the integer!(0-return);s

33、canf(%d,&d);while (d!=0) s=malloc(sizeof(linklist); s-data=d; p=head; while(p-next!=NULL) if (p-next-datanext; else break; s-next=p-next; p-next=s;scanf(%d,&d);return head; 插入一个元素，标志链表的正序性。插入一个元素，标志链表的正序性。void insert(head,x)linklist *head;datatype x;linklist *p,*s;s=malloc(sizeof(linklist);s-data=x;p=head;while (p-next!=NULL) if (p-next-datanext; else break;s-next=p-next;p-next=s;printf(%d has been inser