数据结构 第2章-2.3线性表的链式存储结构及其运算.ppt

《数据结构 第2章-2.3线性表的链式存储结构及其运算.ppt》由会员分享，可在线阅读，更多相关《数据结构 第2章-2.3线性表的链式存储结构及其运算.ppt（18页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、2.3 线性表的链式存储结构及其运算线性表的链式存储结构及其运算一、单一、单链表的链表的存储结构存储结构二、二、单单 链表的操作实现链表的操作实现三、三、链表的运算效率分析链表的运算效率分析12.3 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，我们介绍线性表的另一种存储方式，链式存储结构，简称为链表(Linked List)。22.3.1 线性链表链表是指用一组任意的存储单元来依次存放线性表的结点，特点：这组存储单元即可以是连续的，也可以是

2、不连续的，甚至是零散分布在内存中的任意位置上的。链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构：datalink3 其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。链表正是通过每个结点的链域将线性表的n个结点按其逻辑次序链接在一起的。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表（Single Linked)。4、单链式及表示方法、单链式及

3、表示方法(1)单单链链表表:构构成成链链表表的的结结点点只只有有一一个个指指向向直直接接后后继继结结点点的的指指针针。其其结结构构特特点点：逻逻辑辑上上相相邻邻的的数数据据元元素素在在物物理理上上不一定相邻。不一定相邻。如何实现？通过指针指针指针指针来实现！让每个存储结点都包含两部分：数据域和指针域让每个存储结点都包含两部分：数据域和指针域指针域指针域数据域数据域nextdatadata或或样式：样式：数据域：存储数据域：存储元素数值数据元素数值数据指针域：存储直接后继的指针域：存储直接后继的存储位置存储位置设计思想：牺牲空间效率换取时间效率设计思想：牺牲空间效率换取时间效率设计思想：牺牲空间

4、效率换取时间效率设计思想：牺牲空间效率换取时间效率一、一、单单链表的链表的存储结构存储结构5定义单链表结点的结构体如下定义单链表结点的结构体如下:typedef struct Node DataType data;struct Node*next;SLNode;其中其中,datadata域域用来存放数据元素用来存放数据元素,nextnext域域用来存放指向下用来存放指向下一个结点的指针。一个结点的指针。6例：请画出例：请画出2626个英文字母表的链式存储结构个英文字母表的链式存储结构。该该字母表在内存中链式存放的样式举例如下：字母表在内存中链式存放的样式举例如下：解：解：该字母表的逻辑结构为：

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

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

7、84）头指针、头结点和首元结点的区别）头指针、头结点和首元结点的区别头指针头指针头结点头结点首元结点首元结点a1heada2infoan头指针头指针是指向链表中第一个结点（或为头结点、或为首元是指向链表中第一个结点（或为头结点、或为首元结点）的指针；结点）的指针；头结点头结点是在链表的首元结点之前附设的一个结点；数据域是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。内只放空表标志和表长等信息，它不计入表长度。首元结点首元结点是指链表中存储线性表第一个数据元素是指链表中存储线性表第一个数据元素a a的结点。的结点。示意图如下：示意图如下：9答：答：讨论1.

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

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

10、针域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：答：头指针是指向链头指针是指向链表中第一个结点的指表中第一个结点的指针，因此关键是要寻针，因此关键是要寻找第一个结点的地址。找第一个结点的地址。7ZHAOH31称：头指针称：头指针H的值是的值是31、带头结点单链表和不带头结点单链表的比较、带头结点单链表和不带头结点单链表的比较例：例：11上例链表的逻辑结构示意图有以下上例链表的逻辑结构示意图有以下两种形式两种形式：ZHAOQIANLISUNZHOUWUZHENG/WANGHZHAOQIANLISUNZHOUWUZH

11、ENG/WANGH区别：区别：无头结点无头结点 有头结点有头结点头结点不计入头结点不计入头结点不计入头结点不计入链表长度！链表长度！链表长度！链表长度！12对比带头结点的单链表的插入、删除过程和对比带头结点的单链表的插入、删除过程和不带带头结点的单链表的插入、删除过程，可以不带带头结点的单链表的插入、删除过程，可以得知：得知：若设计的单链表带头结点，则无论是在第一若设计的单链表带头结点，则无论是在第一个数据元素结点前插入还是在其他数据元素结点个数据元素结点前插入还是在其他数据元素结点前插入都不会改变头指针的数值。前插入都不会改变头指针的数值。若设计的单链表不带头结点，则在第一个数据若设计的单链

12、表不带头结点，则在第一个数据元素结点前插入与在其他数据元素结点前插入其元素结点前插入与在其他数据元素结点前插入其算法的处理方法不同。在单链表中删除一个结点算法的处理方法不同。在单链表中删除一个结点时类似。因此，单链表一般构造成带头结点的单时类似。因此，单链表一般构造成带头结点的单链表。链表。13讨论:链表的数据元素有两个域，不再是简单数据类链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所因每个结点至少有两个分量，且数据类型通常不一致，所以要采用以要采用结构结构结构结构数据类型。数据类型。答：答：以以2626个

13、字母的链表为例，每个结点都有两个分量：个字母的链表为例，每个结点都有两个分量：字符型字符型指针型指针型设每个结点用变量设每个结点用变量nodenodenodenode表示，其指针表示，其指针用用p p p p表示，两个分量分别用表示，两个分量分别用datadatadatadata和和*nextnextnextnext表示，这两个分量如何赋值？表示，这两个分量如何赋值？p*next*nextdatadatanodenode方式方式1：直接表示为直接表示为 node.dataaa；node.next=q q方式方式2：p指向结点首地址，然后指向结点首地址，然后 p-data=aa;p-next=q

14、 q;方式方式3：p指向结点首地址，然后指向结点首地址，然后(*p).data=aa；(*p).nextq qaabq qp p14设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。练习：练习：p-dataai的值的值p-nextai+1的地址的地址附附1：介绍：介绍C的三个有用的库函数的三个有用的库函数/算符（都在算符（都在 中）：中）：sizeof(x)计算变量计算变量x x的长度（字节数）；的长度（字节数）；malloc(m)开辟开辟m m字节长度的地址空间，并返回这段空间字节长度的地址空

15、间，并返回这段空间的首地址；的首地址；free(p)释放指针释放指针p p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。15sizeof(x)计算计算x x的长度的长度malloc(m)开开m m字节空间字节空间free(p)删除一个变量删除一个变量问问1：自定义结构类型变量：自定义结构类型变量node的长度的长度m是多少？是多少？问问2：结构变量：结构变量node的首地址的首地址(指针指针p）是多少？是多少？问问3：怎样删除结构变量怎样删除结构变量node？*nextdatanode，长度为长度为m字节字节pmsizeof(node)/单位是字节单位是字节p

16、(node*)malloc(m)free(p)/只能借助只能借助node的指针删除！的指针删除！P-data=a;p-P-data=a;p-next=qnext=q16 对于指向结构类型的指针变量对于指向结构类型的指针变量，可说明为：可说明为：SLNodeSLNodeSLNodeSLNode *p,*q;/或用或用 struct SLNode*p,*q;/注：上面已经定义了注：上面已经定义了SLNSLNode为用户自定义的为用户自定义的NodeNode类型。类型。类型定义和变量说明可以合写为：类型定义和变量说明可以合写为：typedeftypedef structstruct Node /No

17、de/Node是自定义结构类型名称是自定义结构类型名称 DataType data;/定义数据域的变量名及其类型定义数据域的变量名及其类型 structstruct Node*next;/定义指针域的变量名及其类型定义指针域的变量名及其类型SLNode，*p;/SLNodeSLNode是是NodeNode结结构构类类型型的的类类型型替替代代,*p*p是指针型的是指针型的NodeNode结构类型的替代结构类型的替代附附2：补充结构数据类型的补充结构数据类型的C表示法表示法17编程训练建议：编程训练建议：简单：简单：先建立一个整型数的单链表，然后统计单先建立一个整型数的单链表，然后统计单链表中数据元素为链表中数据元素为0 0的个数。的个数。稍难：稍难：先建立一个字母单链表并输出到屏幕上，先建立一个字母单链表并输出到屏幕上，再试着插入一个字母（例如将再试着插入一个字母（例如将I I插入到插入到L L之后）。之后）。18