1.1 线性表

§ 1.1.1 为什么需要线性表#

许多问题中的数据既不是互不相关的集合，也没有树或图那样的分支关系，而是沿一条路径依次排列。
- 例如播放列表、学生签到顺序、编辑器中的字符序列和多项式的项序列，都需要表达“第几个”“前一个”“后一个”。

线性表把具体业务含义暂时隐藏，只保留两件事：

元素序列：元素按逻辑位序排列，位序本身属于模型的一部分。
允许的操作：可以读取、查找、插入、删除或遍历元素，但每个操作必须保持序列关系。
这种抽象让使用者先讨论“操作后的逻辑结果”，再由实现者选择连续数组或链接结点。
- 二者可以呈现同一序列，却具有不同的内存布局和代价。

§ 1.1.2 正式定义与结构边界#

一、线性表的定义#

线性表是由 $n$ 个相同数据类型的数据元素组成的有限序列：

L=(a_1,a_2,\ldots,a_i,\ldots,a_n),\qquad n\ge 0

公式解读

$L$ ：整个线性表。
$n$ ：表中数据元素的个数，也称表长。
$a_i$ ：位序为 $i$ 的元素，合法位序为 $1\le i\le n$ 。
整句可读为：线性表由有限个同类型元素按唯一的先后次序排列；当 $n=0$ 时，它是空表。

当 $n>0$ 时：

$a_1$ 是表头元素，没有直接前驱。
$a_n$ 是表尾元素，没有直接后继。
对 $1<i\le n$ ， $a_{i-1}$ 是 $a_i$ 的直接前驱。
对 $1\le i<n$ ， $a_{i+1}$ 是 $a_i$ 的直接后继。
当 $n=1$ 时，唯一元素 $a_1$ 同时是表头和表尾，既没有直接前驱，也没有直接后继。
- 这不是两个不同元素，而是同一元素同时承担两个边界角色。
这里的“唯一”描述的是结构位置上的相邻关系，不要求元素值互不相同。
- 序列 (A, B, A) 仍然是合法线性表：两个 A 的值相同，但位序分别是 1 和 3。

二、线性表的逻辑特征#

有限性：任一具体线性表都包含有限个元素，空表也在定义范围内。
同质性：同一张表中的元素服从同一个数据类型或同一组操作语义。
有序性：这里的“有序”表示存在明确先后次序，不表示元素按关键字从小到大排列。
一对一关系：除两个边界元素外，每个元素恰有一个直接前驱和一个直接后继。
抽象性：定义关注元素关系和操作，不规定元素在内存中的地址。

§ 1.1.3 抽象接口与操作契约#

线性表 ADT 规定“做什么”，不规定“怎样做”。下面采用 C11 风格表达接口：修改结构时传入指针，只读操作接收指向常量对象的指针；ElemType 和 List 的内部定义由具体实现提供。

#include <stdbool.h>
#include <stddef.h>

typedef int ElemType;
typedef struct List List;

bool InitList(List *list);
void DestroyList(List *list);
size_t Length(const List *list);
bool Empty(const List *list);
bool GetElem(const List *list, size_t position, ElemType *out_value);
bool LocateElem(const List *list, ElemType value, size_t *out_position);
bool ListInsert(List *list, size_t position, ElemType value);
bool ListDelete(List *list, size_t position, ElemType *out_value);

接口中的 position 采用从 1 开始的逻辑位序。
- 使用返回值区分成功与失败，避免把合法数据值误当作错误码。

一、创建、销毁与状态查询#

InitList(list)：把一个可用对象初始化为空表。
- 成功后的表长为 0。
- 若实现需要动态内存，分配失败时返回 false。
DestroyList(list)：释放该实现拥有的资源，并把对象恢复到不可继续读写或可安全重新初始化的状态。
Length(list)：返回数据元素数量，不把头结点、容量或空闲槽位计入。
Empty(list)：判断当前表长是否为 0。

二、读取与定位#

GetElem(list, position, out_value)：返回第 position 个元素的值。
- 前置条件是 1 <= position <= Length(list)。
- 失败时不应把未定义数据写入 out_value。
LocateElem(list, value, out_position)：按既定相等关系查找。
- 若有重复值，通常返回第一个匹配元素的位序；其他语义必须另行说明。
- 未找到属于正常失败路径，不等于结构损坏。

三、插入与删除#

ListInsert(list, position, value)：让 value 成为新的第 position 个元素。
- 对长度为 $n$ 的表，合法插入位序是 $1\le position\le n+1$ 。
- 原来位于 position 及之后的元素，其逻辑位序都增加 1。
ListDelete(list, position, out_value)：删除原第 position 个元素，并通过 out_value 返回它。
- 合法删除位序是 $1\le position\le n$ 。
- 原来位于其后的元素，逻辑位序都减少 1。

§ 1.1.4 必须保持的逻辑不变量#

不变量是每次合法操作前后都必须成立的结构性质。对线性表而言：

表长 $n$ 始终是非负有限整数。
有效元素恰好对应位序 $1$ 到 $n$ ，没有重复位序或位序空洞。
元素的相对次序只会按操作语义改变。
- 插入只增加一个新元素，不丢失旧元素。
- 删除只移除指定元素，不改变其余元素的相对次序。
存储实现中的额外状态必须与逻辑序列一致。
- 顺序表的 length 必须等于有效数组元素数。
- 链表从入口沿链接可达的数据结点数必须等于表长定义。
这些不变量把接口语义与实现连接起来。
- 实现可以改变数组下标或指针，但最终观察到的逻辑序列必须正确。

§ 1.1.5 两种存储表示#

一、顺序表示#

顺序表示把元素放在一段连续存储空间中，逻辑位序通过固定大小的偏移映射为数组下标。

直接定位：已知位序时可以计算地址。
连续布局：顺序遍历通常具有较好的空间局部性。
修改后缀：中间插入或删除需要移动一段元素。
容量管理：静态顺序表容量固定；动态顺序表可扩容，但扩容需要重新分配和复制。

详见 1.2 顺序表。

二、链式表示#

链式表示把每个元素放入独立结点，用链接字段表达相邻关系。

不要求整体连续：新结点可在可用内存中单独分配。
定位依赖遍历：仅知道逻辑位序时，通常要从入口沿链接前进。
局部修改：已经持有正确前驱或目标结点时，只需修改常数个链接。
附加开销：每个结点需要指针或游标，并承担分配、释放和局部性代价。

详见 1.3 单链表和 1.4 链表变体。

§ 1.1.6 完整示例：连续执行四个操作#

这个例子只确定逻辑结果。
- 若用顺序表实现，操作 2 和操作 3 会移动数组元素；若用单链表实现，则先定位前驱，再调整链接。

§ 1.1.7 边界与失败路径#

空表读取或删除：不存在合法位序，操作应返回失败，不访问存储区。
空表插入：唯一合法位序是 1，成功后新元素同时是表头和表尾。
越界位序：
- 读取、删除要求位序位于 $[1,n]$ 。
- 插入要求位序位于 $[1,n+1]$ 。
重复元素：线性表允许重复值；按值查找、删除全部匹配项等操作必须明确自己的重复值策略。
容量或内存不足：逻辑位序合法不代表实现一定能完成插入。静态数组可能已满，动态分配也可能失败。
无效对象或输出指针：C 接口应先检查必要指针，失败时保持原表不变。
并发修改：本章默认单线程或外部同步；一边遍历一边由其他执行流修改表，会破坏这里的前置条件。

理解检查

线性表 (A, B, A) 为什么不违反定义？
为什么不能直接说 ListInsert 的复杂度一定是 $O(1)$ 或 $O(n)$ ？
长度为 4 的线性表，插入和删除各有哪些合法位序？

参考回答：

线性表要求逻辑位置和相邻关系明确，不要求元素值互不相同；两个 A 位于不同位序。
接口只规定逻辑结果。顺序表可能移动后缀，链表可能先遍历定位；是否已持有结点指针也会改变代价。
插入位序是 1 到 5，删除位序是 1 到 4。

总结#

线性表是同类型元素按逻辑位序组成的有限序列，允许空表和重复值；“有序”只表示先后关系明确。
线性表接口使用从 1 开始的位序：长度为 $n$ 时，读取和删除的合法范围是 $[1,n]$ ，插入的合法范围是 $[1,n+1]$ 。
ADT 只规定操作契约，同一线性表可以用顺序表或链表实现；具体复杂度取决于操作、存储表示和调用时已知的条件。

← 0.2 算法和算法评价 | 00-数据结构 | 1.2 顺序表 →