408 计算机学科专业基础综合里，数据结构是我认为最需要建立体系感的一科。它不像计算机网络那样以协议栈为主线，也不像操作系统那样依赖进程管理、内存管理、文件系统三大抽象，数据结构的核心是“逻辑结构 + 存储结构 + 操作实现 + 应用场景”四件事同时讲清楚。很多同学复习 408 数据结构时最大的问题不是知识点难，而是知识太碎：今天背顺序表，明天看图的遍历，后天记排序稳定性，等到做题阶段发现彼此之间连不起来。所以我写数据结构大观系列时，一直想把整门课压缩成一张能放进脑子里的图。这篇作为系列第 2 篇，重点不是单独讲某个算法，而是把 408 数据结构所有高频考点按图结构重新排一遍，给出复习顺序、对比表和自查清单。
1. 先理解 408 数据结构考纲到底在考什么
1.1 从 408 的分值分布确定复习优先级
408 总分为 150 分，数据结构通常占 45 分左右，是四科中分值较高的部分。选择题覆盖广，大题一般会涉及算法设计、代码实现或复杂度分析。数据结构不仅考“这个结构是什么”，更考“为什么要这样设计”“在不同存储方式下，某个操作的时间复杂度是多少”“给定数据你怎么选结构”。
复习优先级可以参考下表：
| 知识模块 | 难度 | 常考题型 | 复习优先级 |
|---|---|---|---|
| 线性表 | 低 | 选择、代码题 | 高 |
| 栈、队列和数组 | 中 | 选择、代码题 | 高 |
| 树与二叉树 | 高 | 选择、大题 | 高 |
| 图 | 高 | 选择、大题 | 中高 |
| 查找 | 中 | 选择、综合应用 | 中 |
| 排序 | 中 | 选择、代码题 | 高 |
需要注意，绝大多数知识点不是孤立出现的。比如树中的二叉排序树既属于树，又会在查找章节里作为动态查找结构出现；堆既是一种完全二叉树，又是堆排序和优先队列的底层结构。复习时如果只按章节顺序背一遍，很难形成这种交叉记忆。
1.2 考纲背后的四条主线
数据结构教材通常从“逻辑结构”出发，再讲“存储结构”，接着是“基本操作”，最后落到“典型应用”。这四条线就是知识图谱的主干：
- 逻辑结构：数据元素之间的关系是什么。线性结构是一对一，树是一对多，图是多对多，集合是元素之间没有直接逻辑关系。
- 存储结构：在计算机里如何表示。常见有顺序存储、链式存储、索引存储、散列存储。
- 基本操作：在这种存储结构上如何增删改查、如何遍历、如何判断空和满。
- 典型应用：这个结构能解决什么问题，例如栈解决括号匹配，哈夫曼树解决编码压缩，图解决最短路径。
408 的大题往往不是单独考某一步，而是让你把四条线串起来。比如给你一个有序顺序表，问二分查找；再问你如果用链表实现二分查找，为什么效率会退化。答案的核心是：顺序表支持随机访问，链表只能顺序访问，所以原来 O(log n) 的查找会被放大成 O(n log n)。
复习任何知识点时，可以先问自己四个问题：
这个结构解决什么问题？ 它有哪些逻辑形态？ 它可以用哪些存储方式实现？ 不同存储方式下，核心操作的复杂度分别是多少？能回答这四个问题，才算真正掌握了这个知识点。
2. 一张数据结构的图应该包含哪些内容
2.1 图的骨架：由大结构到小结构
一图流不是把教材目录抄一遍，而是画一张能体现知识层级和连接关系的结构图。可以参考下面这个骨架：
数据结构骨架 ├── 数据元素 / 结点 ├── 逻辑结构 │ ├── 线性结构：线性表、栈、队列、串、数组 │ └── 非线性结构：树、图、集合 ├── 存储结构 │ ├── 顺序存储：连续内存，支持随机访问 │ ├── 链式存储：指针串联，动态插入删除 │ ├── 索引存储：额外索引定位数据 │ └── 散列存储：通过散列函数计算地址 ├── 基本操作 │ ├── 初始化、判空、判满 │ ├── 插入、删除、修改、查找 │ ├── 遍历、求长度、求深度 │ └── 算法设计：递归、非递归、分治、贪心 └── 典型应用 ├── 栈：函数调用、表达式求值 ├── 队列：缓冲区、层序遍历 ├── 树：文件系统、哈夫曼编码 ├── 图：网络路由、任务调度 └── 查找 / 排序：数据库索引、数据处理这张图的价值在于“定位”。拿到一道题，先在图上定位它属于哪个模块，再回到对应模块的存储结构和操作细节中找答案。如果一上来就盯着代码细节，容易被局部问题带偏。
2.2 每个考点要能挂在图的节点上
画图时，每个知识点都应该能挂到某个位置，并写清与该位置相邻的知识点。以栈为例：
栈 ├── 逻辑结构：操作受限的线性表，只允许在一端插入删除 ├── 存储结构 │ ├── 顺序栈：数组 + 栈顶指针 │ └── 链栈：单链表头插头删 ├── 基本操作 │ ├── 入栈 push：栈顶指针先加 1，再写入 │ ├── 出栈 pop：先取元素，再减栈顶指针 │ └── 判空：top == -1 └── 应用 ├── 括号匹配 ├── 中缀转后缀 ├── 函数递归调用 └── 迷宫求解再以哈希表为例：
哈希表 ├── 逻辑结构：集合，元素之间无明确前后顺序 ├── 存储结构：散列存储 ├── 基本操作：通过散列函数计算地址 │ ├── 冲突处理：开放定址法、拉链法 │ ├── 查找：计算地址后比较关键字 │ └── 扩容：负载因子过大时重建 └── 应用：数据库缓存、字典、去重当这种小图在脑子里积累到一定数量，整门课就会形成一张互相连接的大图。看到的不是几十个孤立算法，而是一棵不断生长的知识树。
2.3 图的维护方式
每次做完题后，把新结论挂回图里。比如做完一道“用两个栈模拟队列”的题，就在栈的应用节点上补充一条“双栈模拟队列：入队 push 到栈 1，出队时先反转栈 1 到栈 2”。这种补充会让自己的知识图越来越接近 408 的出题风格。
绘图工具用什么并不重要。XMind、ProcessOn、幕布，或者直接在纸上画都可以。关键是不要只画图不复习细节。图是线索，细节要靠代码和题目来填。
3. 线性结构：顺序表、链表、栈、队列怎么复习才扎实
3.1 顺序表和链表的对比不能只背结论
408 里线性表是很多算法题的基础，也是容易丢分的地方。顺序表底层是数组，支持 O(1) 随机访问；链表底层是指针串联，插入和删除只要修改指针。单链表结构定义可以写成：
typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;链表常见的初始化方式是头插法或尾插法。头插法建立单链表时，读入的数据顺序和链表顺序相反：
void CreateListHead(LinkList &L, int n) { L = (LNode *)malloc(sizeof(LNode)); L->next = NULL; for (int i = 0; i < n; ++i) { LNode *s = (LNode *)malloc(sizeof(LNode)); scanf("%d", &s->data); s->next = L->next; L->next = s; } }这里要注意，在 C 语言中为了修改头指针，通常要传入指针的指针；如果使用 C++，可以直接用引用类型。408 题目里并不要求严格区分语言，但代码要保证逻辑完整。
顺序表和链表的对比如下：
| 对比项 | 顺序表 | 链表 |
|---|---|---|
| 随机访问 | O(1) | O(n) |
| 头插 / 头删 | 需要移动元素，O(n) | O(1) |
| 中间插入删除 | 需要移动后半部分元素 | 需要先找到前驱，O(n) |
| 空间分配 | 连续空间，可能造成内碎片 | 离散空间，需要额外指针域 |
| 缓存友好度 | 高 | 低 |
| 适用场景 | 读多写少、按位访问 | 频繁插入删除、长度不确定 |
链表的高频代码题包括反转单链表、合并两个有序链表、找链表中间节点、判断是否有环。这些都要能手写，不能只记住“用双指针”这句话。
3.2 栈、队列、数组的考试角度
栈和队列都是操作受限的线性表。栈只在栈顶操作，后进先出；队列在队尾入、队头出，先进先出。
循环队列是重点。为了让队列空间可以复用，通常用模运算实现循环。牺牲一个存储单元来区分空和满：
队空：front == rear 队满：(rear + 1) % MaxSize == front 队中元素个数：(rear - front + MaxSize) % MaxSize为什么要牺牲一个单元？如果不牺牲，空和满时 front 和 rear 都会相等，无法区分。除了牺牲存储单元，还可以设置 flag 或计数器，但 408 基础最常考的还是牺牲一个单元的写法。
栈的应用包括括号匹配、表达式求值、递归转非递归。括号匹配的解题思路是：遇到左括号入栈，遇到右括号时查看栈顶是否匹配；结束后如果栈不为空，说明还有未匹配的左括号。
数组和特殊矩阵部分，主要考按行优先或按列优先存储时，某个元素的下标换算。例如一个 m 行 n 列的二维数组 a[i][j] 按行优先存储，相对于 a[0][0] 的偏移量是 i * n + j。这个公式一定要现场推一遍，不要死记。
4. 树与二叉树：408 中题量最大的一块
4.1 二叉树遍历的递归与非递归
二叉树的定义本身带有递归结构，所以递归遍历很自然。完整的结构体定义和先序遍历可以写成：
typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void PreOrder(BiTree T) { if (T == NULL) { return; } visit(T); PreOrder(T->lchild); PreOrder(T->rchild); }递归版本简洁，但 408 经常要求写出非递归版本，因为非递归更接近程序运行的过程。先序非递归用栈模拟：
void PreOrderNonRecursive(BiTree T) { Stack S; InitStack(S); BiTree p = T; while (p || !StackEmpty(S)) { if (p) { visit(p); Push(S, p); p = p->lchild; } else { Pop(S, p); p = p->rchild; } } }中序和后序也要能写。特别是后序非递归，需要判断从右子树返回时才访问根节点，难度更大。树的层次遍历则用队列，每访问一个节点，就把它的左右孩子入队。
四种遍历方式可以整理成一张表：
| 遍历方式 | 核心顺序 | 递归写法 | 非递归工具 | 典型应用 |
|---|---|---|---|---|
| 先序 | 根左右 | 简单 | 栈 | 复制二叉树、求叶子节点 |
| 中序 | 左根右 | 简单 | 栈 | 二叉排序树中序有序 |
| 后序 | 左右根 | 简单 | 栈 | 释放二叉树、求树高 |
| 层次 | 逐层访问 | 不自然 | 队列 | 求宽度、按层输出 |
4.2 BST、平衡树、堆、哈夫曼树
二叉排序树 BST 的核心性质是：左子树所有节点值小于根，右子树所有节点值大于根，因此中序遍历结果是有序序列。查找时从根开始，小则去左子树，大则去右子树。删除节点要分三种情况：
1. 删除叶子节点：直接删除 2. 删除只有左孩子或右孩子的节点：用唯一孩子顶替 3. 删除同时有两个孩子的节点：用中序前驱或中序后继顶替平衡二叉树是在 BST 基础上限制左右子树高度差绝对值不超过 1。插入后如果失衡，需要做 LL、RR、LR、RL 四种旋转。复习时不只要会画旋转过程，还要能算出旋转后的树高。
堆是一种特殊的完全二叉树。大根堆的根节点最大，常用于堆排序；小根堆常用于优先队列。堆用数组存储，父节点下标为 i 时，左孩子为 2i，右孩子为 2i+1，父节点为 i/2。建堆的过程是自底向上对内部节点做向下调整。
哈夫曼树也称最优二叉树，带权路径长度最小的树。构建方法是每次从当前集合中选择两个权值最小的节点合并。哈夫曼树特点是没有度为 1 的节点，如果叶子节点数为 n，则总节点数为 2n - 1。哈夫曼编码是不等长编码，任一字符的编码都不是另一个字符编码的前缀，因此可以无歧义解码。
常见错误是只记“哈夫曼编码是前缀码”，却不会算 WPL。算 WPL 时，要先画出树，再把每一层每个叶子节点的权值乘以路径长度，最后求和。
5. 图：邻接表、DFS、最小生成树和最短路径是一条线
5.1 图的存储结构选择
图的逻辑结构是多对多，比二叉树更复杂。存储方式主要有邻接矩阵和邻接表。
邻接矩阵用二维数组存储顶点之间的关系，判断两个顶点是否相邻非常快，但稀疏图会浪费大量空间。邻接表为每个顶点维护一条链表，只存储实际存在的边，遍历某个顶点的所有邻接点更方便。
选择依据可以简单记：
稠密图或需要快速判断两点之间是否有边：邻接矩阵 稀疏图或需要频繁遍历邻接点：邻接表图的深度优先搜索本质上类似树的先序遍历，只是多了 visited 数组。代码模板如下：
bool visited[MAX_VERTEX_NUM]; void DFS(Graph G, int v) { visited[v] = true; visit(v); for (int w = FirstNeighbor(G, v); w != -1; w = NextNeighbor(G, v, w)) { if (!visited[w]) { DFS(G, w); } } }由于图可能不连通，需要从每个顶点开始尝试 DFS：
void DFSTraverse(Graph G) { for (int i = 0; i < G.vexnum; ++i) { visited[i] = false; } for (int i = 0; i < G.vexnum; ++i) { if (!visited[i]) { DFS(G, i); } } }BFS 使用队列，先访问起始顶点，再依次访问每个顶点的所有未访问邻接点。BFS 在无权图中可以用来求单源最短路径，因为首次访问某个顶点时，路径长度一定最短。
5.2 四类算法要形成解题流程
图的经典算法集中在最小生成树、最短路径、拓扑排序和关键路径。
最小生成树有两种算法：
| 算法 | 思路 | 适合场景 | 典型复杂度 |
|---|---|---|---|
| Prim | 从一个顶点出发，不断选代价最小的边连接新顶点 | 稠密图 | O(V^2) |
| Kruskal | 把所有边按权值排序，从小到大选边，不成环则加入 | 稀疏图 | O(E log E) |
判断 Kruskal 是否成环，可以用并查集。408 题目中，如果只要求画出选边过程，手算即可；如果需要写代码，并查集是常用手段。
最短路径中，Dijkstra 算法按路径长度递增的顺序逐步确定最短路径，要求边权不能为负。Floyd 算法用动态规划思想，可以处理边权为负的图，但不能存在负环。做题时要注意算法是否适用，不能写完才发现权重条件不满足。
拓扑排序用于有向无环图，判断是否存在环的常用方法是看是否有顶点未入队。关键路径则用于估算完成工程的最短时间和关键活动，它依赖事件最早发生时间、最晚发生时间、活动最早开始时间和最晚开始时间四个概念。
图这一章很容易在考试时犯“忘记重置 visited”的错误。尤其在使用多组测试用例时，visited 数组必须重新初始化为 false。
6. 查找与排序：用一张表完成考前复盘
6.1 查找表：顺序、折半、BST、哈希
查找的重点是“给定一个关键字，如何尽快找到对应记录”。不同查找结构本质上是不同逻辑结构和存储结构的组合。
折半查找要求数据有序且采用顺序存储。如果底层是链表，即使有 mid 指针也无法在 O(1) 时间内跳到中间位置，时间复杂度会退化成 O(n)。这是 408 常考的一句话判断题。
常见查找结构对比：
| 查找结构 | 平均查找成功长度 | 插入删除 | 适用条件 |
|---|---|---|---|
| 顺序查找 | O(n) | 随意 | 对数据无要求 |
| 折半查找 | O(log n) | 不灵活 | 有序且顺序存储 |
| 二叉排序树 | O(log n) 平均 | 支持 | 动态插入删除，最坏退化为链 |
| 平衡二叉树 | O(log n) | 支持 | 动态结构且要求稳定效率 |
| 哈希表 | O(1) 平均 | 支持 | 需要散列函数和冲突处理 |
哈希表的扩容依据是负载因子。负载因子 α 等于表中记录数与表长的比值。α 过大时冲突率上升，查找效率下降，因此要扩容。这个点要会和散列地址的计算结合起来复习。
6.2 排序：平均、最好、最坏、稳定、空间
排序算法是 408 选择题的稳定出题点。复习时要能画出每一趟的过程，而不是只背复杂度。快速排序的 partition 是手写高频代码：
int Partition(int A[], int low, int high) { int pivot = A[low]; while (low < high) { while (low < high && A[high] >= pivot) --high; A[low] = A[high]; while (low < high && A[low] <= pivot) ++low; A[high] = A[low]; } A[low] = pivot; return low; } void QuickSort(int A[], int low, int high) { if (low < high) { int pos = Partition(A, low, high); QuickSort(A, low, pos - 1); QuickSort(A, pos + 1, high); } }快排每一趟会确定一个枢纽元素的最终位置。题目有时给出一组中间序列，问它是哪种排序的某一趟结果，这时要利用“每一趟的局部有序性”和“元素相对位置”来判断。
排序复杂度速查表：
| 排序算法 | 平均时间 | 最坏时间 | 最好时间 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 直接插入 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 希尔 | O(n^1.3) 左右 | O(n^2) | O(n) | O(1) | 不稳定 |
| 冒泡 | O(n^2) | O(n^2) | O(n) | O(1) | 稳定 |
| 快速 | O(n log n) | O(n^2) | O(n log n) | O(log n) | 不稳定 |
| 简单选择 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不稳定 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 |
| 基数排序 | O(d(n+r)) | O(d(n+r)) | O(d(n+r)) | O(r) | 稳定 |
稳定性的判断依据是“相同关键字的相对位置是否会被改变”。相邻交换类的算法通常稳定，跨越较大距离交换的算法通常不稳定。这样理解比死背口诀更可靠。
7. 算法题练习：从读题到验证的完整闭环
7.1 平时练习环境怎么搭
算法题需要能编译、能调试、能构造测试样例。本地环境可以选 Dev-C++、Code::Blocks、Visual Studio Code 配合 C/C++ 插件，也可以直接用 Linux 下的 gcc 和 gdb。关键是不要只会面向在线判题系统写代码，导致本地一调试就无从下手。
最小练习模板可以做成固定结构：
#include <stdio.h> #include <stdlib.h> #include <string.h> // 定义数据结构 typedef struct Node { int data; struct Node *next; } Node; // 核心算法 Node *reverseList(Node *head) { Node *pre = NULL; Node *cur = head; while (cur != NULL) { Node *next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } int main() { // 构造测试样例 Node a = {1, NULL}; Node b = {2, NULL}; Node c = {3, NULL}; a.next = &b; b.next = &c; Node *newHead = reverseList(&a); for (Node *p = newHead; p != NULL; p = p->next) { printf("%d ", p->data); } return 0; }测试样例至少包括四类：
1. 正常数据：能跑通主流程 2. 边界数据：空表、单节点、满队列、空树 3. 重复数据：多个相同元素，检查稳定性 4. 大输入：评估时间和空间是否超限7.2 考场作答和平时练习环境的差异
平时在 IDE 里写代码，有语法高亮、自动补全和编译提示，能迅速修正小错误。考场手写代码则完全不同：不能编译，不能单步调试，甚至不能擦掉重写太多。这个差异要提前适应。
| 对比项 | 平时练习环境 | 考场手写环境 |
|---|---|---|
| 语法检查 | 编译即时报错 | 没有编译提示 |
| 调试 | 可以打断点 | 只能人工模拟运行 |
| 试错成本 | 低，可以多次重跑 | 高，写错要涂改 |
| 代码风格 | 只要通过即可 | 要兼顾清晰和简洁 |
| 复杂度分析 | 可以不写 | 答题要求写出 |
建议在强化阶段每周安排 2 到 3 次“手写算法”练习。选择一道真题或教材习题，先在 A4 纸上写完整代码，再对照参考答案检查。重点检查函数签名、循环边界、递归终止条件和返回值。
动手之前先写算法思想，再写代码，最后写时间复杂度。这种顺序正是 408 算法题的答题规范，平时养成习惯，考场上才不会漏步骤。
8. 复习中常见的坑与排查清单
8.1 六个必须避开的复习误区
第一个误区是看会等于学会。课件看一遍、视频看一遍，觉得自己懂了，合上书却写不出单链表反转。数据结构不靠眼睛学，靠手学。每章结束至少要合书默写两个核心算法。
第二个误区是只背复杂度，不理解算法过程。题目只要把排序序列换一组，就不知道哪一趟结果对。建议每个排序算法都要手工模拟 5 个元素以上。
第三个误区是忽略边界。二分查找的循环条件是 low <= high 还是 low < high，链表反转过程中 next 指针是否会变空，循环队列判满为什么用 (rear+1) % MaxSize。这些问题必须靠边界样例验证。
第四个误区是盲目追求难题。有些同学喜欢刷竞赛难度的题目，反而把 408 真题中基础且重复出现的考点忽略掉。408 算法题更看基本功，优先把真题、教材课后题和常见代码模板练熟。
第五个误区是排序只看口诀。稳定性、时间复杂度和空间复杂度可以整理成表格，但必须理解为什么一种排序稳定、另一种不稳定。否则选择题只要改一个条件，记忆就会失效。
第六个误区是长期不手写。在线判题系统通过并不代表考场能写好代码。从 9 月开始，坚持每周手写几次，能显著减少考场上语法错误的概率。
8.2 做题报错时的排查顺序
当代码运行结果不符合预期时，可以按下面的顺序排查：
1. 检查输入输出格式 2. 检查数组下标和表长是否越界 3. 检查空指针和空结构 4. 检查递归终止条件和返回值 5. 检查复杂度是否超限 6. 检查输出格式和多余空格例如链表反转报段错误，优先检查 cur 是否为 NULL、next 指针是否提前丢失；递归遍历二叉树结果错乱，优先检查是否先访问了右子树；循环队列元素个数算错，优先检查模运算在负数时是否按预期处理。
一道题如果思路正确但结果不对，不要反复重写整个函数。先在纸上模拟一次，用三到五个元素跑一遍，定位到具体出错的那一步。这样比盲目修改代码更快。
8.3 冲刺阶段每日自查清单
冲刺阶段适合用清单做每日复盘，避免在重复的内容上消耗过多时间。
| 检查项 | 做法 |
|---|---|
| 线性表 | 手写单链表反转、有序链表合并 |
| 栈和队列 | 手写循环队列入队出队、括号匹配 |
| 二叉树 | 手写先序非递归、求树高、中序线索化思路 |
| 图 | 手写 DFS、BFS，能用邻接矩阵和邻接表转换 |
| 查找 | 折半查找边界分析、哈希冲突计算 |
| 排序 | 手写快排 partition、堆排序筛选过程 |
| 复杂度 | 每道题末尾标注时间和空间复杂度 |
| 错题整理 | 把错题对应到知识图谱节点，重新做一遍 |
| 限时模拟 | 每周一次完整的 408 选择题限时训练 |
数据结构这门课真正的复习效果，不在于看了多少遍笔记，而在于能不能随手画出每类结构的存储图、在纸上写出核心算法、并解释清楚为什么某个操作是那个复杂度。把一图流变成真正属于自己的知识图，408 数据结构的复习才算过关。下一轮做题时，遇到陌生的代码题，先回到逻辑结构、存储结构、操作、应用这四条线里定位，思路会清楚很多。
