七、线性表的链式存储结构
1、问题引入
开发数组类模板的原因在于：在创建基于顺序存储结构的线性表时，发现这样的线性表可能被误用，因为重载了数组访问操作符，使用时跟数组类似，但是线性表和数组有很大的区别，所以激发了新的需求：开发数组类替换C++原生数组类，因为原生数组类也存在着很大缺陷，使用不方便。
基于顺序存储结构的线性表的另一个缺点：插入或删除元素时，涉及到大量数据元素的移动，对于效率的影响非常大
一个新的需求：在插入或删除元素时不需要大量移动数据元素的一种数据结构，即基于链式存储结构的线性表
2、链式结构的定义
为了表示每个数据元素于其直接后继元素之间的逻辑关系；数据元素除了存储本身的信息外，还需要存储其直接后继的信息。
\(a_i\)和\(a_{i+1}\)是线性表中的两个相邻数据元素，在物理内存中无相邻关系。
一个数据元素包含了两部分：\(a_i\)是数据元素本身的数据信息，还有一个地址信息，地址是第\(i\)个元素的直接后继，即第\(i+1\)个的元素在内存中的地址信息。换句话说就是如果找到了第\(i\)个元素，不仅可以得到第\(i\)个元素的本身的值之外，还可以得到第\(i+1\)个元素在内存中的位置
3、链式存储逻辑结构
基于链式存储结构的线性表中，每个结点都包含数据域和指针域
- 数据域：存储数据元素本身
- 指针域：存储相邻结点的地址
两种线性表名称统一：
- 顺序表：基于顺序存储结构的线性表
- 链表：基于链式存储结构的线性表
- 单链表：每个结点只包含直接后继的地址信息
- 循环链表：单链表的最后一个结点的直接后继为第一个结点
- 双向链表：单链表中的结点包含直接前驱和后继的地址信息
- 双向循环链表……
4、链表中的基本概念
- 头结点：链表中的辅助结点，包含指向第一个数据元素的指针；不包含任何数据信息，是为了简化代码进行辅助
- 数据结点：链表中代表数据元素的结点，表现形式为：(数据元素，地址)
- 尾结点：链表中的最后一个数据结点。单独放出的原因：尾结点包含的地址信息直接决定了链表的性质，地址信息为空，就是单链表；地址为第0个元素的地址信息，就是循环链表；地址信息为随机值，就是一个非法链表
5、单链表
5.1 单链表中的结点定义
// 用struct定义类，默认属性是public
// T是泛指类型，链表可以存储各种类型的数据
struct Node : public Object
{
T value;
Node* next; // 指向后继结点的指针
}5.2 单链表的内部结构
头结点在单链表中的意义是：辅助数据元素的定位，方便插入和删除操作，因此，头结点不存储实际的数据元素。
5.3 在目标位置处插入数据元素
-
从头结点开始，通过
current指针定位到目标位置 -
从堆空间申请新的Node结点
-
执行操作
node->value = e; node->next = current->next; current->next - node;
5.4 在目标位置删除数据元素
-
从头结点开始，通过
previous指针定位到目标位置的前一个地址 -
使用
toDel指针指向需要删除的结点 -
执行操作：
toDel = previous->next; previous->next = toDel->next; delete toDel;
6、小结
链表中的数据元素在物理内存中无相邻关系
链表中的结点都包含数据域和指针域
头结点用于辅助数据元素定位，方便插入和删除操作
插入和删除操作需要保证链表的完整性
版权声明：本文为chenke1731原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。