考频地图
线性表本身的选择题不难,但它是 408 算法设计题(13–15 分)最常见的素材:几乎每年第 41 或 42 题都要求在数组或链表上设计一个高效算法。本章最后有历年真题的思路汇总。
| 考点 | 考频 | 常见问法 |
|---|---|---|
| 顺序表的随机存取与插删 | ★★★☆☆ | “插入第 i 个位置需移动多少元素” |
| 单链表的插入删除 | ★★★★☆ | “下列语句序列能正确插入结点的是” |
| 双链表、循环链表 | ★★★☆☆ | “删除尾结点 / 插入表尾,哪种链表最省时间” |
| 顺序表 vs 链表选择 | ★★★☆☆ | “最常用操作是……,宜采用” |
| 算法设计题 | ★★★★★ | 数组 / 链表上的时间、空间最优算法 |
顺序表
用一组地址连续的存储单元依次存放线性表的元素。第 i 个元素(从 1 起)的地址:
插入与删除要移动多少元素
| 操作 | 移动次数 | 最好 | 最坏 | 等概率平均 |
|---|---|---|---|---|
| 在第 i 个位置插入(1 ≤ i ≤ n+1) | n − i + 1 | 0(表尾) | n(表头) | n / 2 |
| 删除第 i 个元素(1 ≤ i ≤ n) | n − i | 0(表尾) | n − 1(表头) | (n − 1) / 2 |
| 按值查找 | 比较 i 次 | 1 | n | (n + 1) / 2 |
bool ListInsert(SqList &L, int i, ElemType e) { if (i < 1 || i > L.length + 1 || L.length == MaxSize) return false; for (int j = L.length; j >= i; j--) // 从后往前,把 i…n 后移一位 L.data[j] = L.data[j - 1]; L.data[i - 1] = e; // 位序 i 对应下标 i−1 L.length++; return true; }
- 插入时元素要从后往前移,删除时从前往后移,否则会覆盖。
- “位序”从 1 开始,数组下标从 0 开始,题目里要分清。
链表
一、单链表:插入与删除
头结点:在第一个数据结点前附设的结点(数据域可不存信息)。好处:① 在第一个位置插入删除与其他位置操作统一;② 空表与非空表处理统一(头指针永远非空)。
// 每个新结点都插到头结点之后 s->next = L->next; L->next = s; // 输入 1 2 3 → 链表 3 2 1 // 链表逆置就用这个思路
// r 始终指向表尾 r->next = s; r = s; // 最后 r->next = NULL
“已知结点 p,删除 p 本身”的技巧:把后继的值复制到 p,再删后继(O(1),但 p 是尾结点时不行)。
二、双链表:多一个前驱指针
三、循环链表与静态链表
| 结构 | 特点 | 常考结论 |
|---|---|---|
| 循环单链表 | 尾结点指向头结点 | 若只设尾指针 r:表头 r->next、表尾 r 都能 O(1) 找到,适合频繁在两端操作 |
| 循环双链表 | 头结点的 prior 指向尾结点 | 删除尾结点、在尾部插入都是 O(1) |
| 静态链表 | 用数组实现,“指针”是下一个元素的数组下标(游标),−1 表示结束 | 插删不需移动元素,但仍要预先分配连续空间 |
选链表类型的题:“最常用操作是在最后一个元素后插入和删除最后一个元素”→ 删除表尾需要找到它的前驱,只有带头结点的双循环链表能 O(1) 完成;“在表尾插入、删除第一个元素”→ 只设尾指针的循环单链表即可。
- 插入时先改新结点的指针,再改原链表的指针;顺序反了会“断链”。
- 单链表找前驱要 O(n),所以单链表上“删除尾结点”是 O(n),即使有尾指针也一样。
- 链表的存储密度 < 1(每个结点有指针域)。
顺序表 vs 链表
| 对比 | 顺序表 | 链表 |
|---|---|---|
| 存取方式 | 随机存取 O(1) | 顺序存取 O(n) |
| 插入删除 | 平均移动一半元素 O(n) | 修改指针 O(1)(找位置 O(n)) |
| 空间 | 需预先分配连续空间;存储密度 = 1 | 按需分配,不需连续;有指针开销 |
| 适合 | 表长稳定、频繁按序号查找 | 表长变化大、频繁插删 |
线性表算法题:思路与模板
算法设计题的评分一般是:设计思想(3–4 分)+ 代码(7–8 分)+ 复杂度(2 分)。写不出最优解时,写出正确的暴力解通常也能拿到大部分分数——不要空着。
- 设计思想:用 2–4 句话说清“怎么做”和“为什么对”。
- 代码:C/C++ 皆可,关键处写注释;给出函数头和用到的结构体定义。
- 复杂度:时间、空间各一句。
历年线性表算法题一览
| 年份 | 题意 | 最优思路 | 时间 / 空间 |
|---|---|---|---|
| 2009 | 单链表倒数第 k 个结点 | 双指针:先让快指针走 k 步,再快慢同步走,快指针到表尾时慢指针即所求 | O(n) / O(1) |
| 2010 | 数组循环左移 p 位 | 三次逆置:逆置前 p 个、逆置后 n−p 个、再整体逆置 | O(n) / O(1) |
| 2011 | 两个等长升序序列的中位数 | 比较两序列中位数 a、b:相等即答案;a < b 则舍弃 A 的较小半与 B 的较大半,递归 | O(log n) / O(1) |
| 2012 | 两个单词链表的共同后缀起点 | 先求两表长度,长表先走差值步,然后同步走,第一个相同地址的结点 | O(m + n) / O(1) |
| 2013 | 找数组的主元素(出现 > n/2 次) | 摩尔投票:候选 c、计数 count,相同 +1 不同 −1,减到 0 换候选;最后再数一遍确认 | O(n) / O(1) |
| 2015 | 删除链表中绝对值重复的结点(|data| ≤ n) | 开辅助数组 flag[n+1] 标记出现过的绝对值,再次出现就删 | O(m) / O(n) |
| 2016 | 把集合分成两半使元素个数差最小、和之差最大 | 基于快排划分找第 ⌊n/2⌋ 小元素 | 平均 O(n) / O(1) |
| 2018 | 数组中未出现的最小正整数 | 辅助数组 B[1..n] 标记 1~n 中出现过的数,第一个未标记的下标即答案 | O(n) / O(n) |
| 2019 | 链表重排为 a₁, aₙ, a₂, aₙ₋₁, … | 快慢指针找中点 → 逆置后半段 → 两段交替合并 | O(n) / O(1) |
| 2020 | 三个升序数组中三元组的最小距离 | 三指针,每次让当前最小值的指针后移,同时更新最小距离 | O(n) / O(1) |
三个必须能默写的小算法
void Reverse(int a[], int l, int r) { while (l < r) { int t = a[l]; a[l] = a[r]; a[r] = t; l++; r--; } }
void ReverseList(LinkList L) { LNode *p = L->next, *r; L->next = NULL; while (p) { r = p->next; // 先记住后继 p->next = L->next; // 头插 L->next = p; p = r; } }
LNode *slow = L->next, *fast = L->next; while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } // slow 指向中间(偶数个时为后半段第一个)
while (i < m && j < n) C[k++] = A[i] <= B[j] ? A[i++] : B[j++]; while (i < m) C[k++] = A[i++]; while (j < n) C[k++] = B[j++];
真题与自测
一、真题问法
问法 1:“在长度为 n 的顺序表第 i 个位置插入元素,需后移几个元素?”→ n − i + 1。
问法 2:“某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用哪种存储最节省运算时间?”→ 仅有尾指针的单循环链表。
问法 3(算法题):见上表;高频套路是双指针、逆置、辅助数组标记、摩尔投票。
二、折叠自测
1. 顺序表第 1 个元素地址为 100,每个元素 4 字节,第 5 个元素的地址?
100 + (5 − 1) × 4 = 116。
2. 在单链表 p 结点之后插入 s,正确的语句顺序?
s->next = p->next; p->next = s;
3. 为什么要设头结点?
使在第一个位置插入删除的操作与其他位置一致;空表与非空表处理一致。
4. 长度为 n 的单链表,已知尾指针,删除尾结点的时间复杂度?
O(n):需要找到尾结点的前驱,单链表只能从头遍历。
5. 静态链表中的“指针”是什么?
下一个元素在数组中的下标(游标)。
6. 数组循环左移 p 位,如何做到 O(1) 空间?
三次逆置:Reverse(0, p−1)、Reverse(p, n−1)、Reverse(0, n−1)。
三、考前速览
顺序表随机存取,插删移动一半。
链表先连新链,再断旧链。
算法题:思想 + 代码 + 复杂度。
① 插入从后往前移,删除从前往后移。
② 单链表删尾结点是 O(n)。
③ 位序从 1、下标从 0。