数据结构复习

数据结构期末复习大纲

发表于 2026/01/06 更新于 2026/01/06

作者 Metahumanz

66 分钟阅读

数据结构复习

分章节大纲

复习总方针：

选择题 (50分)：重点在于“性质”和“细节”。不要死记代码，要记结论（如：时间复杂度、稳定性、适用场景）。
大题 (50分)：
- 编程 (1题)：集中在线性表（数组/链表）和递归。重点是写出核心逻辑接口。
- 简答 (4题)：集中在树和图的手工模拟（画图）和原理分析。

第一章：绪论 (基础概念)

重点 (选择题)：
- 时间复杂度：会计算基本算法的 $O(n)$, $O(n^2)$, $O(\log n)$。
- 数据结构三要素：逻辑结构（线性/非线性）、存储结构（顺序/链式）、运算。

第二章：线性表 (编程题重灾区 & 简答)

1. 顺序表 (数组)

编程重点：数组原地置换
- 场景：将数组逆序、或按特定条件（如奇偶）重新排列，要求空间复杂度 $O(1)$。
- 思路：双指针法。
  - 定义 i 指向头，j 指向尾。
  - 当 i < j 时，检查 a[i] 和 a[j] 是否满足交换条件。
  - 若满足则 swap(a[i], a[j])，然后 i++, j--。
稀疏矩阵 (简答题考点)
- 定义：非零元素很少的矩阵。
- 存储：三元组表 (row, col, value)。
- 性质：
  - 转置算法：普通转置复杂度 $O(cols \times terms)$；快速转置（使用辅助数组记录每列元素个数）复杂度 $O(cols + terms)$。

2. 链表 (单链表/双链表)

编程重点 1：链表元素互换
- 场景：交换链表中两个节点 p 和 q（不是仅交换数据域，是换节点）。
- 思路：
  1. 必须找到 p 的前驱 pre_p 和 q 的前驱 pre_q。
  2. 修改前驱的 next 指针：pre_p->next = q, pre_q->next = p。
  3. 交换 p 和 q 的 next 指针：temp = p->next; p->next = q->next; q->next = temp;。
  4. 注意：处理头节点和相邻节点的特殊情况。
编程重点 2：链表合并
- 场景：将两个有序链表 A, B 合并为有序链表 C。
- 思路：
  1. 维护三个指针 pa (指向A), pb (指向B), pc (指向C, 初始为头节点)。
  2. 循环比较 pa->data 和 pb->data。
  3. 将较小的一个链接到 pc->next，并移动该链表的指针（如 pa = pa->next）。
  4. pc 指针后移。
  5. 循环结束后，将非空的那条链表剩余部分直接链到 pc 后面。

第三章：栈与队列 (简答题逻辑)

后缀表达式 (重点)
- 概念：操作符在操作数之后，如 3 4 + 表示 3+4。
- 求值思路：
  1. 从左到右扫描。
  2. 遇到数字：压入栈。
  3. 遇到运算符：弹出栈顶两个元素，进行计算，将结果压入栈。
- 中缀转后缀（栈的应用）：数字直接输出，运算符按优先级入栈/出栈。

第五章：递归与广义表 (编程 & 概念)

编程重点：递归
- 核心套路：
  1. 终止条件 (Base Case)：什么时候停止？（如 node == NULL 或 n == 0）。
  2. 递归步骤 (Recursive Step)：如何缩小问题规模？（如 f(n-1) 或 f(node->next)）。
- 典型题目：求阶乘、斐波那契、链表长度、二叉树深度。

第六章：树与森林 (简答题核心)

本章是简答题的重中之重，需掌握画图和手动模拟。

堆 (Heap)
- 定义：完全二叉树。大顶堆（父 $\ge$ 子），小顶堆（父 $\le$ 子）。
- 建堆过程：从最后一个非叶子节点开始，依次进行向下调整 (FilterDown)。
- 插入：放到末尾 $\rightarrow$ 向上调整。
- 删除：输出堆顶 $\rightarrow$ 将末尾元素移到堆顶 $\rightarrow$ 向下调整。
霍夫曼树 (Huffman Tree)
- 定义：带权路径长度 (WPL) 最小的二叉树，用于数据压缩编码。
- 构建算法：
  1. 在集合中选出两个权值最小的树。
  2. 合并它们，新根权值为两者之和。
  3. 将新树放回集合，删除原两树。
  4. 重复直到只剩一棵。
- 霍夫曼编码：左分支记0，右分支记1。前缀编码特性（任一编码不是另一编码的前缀）。
AVL树 (平衡二叉搜索树)
- 定义：任意节点左右子树高度差绝对值 $\le 1$。
- 旋转 (必考)：当插入导致失衡时：
  - LL型 (左子树的左边插入)：右单旋。
  - RR型 (右子树的右边插入)：左单旋。
  - LR型 (左子树的右边插入)：先左旋后右旋。
  - RL型 (右子树的左边插入)：先右旋后左旋。

第八章：图 (Graph) (简答题核心)

本章考察算法的执行过程（通常是填表或画图）以及性质。

存储表示
- 邻接矩阵：二维数组。空间 $O(n^2)$。适合稠密图。判断两点是否有边快。
- 邻接表：链表数组。空间 $O(n+e)$。适合稀疏图。找邻接点快。
遍历
- DFS (深度优先)：一条路走到黑，撞墙回溯。使用栈或递归。
- BFS (广度优先)：层层递进。使用队列。
环的判断
- DFS法：遍历中遇到已访问的节点（且不是父节点）说明有环。
- 拓扑排序法：如果排序结束后输出的顶点数 < 总顶点数，说明有环（因为环上的点入度永远不为0）。
最小生成树 (MST)
- 概念：连通图的极小连通子图，包含所有顶点，边权和最小。
- 唯一性：如果图中所有边权值不同，MST唯一。如果有相同权值边，MST形状可能不唯一，但总权值和唯一。
- Prim算法：
  - 思路：关注点。从一个点开始，每次选离生成树集合最近的一个点加入。
  - 适用：稠密图。
- Kruskal算法：
  - 思路：关注边。将边按权值从小到大排序，依次选边，若不构成回路（用并查集判断）则加入。
  - 适用：稀疏图。
最短路径
- Dijkstra算法 (单源最短路)：
  - 思路：贪心。维护 dist[] 数组。
  - 步骤：每次从未访问点中选 dist 最小的点 $u$，标记 $u$，然后松弛（更新）$u$ 的所有邻接点 $v$：若 dist[u] + weight(u,v) < dist[v]，则更新 dist[v]。
AOV网 (拓扑排序)
- 定义：顶点表示活动，边表示先后关系。
- 算法：
  1. 找入度为0的顶点输出。
  2. 删除该顶点及所有出边（更新邻接点入度）。
  3. 重复直到空。
AOE网 (关键路径)
- 定义：边表示活动，顶点表示事件。
- 概念：
  - 关键路径：从源点到汇点路径长度最长的路径。决定工期。
  - ve (最早发生)：从前往后推，取max。
  - vl (最迟发生)：从后往前推，取min。
  - 关键活动：满足 $e=l$ (最早开始时间=最迟开始时间) 的活动。
  - 加速工程：必须缩短关键路径上的活动时间。注意：如果有多条关键路径，必须同时缩短它们共有的活动，或者分别缩短每条路径上的活动，否则工期不变。

第九章：排序 (选择题核心)

主要记忆排序.txt中的总结，用于做选择题。

稳定性：
- 稳定：归并、插入、冒泡、基数。 (口诀：情绪稳定的人容易被归类，插队如果不冒泡就很稳)
- 不稳定：快速、堆、选择。 (口诀：快点选一堆)
时间复杂度：
- $O(n \log n)$ (快)：快速排序、堆排序、归并排序。
- $O(n^2)$ (慢)：直接插入、冒泡、直接选择。
- 特殊：基数排序 $O(d(n+r))$。
性质细节：
- 快速排序：最坏情况退化为 $O(n^2)$（已有序时）。
- 堆排序：空间复杂度 $O(1)$，适合Top K问题。
- 归并排序：空间复杂度 $O(n)$，最稳的 $O(n \log n)$。

分章节详细

一、顺序表 (数组)

在考试中，顺序表通常就是一个 Array 或者 Vector。

1. 编程重点：数组原地置换

题目要求：通常要求空间复杂度 $O(1)$，意思是不能开辟一个新的数组来存结果，必须在原数组上改。

经典场景 A：数组逆序 (将 [1,2,3,4,5] 变成 [5,4,3,2,1])
- 逻辑：首尾对调。
- 步骤：
  1. 设两个指针（下标）：i 指向头 (0)，j 指向尾 (n-1)。
  2. 只要 i < j，就交换 a[i] 和 a[j]。
  3. i 向后走 (i++)，j 向前走 (j--)。
  4. 相遇时结束。
经典场景 B：奇偶分开 (将所有奇数移到左边，偶数移到右边)
- 逻辑：双指针扫描（类似快速排序的 Partition 操作）。
- 步骤：
  1. i 从左往右扫，j 从右往左扫。
  2. i 找偶数（因为它占了奇数的位置），j 找奇数。
  3. 如果找到了且 i < j，交换它们。
  4. 继续直到 i 和 j 相遇。

2. 稀疏矩阵 (简答题考点)

背景：一个 $1000 \times 1000$ 的矩阵，只有 10 个非零元素。如果存二维数组，浪费 999990 个空间。

存储结构：三元组表 (Triple Table)

只存非零元素。结构体长这样：

        
      
struct Term {
    int row;    // 行号
    int col;    // 列号
    int value;  // 值
};

最后把所有 Term 放在一个数组里。

核心算法：转置 (Transpose)
- 普通转置：
  - 思路：扫描所有列（1到cols）。对于每一列，去遍历三元组表，找到属于这一列的元素，把行列互换存入新表。
  - 缺点：如果非零元素多，每次都要遍历整个表，慢。复杂度 $O(cols \times terms)$。
- 快速转置 (Fast Transpose) —— 重点：
  - 思路：空间换时间。
  - 步骤：
    1. 统计：先扫一遍三元组，统计每一列有多少个非零元素（存入 num[] 数组）。
    2. 定位：计算每一列转置后，在新三元组表中的起始位置（存入 cpot[] 数组）。比如第1列有2个元素，那第2列的起始位置就是 2。
    3. 搬运：再扫一遍三元组，根据元素的列号查 cpot，直接放到新表的正确位置。
  - 优点：只需要扫两遍。复杂度 $O(cols + terms)$。

二、链表 (编程题重灾区)

链表的题，画图是解题的唯一真理。一定要画框框和箭头！

1. 编程重点：链表元素互换 (Swap)

题目：在单链表中交换节点 p 和 q（假设 p 在 q 前面）。陷阱：如果不让你交换数据域（data），只准换指针，这题就有点难度。

核心逻辑：要动节点 p，必须掌握它的前驱（它前面的那个节点）。
1. 找人：遍历链表找到 p 的前驱 pre_p 和 q 的前驱 pre_q。
2. 接头：把 pre_p 的 next 指向 q；把 pre_q 的 next 指向 p。（此时两个节点的前面连好了）。
3. 接尾：这也是最容易错的。需要借用临时变量。
  1 2 3 temp = p->next; p->next = q->next; // p 接上 q 原来的尾巴 q->next = temp; // q 接上 p 原来的尾巴
特殊情况 (必背)：
- 相邻：如果 p 和 q 挨着（p->next == q），那么 pre_q 其实就是 p。上面的通用逻辑会出错（死循环或断链）。需要单独处理：直接 pre_p->next = q; p->next = q->next; q->next = p;。
- 头节点：如果 p 是头节点，没有 pre_p，需要特判或者使用虚拟头节点 (dummy head)。

2. 编程重点：链表合并 (Merge)

题目：合并两个有序链表 A 和 B，生成一个新的有序链表 C。

核心逻辑：尾插法。
变量准备：
- pa：指向链表 A 当前比对的节点。
- pb：指向链表 B 当前比对的节点。
- pc：指向链表 C 的尾部（永远指向最后一个节点，方便往后接）。
步骤：
1. 比大小：
  - 当 pa 和 pb 都不为空时：
  - 如果 pa->data < pb->data：把 pa 接到 pc 后面 (pc->next = pa)，pa 往后走，pc 往后走。
  - 否则：把 pb 接到 pc 后面，pb 往后走，pc 往后走。
2. 接剩余：
  - 循环结束后，肯定有一个链表先空了，另一个还没空。
  - 直接把没空的那个链表剩下的一串，一次性接到 pc 后面（pc->next = pa ? pa : pb）。
  - 注意：这里不需要循环，因为剩下的本来就是有序且连在一起的，直接接链表头即可。

复习小贴士

对于顺序表：记住 i (头) 和 j (尾) 双向奔赴的模型，这是解决大多数 $O(n)$ 复杂度问题的钥匙。
对于链表：考试时如果脑子卡壳，先处理前驱，再处理后继。永远不要先断开链表再想怎么连回去，要先连上新的，再断开旧的。

第三章：栈与队列 (重点考察：后缀表达式与逻辑)

这部分主要在选择题中考察，偶尔出现在简答题的计算步骤中。

1. 后缀表达式 (Reverse Polish Notation, RPN)

这是本章最核心的考点。

基本概念：
- 中缀表达式：我们日常用的数学写法，如 A + B。
- 后缀表达式：运算符在操作数之后，如 A B +。
- 优势：计算机处理时不需要考虑括号优先级，线性扫描即可。
考点 A：后缀表达式求值 (必会)
- 算法思路（常考手动模拟栈的变化）：
  1. 从左到右扫描表达式。
  2. 遇到操作数（数字）：压入栈中。
  3. 遇到运算符（如 +, -, *, /）：
    - 连续弹出栈顶的两个数。
    - 注意顺序：先弹出的数是右操作数，后弹出的是左操作数（对减法和除法很重要，如 A - B，先弹出 B，再弹出 A）。
    - 执行计算（左操作右）。
    - 将结果压回栈中。
  4. 扫描结束，栈顶元素即为最终结果。
考点 B：中缀转后缀 (手算技巧)
- 不需要死记硬背程序代码，考试通常让你选出转换正确的结果。
- 手算技巧（加括号法）：
  1. 按照运算符优先级，给中缀表达式的所有运算单位都加上括号。
  2. 把运算符移到对应的右括号后面。
  3. 去掉所有括号。
- 示例：a + b * c - (d + e)
  1. 加括号：((a + (b * c)) - (d + e))
  2. 移符号：((a (b c)*)+ (d e)+)-
  3. 去括号：a b c * + d e + -
- 程序思路（栈的应用）：
  - 遇到数字直接输出；
  - 遇到运算符，与栈顶运算符比优先级：若当前优先级高于栈顶，入栈；否则，弹出栈顶直到栈顶优先级更低。
  - 遇到 )，弹出直到 (。

2. 队列 (简单概念)

循环队列：
- 为了解决顺序队列“假溢出”的问题（即前面有空位但队尾指针已达上限）。
- 关键公式（选择题常考）：
  - 队满条件：(rear + 1) % MaxSize == front (通常会浪费一个空间来区分空和满)。
  - 队空条件：rear == front。
  - 队列长度：(rear - front + MaxSize) % MaxSize。

第五章：递归与广义表 (编程核心 & 概念陷阱)

这一章是你提到的编程题重点区域，同时广义表的Head/Tail操作是选择题的常客。

1. 递归 (Recursion) —— 编程题核心

递归不是一种数据结构，而是一种算法设计思想。编程题中，关于链表和树的操作非常喜欢用递归，因为代码短，逻辑清晰（虽然空间复杂度高）。

递归解题“三部曲” (通用模板)：
1. 找终止条件 (Base Case)：
  - 什么情况下不需要计算直接返回？通常是 n=0，node=NULL，或者start > end。
2. 找递归关系 (Recursive Relation)：
  - 假设函数 f(n) 已经能解决 n 的问题，那么 f(n) 和 f(n-1) 的关系是什么？
  - 例如阶乘：f(n) = n * f(n-1)。
3. 缩小规模：
  - 每次调用必须离终止条件更近一步。
常考递归编程场景：
- 场景 A：单链表操作 (比数组递归难理解一点)
  - 题目：递归求链表中的最大值。
  - 思路：
    1. 终止：如果当前节点是空，返回一个极小值；如果下个节点空，返回当前值。
    2. 递归：max_rest = f(p->next) （先去求后面所有节点的最大值）。
    3. 逻辑：return (p->data > max_rest) ? p->data : max_rest;。
- 场景 B：二叉树操作 (天然递归)
  - 题目：求二叉树深度。
  - 思路：
    1. 终止：if (!root) return 0;
    2. 递归：left_h = f(root->left); right_h = f(root->right);
    3. 逻辑：return max(left_h, right_h) + 1;
- 场景 C：斐波那契/阶乘
  - 这是送分题，记住公式即可。f(n) = f(n-1) + f(n-2)。

2. 广义表 (Generalized Lists) —— 选择题/简答题陷阱

定义：$LS = (a_1, a_2, \dots, a_n)$。元素 $a_i$ 可以是原子（单个数据），也可以是子表。
重要概念：长度与深度
- 长度：最外层包含的逗号数 + 1。即第一层元素的个数。
- 深度：括号嵌套的最大层数。
核心考点：表头 (Head) 与表尾 (Tail)
- Head(LS)：列表的第一个元素。可以是原子，也可以是列表。
- Tail(LS)：除去第一个元素后，剩下所有元素组成的列表。
- 注意！注意！：表尾一定是一个列表（List），即使只剩下一个元素，也要加括号。
- 实战演练（假设 $L = (a, (b, c))$）：
  1. Head(L) = a （拿出来是什么就是什么）
  2. Tail(L) = ((b, c)) （剩下的部分外面套个括号）
  3. Head(Tail(L)) = (b, c) （拿出第一个元素，是个表）
  4. Head(Head(Tail(L))) = b （拿到原子了）

复习小结：如何准备这两章？

针对编程题：
- 不要背大段代码，而是去理解递归的“相信”机制（相信 f(n-1) 能算出结果，我只需要处理 n 和 n-1 的关系）。
- 在纸上写一遍“递归求链表节点个数”和“递归求二叉树高度”的代码。这很可能是考试的原型。
针对选择题：
- 拿笔在纸上算一遍中缀转后缀。
- 记住广义表取表尾永远要多加一层括号。
- 记住循环队列判满的公式 (rear + 1) % size == front。

第六章：树与森林 (简答题核心)

1. 堆 (Heap) —— 优先级队列的实现基础

定义与性质 (必背)：
- 逻辑结构：必须是一棵完全二叉树（Complete Binary Tree）。这意味着除了最后一层，其他层都是满的，且最后一层的节点都靠左排列。
- 存储结构：通常用数组（顺序表）存储。下标 $i$ 的左孩子是 $2i+1$，右孩子是 $2i+2$，父节点是 $\lfloor(i-1)/2\rfloor$。
- 大顶堆 (Max Heap)：任意节点的值 $\ge$ 其左右子节点的值。（堆顶最大）
- 小顶堆 (Min Heap)：任意节点的值 $\le$ 其左右子节点的值。（堆顶最小）
核心操作 (简答题常考画图)：
- A. 向下调整 (FilterDown / SiftDown) —— 建堆的核心
  - 场景：假设根节点的左右子树都是堆，但根节点本身可能破坏了堆性质。
  - 思路：
    1. 拿出根节点元素 temp。
    2. 比较它的两个孩子，找到更符合堆性质的那个（大顶堆找较大的孩子，小顶堆找较小的孩子）。
    3. 如果孩子比 temp “强”，就把孩子上移到父节点位置。
    4. 指针下移，继续重复，直到叶子节点或满足堆性质。
    5. 将 temp 放入最终位置。
- B. 建堆 (Build Heap)
  - 误区：不要通过一个一个插入来建堆（那样慢）。
  - 正确做法：从最后一个非叶子节点（数组下标 $\lfloor n/2 \rfloor - 1$）开始，一直到根节点（下标0），依次对每个节点进行向下调整。
  - 口诀：从下往上扫，对每个点做沉底操作。
- C. 插入 (Insert)
  - 步骤：
    1. 先把新元素放在数组的最后（保持完全二叉树形态）。
    2. 执行向上调整 (FilterUp)：和父节点比，如果比父节点“强”，就交换，直到根或满足性质。
- D. 删除 (Remove)
  - 通常指删除堆顶（最大值或最小值）。
  - 步骤：
    1. 取出堆顶元素。
    2. 把堆的最后一个元素移动到堆顶。
    3. 对新的堆顶执行向下调整。

2. 霍夫曼树 (Huffman Tree) —— 最优二叉树

定义：带权路径长度 (WPL) 最小的二叉树。
WPL计算公式： $WPL = \sum (\text{叶子节点权值} \times \text{该节点的路径长度})$
- 注意：路径长度 = 从根到该节点的层数 - 1（或者说是边的数量）。
构建算法 (必考手绘过程)：
1. 森林初始化：把所有给定的权值看作全是根节点的森林。
2. 选小：从森林中选出两个权值最小的树。
3. 合并：生成一个新的父节点，其权值为这两个子树权值之和。
4. 放回：从森林中删除那两个小树，把新生成的树放回去。
5. 重复：直到森林里只剩一棵树。
霍夫曼编码 (应用)：
- 规则：霍夫曼树建好后，左分支标0，右分支标1。从根到叶子的路径就是该字符的编码。
- 性质：前缀编码。这意味着没有任何一个字符的编码是另一个字符编码的前缀（例如，A是0，B就不可能是01），这样解码时不会歧义。

3. AVL树 (平衡二叉搜索树) —— 难点

定义：
1. 首先它得是二叉搜索树 (BST)：左 < 根 < 右。
2. 平衡条件：任意节点的左子树和右子树的高度差（平衡因子 BF）绝对值不超过 1。即 $BF \in {-1, 0, 1}$。
旋转 (简答题必考：给一个插入序列，画出平衡后的树)
- 口诀：“哪边沉，往反方向旋”。
- 你需要找到离插入点最近的、失衡的祖先节点（设为 A）。
1. LL型 (单旋)：
  - 原因：在 A 的左孩子的左子树插入导致失衡。
  - 操作：右单旋。
  - 动作：提起 A 的左孩子 B，把 A 按下去变成 B 的右孩子。B 原来的右子树挂给 A 做左子树。
2. RR型 (单旋)：
  - 原因：在 A 的右孩子的右子树插入导致失衡。
  - 操作：左单旋。
  - 动作：提起 A 的右孩子 B，把 A 按下去变成 B 的左孩子。B 原来的左子树挂给 A 做右子树。
3. LR型 (双旋)：
  - 原因：在 A 的左孩子的右子树插入。
  - 操作：先左旋后右旋。
  - 动作：
    1. 先对 A 的左孩子 B 进行左旋（变成LL型）。
    2. 再对 A 进行右旋。
4. RL型 (双旋)：
  - 原因：在 A 的右孩子的左子树插入。
  - 操作：先右旋后左旋。
  - 动作：
    1. 先对 A 的右孩子 B 进行右旋（变成RR型）。
    2. 再对 A 进行左旋。

4. 树与森林的转换 (可能考选择或小简答)

树 -> 二叉树：“左孩右兄”法则。
- 节点的第一个孩子 -> 变成二叉树的左孩子。
- 节点的下一个兄弟 -> 变成二叉树的右孩子。
森林 -> 二叉树：
- 先把每棵树转成二叉树。
- 把第二棵树的根连到第一棵树根的右孩子上，依次类推。

复习建议 (针对这一章)

动手画图：
- 找一组数字（例如 5, 2, 9, 1, 3），试着画出构建堆的过程。
- 用同样的数字，试着画出构建AVL树的过程（注意每次插入都要检查平衡）。
- 用同样的数字（作为权值），画出霍夫曼树。
区分概念：
- 堆只要求父子大小关系（不要求左右孩子大小）。
- 二叉搜索树要求左 < 根 < 右。
- 霍夫曼树只有叶子节点有数据（权值）。

第八章：图 (Graph) —— 简答题核心

1. 图的存储表示 (基础但必考)

邻接矩阵 (Adjacency Matrix)
- 定义：用一个二维数组 A[i][j] 存储。若 $i, j$ 有边，则为 1 (或权值)；无边则为 0 (或 $\infty$)。
- 特点：
  - 空间复杂度：$O(n^2)$。浪费空间（如果图很稀疏）。
  - 度数判断：
    - 无向图：第 $i$ 行之和 = 顶点 $i$ 的度。
    - 有向图：第 $i$ 行之和 = 出度；第 $j$ 列之和 = 入度。
- 适用：稠密图（边很多）。
邻接表 (Adjacency List)
- 定义：数组 + 链表。数组存顶点，每个顶点后挂一条链表，存所有邻接点。
- 特点：
  - 空间复杂度：$O(n+e)$。节省空间。
  - 唯一性：表示不唯一（链表中节点的顺序可以变，取决于插入顺序）。
- 适用：稀疏图（边很少）。

2. 图的遍历 (算法基础)

DFS (深度优先搜索)
- 逻辑：类似树的前序遍历。一条路走到黑，撞墙（无路可走）了就回溯到上一个路口。
- 实现：使用递归或栈。
- 生成树：DFS生成树通常较高、较瘦。
BFS (广度优先搜索)
- 逻辑：类似树的层序遍历。先访问离起点最近的一圈，再访问第二圈…
- 实现：使用队列。
- 生成树：BFS生成树通常较矮、较胖（因为倾向于寻找最短跳数）。
环的判断 (常考简答题：如何判断图中有环？)
1. DFS法：在遍历过程中，如果遇到一个已经访问过的节点，且该节点不是当前节点的父节点（无向图），或者该节点在当前递归栈中（有向图），说明有环。
2. 拓扑排序法：(针对有向图) 每次删除入度为0的点。如果最后图里还有节点删不掉，说明有环。

3. 最小生成树 (MST) —— 必考画图

核心概念：在连通图中选出 $n-1$ 条边，把 $n$ 个点连起来，且边权之和最小。

Prim算法 (普里姆) —— “加点法”
- 逻辑：将顶点分为“已选集合 U”和“未选集合 V-U”。
- 步骤：
  1. 任选一个点（如A）放入 U。
  2. 关键步：在连接 U 和 V-U 的所有边中，找一条权值最小的边。
  3. 把这条边连着的那个新点加入 U。
  4. 重复，直到所有点都在 U 中。
- 记忆口诀：“步步为营”，以点为中心慢慢向外扩张。
- 适用：稠密图（因为复杂度与边数关系不大）。
Kruskal算法 (克鲁斯卡尔) —— “加边法”
- 逻辑：将边按权值排序，从小到大选。
- 步骤：
  1. 把所有边按权值从小到大排序。
  2. 关键步：拿出最小的一条边。
  3. 判断：这条边连的两个点是否已经在同一棵树里？（用并查集判断）。
    - 如果是：扔掉（否则会形成环）。
    - 如果否：加入。
  4. 重复直到选够 $n-1$ 条边。
- 记忆口诀：“各自为政”，先连成很多小树，最后连成大树。
- 适用：稀疏图（因为要对边排序）。
MST唯一性问题：
- 如果图中所有边权值都不相同，MST是唯一的。
- 如果有相同权值的边，MST形状可能不唯一，但总权值之和一定是唯一的。

4. 最短路径 (Shortest Path)

Dijkstra算法 (迪杰斯特拉) —— 单源最短路
- 限制：边权不能为负。
- 逻辑：贪心策略。类似BFS的扩散，但每次选最近的。
- 手工模拟步骤 (必练)：画一个表，包含 S (已求出点集), U (未求出点集), Dist (距离), Path (前驱)。
  1. 初始化：源点距离0，其他 $\infty$。
  2. 选最小：在未访问的点中，选一个距离源点最近的点 $u$。
  3. 松弛 (Relax)：看点 $u$ 的邻居 $v$。如果 源点->u->v 的距离比 源点->...->v 现在的距离短，就更新 $v$ 的距离。
    - 公式：if (Dist[u] + weight < Dist[v]) Dist[v] = Dist[u] + weight。
  4. 重复。

5. AOV网与拓扑排序 (Topological Sort)

定义：AOV (Activity On Vertex)。顶点代表活动，边代表“先后顺序”的制约。
算法流程：
1. 在图中找一个入度为0（没有前驱，也就是没人管它）的顶点。
2. 输出它。
3. 删除该顶点，并且删除它发出的所有边（这会导致它邻居的入度减少）。
4. 重复，直到图空了（成功），或者找不到入度为0的点（失败，说明有环）。
应用：排课表（先修课）、编译依赖。

6. AOE网与关键路径 (Critical Path) —— 难点/计算题

定义：AOE (Activity On Edge)。边代表活动（有持续时间），顶点代表事件（时刻）。
四个核心参数 (简答题要求计算)：
1. 事件的最早发生时间 ($ve$)：
  - 从源点往汇点推（从前往后）。
  - 规则：取最大值（必须等所有前序活动都做完，事件才能发生）。
  - 公式：$ve(j) = \max { ve(i) + weight(i, j) }$。
2. 事件的最迟发生时间 ($vl$)：
  - 从汇点往源点推（从后往前）。
  - 规则：取最小值（不能耽误后续活动按时开始）。
  - 公式：$vl(i) = \min { vl(j) - weight(i, j) }$。
3. 活动的最早开始时间 ($e$)：
  - 等于该活动出发点（事件）的 $ve$。
4. 活动的最迟开始时间 ($l$)：
  - 等于该活动结束点（事件）的 $vl$ 减去活动持续时间。
关键活动：
- 满足 $e = l$ 的活动。即：最早什么时候动 = 最晚什么时候动（没有摸鱼时间）。
关键路径：
- 从源点到汇点，所有边都是关键活动的那条路径。
- 它是全图路径长度最长的路径。
工程加速 (简答题考点)：
- 问：缩短哪些活动可以缩短工期？
- 答：必须缩短关键路径上的活动。
- 陷阱：如果存在多条关键路径，必须同时缩短这些路径上共有的活动，或者分别缩短每条路径上的活动，否则工期不会变（因为被另一条没缩短的关键路径卡住了）。

复习建议 (针对图)

背算法流程：Prim, Kruskal, Dijkstra, 拓扑排序。不要背代码，要背第一步干嘛、第二步干嘛。
画图训练：
- 自己画一个带权无向图，用 Prim 和 Kruskal 跑一遍，看 MST 是否一样。
- 自己画一个带权有向图，用 Dijkstra 跑一遍。
- 画一个 AOE 网，计算 $ve$ 和 $vl$，找出关键路径。这是大题最容易拿分也最容易算错的地方。

第九章：排序 (选择题核心)

1. 核心概念 (必背)

稳定性 (Stability)
- 定义：如果序列中有两个相等的关键字（如 ...5a...5b...），排序后它们的相对位置不变（...5a...5b...），则该算法是稳定的。
- 为什么重要：在多级排序中（例如，先按成绩排，再按姓名排），稳定性至关重要。
时间复杂度
- 最好情况：在特定（通常是有序）输入下的性能。
- 最坏情况：在最不利输入下的性能。
- 平均情况：随机输入下的期望性能。
- 选择题经常考查特定算法在最好/最坏情况下的复杂度。
空间复杂度
- 原地排序 (In-place)：空间复杂度为 $O(1)$，如堆排序、插入排序。
- 非原地排序：需要额外空间，如归并排序 ($O(n)$)、基数排序 ($O(n+r)$)。

2. 插入排序 (Insertion Sort)

核心思想：像打扑克牌一样，每次摸一张牌，把它插入到手中已有序的牌里。
直接插入排序
- 时间：最好 $O(n)$（已基本有序），最坏/平均 $O(n^2)$。
- 稳定性：稳定。
- 适用：基本有序或数据量很小时非常快。
折半插入排序
- 改进：找插入位置时用折半查找，而不是顺序查找。
- 时间：比较次数降为 $O(n \log n)$，但移动次数没变，所以整体还是 $O(n^2)$。
希尔排序 (Shell Sort)
- 改进：缩小增量排序，先宏观调，再微观调。
- 时间：$O(n^{1.3})$ ~ $O(n^{1.5})$，比 $O(n^2)$ 好，但不如 $O(n \log n)$。
- 稳定性：不稳定。

3. 交换排序 (Exchange Sort)

核心思想：通过交换逆序元素的位置来排序。
冒泡排序 (Bubble Sort)
- 思路：相邻元素两两比较，大的往后沉。
- 时间：最好 $O(n)$（已有序，加个标志位可以一趟结束），最坏/平均 $O(n^2)$。
- 稳定性：稳定。
快速排序 (Quick Sort) —— 重中之重
- 思路：分治法。
  1. 选一个基准 (pivot)。
  2. 划分 (Partition)：把比基准小的放左边，大的放右边。
  3. 递归：对左右两部分递归地进行快速排序。
- 时间：
  - 最好/平均：$O(n \log n)$。
  - 最坏：$O(n^2)$。发生场景：当序列已经有序或逆序时，每次划分都极不均衡。
- 稳定性：不稳定。（因为划分时可能会把前面的相同元素换到后面去）
- 空间：$O(\log n)$（递归栈的深度），最坏 $O(n)$。

4. 选择排序 (Selection Sort)

核心思想：每次从待排序序列中选出最小（或最大）的元素，放到已排序序列的末尾。
直接选择排序
- 思路：第一趟从 $n$ 个数中选最小的与第一个交换；第二趟从剩下 $n-1$ 个中选最小的与第二个交换…
- 时间：$O(n^2)$。与初始序列无关，不管好坏都这么慢。
- 稳定性：不稳定。（例如 5a 8 5b，第一趟会把5a和3交换，5a和5b的顺序就变了）
堆排序 (Heap Sort)
- 思路：
  1. 建堆：把整个序列建成一个大顶堆（或小顶堆）。
  2. 排序：
    - 把堆顶（最大/最小元素）和堆的最后一个元素交换。
    - 堆的大小减一。
    - 对新的堆顶进行向下调整。
    - 重复。
- 时间：$O(n \log n)$。
- 空间：$O(1)$。
- 稳定性：不稳定。
- 应用：适合找Top K问题（如找10亿个数中最大的100个）。

5. 归并排序 (Merge Sort)

核心思想：分治法。
1. 分：把序列递归地分成两半。
2. 治：当子序列只有一个元素时，它自然有序。
3. 合：把两个有序的子序列合并成一个有序序列（Merge操作是关键）。
时间：$O(n \log n)$。非常稳定，不受初始序列影响。
空间：$O(n)$。需要一个同样大小的辅助数组。
稳定性：稳定。
应用：外排序的核心思想。

6. 基数排序 (Radix Sort)

核心思想：“分配”与“收集”。不比较大小，按位排序。
LSD (最低位优先)：从个位开始排，然后十位，百位…
时间：$O(d(n+r))$。其中 d 是位数，r 是基数（如十进制是10）。
稳定性：稳定。
适用：当数据范围不大，且位数不多时，非常快。

复习小结 (如何应对选择题)

稳定性口诀：
- 稳定：归并、插入、冒泡、基数。 (情绪稳定的人容易被归类，插队如果不冒泡就很稳)
- 不稳定：快速、堆、选择。 (口诀：快点选一堆)
复杂度辨析：
- 看到 $O(n^2)$ 的，就是插入、冒泡、选择这些简单排序。
- 看到 $O(n \log n)$ 的，就是快排、堆排、归并这些高级排序。
- 看到和初始序列有关的，多半是快排和插入排序。
- 看到“基本有序”时哪个最快？直接插入排序 ($O(n)$)。
- 看到“基本有序”时哪个最慢？快速排序 ($O(n^2)$)。
- 哪个算法的时间复杂度与初始序列无关？直接选择、堆排序、归并排序。
空间复杂度：
- 需要额外 $O(n)$ 空间的主要是归并排序。
- 大部分都是 $O(1)$ 或 $O(\log n)$。
外排序：
- 当数据量太大，内存放不下时使用。
- 核心是多路归并排序，通常会用到败者树或胜者树来优化多路归并的过程。

练习建议：

自己画一张大表，行是排序算法，列是平均/最好/最坏时间复杂度、空间复杂度、稳定性。填完这张表，选择题就没问题了。
手动模拟一遍快速排序的划分过程，理解为什么它不稳定。

选择题

第一部分：基本概念与线性结构

1. 绪论 (算法分析)

时间复杂度：
- $O(1)$ 不代表只执行一条指令，而是指执行时间固定，与问题规模 $n$ 无关。
- 常见增长级：$O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(2^n)$。
- 陷阱：递归算法的空间复杂度通常是递归树的深度（栈空间）。

2. 线性表 (顺序表 vs 链表)

存储密度：顺序表 = 1 (最有效率)，链表 < 1 (因为要存指针)。
访问方式：顺序表是随机存取 (Random Access)，链表是顺序存取 (Sequential Access)。
插入/删除：
- 顺序表平均移动元素个数：插入是 $n/2$，删除是 $(n-1)/2$。时间 $O(n)$。
- 链表：时间 $O(1)$ (前提是已知位置)，但找到该位置需要 $O(n)$。
指针细节：
- 双向链表插入/删除：顺序至关重要，先连后断。比如在 $p$ 后插 $s$：先搞定 $s$ 的前后，再改 $p$ 和 $p \to next$。
- 循环链表：判空条件不是 == NULL，而是 == head 或 next == head。
- 带头结点：统一了空表和非空表的操作，头指针始终不为NULL。

3. 栈与队列 (Stack & Queue)

栈 (LIFO)：
- 出栈序列计数：$n$ 个元素进栈，不同的出栈序列个数为卡特兰数：$\frac{1}{n+1} C_{2n}^{n}$。
- 共享栈：两个栈共用一个数组，栈底在两端，栈满条件是 top1 + 1 == top2。
队列 (FIFO)：
- 循环队列 (必考)：解决“假溢出”问题。
  - 通常牺牲一个存储单元来区分空和满。
  - 队空：front == rear
  - 队满：(rear + 1) % MaxSize == front
  - 队列长度：(rear - front + MaxSize) % MaxSize (这个公式选择题常考计算)。
应用辨析：
- 栈：递归、函数调用、括号匹配、表达式求值、迷宫回溯（DFS）。
- 队列：缓冲区、操作系统作业调度、层序遍历、广度优先搜索（BFS）。

4. 串 (String) & 数组

KMP算法：
- Next数组：核心是最长相等前后缀。
- 手算技巧：第 j 个字符不匹配时，跳到 next[j]。next[1]通常为0。
特殊矩阵压缩：
- 对称矩阵：只存下三角，一维数组长度 $n(n+1)/2$。下标映射公式 $k = i(i-1)/2 + j$ (注意下标从0还是1开始)。
- 稀疏矩阵：三元组表存储，失去随机存取特性。

第二部分：树与二叉树 (高频细碎考点)

1. 二叉树性质 (公式狂魔)

度与节点数：
- $n_0 = n_2 + 1$ (叶子节点数 = 度为2的节点数 + 1)。这个性质最常考！
- 边数 $E = N - 1$。
完全二叉树 (Complete Binary Tree)：
- 节点编号（从1开始）：父节点 $\lfloor i/2 \rfloor$，左孩子 $2i$，右孩子 $2i+1$。
- 第一个叶子节点的编号：$\lfloor n/2 \rfloor + 1$。
- 高度：$\lfloor \log_2 n \rfloor + 1$。
满二叉树：高度 $h$ 的满二叉树节点总数 $2^h - 1$。第 $i$ 层节点数 $2^{i-1}$。

2. 遍历与线索化

序列还原：
- 中序 + 前序 -> 唯一确定二叉树 (可行)。
- 中序 + 后序 -> 唯一确定二叉树 (可行)。
- 前序 + 后序 -> 不可唯一确定 (除非每个非叶节点都有两个孩子)。
线索二叉树：
- 空指针数：$n$ 个节点的二叉树有 $n+1$ 个空链域，用来存线索。
- 前驱/后继：
  - 中序线索树找后继很容易（右子树最左节点）。
  - 后序线索树找后继很难（需要父指针，因为根是最后访问的）。

3. 树与森林

转换法则：左孩子右兄弟 (Left Child, Right Sibling)。
遍历对应关系：
- 树的先根遍历 = 二叉树的先序遍历。
- 树的后根遍历 = 二叉树的中序遍历 (注意！不是后序)。

4. 霍夫曼树 (Huffman)

节点构造：只有度为0和度为2的节点，不存在度为1的节点。
WPL计算：仅计算叶子节点的 (权值 $\times$ 路径长度)。
形态：不唯一 (左右孩子交换不影响WPL)，但WPL值唯一。
编码：前缀编码 (任一编码不是另一编码的前缀)，对应哈夫曼树中没有度为1的结点这一特性不完全准确，准确说是数据只在叶子上。

第三部分：图 (性质最复杂)

1. 基本性质

边数限制：
- 无向图 $n$ 个顶点，最少 $0$ 条边，最多 $n(n-1)/2$ 条边（完全图）。
- 有向图 $n$ 个顶点，最多 $n(n-1)$ 条边。
连通性：
- 连通图：$n$ 个顶点最少需要 $n-1$ 条边（生成树）。
- 强连通图 (有向)：$n$ 个顶点最少需要 $n$ 条边（形成环）。
度数：所有顶点的度数之和 = 2倍边数。

2. 存储与遍历

邻接矩阵：唯一的。无向图是对称的。$A^n[i][j]$ 表示 $i$ 到 $j$ 长度为 $n$ 的路径数目。
邻接表：不唯一 (取决于链表插入顺序)。
DFS：借助栈。适合判断回路。生成树高瘦。
BFS：借助队列。适合找最短路径 (无权图)。生成树矮胖。

3. 应用算法性质

最小生成树 (MST)：
- Prim：时间 $O(n^2)$，适合稠密图。
- Kruskal：时间 $O(e \log e)$，适合稀疏图。
- 边权不同则MST唯一；边权有重复则MST可能不唯一，但权值和唯一。
拓扑排序：
- 针对有向无环图 (DAG)。
- 若拓扑序列不唯一，图不一定有回路。
- 邻接矩阵为三角矩阵 $\rightarrow$ 必存在拓扑序列。
关键路径：
- 关键路径上的活动时间延长 $\rightarrow$ 工期延长。
- 缩短非关键路径活动 $\rightarrow$ 工期不变。

第四部分：广义表 (必考选择题计算)

定义：$LS = (a_1, a_2, \dots, a_n)$。
表头 (Head)：$a_1$ (可以是原子，也可以是表)。
表尾 (Tail)：$(a_2, \dots, a_n)$ (一定要加括号，表尾永远是一个表)。
- 例：$L = (a, b)$。Head($L$) = $a$。Tail($L$) = $(b)$。
- 例：$L = (a)$。Head($L$) = $a$。Tail($L$) = $()$ (空表)。
深度：括号的层数。
长度：第一层元素的个数（逗号数+1）。

第五部分：排序与查找 (比较与结论)

1. 查找

折半查找 (Binary Search)：
- 仅适用于有序顺序表 (链表不行)。
- 判定树是平衡二叉树，高度 $\lceil \log_2(n+1) \rceil$。
BST (二叉排序树)：中序遍历有序。
AVL (平衡二叉树)：
- 左右子树高度差 $\le 1$。
- 查找效率稳定 $O(\log n)$。
- 最少节点数公式：$N_h = N_{h-1} + N_{h-2} + 1$ (类似斐波那契)。

2. 排序 (结论记忆表)

排序算法	平均时间	最好时间	最坏时间	空间	稳定性	特点
直接插入	$O(n^2)$	$O(n)$ (有序)	$O(n^2)$	$O(1)$	稳	$n$小时好用，基本有序时快
冒泡	$O(n^2)$	$O(n)$ (有序)	$O(n^2)$	$O(1)$	稳	每一趟确定一个最大值
简单选择	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	不稳	比较次数与序列无关
希尔	-	-	-	$O(1)$	不稳	插入排序的改进
快速排序	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	不稳	平均最快，有序时最慢(退化)
堆排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(1)$	不稳	适合Top K，建堆 $O(n)$
归并排序	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	稳	外部排序基础，空间换时间
基数排序	$O(d(n+r))$	-	-	$O(r)$	稳	不需要比较

选择题必背结论：

快点选一堆朋友：快速、选择、堆排序是不稳定的。
与初始状态无关（不管有没有序，都要硬算 $O(n^2)$）的是：简单选择排序。
排序趟数与序列无关的是：简单选择排序、归并排序。
比较次数与序列无关的是：简单选择排序、基数排序。
一趟结束后，未必能选出一个元素放在最终位置的是：希尔排序。

学习, 数据结构

数据结构

本文由作者按照 CC BY 4.0 进行授权

分章节大纲

第一章：绪论 (基础概念)

第二章：线性表 (编程题重灾区 & 简答)

1. 顺序表 (数组)

2. 链表 (单链表/双链表)

第三章：栈与队列 (简答题逻辑)

第五章：递归与广义表 (编程 & 概念)

第六章：树与森林 (简答题核心)

第八章：图 (Graph) (简答题核心)

第九章：排序 (选择题核心)

分章节详细

一、 顺序表 (数组)

1. 编程重点：数组原地置换

2. 稀疏矩阵 (简答题考点)

二、 链表 (编程题重灾区)

1. 编程重点：链表元素互换 (Swap)

2. 编程重点：链表合并 (Merge)

复习小贴士

第三章：栈与队列 (重点考察：后缀表达式与逻辑)

1. 后缀表达式 (Reverse Polish Notation, RPN)

2. 队列 (简单概念)

第五章：递归与广义表 (编程核心 & 概念陷阱)

1. 递归 (Recursion) —— 编程题核心

2. 广义表 (Generalized Lists) —— 选择题/简答题陷阱

复习小结：如何准备这两章？

第六章：树与森林 (简答题核心)

1. 堆 (Heap) —— 优先级队列的实现基础

2. 霍夫曼树 (Huffman Tree) —— 最优二叉树

3. AVL树 (平衡二叉搜索树) —— 难点

4. 树与森林的转换 (可能考选择或小简答)

复习建议 (针对这一章)

第八章：图 (Graph) —— 简答题核心

1. 图的存储表示 (基础但必考)

2. 图的遍历 (算法基础)

3. 最小生成树 (MST) —— 必考画图

4. 最短路径 (Shortest Path)

5. AOV网与拓扑排序 (Topological Sort)

6. AOE网与关键路径 (Critical Path) —— 难点/计算题

复习建议 (针对图)

第九章：排序 (选择题核心)

1. 核心概念 (必背)

2. 插入排序 (Insertion Sort)

3. 交换排序 (Exchange Sort)

4. 选择排序 (Selection Sort)

5. 归并排序 (Merge Sort)

6. 基数排序 (Radix Sort)

复习小结 (如何应对选择题)

选择题

第一部分：基本概念与线性结构

1. 绪论 (算法分析)

2. 线性表 (顺序表 vs 链表)

3. 栈与队列 (Stack & Queue)

4. 串 (String) & 数组

第二部分：树与二叉树 (高频细碎考点)

1. 二叉树性质 (公式狂魔)

2. 遍历与线索化

3. 树与森林

4. 霍夫曼树 (Huffman)

第三部分：图 (性质最复杂)

1. 基本性质

2. 存储与遍历

3. 应用算法性质

第四部分：广义表 (必考选择题计算)

第五部分：排序与查找 (比较与结论)

1. 查找

2. 排序 (结论记忆表)

热门标签

一、顺序表 (数组)

二、链表 (编程题重灾区)