第2章(3)_线性链表

1、 河南科技大学计算机系第2章 数据结构-线性链表软件技术基础第第2 2页页本单元要点n线性链表及其运算线性链表及其运算n链栈链栈n链队列链队列n循环链表循环链表第第3 3页页（一）线性表的链式存储结构线性表的顺序存储结构容易实现，可以随机存取线性表的顺序存储结构容易实现，可以随机存取表中的任意元素。表中的任意元素。链表存储结构在这两个方面恰好是优点：n容易插入、删除操作n不需要预分空间。顺序表缺点是：n难于插入、删除操作；n需要预先分配空间，不管这些空间能否最大限度地利用。第第4 4页页链式存储结构特点链式存储结构特点其结点在存储器中的位置是其结点在存储器中的位置是随意随意的，的，即逻辑上相邻

2、的数逻辑上相邻的数据元素在物理上不一定相邻。据元素在物理上不一定相邻。如何实现？通过来实现！让每个存储结点都包含两部分：让每个存储结点都包含两部分：数据域数据域和和指针域指针域指针指针指针指针指针指针或或样式：样式：数据域：数据域：存储存储元素数值数据元素数值数据指针域：指针域：存储直接后继或存储直接后继或者直接前驱的存储位置者直接前驱的存储位置设计思想：牺牲空间效率换取时间效率设计思想：牺牲空间效率换取时间效率1. 链表的表示链表的表示第第5 5页页例：请画出例：请画出26 个英文字母表的链式存储结构。个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：该字母表在内存中链式存

3、放的样式举例如下： 解：该字母表的逻辑结构为：解：该字母表的逻辑结构为：（ a, b, a, b, ,y, z ,y, z）链表存放示意图如下：链表存放示意图如下： a1heada2/an讨论讨论1 ：每个存储结点都包含两部分：数据域和：每个存储结点都包含两部分：数据域和 。讨论讨论2：在单链表中，除了首元结点外，任一结点的存储位置在单链表中，除了首元结点外，任一结点的存储位置 由由 指示。指示。 其直接前驱结点的链域的值其直接前驱结点的链域的值指针域指针域(链域链域)第第6 6页页1）结点：）结点：数据元素的存储映像。由数据域和指针域两部分组数据元素的存储映像。由数据域和指针域两部分组成；成

4、；2）链表：）链表： n n 个结点由个结点由指针链指针链组成一个链表。它是线性表的组成一个链表。它是线性表的链式存储映像链式存储映像，称为线性表的链式存储结构称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表）单链表、双链表、多链表、循环链表： 结点只有一个指针域的链表，称为结点只有一个指针域的链表，称为单链表单链表或或线性链表线性链表；有两个指针域的链表，称为有两个指针域的链表，称为双链表（但未必是双向链双链表（但未必是双向链表）表）；有多个指针域的链表，称为有多个指针域的链表，称为多链表多链表；首尾相接的链表称为首尾相接的链表称为循环链表循环链表。(2) 与链式存储有关的术语

5、与链式存储有关的术语第第7 7页页4）头指针、头结点和首元结点的区别头指针头指针头结点头结点首元结点首元结点a1heada2infoan头指针头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指是指向链表中第一个结点（或为头结点、或为首元结点）的指针；针；头结点头结点是在链表的首元结点之前是在链表的首元结点之前附设附设的一个结点；数据域内只放空表的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。标志和表长等信息，它不计入表长度。首元结点首元结点是指链表中存储线性表第一个数据元素是指链表中存储线性表第一个数据元素a a1 1的结点。的结点。 示意图如下：示意图如下：第第8 8

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

7、，当头有头结点时，当头结点结点的的指针域为空指针域为空时表示空表。时表示空表。第第9 9页页上例链表的逻辑结构示意图有以下上例链表的逻辑结构示意图有以下两种形式两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别：区别： 无头结点无头结点 有头结点有头结点第第10 10页页讨论: 链表的数据元素有链表的数据元素有两个域两个域，不再是简单数据，不再是简单数据类型，类型，编程编程时该如何表示？时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所因每个结点至少有两个分量，且数据类型通常不一致，所以要采用以要

8、采用数据类型。数据类型。答：答：以以2626个字母的链表为例，每个结点都有两个分量：个字母的链表为例，每个结点都有两个分量：字符型指针型设每个结点用变量设每个结点用变量表示，其指表示，其指针用针用 表示，两个分量分别用表示，两个分量分别用和和表示，这两个分量如何赋值？表示，这两个分量如何赋值？p方式方式1： 直接表示为直接表示为 node.data；node.next=方式方式2：p指向结点首地址，然后指向结点首地址，然后 p-data=; p-next= ; 方式方式3： p指向结点首地址，然后指向结点首地址，然后 (*p).data=； (*p).nextb第第11 11页页设设p p为指

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

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

11、ext=q第第13 13页页 对于指向结构类型的指针变量，可说明为：对于指向结构类型的指针变量，可说明为：node *p, *q; /或用或用 struct liuyu *p , *q; /注：上面已经定义了注：上面已经定义了node为用户自定义的为用户自定义的liuyu类型。类型。 类型定义和变量说明可以合写为：类型定义和变量说明可以合写为： liuyu /liuyu是自定义结构类型名称是自定义结构类型名称 char data; /定义数据域的变量名及其类型定义数据域的变量名及其类型 liuyu *next; /定义指针域的变量名及其类型定义指针域的变量名及其类型node，*pointer;

12、 /nodenode是是liuyu结构类型的类型替代结构类型的类型替代, , * *pointerpointer是指针型的是指针型的liuyu结构类型的替代，也是数据类型结构类型的替代，也是数据类型* */ / 补充：结构数据类型的补充：结构数据类型的C表示法表示法第第14 14页页单链表的抽象数据类型描述如下单链表的抽象数据类型描述如下typedef struct Lnode ElemType data; /数据域数据域 struct Lnode *next; /指针域指针域Lnode, *LinkList; / *LinkList为为Lnode类型的指针类型的指针如何具体编程来建立如何具体

13、编程来建立和访问链表？和访问链表？链表的实现链表的实现第第15 15页页typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 线性表的单链表存储结构描述:问题讨论：问题讨论：Q1Q1：第一行的第一行的LnodeLnode 与最后一行的与最后一行的LnodeLnode是不是一回事？是不是一回事？A1A1：不是。前者不是。前者LnodeLnode是结构名，后者是结构名，后者LnodeLnode是对整个是对整个structstruct类型的一种类型的一种“缩写缩写”，是一种，是一种“新定义名新定义名”，它只

14、，它只是对现有类型名的补充，而不是取代。是对现有类型名的补充，而不是取代。请注意：请注意：typedeftypedef不可能创造不可能创造任何新的数据类型，而仅仅是任何新的数据类型，而仅仅是在原有的数据类型中命名一个在原有的数据类型中命名一个新名字，其目的是使你的程序新名字，其目的是使你的程序更易阅读和移植。更易阅读和移植。第第16 16页页Typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; Q2Q2：为何两处要同名为何两处要同名( (Lnode和和Lnode）？）？A2A2：同名是为了表述起来方便

15、。例如，若结构名为同名是为了表述起来方便。例如，若结构名为Lnode ，其新定义名缩写也最好写成其新定义名缩写也最好写成Lnode ，因为描述的对象相同，因为描述的对象相同，方便阅读和理解。方便阅读和理解。Q3Q3：结构体中间的那个：结构体中间的那个structstruct LnodeLnode是何意？是何意？A3A3：在：在“缩写缩写” LnodeLnode还没出现之前，只能用原始的还没出现之前，只能用原始的struct Lnodestruct Lnode来进行变量说明。此处说明了指针分量的数来进行变量说明。此处说明了指针分量的数据类型是据类型是structstruct LnodeLnode

16、。typedef struct Lnode ElemType data; struct Lnode *next; Lnode, *LinkList; 第第17 17页页2. 链表的实现链表的实现（1 1） 单链表的建立和输出单链表的建立和输出（2 2） 单链表的修改单链表的修改（3 3） 单链表的插入单链表的插入（4 4） 单链表的删除单链表的删除第第18 18页页（1）链表的动态生成）链表的动态生成n链表是一种动态存储结构。因此，建立链表的过程是动态生成的过程。 n 按链表结点建立的顺序、方向不同，分为两种方法：n从前往后的动态生成法n从后往前的动态生成法第第19 19页页链表的动态生成（方

17、法一）：从前往后链表的动态生成（方法一）：从前往后n算法操作步骤：算法操作步骤：step1 step1 初始化；头指针置初始化；头指针置NULLNULLstep2 step2 输入结点数据输入结点数据,(,(非非0)0)循环循环 1)1)使使s s指向新生成的结点，指向新生成的结点，s-data = nums-data = num 2) 2)若若 head=NULL(head=NULL(第第1 1个结点个结点) ,head=p=s) ,head=p=s，否则，否则 p-next=sp-next=s 3) 3) 指针指针p p始终指向始终指向s , p=ss , p=sstep3 step3 结

18、束循环结束循环,p-next =NULL, ,p-next =NULL, 返回头指针返回头指针headhead。shead .pa iai-1a2a1第第2020页页链表的动态生成（方法二）：从后往前链表的动态生成（方法二）：从后往前n 算法操作步骤：算法操作步骤：nStep1 Step1 初始化；头指针置初始化；头指针置NULLNULLnStep2 Step2 输入结点数据输入结点数据,(,(非非0)0)循环循环 1) 1) 使使s s指向新生成的结点，指向新生成的结点， 2) 2) s-data = nums-data = num，s-next = head s-next = head 3

19、) 3)头指针始终指向头指针始终指向s s ，head=shead=sn step3 step3 结束循环结束循环, , 返回头指针返回头指针headhead。shead . aiai-1a1ai+1第第21 21页页单链表的建立和输出举例单链表的建立和输出举例例：从键盘输入n个字符，以0作为结束标记，产生不带表头的单链表，请写出C语言程序。（从后往前生成）实现思路：实现思路：先开辟头指针，然后陆续为每个结点开辟存储先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要空间并及时赋值，后继结点的地址要提前提前送给前面的指针。送给前面的指针。先挖先挖“坑坑”, ,后种后种“萝萝

20、卜卜”！第第2222页页Typedef struct Lnode char data; struct Lnode *next; Lnode, *LList; 将全局变量及函数提前说明：将全局变量及函数提前说明：int m=sizeof(Lnode); /*结构类型定义好之后，结构类型定义好之后，每个每个LnodeLnode类类型型的长度就固定了，的长度就固定了，m求一次即可求一次即可*/第第2323页页char ch;Lnode *head, *s;/*s为工作指针，为工作指针，head为头指针为头指针*/head=NULL; /*链表开始为空链表开始为空*/ printf(“please i

21、nput data,use 0 as the end flagn);scanf(“%c”,&ch); /*输入字符输入字符*/ while (ch!=0) s=(Lnode *)malloc(sizeof(Lnode); /*生成新结点生成新结点*/ s-data=ch; s-next=head; /*置新结点的数据域和指针域置新结点的数据域和指针域*/ head=s; scanf(%c,&ch);return head;/*返回头指针返回头指针*/Lnode *Create( void) /字符链表的生成，从后往前生成字符链表的生成，从后往前生成或者：或者：s=(Lnode

22、*)malloc(m);或者：或者： LList head, s;第第2424页页 Lnode *p; p=head; while (p) /当指针不空时循环（仅限于当指针不空时循环（仅限于无头结点无头结点的情况）的情况） printf(%c,p-data); p=p-next; /让指针不断让指针不断“顺藤摸瓜顺藤摸瓜” 讨论：要统计链表中数据元素的个数，该如何改写？讨论：要统计链表中数据元素的个数，该如何改写？ sum+;sum+;sum=0;sum=0;void display(Lnode *head) /*链表的输出链表的输出*/第第2525页页（2） 单链表的修改单链表的修改(或读取

23、或读取/查找）查找）n 举例举例: 设有数列设有数列4,5,8,10,21,30,43,59，长度为，长度为8，输入一个，输入一个结点值结点值30，显示该结点的位置。，显示该结点的位置。第第2626页页算法 单链表查找算法 Lnode *get(Lnode *head, char x） Lnode *p=head; /*从头结点开始比较从头结点开始比较*/ int count= 1; while(p!=NULL)&(p-data!=x) /*直到直到p为为NULL或或p-data是是x为止为止*/ p=p-next; count+; /*扫描下一结点扫描下一结点*/ if(p=NULL

24、) printf(找不到该元素找不到该元素n); else printf(找到了，它的位置是找到了，它的位置是:%dn ,count); return p; 第第2727页页在链表中插入一个元素在链表中插入一个元素X X 的示意图如下：的示意图如下：X Xsabp链表插入的核心语句：链表插入的核心语句：p-nexts-nextX X 结点的生成方式：结点的生成方式：s=(Lnode*)malloc(m);s-data=X X ;s-next= ?bapX X （3） 单链表的插入单链表的插入第第2828页页单链表的插入算法程序(将x插入到值为b的结点前） LList insert(Lnode

25、*head, char b,char x)Lnode *p,*q;p=(Lnode *)malloc(sizeof(Lnode); /申请一个新结点申请一个新结点p-data=x; /置新结点的数据域置新结点的数据域if(head=NULL) /原链表为空原链表为空 head=p; p-next=NULL; return head;if(head-data=b) /在第一个结点前插入在第一个结点前插入 p-next=head; head=p; return head;q=head;while(q-next!=NULL)&(q-next)-data)!=b)q=q-next; /寻找包含

26、元素寻找包含元素b的前一个结点的前一个结点qp-next=q-next; q-next=p; /新结点新结点p插入到结点插入到结点q之后之后return head;第第2929页页在链表中删除某元素在链表中删除某元素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 b结点空间

27、结点空间p-next思考：思考： 省略省略free(q)语句语句行不行？行不行？(p-next) - nextq（4） 单链表的删除单链表的删除第第3030页页单链表的删除算法程序(删除单链表中值为b的结点）LList delete(LList head, char b)Lnode *p,*q;if(head=NULL) return head; /链表为空，无删除的元素链表为空，无删除的元素 if(head-data)=b) /删除第一个结点删除第一个结点 p=head-next; free(head); head=p; return head; q=head;while(q-next!=N

28、ULL)&(q-next)-data)!=b)q=q-next; /寻找包含元素寻找包含元素b的前一个结点的前一个结点q if(q-next=NULL) return head; /链表中无删除的元素链表中无删除的元素p=q-next; q-next=p-next; /删除删除q的下一个结点的下一个结点p free(p); /释放结点释放结点p的存储空间的存储空间return head;第第31 31页页3. 链表的运算效率分析链表的运算效率分析（1） 查找查找 因线性链表只能顺序存取，即在查找时要从头指针找起，因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为查找的

29、时间复杂度为 O(n)。时间效率分析时间效率分析（2） 插入和删除插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为间复杂度为 O(1)。但是，如果要在单链表中进行但是，如果要在单链表中进行前前插或删除操作，因为要插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是从头查找前驱结点，所耗时间复杂度将是 O(n)。第第3232页页讨论讨论1 1： 顺序存储和链式存储的区别和优缺点？顺序存储和链式存储的区别和优缺点？顺序存储时，顺序存储时，逻辑上相邻的数据元素，其物理存放地址逻辑上相邻的数据元素，其物理存放地址也相邻。

30、顺序存储的优点是存储密度大，存储空间利用率高；也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。缺点是插入或删除元素时不方便。链式存储时，链式存储时，相邻数据元素可随意存放，但所占存储空相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。使用灵活。缺点是存储密度小，存储空间利用率低。顺序表顺序表适宜于做适宜于做查找查找这样的静

31、态操作；这样的静态操作；链表链表宜于做宜于做插插入、删除入、删除这样的动态操作。若这样的动态操作。若线性表的长度变化不大线性表的长度变化不大，且，且其主要操作是查找，则采用顺序表；若其主要操作是查找，则采用顺序表；若线性表的长度变化线性表的长度变化较大较大，且其主要操作是插入、删除操作，则采用链表。，且其主要操作是插入、删除操作，则采用链表。第第3333页页讨论讨论2：什么是指针？指针的作用？什么是指针？指针的作用？ 指针指针即变量的内存地址。即变量的内存地址。指针主要功能指针主要功能有二：有二：提供了一种快速访问数组单元的途径；提供了一种快速访问数组单元的途径；使使C C语言函数可以修改其调

32、用的参数。语言函数可以修改其调用的参数。 & &-指针操作符指针操作符（单目），返回操作数地址；（单目），返回操作数地址； *-运算符运算符（单目），是对（单目），是对&的补充，返回位于这个的补充，返回位于这个地址内的变量之值。地址内的变量之值。例：例： q=*m意即意即“q取地址取地址m中的值中的值”。如果数值。如果数值100存存储在内存地址储在内存地址2000中，而这一地址又存在中，而这一地址又存在m中，则中，则q=(2000)=100讨论讨论3 3：与指针有关的符号与指针有关的符号& &和和* *之间有何区别？之间有何区别？第第3434页页预告第预

33、告第1 1次上机内容：次上机内容：单链表的运算（含链表的建立、输出、查找、插单链表的运算（含链表的建立、输出、查找、插入、删除等）入、删除等）上机时间：待定上机时间：待定上机地点：待定上机地点：待定第第3535页页（二）链栈（二）链栈(1) 链栈的构造方式链栈的构造方式以头指针为栈顶，以头指针为栈顶，在头指针处在头指针处插入或删除插入或删除.Node *st, *p;int m=sizeof(Node); 栈顶栈顶栈底栈底栈也可以用链式结构来表示，用链式结构来表示的栈就是栈也可以用链式结构来表示，用链式结构来表示的栈就是链栈链栈 a1 a2an-1 annextdata链栈中每个结点由两个域构

34、成：链栈中每个结点由两个域构成：datadata域和域和nextnext域，其定义为：域，其定义为：typedef Struct SNode SElemType data; Struct SNode * next; Node;第第3636页页Push (SElemType e) p=(Node*)malloc(m); if(!p)上溢上溢else p-data=e; p-next=st; st=p; Status Pop( ) if(st=NULL)下溢下溢elsee=st-data;p=st;st=st-next; free(p); return(e); 插入插入表头表头从表头从表头删除删除

35、(2) 操作操作由此可以看出：一个链栈由其由此可以看出：一个链栈由其栈顶指针唯一指定栈顶指针唯一指定 设设指向栈顶元素，当指向栈顶元素，当=NULL=NULL时表示栈空时表示栈空第第3737页页链栈链栈不必设头结点不必设头结点，因为栈顶（表头）操作频繁；，因为栈顶（表头）操作频繁；链栈一般链栈一般不会出现栈满不会出现栈满情况，除非没有空间导致情况，除非没有空间导致mallocmalloc分配失败。分配失败。链栈的入栈、出栈操作就是栈顶的插入与删除操作，链栈的入栈、出栈操作就是栈顶的插入与删除操作，修改指针即可完成修改指针即可完成。几点说明几点说明:第第3838页页链链队列队列类型定义：类型定义

36、： typedef struct QueuePtr front ; /队首指针队首指针 QueuePtr rear ; /队尾指针队尾指针 LinkQueue;结点结点类型定义：类型定义： typedef Struct QNode QElemType data; /元素元素 Struct QNode *next; /指向下一结点的指针指向下一结点的指针 Qnode , * QueuePtr ;关于整个链队的关于整个链队的总体描述总体描述链队中任一链队中任一结点的结构结点的结构第第3939页页讨论：讨论： 空链队的特征？空链队的特征？Q(队尾队尾)(队首队首)fronta1a2a3rearpfrontrear 怎样实现链队的怎样实现链队的入队和出队入队和出队操作？操作？ 链队会满吗？链队会满吗？front=rear一般不会，因为删除时有一般不会，因为删除时有free动作。除非内存不足！动作。除非内存不足！入队（尾部插入）：入队（尾部插入）：rear-next=S; rear=S;出队（头部删除）：出队（头部删除）：front-next=p-next;SD链队示意图：链队示意图：第第4040页页（1）单链表中存在的问题：）单链表中存在的问题：在运算过程中对于空表与对第一在运算过程中对于空表与对第一个结点的处理必须单独考虑，从而使空表与非空表