《大话数据结构》之线性表
1. 线性表的主要类型
线性表在存储方式上划分，可分为：
- 顺序存储结构，如标准数组
- 链式存储结构，如单链表
2. 顺序存储结构
所谓顺序存储结构，即使用一段地址连续的存储单依次存储线性表的数据元素。
我们可以使用数组来描述线性表的顺序存储结构。
2.1 地址计算方法（读取数据）
通俗地讲，与数据下标访问的方式类似，后一个数据的地址是前一个地址加上数据大小。对于第i个数据的储存位置，即可使用以下方式得出：
LOC(a(i + 1)) = LOC(a(i)) + (i - 1) * c
由于任意地址的数据均可以由以上公式一步得出，故顺序存储结构的存储时间为O(1)，即时间复杂度为常数阶。
2.2 插入数据
主要步骤为：
- 查找到要插入的位置i
- 将i之后的数据依次后移一个位置
- 在i的位置上插入数据e
- 表长加1
总的执行次数为 1 + n + 1 + 1，故插入操作的时间复杂度为O(n)。
2.3 删除数据
主要步骤为：
- 查找到要删除的位置i
- 在i的位置上取出数据e
- 将i之后的数据依次前移一个位置
- 表长减1
总的执行次数为 1 + 1 + n + 1，故删除操作的时间复杂度为O(n)。
2.4 顺序存储结构的优缺点
优点：
- 无需为数据元素之间的逻辑关系增加额外存储空间
- 可以快速读取任一位置的元素
缺点：
- 插入和删除数据需要移动大量元素
- 当线性表长度变化较大时，难以确定存储空间的长度
- 造成存储空间的”碎片“
3. 链式存储结构（以单链表为例）
链式存储结构的特点，是使用一组任意的存储单元存储线性表的数据元素。这些存储单元可以是不连续的，任意位置均可。
链式存储结构中的数据结点（Node），除了包含自身数据（数据域），还需要存储一个后继结点的地址（指针域）。
当n个数据结点组成一个链表，其中每一个结点都只包含一个指针域时，这种链式结构称为单链表。
我们这里使用单链表来描述线性表的链式存储结构。
3.1 单链表的基本描述
- 头指针：指向单链表第一个结点存储位置（即第一个结点的地址）的指针。
- 头结点：在第一个结点前设置的一个结点，其指针域为头指针地址。
- 线性表最后一个结点的指针域为NULL或^。
3.2 头指针与头结点的异同
头指针：
- 指链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针。
- 有标识作用，常用头指针冠以链表的名字。
- 无论链表是否为空，头指针均不为空。头指针是链表的必要元素。
头结点：
- 为了操作统一和方便而设置，放在第一个结点之前，其数据域一般无意义（可以存放链表长度）。
- 有了头结点，对在第一个结点前插入结点或删除第一结点，其操作与其他结点完成统一。
- 头结点不一定是链表的必须要素。
3.3 单链表的读取
由于每一个结点的存储位置都在前一个结点的指针域中保存，故获取指定位置的结点数据，需要从单链表的头结点开始，依次查找。故其查找的时间复杂度为O(n)。
查找方式，即循环”指针后移“。
3.4 单链表的插入
单链表的插入过程，如下图所示：
单链表的插入.jpg
其中，待插入的结点s（数据e），插入到结点p和p->next之间（数据a(i)和数据a(i+1)）之间。其关键操作为:
// 将插入结点s的指针域指向原后结点p->next
s->next = p->next;
// 原结点p的指针域指向插入结点s
p->next = s;
故此插入行为的复杂度为O(1)。
不过，由于查找插入位置结点的复杂度为O(n)，故最终单链表插入操作的时间复杂度为O(n)。
3.5 单链表的删除
单链表的删除过程，如下图所示：
单链表的删除.jpg
其中，a(i)为待删除元素，即p->next结点。删除后即将结点p的指针域指向a(i+1)元素的结点。
// 待删除结点的前一个结点的指针域 指向 待删除结点的后一个结点
p->next = p->next->next;
// 或
q = p->next;
p->next = q->next;
// 最后，释放删除结点的内存
free(q);
故此删除行为的复杂度为O(1)。
不过，由于查找删除位置结点的复杂度为O(n)，故最终单链表删除操作的时间复杂度为O(n)。
3.6 单链表的整表创建
- 头插法：每次均从头指针插入新结点。
// 创建单链表L(空表)
*L = (LinkList)malloc(sizeOf(Node));
(*L->next) = NULL;
for (int i = 0; i < n; i++) {
// L为单链表的头结点，p为待插入结点
p->next = (*L)->next;
(*L)->next = p;
}
- 尾插法：每次均插入到尾结点的后面。
// 创建单链表L(空表)
*L = (LinkList)malloc(sizeOf(Node));
(*L->next) = NULL;
// r为指向尾部的结点
r = *L;
for (int i = 0; i < n; i++) {
// p为待插入结点，插入到尾结点后面
r->next = p;
// 新加入结点作为新的尾结点
r = p;
}
// 尾结点指针域赋值
r->next = NULL;
3.7 单链表的整表删除
做法：依次边遍历边删除
// L为待删除链表，p和q分别指向当前结点
// p指向第一个结点
p = (*L)->next;
while(p) {
// q指向后继结点
q = p->next;
// 删除当前结点
free(p);
// p指向后继结点
p = q;
}
// 循环结束后，p结点已经不存在
// 置为空表，让头结点的头指针为空
(*L)->next = NULL;
3.8 单链表与顺序存储结构实用性对比
- 在频繁查找，且很少进行插入和删除操作时，可以考虑使用顺序存储结构。若频繁插入或删除，则考虑使用单链表。
- 在不确定线性表的元素个数时，可以考虑使用单链表，忽略存储空间的需求问题。
4. 其他类型链表结构
4.1 静态链表
静态链表是在没有指针的情况下实现的“模拟”单链表，本质上是使用数组进行描述并实现。
其结构如下所示：
静态链表.jpg
其中，数组分为两部分结构：
- 以数组的末尾元素为头结点，根据游标（cur）索引，直到元素的游标为0为止，连接而成的结构，也就是真正的单链表。
- 以数组第一个元素为头结点，根据游标索引，直到元素的游标为末尾元素的下标为止，作为备用链表，用于动态分配数据（插入、移除数据使用）。
主要结构：
- 数组的末尾元素：初始状态下，末尾元素的游标指向首元素，即为空表。当插入数据后，其游标永远指向链表第一个数据。
- 数组的首元素：初始状态下，其游标指向数组的下一个元素。当插入数据后，其游标总是指向备用链表的第一个数据。
- 数组的其他元素：默认情况下，当前元素的游标指向下一个元素。当插入数据后，数据的游标即保存的是下一个插入数据所在数组的下标。单链表最后一个数据的游标保存的是0，即数组首元素下标，标识单链表已结束。
静态链表的优缺点：
优点：
避免了插入和删除数据时对大量数据的移动，只要修改游标即可实现。缺点：
- 由于使用数组进行实现，依然无法避免对内存空间进行考虑。
- 失去了顺序存储结构随机存取的特性。
备注：
静态链表的创建、插入和删除等操作的Objective-C版本实现：项目地址
4.2 循环链表
循环链表作为单链表的扩展，在链表尾部定义了尾指针，指向最后一个结点rear。其指针域next指向链表的头结点。
同时，判定链表结束的条件变为了rear->next == 头指针p。
4.3 双向链表
双向链表作为单链表的扩展，在结点的头部和尾部均设有指针域（prior和next），分别指向前驱结点和后继结点。可以双向访问链表的元素。
