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, 小结
链表中的数据元素在物理内存中无相邻关系
链表中的结点都包含数据域和指针域
头结点用于辅助数据元素定位, 方便插入和删除操作
插入和删除操作需要保证链表的完整性
来源: https://www.cnblogs.com/chenke1731/p/9495573.html