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

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），分别指向前驱结点和后继结点。可以双向访问链表的元素。