《大话数据结构》之线性表

1. 线性表的主要类型

线性表在存储方式上划分，可分为：

• 顺序存储结构，如标准数组
• 链式存储结构，如单链表

2. 顺序存储结构

所谓顺序存储结构，即使用一段地址连续的存储单依次存储线性表的数据元素。

我们可以使用数组来描述线性表的顺序存储结构。

2.1 地址计算方法（读取数据）

通俗地讲，与数据下标访问的方式类似，后一个数据的地址是前一个地址加上数据大小。对于第i个数据的储存位置，即可使用以下方式得出：

LOC(a(i + 1)) = LOC(a(i)) + (i - 1) * c

由于任意地址的数据均可以由以上公式一步得出，故顺序存储结构的存储时间为O(1)，即时间复杂度为常数阶。

2.2 插入数据

主要步骤为：

1. 查找到要插入的位置i
2. 将i之后的数据依次后移一个位置
3. 在i的位置上插入数据e
4. 表长加1

总的执行次数为 1 + n + 1 + 1，故插入操作的时间复杂度为O(n)。

2.3 删除数据

主要步骤为：

1. 查找到要删除的位置i
2. 在i的位置上取出数据e
3. 将i之后的数据依次前移一个位置
4. 表长减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

其中，数组分为两部分结构：

1. 以数组的末尾元素为头结点，根据游标（cur）索引，直到元素的游标为0为止，连接而成的结构，也就是真正的单链表。
2. 以数组第一个元素为头结点，根据游标索引，直到元素的游标为末尾元素的下标为止，作为备用链表，用于动态分配数据（插入、移除数据使用）。

主要结构：

• 数组的末尾元素：初始状态下，末尾元素的游标指向首元素，即为空表。当插入数据后，其游标永远指向链表第一个数据。
• 数组的首元素：初始状态下，其游标指向数组的下一个元素。当插入数据后，其游标总是指向备用链表的第一个数据。
• 数组的其他元素：默认情况下，当前元素的游标指向下一个元素。当插入数据后，数据的游标即保存的是下一个插入数据所在数组的下标。单链表最后一个数据的游标保存的是0，即数组首元素下标，标识单链表已结束。

静态链表的优缺点：

优点：
避免了插入和删除数据时对大量数据的移动，只要修改游标即可实现。

缺点：

• 由于使用数组进行实现，依然无法避免对内存空间进行考虑。
• 失去了顺序存储结构随机存取的特性。

备注：

静态链表的创建、插入和删除等操作的Objective-C版本实现：项目地址

4.2 循环链表

循环链表作为单链表的扩展，在链表尾部定义了尾指针，指向最后一个结点rear。其指针域next指向链表的头结点。

同时，判定链表结束的条件变为了rear->next == 头指针p。

4.3 双向链表

双向链表作为单链表的扩展，在结点的头部和尾部均设有指针域（prior和next），分别指向前驱结点和后继结点。可以双向访问链表的元素。