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

《数据结构 第2章-2.3线性表的链式存储结构及其运算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

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

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

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

5、像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……循环链表示意图：head(2)与链式存储有关的术语：84）头指针、头结点和首元结点的区别头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标

6、志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a０的结点。示意图如下：9答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；^头指针无头结点^头指针头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表长度！10一个线性表的逻

7、辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31称：头指针H的值是31２、带头结点单链表和不带头结点单链表的比较例：11上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZ

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