第2章线性表2(单链表)课件

1、12.3 线性表的链式表示和实现线性表的链式表示和实现一、单链表的存储结构一、单链表的存储结构二、二、 单单 链表的操作实现链表的操作实现三、链表的运算效率分析三、链表的运算效率分析2、单链式及表示方法、单链式及表示方法(1)单链表单链表:构成链表的结点只有一个指向直接后继结点构成链表的结点只有一个指向直接后继结点的指针。的指针。其结构特点：其结构特点：逻辑上相邻的数据元素在物理上逻辑上相邻的数据元素在物理上不一定相邻。不一定相邻。如何实现？通过来实现！让每个存储结点都包含两部分：让每个存储结点都包含两部分：数据域数据域和和指针域指针域指针域指针域next或或样式：样式：数据域：数据域：存储存

2、储元素数值数据元素数值数据指针域：指针域：存储直接后继的存储直接后继的存储位置存储位置一、一、 单链表的存储结构单链表的存储结构3定义单链表结点的结构体如下定义单链表结点的结构体如下:typedef struct Node DataType data; struct Node *next;SLNode; 其中其中, ,datadata域域用来存放数据元素用来存放数据元素, ,nextnext域域用来存放指向下用来存放指向下一个结点的指针。一个结点的指针。4例：请画出例：请画出2626个英文字母表的链式存储结构。个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：该字母表在内存中

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

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

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

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

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

8、：头指针头指针是指向链是指向链表中表中第一个第一个结点的指结点的指针，因此关键是要寻针，因此关键是要寻找找第一个结点第一个结点的的地址地址。7ZHAOH31称：头指针称：头指针H的值是的值是31、带头结点单链表和不带头结点单链表的比较、带头结点单链表和不带头结点单链表的比较例：例：9上例链表的逻辑结构示意图有以下上例链表的逻辑结构示意图有以下两种形式两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZHENG/WANGH区别：区别： 无头结点无头结点 有头结点有头结点10对比带头结点的单链表的插入、删除过程和对比带头结点的单链表的插入、

9、删除过程和不带带头结点的单链表的插入、删除过程，可以不带带头结点的单链表的插入、删除过程，可以得知：若设计的单链表得知：若设计的单链表带头结点带头结点，则无论是在第，则无论是在第一个数据元素结点前插入还是在其他数据元素结一个数据元素结点前插入还是在其他数据元素结点前点前插入都不会改变头指针的数值插入都不会改变头指针的数值。若设计的单。若设计的单链表链表不带头结点不带头结点，则在第一个数据元素结点前插，则在第一个数据元素结点前插入与在其他数据元素结点前入与在其他数据元素结点前插入其算法的处理方插入其算法的处理方法不同法不同。在单链表中删除一个结点时类似。因此，。在单链表中删除一个结点时类似。因此

10、，单链表一般构造成单链表一般构造成带头结点带头结点的单链表的单链表。11讨论: 链表的数据元素有链表的数据元素有两个域两个域，不再是简单数据，不再是简单数据类型，类型，编程编程时该如何表示？时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所因每个结点至少有两个分量，且数据类型通常不一致，所以要采用以要采用数据类型。数据类型。答：答：以以2626个字母的链表为例，每个结点都有两个分量：个字母的链表为例，每个结点都有两个分量：字符型字符型指针型指针型设每个结点用变量设每个结点用变量表示，其指表示，其指针用针用 表示，两个分量分别用表示，两个分量分别用和和表示，这两个分量如何赋值？表示

11、，这两个分量如何赋值？p方式方式1： 直接表示为直接表示为 node.data；node.next=方式方式2：p指向结点首地址，然后指向结点首地址，然后 p-data=; p-next= ; 方式方式3： p指向结点首地址，然后指向结点首地址，然后 (*p).data=； (*p).nextb12设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针, ,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。练习：练习：p-dataai的值的值p-nextai+1的地址的地址附附1：介绍介绍C的三个有用的库函数的三个有用的库函数/算符（都在算符（都在

12、中）：中）：sizeof(x)计算变量计算变量x x的长度（字节数）；的长度（字节数）；malloc(m) 开辟开辟m m字节长度的地址空间，并返回这段空间字节长度的地址空间，并返回这段空间的首地址；的首地址；free(p) 释放指针释放指针p p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。13sizeof(x)计算计算x x的长度的长度malloc(m) 开开m m字节字节空间空间free(p) 删除一个变量删除一个变量问问1：自定义结构类型变量自定义结构类型变量node的长度的长度m是多少？是多少？问问2：结构变量结构变量node的首地址的首地址(指针指

13、针p）是多少？）是多少？问问3：怎样删除结构变量怎样删除结构变量node？*nextdatanode，长度为长度为m字节字节pmsizeof(node) /单位是字节单位是字节p(node*)malloc(m)free(p) /只能借助只能借助node的指针删除！的指针删除！p-data=a; p-data=a; p-next=qnext=q14 对于指向结构类型的指针变量，可说明为：对于指向结构类型的指针变量，可说明为： *p, *q; /或用或用 struct SLNode *p , *q; /注：上面已经定义了注：上面已经定义了SLNSLNode为用户自定义的为用户自定义的NodeNod

14、e类型。类型。 类型定义和变量说明可以合写为：类型定义和变量说明可以合写为： Node /Node/Node是自定义结构类型名称是自定义结构类型名称 DataType data; /定义数据域的变量名及其类型定义数据域的变量名及其类型 Node *next; /定义指针域的变量名及其类型定义指针域的变量名及其类型SLNode，*p; /SLNodeSLNode是是NodeNode结构类型的类型替代结构类型的类型替代, , * *p p是指针型的是指针型的NodeNode结构类型的替代结构类型的替代附附2： 补充结构数据类型的补充结构数据类型的C表示法表示法1516例：例： 单链表的建立和输出单

15、链表的建立和输出例：用单链表结构来存放例：用单链表结构来存放26个英文字母组成的个英文字母组成的线性表（线性表（a，b，c，z）,请写出请写出C语言程序。语言程序。实现思路：实现思路：先开辟头指针，然后陆续为每个结点开辟存储先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要空间并及时赋值，后继结点的地址要提前提前送给前面的指针。送给前面的指针。先挖先挖“坑坑”, ,后种后种“萝萝卜卜”！17typedef struct nodechar data; struct node *next;node; 将全局变量及函数提前说明：将全局变量及函数提前说明：node *p,*q,*

16、head; /一般需要一般需要3 3个指针变量个指针变量int n ; / / 数据元素的个数数据元素的个数int m=sizeof(node); / /* *结构类型定义好之后，结构类型定义好之后，每个每个nodenode类型类型的长的长度就固定了，度就固定了，m m求一次即可求一次即可* */ /18新手特别容易忘记！新手特别容易忘记！ int i;head=(node*)malloc(m); /m=sizeof(node) 前面已求出前面已求出p=head;for( i=1; idata=i+a-1; / 第一个结点值为字符第一个结点值为字符ap-next=(node*)malloc(m

17、); /为后继结点为后继结点“挖坑挖坑”！p=p-next； /让指针变量让指针变量P指向后一个结点指向后一个结点p-data=i+a-1; /最后一个元素要单独处理最后一个元素要单独处理p-next=NULL ; / /单链表尾结点的指针域要置空！单链表尾结点的指针域要置空！void build( ) /字母链表的生成字母链表的生成。要一个个慢慢链入要一个个慢慢链入19p=head;while (p) /当指针不空时循环（仅限于当指针不空时循环（仅限于无头结点无头结点的情况）的情况） printf(%c,p-data); p=p-next; /让指针不断让指针不断“顺藤摸瓜顺藤摸瓜” 讨论：

18、要统计链表中数据元素的个数，该如何改写？讨论：要统计链表中数据元素的个数，该如何改写？ sum+;sum+;sum=0;sum=0;void display() /*字母链表的输出字母链表的输出*/20void main( )void main( ) build( ); build( ); display( ); display( ); 问：上述建立的单链表带头结点吗？问：上述建立的单链表带头结点吗？21二、单链表的操作实现二、单链表的操作实现定义单链表结点的结构体如下定义单链表结点的结构体如下: :t typedef struct Node DataType data; struct Nod

19、e *next;SLNode;、初始化、初始化void ListInitiate(SLNode *head)*初始化*/ /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/if(*head = (SLNode *)malloc(sizeof(SLNode) = NULL) exit(1);(*head)-next = NULL; /*置链尾标记NULL */22、求单链表中数据元素的个数、求单链表中数据元素的个数int ListLength(SLNode int ListLength(SLNode * *head)head) SLNode SLNode * *p = head;

20、p = head;/ /* *p p指向头结点指向头结点* */ /int size = 0;int size = 0;/ /* *sizesize初始为初始为0 0* */ / while(p-next != NULL) /while(p-next != NULL) /* *循环计数循环计数* */ / p = p-next;p = p-next;size +;size +; return size;return size; 23在链表中插入一个元素在链表中插入一个元素X X 的示意图如下：的示意图如下：X Xqabp链表插入的核心语句：链表插入的核心语句：p-nextp-nextX X 结

21、点的生成方式：结点的生成方式：m=m=sizeof(SLNode); q=(SLNode *)malloc(m);q-data=X X ;q-next= ?bapX X 、向单链表中插入一个元素、向单链表中插入一个元素24int ListInsert(SLNode int ListInsert(SLNode * *head, int i, DataType x)head, int i, DataType x) SLNode SLNode * *p, p, * *q; q; int j; int j; p = head;p = head;j = -1;j = -1; while(p-next !

22、= NULL & j next != NULL & j next; j+;p = p-next; j+; if(j != i - 1)if(j != i - 1)printf(printf(插入位置参数错！插入位置参数错！););return 0; return 0; (2)(2) if(q = (SLNode if(q = (SLNode * *)malloc(sizeof(SLNode) = NULL) )malloc(sizeof(SLNode) = NULL) exit(1); exit(1);q-data = x;q-data = x;(3)(3) q-next = p-next;q

23、-next = p-next;p-next = q; (4)p-next = q; (4)return 1; return 1; 注：此单链表是带头结点的注：此单链表是带头结点的25在链表中删除某元素在链表中删除某元素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结点空

24、间结点空间p-next思考：思考： 省略省略free(q)语句语句行不行？行不行？(p-next) - nextq、从、从 单链表中删除一个元素单链表中删除一个元素26int ListDelete(SLNode int ListDelete(SLNode * *head, int i, DataType head, int i, DataType * *x)x) SLNode SLNode * *p, p, * *s;s;int j;int j;(1) p = head;(1) p = head; j = -1;j = -1;while(p-next != NULL & p-next-next

25、!= NULL while(p-next != NULL & p-next-next!= NULL & j i - 1) & j next;p = p-next;j+;j+; if(j != i - 1)if(j != i - 1) printf(“printf(“插入位置参数错！插入位置参数错！”););return 0;return 0; (2)(2)s = p-next; s = p-next; * *x = s-data; x = s-data; (3) (3) p-next = p-next-next;p-next = p-next-next;free(s); free(s); re

26、turn 1;return 1; 27三、单链表的操作效率分析三、单链表的操作效率分析（1） 查找查找 因线性链表只能顺序存取，即在查找时要从头指针找起，因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为查找的时间复杂度为 O(n)。时间效率分析时间效率分析（2） 插入和删除插入和删除 因线性链表不需要移动元素，只要修改指针，仅就插入或删因线性链表不需要移动元素，只要修改指针，仅就插入或删除而言，时间复杂度为除而言，时间复杂度为 O(1)。但是，如果要在单链表中进行在某结点但是，如果要在单链表中进行在某结点前前插或删除操作，插或删除操作，因为要因为要从头查找前驱从头查找前驱结

27、点，所以一般情况下，结点，所以一般情况下，单链表插单链表插入和删除操作入和删除操作的时间复杂度是的时间复杂度是 O(n)（同顺序表）。（同顺序表）。28五、循环单链表五、循环单链表xheada0an循环链表循环链表示意图：示意图：循环单链表是单链表的另一种形式，其结构特点是链表中循环单链表是单链表的另一种形式，其结构特点是链表中的最后一个结点的指针域不再是结束标记，而是指向整个链表的最后一个结点的指针域不再是结束标记，而是指向整个链表的第一个结点，从而使链表形成一个环。的第一个结点，从而使链表形成一个环。问：带头结点的循环单链表的插入、删除算法如何写？问：带头结点的循环单链表的插入、删除算法如何写？29例例2 2：试用试用C C语言编写一个算法，将一循环单链表