---- 整理自狄泰软件唐佐林老师课程

1. 线性表的链式存储结构

• 顺序存储结构线性表的问题：插入和删除需要移动大量的元素

1.1 定义

为了表示每个数据元素与其直接后继元素之间的逻辑关系，数据元素除了存储自身的信息外，还需要存储其直接后继的信息。

1.2 逻辑结构

• 基于链式存储结构的线性表中，每个结点都包含数据域和指针域
  • 数据域：存储数据元素本身
  • 指针域：存储相邻结点的地址

1.3 专业术语的统一

• 顺序表：基于顺序存储结构的线性表
• 链表：基于链式存储结构的线性表
  • 单链表：每个结点只包含直接后继的地址信息
  • 循环链表：单链表中的最后一个结点的直接后继为第一个结点
  • 双向链表：单链表中的结点包含前驱和后继的地址信息

2. 链表的基本概念

• 头结点：链表中的辅助结点，包含指向第一个数据元素的指针
• 数据结点：链表中代表数据元素的结点，表现形式为：（数据元素，地址）
• 尾结点：链表中的最后一个数据结点，包含的地址信息为空

2.1 单链表中的结点定义

2.2 单链表中的内部结构

• 头结点在单链表中的意义是：辅助数据元素的定位，方便插入和删除；因此，头结点不存储实际的数据元素。

2.3 在目标位置处插入数据元素

1. 从头结点开始，通过 current 指针定位到目标位置
2. 从堆空间申请新的 Node 结点
3. 执行操作：

node->value = e;
node->next = current->next;
current->next = node;

2.4 在目标位置处删除数据元素

1. 从头结点开始，通过 current 指针定位到目标位置
2. 使用 toDel 指针指向需要删除的结点
3. 执行操作：

toDel = current->next;
current->next = toDel->next;
delete toDel;

3. 链式存储结构线性表的实现

3.1 设计要点

1. 类模板，通过头结点访问后继结点
2. 定义内部结点类型 Node，用于描述数据域和指针域
3. 实现线性表的关键操作（增、删、查，等）

template<typename T>
class LinkList : public List<T>
{
protected:struct Node : public Object {T value;Node* next;};Node m_header;int m_length;
public:LinkList();// ...
};

3.2 实现

【单链表的具体实现】

3.3 问题

• 头结点是否存在隐患？代码如何优化？

#include <iostream>
#include "LinkList.h"using namespace DTLib;
using namespace std;class Test
{
public:Test(){throw 0;}
};int main()
{LinkList<Test> list;cout << "test" << endl;return 0;
}

• LinkList 成员 m_header，在构造 LinkList 对象的时候，会构造 Node 对象，进一步构造 T 对象，和用户定义的对象类型有关。

3.4 优化

【单链表优化】

4. 小结

• 通过类模板实现链表，包含头结点成员和长度成员
• 定义结点类型，并通过堆中的结点对象构成链式存储
• 为了避免构造错误的隐患，头结点类型需要重定义