第 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)（已知位置）
空间	预分配，可能浪费/溢出	按需分配，有指针开销
适用	读多写少、规模可估	频繁插删、规模未知

本章要点（考试常考）

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