线性表

考点定位

所属大纲章节：线性表的定义和基本操作、顺序表与链表
常见题型：选择题（操作边界条件、移动次数计算、存储密度、各链表变体适用场景）；算法设计大题（几乎每年一道，链表/顺序表上的原地操作）
考查频率：高。选择题每年 1-2 道，算法大题高频命题区

工程直觉迁移：动态数组 vs linked list 的取舍你天天在做，工程上链表因缓存不友好已基本被弃用——但考试恰恰偏爱考链表（指针操作可控、能出设计题），必须按考纲把指针边界练到肌肉记忆。

核心讲解：顺序表与链表的考点对比

线性表、顺序表与链表的严格定义

线性表：具有相同数据类型的 $n\ (n \ge 0)$ 个数据元素的有限序列，记为 $L = (a_1, a_2, \ldots, a_n)$ 。除首元素 $a_1$ 外每个元素有且仅有一个直接前驱，除尾元素 $a_n$ 外每个元素有且仅有一个直接后继——"一对一"的逻辑关系（逻辑结构的分类见 01-绪论与复杂度分析）。 $n = 0$ 时为空表。
顺序表：用顺序存储实现的线性表——一组地址连续的存储单元依次存放表中元素，逻辑相邻的元素物理位置也相邻，第 $i$ 个元素的存储地址 $\text{Loc}(a_i) = \text{Loc}(a_1) + (i-1) \times L$ （ $L$ 为单个元素大小），因此支持随机存取。
链表：用链式存储实现的线性表——每个结点（数据域 + 指针域）存放一个元素，通过指针链接逻辑前驱后继，逻辑相邻的元素物理位置不一定相邻，只支持顺序存取。

下表的"随机存取 vs 顺序存取"等全部差异都源于这两种存储方式的不同。

对比项	顺序表（数组实现）	单链表
存取方式	随机存取，按位查找 $O(1)$	顺序存取，按位查找 $O(n)$
插入/删除	需移动元素，平均 $O(n)$	已知位置后改指针 $O(1)$
存储密度	$\frac{数据本身}{总存储} = 1$ （无指针开销）	< 1（每个结点带指针域）
空间分配	静态分配可能溢出/预留浪费；动态分配（realloc）需整体搬迁	按需分配，无浪费
逻辑与物理	相邻元素物理相邻	逻辑相邻，物理可不相邻

插入/删除移动次数计算（高频计算题）

设表长 $n$ ，各位置等概率：

操作	移动次数分析	平均次数
在第 $i$ 位插入（ $1 \le i \le n+1$ ）	移动 $n-i+1$ 个元素（第 $n$ 到第 $i$ 位整体后移）	$\frac{1}{n+1}\sum_{i=1}^{n+1}(n-i+1) = \frac{n}{2}$
删除第 $i$ 位元素（ $1 \le i \le n$ ）	移动 $n-i$ 个元素	$\frac{1}{n}\sum_{i=1}^{n}(n-i) = \frac{n-1}{2}$

分步示例（插入 $i=2$ ， $n=5$ ，元素 $a_1..a_5$ ）：

步骤	下标 1	2	3	4	5	6	说明
0（初始）	$a_1$	$a_2$	$a_3$	$a_4$	$a_5$		移动 4 个元素
1	$a_1$	$a_2$		$a_3$	$a_4$	$a_5$	$a_5$ →6
2	$a_1$	$a_2$		$a_3$	$a_4$	$a_5$	$a_4$ →5
3	$a_1$		$a_2$	$a_3$	$a_4$	$a_5$	$a_2$ →3
4	$a_1$	x	$a_2$	$a_3$	$a_4$	$a_5$	空位写入 x

选择题变式："在等概率下，插入时平均移动多少个元素？"答 $\frac{n}{2}$ （不是 $\frac{n+1}{2}$ ）；"删除时"答 $\frac{n-1}{2}$ （不是 $\frac{n}{2}$ ）。这是最经典的计算陷阱。

按位查找

顺序表：L.data[i-1]， $O(1)$ 。选择题坑：位序（1 起）与数组下标（0 起）的换算。
单链表：从头遍历，第 $i$ 个结点需走 $i-1$ 步， $O(n)$ 。按值查找两者都需 $O(n)$ 。

链表变体的操作边界

单链表

结构定义（考试作答时的标准写法）：

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

关键边界规则：

带头结点 vs 不带头结点：头结点使"在第 1 位插入/删除"与中间位置逻辑统一，考试题默认带头结点，题目说不带头结点时要单独处理首元结点（这是高频陷阱）。
插入的指针顺序：在 p 之后插入 s，必须先接后断： s->next = p->next; p->next = s;（顺序颠倒则丢失后半段）
删除：p->next = p->next->next; 前需暂存被删结点 q = p->next; 以便 free(q)。
头插法建表：读入序列 $a_1, a_2, \ldots, a_n$ ，得到链表次序为 $a_n, \ldots, a_1$ （逆序）——选择题直接考；头插法也是"就地逆置"的原理。
尾插法建表：需维护尾指针，结果保持原序。

双链表

typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinklist;

在 p 之后插入 s（四条语句，顺序必须保证不断链）：

s->next = p->next;        // 1
p->next->prior = s;       // 2  （若 p->next 为空则跳过）
s->prior = p;             // 3
p->next = s;              // 4

坑：p 是尾结点时 p->next 为 NULL，语句 2 不可执行——代码题里要么判空，要么题目保证非尾部。

循环链表

变体	判空条件	尾操作
循环单链表（带头结点）	`L->next == L`	从任意结点可达全表
循环单链表（仅设尾指针 `r`）	`r->next == r` 或按头结点判断	头 = `r->next->next`，尾指针下在表尾/表头插入删除均为 $O(1)$

经典选择题："在循环单链表中，设 rear 指针比设 head 指针的优势是？"——尾插/两表合并 $O(1)$ ：p = r->next; r->next = q->next->next; ... 合并两表不需遍历找尾。

静态链表

用数组 + 游标（cur）模拟指针，适合不支持指针的语言。考点：插入删除不需移动元素，仍需修改游标，且没有改善按位查找的效率（仍 $O(n)$ ）；存储密度低于顺序表。

408 算法题的类 C 伪代码规范（如何拿结构分）

408 算法大题（约 13-15 分）按步骤给分：思路（文字/流程说明）→ 类 C 伪代码 → 时间/空间复杂度分析。规范要点：

语言：类 C 代码即可，不要求编译通过，但语法不能面目全非。变量先声明后使用；结点类型定义可直接引用题面已给结构。
注释：关键行加简短注释，阅卷按"功能块"给分，注释帮助阅卷人定位你的意图。
边界：空表、单元素、i 非法等边界判断写出来就是分。判空 if (L == NULL || L->next == NULL) return; 一行值 1-2 分。
返回值：按题面要求返回（如找到返回 1 找不到返回 0），题目没要求时选一个并在说明里讲清楚。
复杂度分析必写：最后一问通常明确"分析本算法的时间和空间复杂度"，不写直接丢分。
禁止：直接调库函数假装完成（如直接 qsort）；引用未定义的魔法函数。所有辅助函数要么给出定义，要么用自然语言注明"其功能为 XX"。

真题风格算法设计题

题 1（2010 年 408 真题改编，结构同源）

题目：设将 $n\ (n>1)$ 个整数存放到一维数组 R 中。试设计一个在时间和空间两方面都尽可能高效的算法，将 R 中保存的序列循环左移 $p\ (0 < p < n)$ 个位置，即将 R 中的数据由 $(X_0, X_1, \ldots, X_{n-1})$ 变换为 $(X_p, X_{p+1}, \ldots, X_{n-1}, X_0, \ldots, X_{p-1})$ 。要求：

给出算法的基本设计思想；
根据设计思想，采用类 C 语言描述；
说明算法的时间复杂度和空间复杂度。

完整解答

思路：整体逆置三次。将数组视为两段 $A = (X_0..X_{p-1})$ 、 $B = (X_p..X_{n-1})$ ，目标为 $BA$ 。利用 $(A^r B^r)^r = BA$ （ $r$ 表示逆置）：

逆置前 $p$ 个元素；
逆置后 $n-p$ 个元素；
整体逆置。

分步演示（ $n=5$ ， $p=2$ ，R = a b c d e，待动画化）：

步骤	数组内容	操作
初始	a b c d e
1	b a c d e	逆置前 2 个
2	b a e d c	逆置后 3 个
3	c d e a b	整体逆置，得 $BA$

伪代码：

// 将 R[left..right] 逆置（闭区间）
void Reverse(int R[], int left, int right) {
    int i = left, j = right, tmp;
    while (i < j) {              // 首尾对称交换
        tmp = R[i];
        R[i] = R[j];
        R[j] = tmp;
        i++;  j--;
    }
}

void LeftShift(int R[], int n, int p) {
    if (p <= 0 || p >= n) return;   // 边界：非法 p 直接返回
    Reverse(R, 0, p - 1);           // 逆置 A
    Reverse(R, p, n - 1);           // 逆置 B
    Reverse(R, 0, n - 1);           // 整体逆置
}

复杂度分析：三段逆置的交换次数分别为 $\lfloor p/2 \rfloor$ 、 $\lfloor (n-p)/2 \rfloor$ 、 $\lfloor n/2 \rfloor$ ，合计约 $n$ 次交换，总时间 $O(n)$ ；只用 tmp 常数辅助单元，空间 $O(1)$ 。

评分要点对照：思路中写出"数学恒等式 $(A^rB^r)^r = BA$ "是满分思路分的关键；若用辅助数组 $O(n)$ 空间或逐个左移 $O(np)$ 时间，会因"未尽可能高效"扣思路分。

题 2（2009 年 408 真题，链表经典）

题目：已知一个带有头结点的单链表，结点结构为 (data, next)，假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第 $k$ 个位置上的结点（ $k$ 为正整数）。若查找成功，输出该结点的 data 值并返回 1；否则返回 0。要求给出基本设计思想、类 C 描述、时间空间复杂度。

完整解答

思路：双指针（间隔指针）一次遍历。设 $p$ 、 $q$ 均从头出发，先让 $q$ 沿 next 走 $k-1$ 步（到达正数第 $k$ 个结点），随后 $p$ 、 $q$ 同步后移； $q$ 到达尾结点时， $p$ 恰指向倒数第 $k$ 个结点（ $p$ 与 $q$ 相距恒为 $k-1$ ）。

分步演示（链表 a→b→c→d→e， $k=2$ ，待动画化）：

步骤	p 位置	q 位置	说明
0	头结点	头结点	起始
1	头结点	a（走 1 步）	q 先走 $k-1=1$ 步
2	a	b	同步后移
3	b	c	同步后移
4	c	d	同步后移
5	d	e（尾结点）	停止：p 指向倒数第 2 个结点 d

伪代码：

typedef struct LNode {          // 结点定义
    int data;
    struct LNode *next;
} LNode, *LinkList;

int FindKthFromEnd(LinkList list, int k) {
    LNode *p = list->next, *q = list->next;   // 均指向首元结点
    if (k <= 0) return 0;                     // 边界：k 非法
    while (k > 1 && q != NULL) {              // q 先走 k-1 步
        q = q->next;
        k--;
    }
    if (q == NULL) return 0;                  // 表长不足 k，查找失败
    while (q->next != NULL) {                 // 同步后移直到 q 为尾结点
        p = p->next;
        q = q->next;
    }
    printf("%d", p->data);
    return 1;
}

复杂度分析：时间 $O(n)$ （一遍扫描）；空间 $O(1)$ （两个指针）。

命题陷阱：若先遍历求表长 $n$ 再走 $n-k$ 步，同样是 $O(n)$ ，但需要两遍扫描，题面"尽可能高效"下双指针版是最优答法（一遍）。k > 表长 的失败分支必须显式处理，否则扣边界分。

常见坑

位序 vs 下标：题面"第 i 个元素"是 1 起位序，数组下标是 $i-1$ ；自己设的游标变量在伪代码里要交代清楚从 0 还是从 1 开始。
带头结点与否：题干画图带头结点但你的代码没写 L->next 取首元，属审题失误；反之亦然。
"链表插入删除 O(1)"的隐含前提：是在已定位的结点处操作；若包含查找定位过程，仍是 $O(n)$ 。选择题最爱挖这一点。
存储密度： $\text{存储密度} = \frac{数据域所占空间}{结点总空间}$ ，链表因指针域小于 1；顺序表为 1。问"空间利用率"指同一概念。
顺序表按值查找：无序表需 $O(n)$ 全表扫描，有序表提前终止也不能改进最坏 $O(n)$ （二分要"可随机存取"前提，顺序表满足，但题面问"顺序表按值查找"默认线性扫描）。

自测

表长 $n=100$ 的顺序表，等概率删除一个元素平均移动多少次？在末尾插入移动多少次？
不带头结点的单链表 H，删除首元结点的语句序列是什么？与带头结点时的差别？
双链表中在 p 之前插入 s 的语句（利用 prior 指针，4 条）？
判断：循环单链表任何结点出发都能遍历全表，因此按位查找的平均时间比普通单链表低。（对/错）
设计思路一句话：如何用单链表实现"时间上尽可能高效"的就地逆置（不申请新结点）？

答案与简析

删除平均 $\frac{n-1}{2} = 49.5$ 次；末尾插入（第 $n+1$ 位）移动 0 次。
不带头结点：q = H; H = H->next; free(q);。带头结点：首元结点与中间结点统一为 q = L->next; L->next = q->next; free(q);。
s->prior = p->prior; p->prior->next = s; s->next = p; p->prior = s;（对称于"之后插入"）。
错。遍历可达性不等于查找效率，仍需 $O(n)$ ，平均比较次数不降。
头插法：依次取原表结点插到头结点之后，p=L->next; L->next=NULL; 后逐个头插， $O(n)$ 时间、 $O(1)$ 空间。

下一步：学完本章 → 做 01-线性表与栈队列-章节测校验掌握度。

#线性表

#考点定位

#核心讲解：顺序表与链表的考点对比

#线性表、顺序表与链表的严格定义

#插入/删除移动次数计算（高频计算题）

#按位查找

#链表变体的操作边界

#单链表

#双链表

#循环链表

#静态链表

#408 算法题的类 C 伪代码规范（如何拿结构分）

#真题风格算法设计题

#题 1（2010 年 408 真题改编，结构同源）

#题 2（2009 年 408 真题，链表经典）

#常见坑

#自测

线性表