2.2 链表 数据结构ppt课件

1、第第2章章 线性表线性表2.1 线性表的逻辑结构线性表的逻辑结构 2.2 线性表的顺序表示和实现线性表的顺序表示和实现2.3 线性表的链式表示和实现线性表的链式表示和实现2.4 1;.上堂课要点回顾上堂课要点回顾线性结构线性结构( (包括表、栈、队、数组）的定义和特点包括表、栈、队、数组）的定义和特点 仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。仅一个首、尾结点，其余元素仅一个直接前驱和一个直接后继。2. 2. 线性表线性表逻辑结构：逻辑结构：“一对一一对一” 或或 1:11:1存储结构：顺序、链式存储结构：顺序、链式运运 算算 ：修改、插入、删除：修改、插入、删除3.3.顺序存储

2、顺序存储特征：逻辑上相邻，物理上也相邻；特征：逻辑上相邻，物理上也相邻；优点：随机查找快优点：随机查找快 O(1)O(1)缺点：插入、删除慢缺点：插入、删除慢 O(n)O(n)2;.链式存储结构链式存储结构总结总结线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷优点：可以随机存取表中任一元素，方便快捷缺点：在插入或删除某一元素时，需要移动大量元素。缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：解决问题的思路：改用另一种

3、线性存储方式：3;.2.3 线性表的链式表示和实现线性表的链式表示和实现2.3.1 链表的表示链表的表示2.3.2 链表的实现链表的实现2.3.3 链表的运算效率分析链表的运算效率分析4;.复习复习C语言语言指针指针: :即地址。即地址。指针变量指针变量: :是专门用来存放另一个变量的地址的是专门用来存放另一个变量的地址的变量变量，即专门存放地址的，即专门存放地址的，指针变指针变量量的值是指针的值是指针Int *p,*q; / /* *p,q是变量名，都是指向整型变量的指针变量，是变量名，都是指向整型变量的指针变量，*表示该变量为指针表示该变量为指针变量变量，（，（*p)是指指针变量是指指针变

4、量P P所指向的变量所指向的变量* */ /数组指针数组指针: :是指数组的起始地址，数组元素的指针是数组元素的地址。是指数组的起始地址，数组元素的指针是数组元素的地址。 Int *p, a10; 若若p=a , ,则则p+1=a+1 指针数组指针数组: :是指数组元素均为指针类型的数组是指数组元素均为指针类型的数组5;.链式存储结构特点：链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。定相邻。如何实现？如何实现？通过指针来实现！通过指针来实现！让每个存储结点都包含两部分：数据域和指针

5、域让每个存储结点都包含两部分：数据域和指针域指针指针指针指针指针指针或或样样 式式数据域：存储元素数数据域：存储元素数值数据值数据指针域：存储直接后继或者直接前指针域：存储直接后继或者直接前驱的存储位置驱的存储位置2.3.1 链表的表示链表的表示6;.例：请画出例：请画出26 个英文字母表的链式存储结构。个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：该字母表在内存中链式存放的样式举例如下： 解：该字母表的逻辑结构为：（解：该字母表的逻辑结构为：（ a, b, a, b, ,y, z ,y, z）链表存放示意图如下：链表存放示意图如下： a1heada2/an讨论讨论1:1

6、:每个存储结点都包含两部分：数据和每个存储结点都包含两部分：数据和 。讨论讨论2:2:在单链表中，除了首元结点外，任一结点的存储位置由在单链表中，除了首元结点外，任一结点的存储位置由 指示。指示。 其直接前驱结点的链域的值其直接前驱结点的链域的值指针域指针域( (链域链域) )7;.1 1）结点：）结点：数据元素的存储映像。由数据域和指针域两部分组成；数据元素的存储映像。由数据域和指针域两部分组成；2 2）链表：）链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。表的链式存储结构。3 3）单

7、链表、双链表、多链表、循环链表：）单链表、双链表、多链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表结点只有一个指针域的链表，称为单链表或线性链表有两个指针域的链表，称为双链表（但未必是双向链表）；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。首尾相接的链表称为循环链表。a1heada2an循环链表示意图：循环链表示意图：(2) (2) 与链式存储有关的术语：与链式存储有关的术语：8;.4 4）头指针、头结点和首元结点的区别）头指针、头结点和首元结点的区别头指针头指针头结点头结点首

8、元结点首元结点a1heada2infoan头指针头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；一般用头是指向链表中第一个结点（或为头结点、或为首元结点）的指针；一般用头指针唯一标识一个单链表指针唯一标识一个单链表. .头结点头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度信息，它不计入表长度首元结点首元结点是指链表中存储线性表第一个数据元素是指链表中存储线性表第一个数据元素a a1 1的结点的结点 示意图如下：示意图如下：9;.答答:讨论1. 在链表中设置头结点有什么

9、好处？在链表中设置头结点有什么好处？讨论2. 如何表示空表？如何表示空表？头结点头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放也可存放表长度表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。表的情况以及对首元结点进行统一处理，编程更方便。答答:无头结点时，当头指针的值为空时表示空表；无头结点时，当头指针的值为空时表示空表；头指针头指针无头结点无头结点头指针头指针头结点头结点有头结点有头

10、结点有头结点时，当头结点的指针域为空时表示空表。有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表头结点不计入链表长度！长度！10;.一个线性表的逻辑结构为：（一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANGZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），），其存储结构用单链表表示如下，其存储结构用单链表表示如下，请问其头指针的值是多少？请问其头指针的值是多少？存储地址存储地址数据域数据域指针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU

11、25答：答：头指针是指向链表中第一个头指针是指向链表中第一个结点的指针，因此关键是要寻找结点的指针，因此关键是要寻找第一个结点的地址。第一个结点的地址。7ZHAOH31称：头指针称：头指针H的值是的值是31（3 3）举例）举例例例1 1：11;.上例链表的逻辑结构示意图有以下两种形式：上例链表的逻辑结构示意图有以下两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别：区别： 无头结点无头结点 有头结点有头结点头结点不计入链表长头结点不计入链表长度！度！12;. 其中指针其中指针X X，Y Y，Z Z的值分别为多少

12、？该线性表的首结点起始地址为多少？末结点的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？的起始地址为多少？答：答：X=X= Y= Y= Z= Z= , , 首址首址= = 末址末址= = 。例例2 2：线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个：线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表元素的线性表L=23L=23，1717，4747，0505，3131，若它以链接方式存储在下列，若它以链接方式存储在下列100100119119号地址空间中，每个结点由数据（占号地址空间中，每个结点由数据（占2 2个字节）和指针（占个字

13、节）和指针（占2 2个字节）组成，个字节）组成，如下图所示。如下图所示。13;.讨论: 链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所以要采用因每个结点至少有两个分量，且数据类型通常不一致，所以要采用数据类数据类型。型。答答:以以2626个字母的链表为例，每个结点都有两个分量：个字母的链表为例，每个结点都有两个分量：字符型字符型指针型指针型pb14;.实现实现typedef struct node datatype data; struct node *next;*l

14、inklist, node;node *head,*p;datanextp结点（结点（*p）(*p)表示表示p p所指向的结点所指向的结点(*p).datap-data表示表示p p指向结点的数据域指向结点的数据域(*p).nextp-next表示表示p p指向结点的指针域指向结点的指针域生成一个生成一个lnodelnode型型新结点：新结点：p=(node p=(node * *)malloc(sizeof(node);)malloc(sizeof(node);系统回收系统回收p p结点：结点：free(p)free(p)15;. 对于指向结构类型的指针变量，可被说明为：对于指向结构类型的指

15、针变量，可被说明为： node *p, *q; /或用或用 struct bird *p , *q; /注：上面已经定义了注：上面已经定义了nodenode为用户自定义的为用户自定义的birdbird类型。类型。补充结构数据类型的补充结构数据类型的C C表示法表示法 类型定义和变量说明可以合写为：类型定义和变量说明可以合写为：typedef struct bird /bird/bird是自定义结构类型名称是自定义结构类型名称 char data; /定义数据域的变量名及其类型定义数据域的变量名及其类型struct bird *next; /定义指针域的变量名及其类型定义指针域的变量名及其类型n

16、ode，*pointer; /node/node是是birdbird结构类型的类型替代结构类型的类型替代, , * *pointerpointer是指针型的是指针型的birdbird结构类型的替代，也是数据类型结构类型的替代，也是数据类型* */ /16;.Typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 教材教材P28P28对于线性表的单链表存储结构对于线性表的单链表存储结构描述描述: :教材问题讨论：教材问题讨论：Q1Q1：第一行的：第一行的Lnode Lnode 与最后一行的与最后一行的Ln

17、odeLnode是不是一回事？是不是一回事？A1A1：不是。前者：不是。前者LnodeLnode是结构名，后者是结构名，后者LnodeLnode是对整个是对整个structstruct类型的一种类型的一种“缩写缩写”，是一种是一种“新定义名新定义名”，它只是对现有类型名的补充，而不是取代。，它只是对现有类型名的补充，而不是取代。请注意：请注意：TypedefTypedef不可能创造任何新的不可能创造任何新的数据类型，而仅仅是在原有的数据类型数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程中命名一个新名字，其目的是使你的程序更易阅读和移植。序更易阅读和移植。17;.Typed

18、ef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; Q2Q2： 那为何两处要同名那为何两处要同名( (Lnode和和Lnode）？太不严谨）？太不严谨 了吧？了吧？A2A2：同名是为了表述起来方便。例如，若结构名为：同名是为了表述起来方便。例如，若结构名为studentstudent，其新定义名缩写也，其新定义名缩写也最好写成最好写成studentstudent，因为描述的对象相同，方便阅读和理解。，因为描述的对象相同，方便阅读和理解。Q3Q3：结构体中间的那个：结构体中间的那个struct Lnodestr

19、uct Lnode是何意？是何意？A3A3：在：在“缩写缩写” LnodeLnode还没出现之前，只能用原始的还没出现之前，只能用原始的struct Lnodestruct Lnode来进行变来进行变量说明。此处说明了指针分量的数据类型是量说明。此处说明了指针分量的数据类型是struct Lnodestruct Lnode。Typedef struct student char name; int age; student,*pointer; 18;.设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针, ,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针

20、域写为 。练习：练习：p-dataai的值的值p-nextai+1的地址的地址附附1 1：介绍：介绍C C的三个有用的库函数的三个有用的库函数/ /算符（都在算符（都在 中）中）sizeof(x)计算变量计算变量x x的长度（字节数）；的长度（字节数）；malloc(m) 开辟开辟m m字节长度的地址空间，并返回这段空间的首地址；字节长度的地址空间，并返回这段空间的首地址；free(p ) 释放指针释放指针p p所指变量的存储空间，即彻底删除一个变量。所指变量的存储空间，即彻底删除一个变量。19;.sizeof(x)计算计算x x的长度的长度malloc(m) 开开m m字节空间字节空间fre

21、e(p) 删除一个变量删除一个变量问问1 1：自定义结构类型变量：自定义结构类型变量nodenode的长度的长度m m是多少？是多少？问问2 2：结构变量：结构变量nodenode的首地址的首地址( (指针指针p p）是多少？）是多少？问问3 3：怎样删除结构变量：怎样删除结构变量nodenode？*nextdatanode，长度为，长度为m字节字节pmsizeof(nodenode) /单位是字节单位是字节p(node(node* *) )malloc(m)free(p) /只能借助只能借助nodenode的指针删除！的指针删除！P-data=P-data=a a; p-next=q; p-

22、next=q20;.单链表的抽象数据类型描述如下单链表的抽象数据类型描述如下（参见教材（参见教材P28P28）：）：Typedef struct Lnode ElemType data; /数据域数据域 struct Lnode *next; /指针域指针域Lnode, *LinkList; / *LinkList为为Lnode类型的指针类型的指针 至此应可看懂教材至此应可看懂教材P22P22关于顺序表动态分配的存储结构。关于顺序表动态分配的存储结构。其特点是：用结构类型和指针来表示顺序结构，更灵活。其特点是：用结构类型和指针来表示顺序结构，更灵活。如何具体编程来建立和访问如何具体编程来建立和

23、访问链表？链表？链表的实现链表的实现21;.2.3.2 链表的实现链表的实现（1 1） 单链表的建立和输出单链表的建立和输出（2 2） 单链表的修改单链表的修改（3 3） 单链表的插入单链表的插入（4 4） 单链表的删除单链表的删除22;.（1） 单链表的建立和输出单链表的建立和输出例：用单链表结构来存放例：用单链表结构来存放26个英文字母组成的线性表（个英文字母组成的线性表（a，b，c，z）,请写出请写出C语言程序。语言程序。实现思路：实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。

24、后继结点的地址要提前送给前面的指针。先挖先挖“坑坑”, ,后种后种“萝卜萝卜”！23;.typedef struct node char data; struct node *next;node; node *p,*q,*head; /一般需要一般需要3 3个指针变量个指针变量int n ; / / 数据元素的个数数据元素的个数int m=sizeof(node); / /* *结构类型定义好之后，每个变量的长度就固定了，结构类型定义好之后，每个变量的长度就固定了，m m求一次求一次即可即可* */ /将全局变量及函数提前说明：将全局变量及函数提前说明：24;.新手特别容易忘记！新手特别容易忘

25、记！ int i;head=(node*)malloc(m); /m=sizeof(node) 前面已求出前面已求出p=head; for( i=1; idata=i+a-1; / 第一个结点值为字符第一个结点值为字符a p-next=(node*)malloc(m); /为后继结点为后继结点“挖坑挖坑”！ p=p-next； /让指针变量让指针变量P指向后一个结点指向后一个结点p-data=i+a-1; /最后一个元素要单独处理最后一个元素要单独处理p-next=NULL ; / /单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！void build( ) /字母链表的生成。字母链表

26、的生成。要一个个慢慢链入要一个个慢慢链入25;.p=head;while (p) /当指针不空时循环，仅限于无头结点的情况当指针不空时循环，仅限于无头结点的情况 printf(%c,p-data); p=p-next; /让指针不断让指针不断“顺藤摸瓜顺藤摸瓜” 讨论：要统计链表中数据元素的个数，该如何讨论：要统计链表中数据元素的个数，该如何 改写？改写？ sum+;sum+;sum=0;sum=0;void display() /*字母链表的输出字母链表的输出*/26;.（2） 单链表的修改单链表的修改(或读取）或读取）思路：思路：要修改第要修改第i个数据元素，必须从头指针起一直找到该结点的

27、指针个数据元素，必须从头指针起一直找到该结点的指针p，然后才，然后才能执行能执行p-data=new_value 。修改第修改第i i个数据元素的操作函数可写为：个数据元素的操作函数可写为：Status GetElem_L(LinkList L, int i, ElemType &e)p=L-next; j=1; /带头结点的链表带头结点的链表while(p&jnext; +j; /顺指针向后查找，直到顺指针向后查找，直到p指向第指向第i个元素或个元素或p唯空唯空if( !p | ji ) return ERROR; p-data =e; /若是读取则为：若是读取则为：e=p-

28、data; return OK;/ GetElem_L缺点：缺点：想寻找单链表中第想寻找单链表中第i i个元素，只能从头指针开始逐一查询（顺藤摸瓜），个元素，只能从头指针开始逐一查询（顺藤摸瓜），无法随机存取无法随机存取 。27;.在链表中插入一个元素在链表中插入一个元素X X 的示意图如下：的示意图如下：X Xsabp链表插入的核心语句：链表插入的核心语句：p-nexts-nextX X 结点的生成方式：结点的生成方式：s=(nodes=(node* *)malloc(m);)malloc(m);s-data=s-data=X X ; ;s-next= ?s-next= ?bapX X （3

29、） 单链表的插入单链表的插入28;. Status ListInsert_L(LinkList L, int i, ElemType e) / L 为带头结点的单链表的头指针，本算法为带头结点的单链表的头指针，本算法 / 在链表中第在链表中第i 个结点之前插入新的元素个结点之前插入新的元素 e / LinstInsert_L算法的时间复杂度算法的时间复杂度为为:O(ListLength(L)p = L; j = 0;while (p & j next; +j; / 寻找第寻找第 i-1 个结点个结点if (!p | j i-1) return ERROR; / i 大于表长或者小于大于

30、表长或者小于1 s = new LNode; / 生成新结点生成新结点s-data = e; s-next = p-next; p-next = s; / 插入插入return OK;29;.在链表中删除某元素在链表中删除某元素b b的示意图如下：的示意图如下：c a bp删除动作的核心语句（要借助辅助指针变量删除动作的核心语句（要借助辅助指针变量q q）：）：q = p-next; /首先保存首先保存b b的指针，靠它才能找到的指针，靠它才能找到c c；p-next=q-next; /将将a a、c c两结点相连，淘汰两结点相连，淘汰b b结点；结点；free(q) ； /彻底释放彻底释放b

31、 b结点空间结点空间p-next思考：思考： 省略省略free(q)语句语句行不行？行不行？(p-next) - nextq（4） 单链表的删除单链表的删除30;. Status ListDelete_L(LinkList L, int i, ElemType &e) / / 删除以删除以 L L 为头指针为头指针( (带头结点带头结点) )的单链表中第的单链表中第 i i 个结点个结点 / ListDelete_L算法的时间复杂度算法的时间复杂度为:O(ListLength(L)p = L; j = 0;while (p-next & j next; +j; / / 寻找第寻

32、找第 i i 个结点，并令个结点，并令 p p 指向其前趋指向其前趋if (!(p-next) | j i-1) return ERROR; / / 删除位置不合理删除位置不合理q = p-next; p-next = q-next; / / 删除并释放结点删除并释放结点e = q-data; free(q);return OK;31;.2.3.3 链表的运算效率分析链表的运算效率分析（1） 查找查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为度为 O(n)。时间效率分析时间效率分析（2） 插入和删除插入

33、和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是所耗时间复杂度将是 O(n)。32;.空间效率分析空间效率分析链表中每个结点都要增加一个指针空间，相当于总共增加了链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，个整型变量，空间复杂度为空间复杂度为 O(n)。在在n n个结点的单链表中要删除已知结点个结点的单链表中要删除已知结点* *

34、P P，需找到它的，需找到它的 ，其，其时间复杂度为时间复杂度为 。 O(n)O(n)练习：练习：33;.如何从线性表得到单链表？如何从线性表得到单链表？链表是一个动态的结构，它不需要预分配空间，因此生成链表的过程是一个结链表是一个动态的结构，它不需要预分配空间，因此生成链表的过程是一个结点点“逐个插入逐个插入”的过程。的过程。34;.例如：逆位序输入例如：逆位序输入 n n 个数据元素的值，个数据元素的值， 建立带头结点的单链表。建立带头结点的单链表。操作步骤：操作步骤：一、建立一个一、建立一个“空表空表”；二、输入数据元素二、输入数据元素an， 建立结点并插入；建立结点并插入；三、输入数据

35、元素三、输入数据元素an-1， 建立结点并插入；建立结点并插入；ananan-1四、依次类推，直至输入四、依次类推，直至输入a1为止。为止。35;.Void CreateList_L(LinkList &L,int n)/逆位序输入逆位序输入n个元素的值，建立带头结点的单链线性表个元素的值，建立带头结点的单链线性表L L=(LinkList) malloc (sizeof(Lnode); L-next=NULL; /先建立一个带头结点的单链表先建立一个带头结点的单链表 for(i=n; i0; -i) p= (LinkList) malloc (sizeof(Lnode); /生成新结

36、点生成新结点 scanf(&p-data); /输入元素值输入元素值 p-next= L-next; L-next=p; / CreateList_L从表尾到表头逆向建立单链表算法描述从表尾到表头逆向建立单链表算法描述36;.操作操作 ClearList(&L) 在链表中的实现在链表中的实现:void ClearList(&L) / 将单链表重新置为一个空表将单链表重新置为一个空表 while (L-next) p=L-next; L-next=p-next; / ClearListfree(p);算法时间复杂度：O(ListLength(L)37;.2.4 应用举例应

37、用举例算法要求：算法要求：已知已知: :线性表线性表 A A和和B B，分别由单链表，分别由单链表 LaLa和和Lb Lb 存储，其中数据元素按值非递减有序排存储，其中数据元素按值非递减有序排列（即已经有序）；列（即已经有序）；要求：要求：将将A A和和B B归并为一个新的线性表归并为一个新的线性表C, CC, C的数据元素仍按值非递减排列。设线性表的数据元素仍按值非递减排列。设线性表C C由单链表由单链表LcLc存储。存储。假设：假设：A=A=（3 3，5 5，8 8，1111），），B=B=（2 2，6 6，8 8，9 9，1111）预测：预测：合并后的合并后的C =C =（2, 3, 5

38、, 6, 8, 8, 9, 112, 3, 5, 6, 8, 8, 9, 11，1111）例例1 1：两个链表的归并（：两个链表的归并（教材教材P31P31例例）重点是链表重点是链表38;.链表示意图：链表示意图： 3 3 5 51111 / 8 8 LaLa 2 2 6 61111 / 8 8 LbLb 9 9 2 2 3 3 6 6 5 5 LcLc 8 8 811 / 911头结点头结点39;.算法设计：算法设计：算法主要包括搜索、比较、插入三个操作：算法主要包括搜索、比较、插入三个操作：搜索：需要设立三个指针来指向搜索：需要设立三个指针来指向La La 、LbLb和和LcLc链表；链表

39、；比较：比较比较：比较LaLa和和LbLb表中结点数据的大小；表中结点数据的大小；插入：将插入：将LaLa和和LbLb表中数据较小的结点插入新链表表中数据较小的结点插入新链表Lc Lc 。请注意链表的特点，仅改变指针便可实现数据的移动请注意链表的特点，仅改变指针便可实现数据的移动, ,即即“数据不动，指针动数据不动，指针动”40;.La3 5 8 11 Lb2 6 8 119 PaPbPaPbPaPa、PbPb用于搜索用于搜索LaLa和和LbLb， PcPc指向新链表当前结点。指向新链表当前结点。归并过程示意如下：归并过程示意如下：Lc=LaPbPaPaPb41;.算法实现：算法实现： Voi

40、d MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc) /已知单链线性表已知单链线性表LaLa和和LbLb的元素按值非递减排列。归并为的元素按值非递减排列。归并为LcLc后也按值非递减排列。后也按值非递减排列。 free(Lb); /释放释放LbLb的头结点的头结点 /MergeList_L pc-next = pa pa: pb ; /插入非空表的剩余段插入非空表的剩余段 while(pa&pb) /将将pa pa 、pbpb结点按大小依次插入结点按大小依次插入LcLc中中 if(pa-datadata) p

41、c-next=pa; pc=pa; pa=pa-next; else pc-next=pb; pc=pb; pb=pb-next pa=LaLa-next; pb=LbLb-next; Lc=pc=La； /有头结点有头结点见见P31P31算法算法2.122.12? ?是条件运算符（为真则取第是条件运算符（为真则取第1 1项，见项，见P10P10条件赋值）条件赋值）注：注：LcLc用的是用的是LaLa的头指针的头指针42;.思思 考：考：1 1、不用、不用LcLc，直接把，直接把LaLa表插到表插到LbLb表中；或者把表中；或者把LbLb表插到表插到LaLa表中，怎么表中，怎么修改？修改？2

42、2、重复的数据元素不需要插入，怎么修改？、重复的数据元素不需要插入，怎么修改？43;.循环链表循环链表(circular linked list)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致操作与单链表基本一致, ,循环条件不同循环条件不同单链表单链表p或或p-next=NULL循环链表循环链表p或或p-next=headhh空表空表44;.双向链表（双向链表（double linked

43、list）单链表具有单向性的缺点单链表具有单向性的缺点结点定义结点定义typedef struct node datatype element; struct node *prior,*next;dnode;priorelementnextL空双向循环链表：空双向循环链表：非空双向循环链表：非空双向循环链表：LABbcapp-prior-next= p= p-next-prior;NextElem的执行时间为的执行时间为O(1)PriorElem的执行时间为的执行时间为O(n)45;.bcaPvoid del_dulist(dnode *p)p-prior-next=p-next; p-nex

44、t-prior=p-prior; free(p);删除删除算法描述算法描述算法评价：算法评价：T(n)=O(1)p-prior-next=p-next;p-next-prior=p-prior;46;.void ins_dulist(dnode* p,int x)dnode *s; s=(dnode*)malloc(sizeof(dnode); s-element=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s;算法描述算法描述算法评价：算法评价：T(n)=O(1)xSbaP插入插入47;.用上述定义的单链表实现线性表的操作时，用

45、上述定义的单链表实现线性表的操作时，存在的问题：存在的问题： 改进链表的设置：改进链表的设置：1单链表的表长是一个隐含的值；单链表的表长是一个隐含的值； 1增加增加“表长表长”、“表尾指针表尾指针” 和和 “当前位置的当前位置的 指针指针” 三个数据域；三个数据域；2在单链表的最后一个元素之后插入元素时，在单链表的最后一个元素之后插入元素时， 需遍历整个链表；需遍历整个链表；3在链表中，元素的在链表中，元素的“位序位序”概念淡化，结点的概念淡化，结点的 “位置位置”概念加强。概念加强。2将基本操作中的将基本操作中的“位序位序 i ”改变为改变为“指针指针 p ”。48;.四、一个带头结点的线性

46、链表类型四、一个带头结点的线性链表类型typedef struct LNode / 结点类型结点类型 ElemType data; struct LNode *next; *Link, *Position;Status MakeNode( Link &p, ElemType e ); / 分配由分配由 p 指向的值为指向的值为e的结点，并返回的结点，并返回OK； / 若分配失败，则返回若分配失败，则返回 ERRORvoid FreeNode( Link &p ); / 释放释放 p 所指结点所指结点49;.typedef struct / 链表类型链表类型 Link head,

47、 tail; / 分别指向头结点和分别指向头结点和 / 最后一个结点的指针最后一个结点的指针 int len; / 指示链表长度指示链表长度 Link current; / 指向当前被访问的结点指向当前被访问的结点 /的指针，初始位置指向头结点的指针，初始位置指向头结点 LinkList;50;.链表的基本操作链表的基本操作: : 结构初始化和销毁结构结构初始化和销毁结构 Status InitList( LinkList &L ); / 构造一个空的线性链表构造一个空的线性链表 L，其头指针、，其头指针、 / 尾指针和当前指针均指向头结点，尾指针和当前指针均指向头结点， / 表长为零

48、。表长为零。Status DestroyList( LinkList &L ); / 销毁线性链表销毁线性链表 L，L不再存在。不再存在。 O(1) O(n)51;. 引用型操作引用型操作 Status ListEmpty ( LinkList L ); /判表空判表空int ListLength( LinkList L ); / 求表长求表长Status Prior( LinkList L ); / 改变当前指针指向其前驱改变当前指针指向其前驱Status Next ( LinkList L ); / 改变当前指针指向其后继改变当前指针指向其后继ElemType GetCurElem

49、 ( LinkList L ); / 返回当前指针所指数据元素返回当前指针所指数据元素O(1)O(1)O(n)O(1)O(1)52;. Status LocatePos( LinkList L, int i ); / 改变当前指针指向第改变当前指针指向第i个结点个结点Status LocateElem (LinkList L, ElemType e, Status (*compare)(ElemType, ElemType); / 若存在与若存在与e 满足函数满足函数compare( )判定关系的元判定关系的元 / 素，则移动当前指针指向第素，则移动当前指针指向第1个满足条件的个满足条件的 /

50、 元素的前驱，并返回元素的前驱，并返回OK; 否则返回否则返回ERRORStatus ListTraverse(LinkList L, Status(*visit)() ); / 依次对依次对L的每个元素调用函数的每个元素调用函数visit()O(n)O(n)O(n)53;. 加工型操作加工型操作Status ClearList ( LinkList &L ); / 重置重置 L 为空表为空表Status SetCurElem(LinkList &L, ElemType e ); / 更新当前指针所指数据元素更新当前指针所指数据元素Status Append ( LinkLis

51、t &L, Link s ); / 在表尾结点之后链接一串结点在表尾结点之后链接一串结点Status InsAfter ( LinkList &L, Elemtype e ); / 将元素将元素 e 插入在当前指针之后插入在当前指针之后Status DelAfter ( LinkList &L, ElemType& e ); / 删除当前指针之后的结点删除当前指针之后的结点 O(1)O(n) O(s) O(1) O(1)54;.Status InsAfter( LinkList& L, ElemType e ) / 若当前指针在链表中，则将数据元素若当前

52、指针在链表中，则将数据元素e插入在线性链插入在线性链 / 表表L中当前指针所指结点之后中当前指针所指结点之后,并返回并返回OK; / 否则返回否则返回ERROR。 / InsAfter if ( ! L.current ) return ERROR; if (! MakeNode( s, e) ) return ERROR; s-next = L.current-next; L.current-next = s; if (L.tail = L.current) L.tail = s; L.current = s; +L.len; return OK;55;.Status DelAfter( L

53、inkList& L, ElemType& e ) / / 若当前指针及其后继在链表中，则删除线性链表若当前指针及其后继在链表中，则删除线性链表L L中当前中当前 / / 指针所指结点之后的结点，并返回指针所指结点之后的结点，并返回OK; OK; 否则返回否则返回ERRORERROR。 /DelAfterif ( !(L.current & L.current-next ) ) return ERROR;q = L.current-next;L.current-next = q-next;if (L.tail = q) L.tail = L.current;e=q-da

54、ta; FreeNode(q); L.len=len-1;return OK;56;. 例一例一Status ListInsert_L(LinkList L, int i, ElemType e) / 在带头结点的单链线性表在带头结点的单链线性表 L 的第的第 i 个元素之前插入元素个元素之前插入元素 e / ListInsert_L 利用上述定义的线性链表如何完成利用上述定义的线性链表如何完成 线性表的其它操作线性表的其它操作 ？if (!LocatePos (L, i-1, h) return ERROR; / i 值不合法，第值不合法，第 i-1 个结点不存在个结点不存在if (!Mak

55、eNode (s, e) return ERRORInsAfter (h, s); return OK; / 完成插入完成插入57;.Status MergeList_L(LinkList &Lc, LinkList &La,LinkList &Lb ，int (*compare)(ElemType,ElemType) / 归并有序表归并有序表 La 和和 Lb , ,生成新的有序表生成新的有序表 Lc, , / 并在归并之后销毁并在归并之后销毁La 和和 Lb, , / compare 为指定的元素大小判定函数为指定的元素大小判定函数 / MergeList_L例二例

56、二58;.if ( !InitList(Lc) return ERROR; / 存储空间分配失败存储空间分配失败while (!( a=MAXC & b=MAXC) / La 或或 Lb 非空非空 LocatePos (La, 0); LocatePos (Lb, 0); / 当前指针指向头结点当前指针指向头结点if ( DelAfter( La, e) a = e; / 取得取得 La 表中第一个元素表中第一个元素 aelse a = MAXC; / MAXC为常量最大值为常量最大值if ( DelFirst( Lb, e) b = e; / 取得取得 Lb 表中第一个元素表中第一个

57、元素 belse b = MAXC; / a 和和 b 为两表中当前比较元素为两表中当前比较元素DestroyList(La); DestroyList(Lb); / 销毁链表销毁链表 La 和和 Lbreturn OK;59;. if (*compare)(a, b) exponPa-expon =、Pb-exponPb-expon等情况，等情况，再决定是将两系数域的数值相加再决定是将两系数域的数值相加（并判其和是否为（并判其和是否为0 0），还是将较高指数项的结点插入到新表），还是将较高指数项的结点插入到新表c c中。中。3 142 81 0 aPaPa8 14-3 1010 6 bPbPb11 14-3 102 81 0 cPcPc10 6+64;.运算效率分析：运算效率分析：(1)系数相加系数相加0 加法次数加法次数 min(m, n)其中其中 m m和和n n分别表示表分别表示表A A和表和表B B的结点数。的结点数。(2)指数比较指数比较极端情况是极端情况是表表A A和表和表B B 没