# 第 2 章 线性表（示例讲义）

> 本文件是示例知识库的演示材料，为简化版讲义提纲。

## 2.1 线性表的定义

线性表是 n (n≥0) 个数据元素的有限序列。除首尾元素外，
每个元素有且仅有一个直接前驱和一个直接后继。

## 2.2 顺序表（顺序存储）

用一段连续的存储单元依次存放线性表元素，逻辑相邻 = 物理相邻。

- **随机存取**：按下标访问任意元素 O(1) —— 顺序表最大优势。
- **插入**：在第 i 个位置插入需要把后面 n-i+1 个元素整体后移，
  平均移动 n/2 个元素，时间复杂度 O(n)。
- **删除**：同理需要前移，平均移动 (n-1)/2 个元素，O(n)。
- 缺点：需要预分配空间，可能溢出或浪费；插删代价高。

## 2.3 单链表（链式存储）

每个结点 = 数据域 + 指针域（next）。逻辑相邻不要求物理相邻。

- **按位查找** O(n)：必须从头结点开始顺链扫描，不支持随机存取。
- **插入/删除** O(1)（在已知前驱结点 p 时）：
  插入 s：`s->next = p->next; p->next = s;`（顺序不能颠倒！）
  删除 p 的后继：`q = p->next; p->next = q->next; free(q);`
- 头结点的作用：统一空表与非空表、首位置与其他位置的操作逻辑。

## 2.4 其他链表变体

- **双向链表**：每个结点增加 prior 指针，可双向扫描；
  插删需要同时修改 4 个指针。
- **循环链表**：尾结点 next 指回头结点，从任一结点可遍历全表；
  设尾指针 rear 后，访问表头 rear->next->next 和表尾 rear 都是 O(1)。
- **静态链表**：用数组模拟指针（游标 cur），适用于不支持指针的语言。

## 2.5 顺序表 vs 链表的选择

| 维度 | 顺序表 | 链表 |
|---|---|---|
| 随机存取 | O(1) ✓ | O(n) |
| 插入/删除 | O(n)（移动元素） | O(1)（已知位置） |
| 空间 | 预分配，可能浪费/溢出 | 按需分配，有指针开销 |
| 适用 | 读多写少、规模可估 | 频繁插删、规模未知 |

## 本章要点（考试常考）

1. 顺序表插入/删除平均移动元素次数的推导（必考计算题）。
2. 单链表插入删除的指针操作语句及顺序（必考代码题）。
3. 头结点 vs 头指针的区别。
4. 给定场景选择存储结构并说明理由（简答题）。
