数据结构4——线性表3：线性表的链式结构

基本概念

​ 链式存储结构用一组物理位置任意的存储单元来存放线性表的数据元素。

​ 这组存储单元既可以是连续的又可以是不连续的甚至是零散分布在任意位置上的。所以链表中元素的逻辑次序和物理次序不一定相同。而正是因为这一点，所以我们要利用别的方法将这些数据元素衔接起来。而链式存储结构通过存储下一个内容的地址完成衔接。这样，依次通过衔接，就可以将整张表串联起来。我们将存储的内容叫做数据域，将衔接叫做指针域。数据域和指针域共同构成了结点。之后我们只要记录下第一个元素的地址，就可以找到多有链表存储内容，第一个元素的地址叫做头指针。而由若干个结点由指针链组成了链表。

头指针：指向链表中第一个结点的指针

头结点：在首元结点之前附设的一个结点，不储存实际所需要的信息

设置头结点的好处：

(1) 便于首元结点的处理：首元结点的地址保存在头结点的指针域中，所以在链表的第一个位置上的操作和其他位置一致。

(2) 便于空表和非空表的处理：无论链表是否为空，头指针都指向头结点的非空指针，因此空表与非空表的处理也就统一了

首元结点：指向链表中存储第一个数据元素的结点

链表分类

单链表：结点只有一个指针域的链表

①不带头结点：

空表：头指针为空

②带头结点：

空表：头结点的指针域为空

双链表：结点有两个指针域的链表

循环链表：首尾相接的链表

链表的特点：

① 链表用一组物理位置任意的存储单元来存放线性表的数据元素，即逻辑上相邻的元素位置上不一定相邻。

② 访问时只能通过头指针进入链表，之后顺着结点一个个向后寻找。

顺序表->随机存取 链表->顺序存取

单链表

定义：

定义链表的两种方式：

Lnode *L; 或 LinkList L;

虽然两者的意思上差不多，但是对定义链表我们一般使用后者。

定义结点指针p两种方式：

Lnode *p；或 LinkList p；

虽然两者的意思上差不多，但是对定义结点我们一般使用前者。

例子：

基本操作的实现

单链表的初始化：

构造一个如图的空表

算法思路：

（1）生成新结点作为头结点 ，用头指针L指向头结点

（2）将头结点的指针域置空

判断链表是否为空：

算法思路：判断头结点指针域是否为空

单链表的销毁：

算法思路：从头指针开始，依次释放所有结点

单链表的清空：

与链表的校徽不同，清空链表后链表仍然存在，只不过链表中没有元素、成为空链表。

算法思路：依次释放所有结点，并将头结点指针域置空

注意点：由于单链表的清空不能把头结点删去，所以在链表结点的删除操作上比单链表的销毁更为复杂。

求单链表表长

算法思路：从首元结点开始，依次计数所有结点。

单链表的取值：（取单链表中的第i个元素）

算法步骤：

1、从第一个结点（L->next）顺链扫描，用指针 p 指向当前扫描到的结点，p 处置 p=L->next

2、j 做计数器，累计当前扫描过的结点数，j 初始值为1。

3、当 p 指向扫描到的下一个结点时，计数器 j+1。

4、当 j==i 时，p所指的结点就是要找的第 i 个结点。

单链表的查找：

算法步骤：

1、从第一个结点起，依次和e相比较

2、如果找到一个其值与e相等的数据元素，则返回其在链表中的位置或这地址

3、如果查遍整个链表都没有找到其值和e相等的元素，则返回0或者NULL

① 按数值查找——返回值

② 按数值查找——返回序号

前后两者的差别是：

按数据内容查找增加了j的初始化并增加了j++记数功能、返回值变化。这些都只是在按数据内容查找的基础上增加了序号，本质没变。

单链表的插入：

算法步骤：

1、首先找到a(i-1)的存储位置p

2、生成一个数据域为e的新结点s

3、插入新结点：

① 新结点的指针域指向结点a(i)

s -> next = p -> next

② 结点a(i-1)的指针域指向新结点

p -> next = s

思考：① ② 两步可以直接交换吗？

不可以，因为先将a(i-1)指向s会导致p->next不能达到指向a(i)的效果，如果硬是要这样做，要多用一个指针指向a(i)

关于代码第83行 p=L 而不是 p=L->next 的解释：因为删除的结点有可能是就是第一个结点，指向Lnext会导致第一个结点无法删除。

单链表的删除：

算法步骤：

1、首先找到 a(i) 的存储位置p，保存要删除的 a(i) 的值

2、令p->next 指向 a(i+1)

3、释放结点空间

建立单链表：

头插法：元素插在链表的前部

尾插法：元素插在链表的尾部

总结

总结1：常用指针操作

指向头结点：p=L

指向首元结点：s=L->next

指向下一个结点：p=p->next

总结2：各操作时间效率分析：

查找：O(n)

插入和删除：O(n)

头插法/尾插法：O(n)

循环链表

定义：

头尾相接的链表，即表中最后一个结点的指针指向头结点，整个链表形成一个环。

优点：从表中任何一个结点出发均可以找到其它结点。

循环条件：

循环链表中没有空指针，其终止条件判断为p或者p->next是否等于头指针

p!=NuLL	p!=L
p->next!=NULL	p->next!=L
单链表	单循环链表

基本操作的实现

带尾指针循环链表的合并（将Tb合并在Ta之后）

算法步骤：

1、p存表头节点 p=Ta->next

2、Tb表头连接到Ta表尾 Ta->next=Tb->next->next

3、释放Tb表头结点 delete Tb->next

4、修改Tb尾指针 Tb->next=Ta

双向链表

定义：

在单链表的每个结点里面再增加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链。

优点：方便查找前驱结点

双向链表结构定义：

对称性：p->prior->next = p = p->next->prior

基本操作实现

双向链表的插入：

双向链表的删除：

单链表、循环链表和双向链表的时间效率比较：

（1）查找表头几种链表时间复杂度相同。

（2）查找表尾结点使用循环链表时间复杂度小。

（3）查找前驱结点用双向循环链表时间复杂度最小。

顺序与链式比较

链式存储结构

优点：

① 结点空间可以动态申请和释放；

② 插入和删除操作时不需要移动大量元素；

缺点;

① 存储密度小，每个结点的指针域需额外占用存储空间；

② 是非随机存取结构，对任意一个结点的操作都要从头开始操作；