数据结构是计算机专业的“内功心法”也是 408 考研中投入产出比最高的一门课。它不像计算机网络那样知识点零散也不像计算机组成原理那样需要大量硬件基础而是有一套非常清晰的逻辑主线按存储结构分类、按操作场景设计、按时间空间复杂度取舍。很多同学复习数据结构时容易陷入“学了后面忘前面”的困境或者刷题时觉得“每个题都见过但每个题都不确定”。根本原因不是不够努力而是缺少一张能把所有知识点串起来的地图。本文就用“一图流”的思路把 408 数据结构涉及的核心概念、重难点、常考题型、复习优先级一次性梳理清楚后续你可以据此建立自己的知识框架。如果你正在准备 408 考研或者正在期末复习数据结构、准备保研面试这篇文章可以作为你的复习导览。内容覆盖线性表、栈、队列、串、树与二叉树、图、查找、排序以及每个模块在 408 中的常见考法和复习建议。1. 为什么要用“一图流”复习数据结构先解释一个概念什么是“一图流”复习法。简单说就是把一门课的全部核心知识点用一张结构化的“知识地图”呈现出来。为什么这对数据结构特别有效因为数据结构的本质是在特定存储结构上定义特定操作而存储结构只有两类顺序存储和链式存储。抓住这个源头你会发现所有数据结构都是“同一棵树上的不同分支”。举个例子线性表用数组存就是顺序表用指针串起来就是链表。栈和队列是操作受限的线性表所以它们也有顺序栈、链栈、顺序队列、链队列之分。树可以用双亲数组、孩子链表、二叉链表存储。图可以用邻接矩阵或邻接表存储。当你理解了“存”与“取”的关系很多细节就不需要死记硬背。比如为什么循环队列要预留一个存储单元因为需要区分队空和队满。为什么二叉树用二叉链表存储就够了因为每个节点最多只有两个孩子。这些知识点不是孤立的而是由“存储 操作 边界条件”共同决定的。一图流复习的另一个优势是帮助查漏补缺。你可以先试着凭记忆画一张数据结构知识导图画不出来的部分就是你的薄弱点。然后再对照本文的框架标记出哪些是你已经掌握的、哪些是需要在真题中反复强化的。2. 408 数据结构整体知识地图先上一张文字版的知识地图这是全文的总纲。建议你把它抄下来或者自己画一张思维导图作为后续复习的索引。数据结构 ├── 线性结构 │ ├── 线性表 │ │ ├── 顺序表 │ │ └── 链表单链表、双链表、循环链表、静态链表 │ ├── 栈 │ │ ├── 顺序栈、链栈 │ │ └── 共享栈 │ ├── 队列 │ │ ├── 顺序队列、循环队列 │ │ └── 链队列、双端队列 │ └── 串 │ ├── 朴素模式匹配 │ └── KMP 算法 ├── 非线性结构 │ ├── 树与二叉树 │ │ ├── 二叉树性质、存储、遍历 │ │ ├── 线索二叉树 │ │ ├── 树与森林互转 │ │ ├── 哈夫曼树与编码 │ │ └── 并查集 │ ├── 图 │ │ ├── 图的存储邻接矩阵、邻接表 │ │ ├── 图的遍历BFS、DFS │ │ ├── 最小生成树Prim、Kruskal │ │ ├── 最短路径Dijkstra、Floyd │ │ ├── 拓扑排序 │ │ └── 关键路径 │ └── 查找 │ ├── 顺序查找、折半查找 │ ├── 二叉排序树、平衡二叉树、红黑树 │ ├── B 树、B 树 │ └── 哈希表散列函数、冲突处理、装填因子 └── 排序 ├── 插入类直接插入、折半插入、希尔 ├── 交换类冒泡、快速 ├── 选择类简单选择、堆排序 ├── 归并类二路归并 └── 基数排序从这张地图可以看出数据结构学习有两条主线按逻辑结构分类线性结构、树形结构、图形结构、集合结构。按操作目标分类查找和排序是建立在特定存储结构上的算法设计。408 选择题的常见考法是给一个场景问你应该选哪种存储结构、哪种算法或者某种算法的平均/最坏时间复杂度。综合应用题的常见考法是让你手动模拟一个算法过程如快速排序一趟划分、Dijkstra 求最短路径、构造哈夫曼树或者让你设计一个小型算法。下面按模块展开逐个说明核心考点和复习重点。3. 线性表一切数据结构的基础线性表是数据结构中最简单、最基础的结构也是 408 的必考内容。它直接考察你对顺序存储和链式存储的理解很多综合题的小问都会以链表操作为背景。3.1 顺序表与链表对比顺序表和链表的选择是高频选择题。需要掌握以下判断依据顺序表支持随机访问时间复杂度 O(1)链表不支持随机访问查找第 k 个元素需要 O(n)。顺序表插入/删除需要移动大量元素平均移动 n/2 次链表只要修改指针时间复杂度 O(1)前提是已经定位到目标节点。顺序表需要预分配连续空间扩容代价高链表按需分配节点空间利用率更灵活。顺序表适合“存多改少、频繁按下标访问”的场景链表适合“频繁插入删除、长度不确定”的场景。代码层面顺序表的核心是理解数组下标与元素位序的关系。C 语言中数组下标从 0 开始而教材中线性表的位序通常从 1 开始。408 真题经常在这个细节上设置陷阱。// 顺序表结构体定义408 高频写法 #define MaxSize 50 typedef struct { int data[MaxSize]; // 存放元素 int length; // 当前长度 } SqList; // 在第 i 个位置插入元素 e // 注意i 的范围是 1 i length 1 bool ListInsert(SqList *L, int i, int e) { if (i 1 || i L-length 1) { return false; } if (L-length MaxSize) { return false; // 存储满 } for (int j L-length; j i; j--) { L-data[j] L-data[j - 1]; // 从后往前移动元素 } L-data[i - 1] e; L-length; return true; }3.2 单链表的头插法与尾插法头插法和尾插法是建立链表最常用的两种方法408 选择题和算法题都爱考。头插法每次把新节点插入到头节点之后最终得到的链表顺序与输入顺序相反。尾插法需要维护一个尾指针得到的链表顺序与输入顺序一致。typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 头插法建立单链表 LinkList List_HeadInsert(LinkList *head) { *head (LNode *)malloc(sizeof(LNode)); // 头节点 (*head)-next NULL; int x; scanf(%d, x); while (x ! -1) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data x; s-next (*head)-next; // 新节点指向原首元节点 (*head)-next s; // 头节点指向新节点 scanf(%d, x); } return *head; }复习线性表时的常见误区忘记判断“插入位置是否合法”和“链表是否为空”。在删除链表节点时没有先用临时变量保存待删节点导致 free 后无法访问 next 指针。没有区分“头节点”和“首元节点”。头节点是虚拟节点不存储有效数据作用是统一空表和非空表的操作逻辑。4. 栈、队列与串操作受限的线性结构栈和队列是线性表的“特长生”它们限制了操作位置。这类题目在 408 中不仅出现在选择题也会作为综合题的小问出现。4.1 栈的核心考点栈是后进先出LIFO结构只能在栈顶插入和删除。核心考点有三个方向方向一出栈序列的合法性判断。给定入栈序列 1, 2, 3, ..., n判断某个出栈序列是否合法。核心定理是出栈序列中若元素 i j k则 k 不能在 i、j 之前出栈即“大数不能压在小数上面弹出”更准确地说任意三个元素若入栈顺序递增则出栈顺序不能出现 k, i, j 这种逆序模式。更简洁的方法是模拟入栈出栈过程。方向二栈的存储实现。包括顺序栈和链栈。408 常考栈空、栈满条件特别是共享栈的两个栈顶指针相遇时栈满。方向三栈的应用。括号匹配、表达式求值、递归消除、迷宫求解。其中表达式求值是重中之重需要掌握中缀转后缀、后缀表达式求值。// 顺序栈结构体 #define MaxSize 50 typedef struct { int data[MaxSize]; int top; // 栈顶指针 } SqStack; // 栈满条件top MaxSize - 1 // 栈空条件top -1 // 入栈data[top] x; // 出栈x data[top--];4.2 队列的核心考点队列是先进先出FIFO结构。408 最爱考的是循环队列。为什么要用循环队列因为普通顺序队列在出队后队头指针前移会导致“假溢出”——明明数组前面有空位队尾指针却已经到末尾了。循环队列通过取模运算让队尾指针可以绕回数组开头。循环队列有三个关键条件必须背熟队空条件front rear队满条件(rear 1) % MaxSize front队列长度(rear - front MaxSize) % MaxSize这里有一个容易混淆的点循环队列浪费了一个存储单元来区分队空和队满。如果不浪费这个单元就需要在结构体中额外增加一个 size 字段或 tag 字段来标记状态。#define MaxSize 50 typedef struct { int data[MaxSize]; int front, rear; // 队头队尾指针 } SqQueue; // 入队将元素放入 rear 位置然后 rear (rear 1) % MaxSize // 出队取出 front 位置元素然后 front (front 1) % MaxSize // 队满条件(rear 1) % MaxSize front408 考试还经常考双端队列。双端队列允许在两端进行插入和删除。考试常问“输入受限的双端队列”或“输出受限的双端队列”能否得到某种输出序列。这种题目本质上还是在考栈的输出序列合法性只不过多了另一个操作端口需要灵活分析。4.3 串与 KMP 算法串是线性表的推广但 408 对串的考试要求集中在字符串匹配上。朴素匹配算法很容易理解就是逐位比较失配后主串回溯到下一位模式串回到开头。时间复杂度 O(n*m)。KMP 算法解决了朴素匹配中主串回溯导致效率低下的问题核心是 next 数组。很多人觉得 KMP 难是因为没有理解 next 数组的含义next[j] 表示当第 j 个字符失配时模式串应该跳到哪个位置继续比较。它本质上是在模式串中找“最长相等前后缀”。next 数组的推导规则408 常用版本next[1] 0。next[2] 1。对于 j 2next[j] 为模式串前 j-1 个字符组成的子串的最长相等前后缀长度 1。例如模式串abaabc计算时先看每个前缀的最长相等前后缀前缀a无前后缀next[1] 0。前缀ab最长相等前后缀长度为 0next[2] 1。前缀aba最长相等前后缀为a长度 1next[3] 2。前缀abaa最长相等前后缀为a长度 1next[4] 2。前缀abaab最长相等前后缀为ab长度 2next[5] 3。完整串abaabc最长相等前后缀为 0next[6] 1。所以 next 数组为0 1 1 2 2 3下标从 1 开始。KMP 配 next 数组的 C 语言核心逻辑如下// 求模式串 T 的 next 数组 // 注意T[0] 存储串长字符从下标 1 开始 void getNext(char T[], int next[]) { int i 1, j 0; next[1] 0; while (i T[0]) { if (j 0 || T[i] T[j]) { i; j; next[i] j; } else { j next[j]; } } }需要提醒的是不同教材对 next 数组的定义有差异。王道、严蔚敏版本和部分高校教材的 next[1] 可能是 0也可能有“nextval 优化”的版本。考试时先看清楚题目是“求 next 数组”还是“求 nextval 数组”不要混淆。5. 树与二叉树408 的“半壁江山”如果说线性表是数据结构的基础那树就是 408 数据结构的核心。选择题、综合题都离不开树尤其是二叉树。这个模块知识点多、性质多、算法多是复习耗时最长的一部分。5.1 二叉树的重要性质以下性质是选择题的“常客”必须做到能快速推导而不是死记非空二叉树的叶子节点数 度为 2 的节点数 1即 n0 n2 1。二叉树的第 i 层最多有 2^(i-1) 个节点i 1。深度为 k 的二叉树最多有 2^k - 1 个节点k 1。具有 n 个节点的完全二叉树深度为 ⌊log2 n⌋ 1。完全二叉树中编号为 i 的节点左孩子编号 2i右孩子编号 2i1父节点编号 ⌊i/2⌋。这些性质不仅仅是理论还直接决定了完全二叉树可以用顺序存储。因为完全二叉树的节点编号是连续的所以你能用一个一维数组存下整棵树不需要指针。5.2 二叉树的遍历二叉树的先序、中序、后序、层序遍历是必考内容。408 选择题最常见的是已知先序 中序求后序或已知后序 中序求先序。这里有一个判断技巧中序序列必须知道否则无法唯一确定一棵二叉树。前序 中序重建二叉树的递推思路是前序第一个节点是根在中序中找到根的位置左边是左子树右边是右子树然后递归处理。// 根据先序序列 pre[] 和中序序列 in[] 重建二叉树 // 参数说明 // preL, preR 为先序区间下标inL, inR 为中序区间下标 BiTree buildTree(int preL, int preR, int inL, int inR) { if (preL preR) { return NULL; } BiTree root (BiTree)malloc(sizeof(BiTNode)); root-data pre[preL]; // 在中序中找到根节点位置 int k inL; while (in[k] ! pre[preL]) { k; } int leftLen k - inL; // 左子树节点个数 root-lchild buildTree(preL 1, preL leftLen, inL, k - 1); root-rchild buildTree(preL leftLen 1, preR, k 1, inR); return root; }遍历是很多树算法的基础。后续的线索二叉树、二叉排序树、平衡二叉树、哈夫曼树本质上都是在遍历的基础上做文章。5.3 二叉树与森林的转换408 选择题经常考一棵树转换成二叉树后它的某种遍历序列是什么。核心规则是左孩子右兄弟树转换成二叉树每个节点的第一个孩子作为左孩子第一个孩子的兄弟作为右孩子。森林转换成二叉树第一棵树的根作为根其他树的根作为第一棵树根的右子树链。一个高频结论树的先序遍历 转换后二叉树的先序遍历树的后序遍历 转换后二叉树的中序遍历。这个结论在选择题里可以直接套用能节省大量时间。5.4 哈夫曼树与哈夫曼编码哈夫曼树是带权路径长度WPL最小的二叉树。构造方法每次从节点集合中选出两个权值最小的节点作为新节点的左右孩子新节点权值为两者之和然后放回集合重复直到只剩一个节点。考试常见题型给定权值集合求哈夫曼树的 WPL。给定权值集合画出哈夫曼树并写出哈夫曼编码。判断某个编码是否是前缀编码。求 WPL 时有一个简便方法WPL 所有非叶节点的权值之和。因为每个非叶节点都被构造过程中累加过。例如权值 {2, 3, 4, 7}构造过程中新增节点权值依次为 5、9、16所以 WPL 5 9 16 30。哈夫曼编码的重要特征是没有任何一个编码是另一个编码的前缀因此解码时不需要分隔符可以唯一还原。408 常以“判断一组编码是否为合法的哈夫曼编码”命题解法就是检查前缀冲突。5.5 并查集并查集是 408 大纲中一个相对独立的内容常与图的最小生成树Kruskal 算法结合考察。并查集支持两种操作查找Find和合并Union。它的存储结构是一个双亲数组parent[i]表示节点 i 的父节点根节点的父节点指向自己或为 -1。#define MAXN 1000 int parent[MAXN]; // 初始化每个节点都是独立的集合 void init(int n) { for (int i 1; i n; i) { parent[i] -1; // 根节点用负数表示集合大小 } } // 查找根节点带路径压缩 int find(int x) { if (parent[x] 0) { return x; } // 路径压缩让路径上的所有节点直接指向根 return parent[x] find(parent[x]); } // 合并两个集合小树并入大树 void unionSet(int a, int b) { int ra find(a); int rb find(b); if (ra rb) { return; } if (parent[ra] parent[rb]) { // 注意负数比较越小表示树越大 int temp ra; ra rb; rb temp; } parent[ra] parent[rb]; parent[rb] ra; }路径压缩和按规模合并能让并查集的操作时间复杂度接近 O(1)这是 Kruskal 算法高效的原因。6. 图从存储到算法的完整链路图是数据结构中逻辑最复杂、算法最多的部分。408 对图的要求包括存储结构、遍历、最小生成树、最短路径、拓扑排序、关键路径。其中 Dijkstra、Prim、Kruskal、Floyd 这四大算法是重中之重。6.1 图的两种存储结构邻接矩阵用二维数组存储A[i][j]表示顶点 i 到顶点 j 是否有边或边的权值。优点是判断两个顶点是否相邻只需要 O(1)缺点是空间复杂度 O(n²)适合稠密图。邻接表对每个顶点建立一个链表链表中存储该顶点的所有邻接点。优点是空间复杂度 O(ne)适合稀疏图缺点是需要遍历链表才能判断两个顶点是否相邻。408 选择题常问“某个图的邻接表长什么样”或者“用邻接表和邻接矩阵分别做 BFS/DFS 的时间复杂度”。需要牢记邻接矩阵做 DFS/BFS时间复杂度 O(n²)。邻接表做 DFS/BFS时间复杂度 O(ne)。6.2 最小生成树Prim 与 Kruskal最小生成树是连通无向图中所有生成树里各边权值之和最小的那棵。Prim 算法的特点是从顶点出发每次选择当前连通集合与外部之间权值最小的边。时间复杂度 O(n²)适合稠密图。Kruskal 算法的特点是从边出发按权值从小到大选择边只要不构成回路就加入。时间复杂度 O(e·log e)适合稀疏图。判断是否构成回路就用到了并查集。一个常考结论当图中有权值相同的边时最小生成树不一定唯一。但如果所有边的权值互不相同则最小生成树唯一。6.3 最短路径Dijkstra 与 FloydDijkstra 算法用于求单源最短路径即从一个源点出发到其他所有顶点的最短路径。算法思想是贪心每次从未确定最短路径的顶点中选一个距离源点最近的顶点加入集合然后更新它的邻接点。Dijkstra 不适用于负权边这是常考点。Floyd 算法用于求所有顶点之间的最短路径核心思想是动态规划允许经过前 k 个顶点中转逐步求解。Floyd 可以处理负权边但不能有负权回路。// Floyd 算法核心代码 // 邻接矩阵 dist[i][j] 初始为边的权值不相邻为正无穷 void floyd(int n, int dist[][MAXN]) { for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { // 经过 k 点中转后距离是否变小 if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } }理解 Floyd 的关键是三层循环的顺序。最外层一定是“中转点 k”而不是 i 或 j。如果这个顺序写反求出来的就是错的。6.4 拓扑排序与关键路径拓扑排序用于有向无环图DAG输出的序列要满足每个顶点出现且只出现一次如果存在边 A→B则 A 必须排在 B 前面。实现方法每次输出一个入度为 0 的顶点然后删除它和它的出边。AOV 网顶点表示活动求拓扑排序AOE 网边表示活动求关键路径。关键路径是 AOE 网中从源点到汇点的最长路径关键路径上的活动称为关键活动。缩短关键活动可以缩短整个工期但缩短到一定程度后关键路径可能发生转移。408 真题中关键路径常以选择题形式考察需要会计算事件的最早发生时间 ve、最迟发生时间 vl以及活动的最早开始时间、最迟开始时间。7. 查找顺序表、树表与哈希表查找模块在 408 中属于“块头不大但分值稳定”的内容。重点关注折半查找、二叉排序树、平衡二叉树、哈希表。7.1 折半查找与判定树折半查找要求查找表有序且采用顺序存储。平均查找长度 O(log n)但插入删除不方便。折半查找的过程可以画成一棵判定树。判定树是一棵平衡二叉树树的高度决定了最坏情况下的比较次数。对于 n 个元素折半查找最多比较 ⌊log2 n⌋ 1 次。408 选择题可能会给出折半查找的判定树让你求某个元素的比较次数。7.2 二叉排序树 BST二叉排序树左子树所有节点值小于根右子树所有节点值大于根中序遍历得到递增序列。BST 最重要的考点是删除操作删除叶子节点直接删除。删除只有一个孩子的节点让孩子顶替被删节点。删除有两个孩子的节点用被删节点的中序前驱或中序后继代替它然后删除那个前驱/后继节点。一个常见误区是“把左子树最大的节点替换上去之后忘记处理该节点的左子树”。实际上左子树最大节点要么是叶子要么只有左孩子所以替换后的删除操作是简单的。BST 的查找效率与树的高度相关。最坏情况下插入序列有序BST 退化成单链表查找复杂度 O(n)。这就引出了平衡二叉树。7.3 平衡二叉树 AVL平衡二叉树要求任意节点的左右子树高度差绝对值不超过 1。插入节点后从插入点向上找第一个不平衡的节点然后根据不平衡模式进行 LL、RR、LR、RL 旋转。LL右旋。RR左旋。LR先左旋后右旋。RL先右旋后左旋。408 考试常让你画出插入若干节点后的平衡二叉树或者计算平衡二叉树的最小节点数。这里有一个公式值得记忆高度为 h 的平衡二叉树至少需要的节点数 N(h) N(h-1) N(h-2) 1其中 N(0) 0N(1) 1。这个公式和斐波那契数列很像常用来手算最小节点数。7.4 哈希表哈希表通过散列函数把关键字映射到存储位置理想情况下查找 O(1)。408 必考内容集中在散列函数的构造除留余数法 H(key) key % pp 通常取不大于表长的质数。冲突处理方法开放定址法线性探测、平方探测、再散列和链地址法。装填因子 α 表中记录数 / 表长。平均查找长度 ASL 的手动计算分为查找成功和查找失败两种情况。线性探测法容易产生“堆积”现象因为发生冲突时关键字会占据本来不属于它的位置。链地址法把冲突元素放在同一个链表里不会堆积但需要额外空间。// 链地址法哈希表节点定义 typedef struct HashNode { int key; struct HashNode *next; } HashNode; // 哈希表一个指针数组每个元素是一条链表的头指针 #define HASHSIZE 13 HashNode *hashTable[HASHSIZE]; // 用除留余数法计算哈希地址 int hash(int key) { return key % HASHSIZE; }408 选择题中哈希表题目通常需要你手工模拟哈希表的构建过程。记住线性探测的规则是“遇到空位就放找不到就往后找绕一圈回到起点还没有就表满”而查找失败时的比较次数要一直数到空位置为止。8. 排序算法对比记忆逐一攻破排序是数据结构中代码量最大、算法思想最多的部分。408 对排序的要求是掌握每一种排序算法的过程、时间复杂度、空间复杂度、稳定性并会手工模拟一趟排序过程。8.1 排序算法总览表这张表建议反复默写排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入O(n²)O(n²)O(1)稳定折半插入O(n²)O(n²)O(1)稳定希尔排序O(n^1.3) 左右O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定快速排序O(n·log n)O(n²)O(log n)不稳定简单选择O(n²)O(n²)O(1)不稳定堆排序O(n·log n)O(n·log n)O(1)不稳定归并排序O(n·log n)O(n·log n)O(n)稳定基数排序O(d(nr))O(d(nr))O(r)稳定注意快速排序最坏情况发生在每次划分都极度不均匀时比如序列已经有序。此时每次划分只确定一个元素的位置退化为 O(n²)。但快排的平均性能是所有排序算法中最好的这是它被称为“快排”的原因。8.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); } }408 选择题经常问“经过一趟快排后哪些元素已经处于最终位置”。答案是基准元素一定在最终位置而且所有划分元素都满足“左边都比它小右边都比它大”。8.3 堆排序堆排序是选择排序的优化用到了完全二叉树的性质。大根堆中每个节点的值都大于等于其左右孩子小根堆则相反。堆排序的关键操作是“下沉”和“建堆”。给你一个数组建初始大根堆的步骤从最后一个非叶节点开始即下标 n/2依次向前做下沉调整。// 以 i 为根调整为大根堆 // n 为堆中元素个数 void adjustDown(int a[], int i, int n) { int val a[i]; // 暂存当前节点值 for (int j 2 * i; j n; j * 2) { if (j n a[j] a[j 1]) { j; // 选择较大的孩子 } if (val a[j]) { break; } a[i] a[j]; // 孩子上移 i j; } a[i] val; } // 堆排序先建堆再依次输出堆顶 void heapSort(int a[], int n) { for (int i n / 2; i 1; i--) { adjustDown(a, i, n); // 建初始堆 } for (int i n; i 1; i--) { int temp a[1]; // 堆顶与末尾交换 a[1] a[i]; a[i] temp; adjustDown(a, 1, i - 1); // 重新调整 } }堆排序常考的点堆的插入新节点插入末尾向上调整、建堆时间复杂度 O(n)、堆排序时间复杂度 O(n·log n)、堆排序不稳定。9. 408 真题的考察方式与复习策略了解“怎么考”才知道“怎么复习”。408 数据结构部分的真题主要有两类第一类选择题约 11 道。覆盖范围广从基础概念到复杂算法都有。常见的命题角度有给一段代码问时间复杂度。给一个数据结构问它的存储特点或操作结果。给一个场景要求选择最优数据结构。让手动模拟排序算法的一趟过程。给一个图求最小生成树、最短路径或关键路径。判断某个数据结构的性质是否成立。选择题往往考查的是“计算”和“模拟”而不是死记概念。所以复习时一定要动手画图、动手推演不能只看不练。第二类综合应用题约 2 道。数据结构在 408 中一般有两道大题常见形式是第一道大题通常是线性表或二叉树相关的算法设计题用 C 语言写出算法思路和代码或者补全代码。第二道大题通常是图或排序相关的综合题要求分析算法过程、统计时间空间复杂度或者解决一个具体的应用问题。综合题的评分方式是“按步骤给分”所以在考场上即使写不出完整代码也要把算法思路、数据结构定义、关键步骤写清楚。9.1 高效复习路线建议如果你从现在开始准备数据结构建议按下面的阶段推进基础阶段约 4 周构建知识框架。对照本文的知识地图先过一遍教材或视频每学完一个模块就做对应的基础题。这个阶段不求快但求把每个原理搞清楚。核心任务是理解“存储结构 操作”的对应关系。强化阶段约 3 周刷题 手写代码。开始刷 408 真题和题库中的选择题、算法题。每道题都要尝试手动模拟过程。特别是排序、图算法、哈希表查找过程不要在草稿纸上跳步完整模拟一到两遍考试时才能稳定输出。冲刺阶段约 2 周按真题套卷限时练习。这时候不要只做数据结构单科题要按整套 408 真题的时间来模拟。数据结构部分控制在 50 到 60 分钟内完成。做完后重点复盘错题确定是概念不清、计算失误还是审题偏差。9.2 数据结构与其他 408 科目的联系408 的四门科目之间是有联动关系的。复习数据结构时可以注意以下联系数据结构 计算机组成原理栈的实现与函数调用栈、数的原码补码表示与数据类型的存储、Cache 与局部性原理对数据访问效率的影响。数据结构 操作系统进程调度中的队列、内存管理中的页表类哈希表思想、文件系统的索引结构与 B 树。数据结构 计算机网络路由算法的本质是在图上求最短路径TCP 滑动窗口和缓冲区本质上也是队列的应用。如果你能在复习时把这些跨科目联系点串起来不但能加深对数据结构的理解还能顺便复习其他科目事半功倍。10. 高频易错点与避坑指南结合历届考生和期末复习常犯的错误这里整理一份避坑清单易错点错误认知正确理解循环队列长度计算直接用 rear - front应使用 (rear - front MaxSize) % MaxSize树转二叉树后序遍历结果不变树的后序对应二叉树的中序KMP next 数组next[j] 是“最长相等前后缀长度”next[j] 是最长相等前后缀长度 1完全二叉树存储所有二叉树都能顺序存储只有完全二叉树才能用顺序存储且不浪费空间折半查找前提链表也可以折半查找折半查找必须随机访问链表不行哈希表删除线性探测法可以直接删除记录直接删除会破坏探测链需要“软删除”标记快速排序最坏情况随机数据时最坏初始序列有序/逆序时最坏堆排序建堆时间认为建堆是 O(n·log n)自底向上建堆总复杂度 O(n)Dijkstra 算法可以处理负权边Dijkstra 基于贪心不适用于负权边拓扑排序结果唯一拓扑序列唯一同时存在多个入度为 0 的顶点时拓扑序列不唯一这十个易错点几乎每年都会以某种形式出现在选择题或分析题中。建议你把这张表抄在笔记扉页每次做题前扫一眼形成条件反射。11. 总结与下一步行动写到这里408 数据结构的主要脉络已经全部梳理了一遍。我们沿着“数据结构 存储结构 操作集合”这条主线把线性表、栈、队列、串、树、图、查找、排序串成了一张完整的知识网。这张网既是复习的索引也是查漏补缺的清单。下一步你可以做三件事第一凭记忆画出你自己的知识地图。不要看书也不要看笔记就凭记忆写能写多少写多少。写完之后对照本文找出那些你没写出来或者写得模糊的部分这些就是你当前最大的提分点。第二针对薄弱模块做专项练习。如果树这块薄弱就把遍历、重建、线索化、BST 删除、AVL 旋转、哈夫曼编码一次性练透。不要“雨露均沾”要集中火力突破薄弱环节。第三把核心代码手写一遍。数据结构的关键不是“看懂”而是“能写出来”。限时 15 分钟手写快速排序或二叉树中序遍历然后对照标准答案检查细节。这个过程重复三到五次考场上你会非常自信。数据结构是一门“开窍之后越学越顺”的科目。如果你正在为 408 考研焦虑或者被期末的算法题折磨不要怕按图索骥逐个模块击穿。掌握好这些原型算法和数据结构你赢下的不只是数据结构这一科而是整个 408 的地基。 408数据结构一图流复习：线性表、树、图与排序算法全梳理
数据结构是计算机专业的“内功心法”也是 408 考研中投入产出比最高的一门课。它不像计算机网络那样知识点零散也不像计算机组成原理那样需要大量硬件基础而是有一套非常清晰的逻辑主线按存储结构分类、按操作场景设计、按时间空间复杂度取舍。很多同学复习数据结构时容易陷入“学了后面忘前面”的困境或者刷题时觉得“每个题都见过但每个题都不确定”。根本原因不是不够努力而是缺少一张能把所有知识点串起来的地图。本文就用“一图流”的思路把 408 数据结构涉及的核心概念、重难点、常考题型、复习优先级一次性梳理清楚后续你可以据此建立自己的知识框架。如果你正在准备 408 考研或者正在期末复习数据结构、准备保研面试这篇文章可以作为你的复习导览。内容覆盖线性表、栈、队列、串、树与二叉树、图、查找、排序以及每个模块在 408 中的常见考法和复习建议。1. 为什么要用“一图流”复习数据结构先解释一个概念什么是“一图流”复习法。简单说就是把一门课的全部核心知识点用一张结构化的“知识地图”呈现出来。为什么这对数据结构特别有效因为数据结构的本质是在特定存储结构上定义特定操作而存储结构只有两类顺序存储和链式存储。抓住这个源头你会发现所有数据结构都是“同一棵树上的不同分支”。举个例子线性表用数组存就是顺序表用指针串起来就是链表。栈和队列是操作受限的线性表所以它们也有顺序栈、链栈、顺序队列、链队列之分。树可以用双亲数组、孩子链表、二叉链表存储。图可以用邻接矩阵或邻接表存储。当你理解了“存”与“取”的关系很多细节就不需要死记硬背。比如为什么循环队列要预留一个存储单元因为需要区分队空和队满。为什么二叉树用二叉链表存储就够了因为每个节点最多只有两个孩子。这些知识点不是孤立的而是由“存储 操作 边界条件”共同决定的。一图流复习的另一个优势是帮助查漏补缺。你可以先试着凭记忆画一张数据结构知识导图画不出来的部分就是你的薄弱点。然后再对照本文的框架标记出哪些是你已经掌握的、哪些是需要在真题中反复强化的。2. 408 数据结构整体知识地图先上一张文字版的知识地图这是全文的总纲。建议你把它抄下来或者自己画一张思维导图作为后续复习的索引。数据结构 ├── 线性结构 │ ├── 线性表 │ │ ├── 顺序表 │ │ └── 链表单链表、双链表、循环链表、静态链表 │ ├── 栈 │ │ ├── 顺序栈、链栈 │ │ └── 共享栈 │ ├── 队列 │ │ ├── 顺序队列、循环队列 │ │ └── 链队列、双端队列 │ └── 串 │ ├── 朴素模式匹配 │ └── KMP 算法 ├── 非线性结构 │ ├── 树与二叉树 │ │ ├── 二叉树性质、存储、遍历 │ │ ├── 线索二叉树 │ │ ├── 树与森林互转 │ │ ├── 哈夫曼树与编码 │ │ └── 并查集 │ ├── 图 │ │ ├── 图的存储邻接矩阵、邻接表 │ │ ├── 图的遍历BFS、DFS │ │ ├── 最小生成树Prim、Kruskal │ │ ├── 最短路径Dijkstra、Floyd │ │ ├── 拓扑排序 │ │ └── 关键路径 │ └── 查找 │ ├── 顺序查找、折半查找 │ ├── 二叉排序树、平衡二叉树、红黑树 │ ├── B 树、B 树 │ └── 哈希表散列函数、冲突处理、装填因子 └── 排序 ├── 插入类直接插入、折半插入、希尔 ├── 交换类冒泡、快速 ├── 选择类简单选择、堆排序 ├── 归并类二路归并 └── 基数排序从这张地图可以看出数据结构学习有两条主线按逻辑结构分类线性结构、树形结构、图形结构、集合结构。按操作目标分类查找和排序是建立在特定存储结构上的算法设计。408 选择题的常见考法是给一个场景问你应该选哪种存储结构、哪种算法或者某种算法的平均/最坏时间复杂度。综合应用题的常见考法是让你手动模拟一个算法过程如快速排序一趟划分、Dijkstra 求最短路径、构造哈夫曼树或者让你设计一个小型算法。下面按模块展开逐个说明核心考点和复习重点。3. 线性表一切数据结构的基础线性表是数据结构中最简单、最基础的结构也是 408 的必考内容。它直接考察你对顺序存储和链式存储的理解很多综合题的小问都会以链表操作为背景。3.1 顺序表与链表对比顺序表和链表的选择是高频选择题。需要掌握以下判断依据顺序表支持随机访问时间复杂度 O(1)链表不支持随机访问查找第 k 个元素需要 O(n)。顺序表插入/删除需要移动大量元素平均移动 n/2 次链表只要修改指针时间复杂度 O(1)前提是已经定位到目标节点。顺序表需要预分配连续空间扩容代价高链表按需分配节点空间利用率更灵活。顺序表适合“存多改少、频繁按下标访问”的场景链表适合“频繁插入删除、长度不确定”的场景。代码层面顺序表的核心是理解数组下标与元素位序的关系。C 语言中数组下标从 0 开始而教材中线性表的位序通常从 1 开始。408 真题经常在这个细节上设置陷阱。// 顺序表结构体定义408 高频写法 #define MaxSize 50 typedef struct { int data[MaxSize]; // 存放元素 int length; // 当前长度 } SqList; // 在第 i 个位置插入元素 e // 注意i 的范围是 1 i length 1 bool ListInsert(SqList *L, int i, int e) { if (i 1 || i L-length 1) { return false; } if (L-length MaxSize) { return false; // 存储满 } for (int j L-length; j i; j--) { L-data[j] L-data[j - 1]; // 从后往前移动元素 } L-data[i - 1] e; L-length; return true; }3.2 单链表的头插法与尾插法头插法和尾插法是建立链表最常用的两种方法408 选择题和算法题都爱考。头插法每次把新节点插入到头节点之后最终得到的链表顺序与输入顺序相反。尾插法需要维护一个尾指针得到的链表顺序与输入顺序一致。typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 头插法建立单链表 LinkList List_HeadInsert(LinkList *head) { *head (LNode *)malloc(sizeof(LNode)); // 头节点 (*head)-next NULL; int x; scanf(%d, x); while (x ! -1) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data x; s-next (*head)-next; // 新节点指向原首元节点 (*head)-next s; // 头节点指向新节点 scanf(%d, x); } return *head; }复习线性表时的常见误区忘记判断“插入位置是否合法”和“链表是否为空”。在删除链表节点时没有先用临时变量保存待删节点导致 free 后无法访问 next 指针。没有区分“头节点”和“首元节点”。头节点是虚拟节点不存储有效数据作用是统一空表和非空表的操作逻辑。4. 栈、队列与串操作受限的线性结构栈和队列是线性表的“特长生”它们限制了操作位置。这类题目在 408 中不仅出现在选择题也会作为综合题的小问出现。4.1 栈的核心考点栈是后进先出LIFO结构只能在栈顶插入和删除。核心考点有三个方向方向一出栈序列的合法性判断。给定入栈序列 1, 2, 3, ..., n判断某个出栈序列是否合法。核心定理是出栈序列中若元素 i j k则 k 不能在 i、j 之前出栈即“大数不能压在小数上面弹出”更准确地说任意三个元素若入栈顺序递增则出栈顺序不能出现 k, i, j 这种逆序模式。更简洁的方法是模拟入栈出栈过程。方向二栈的存储实现。包括顺序栈和链栈。408 常考栈空、栈满条件特别是共享栈的两个栈顶指针相遇时栈满。方向三栈的应用。括号匹配、表达式求值、递归消除、迷宫求解。其中表达式求值是重中之重需要掌握中缀转后缀、后缀表达式求值。// 顺序栈结构体 #define MaxSize 50 typedef struct { int data[MaxSize]; int top; // 栈顶指针 } SqStack; // 栈满条件top MaxSize - 1 // 栈空条件top -1 // 入栈data[top] x; // 出栈x data[top--];4.2 队列的核心考点队列是先进先出FIFO结构。408 最爱考的是循环队列。为什么要用循环队列因为普通顺序队列在出队后队头指针前移会导致“假溢出”——明明数组前面有空位队尾指针却已经到末尾了。循环队列通过取模运算让队尾指针可以绕回数组开头。循环队列有三个关键条件必须背熟队空条件front rear队满条件(rear 1) % MaxSize front队列长度(rear - front MaxSize) % MaxSize这里有一个容易混淆的点循环队列浪费了一个存储单元来区分队空和队满。如果不浪费这个单元就需要在结构体中额外增加一个 size 字段或 tag 字段来标记状态。#define MaxSize 50 typedef struct { int data[MaxSize]; int front, rear; // 队头队尾指针 } SqQueue; // 入队将元素放入 rear 位置然后 rear (rear 1) % MaxSize // 出队取出 front 位置元素然后 front (front 1) % MaxSize // 队满条件(rear 1) % MaxSize front408 考试还经常考双端队列。双端队列允许在两端进行插入和删除。考试常问“输入受限的双端队列”或“输出受限的双端队列”能否得到某种输出序列。这种题目本质上还是在考栈的输出序列合法性只不过多了另一个操作端口需要灵活分析。4.3 串与 KMP 算法串是线性表的推广但 408 对串的考试要求集中在字符串匹配上。朴素匹配算法很容易理解就是逐位比较失配后主串回溯到下一位模式串回到开头。时间复杂度 O(n*m)。KMP 算法解决了朴素匹配中主串回溯导致效率低下的问题核心是 next 数组。很多人觉得 KMP 难是因为没有理解 next 数组的含义next[j] 表示当第 j 个字符失配时模式串应该跳到哪个位置继续比较。它本质上是在模式串中找“最长相等前后缀”。next 数组的推导规则408 常用版本next[1] 0。next[2] 1。对于 j 2next[j] 为模式串前 j-1 个字符组成的子串的最长相等前后缀长度 1。例如模式串abaabc计算时先看每个前缀的最长相等前后缀前缀a无前后缀next[1] 0。前缀ab最长相等前后缀长度为 0next[2] 1。前缀aba最长相等前后缀为a长度 1next[3] 2。前缀abaa最长相等前后缀为a长度 1next[4] 2。前缀abaab最长相等前后缀为ab长度 2next[5] 3。完整串abaabc最长相等前后缀为 0next[6] 1。所以 next 数组为0 1 1 2 2 3下标从 1 开始。KMP 配 next 数组的 C 语言核心逻辑如下// 求模式串 T 的 next 数组 // 注意T[0] 存储串长字符从下标 1 开始 void getNext(char T[], int next[]) { int i 1, j 0; next[1] 0; while (i T[0]) { if (j 0 || T[i] T[j]) { i; j; next[i] j; } else { j next[j]; } } }需要提醒的是不同教材对 next 数组的定义有差异。王道、严蔚敏版本和部分高校教材的 next[1] 可能是 0也可能有“nextval 优化”的版本。考试时先看清楚题目是“求 next 数组”还是“求 nextval 数组”不要混淆。5. 树与二叉树408 的“半壁江山”如果说线性表是数据结构的基础那树就是 408 数据结构的核心。选择题、综合题都离不开树尤其是二叉树。这个模块知识点多、性质多、算法多是复习耗时最长的一部分。5.1 二叉树的重要性质以下性质是选择题的“常客”必须做到能快速推导而不是死记非空二叉树的叶子节点数 度为 2 的节点数 1即 n0 n2 1。二叉树的第 i 层最多有 2^(i-1) 个节点i 1。深度为 k 的二叉树最多有 2^k - 1 个节点k 1。具有 n 个节点的完全二叉树深度为 ⌊log2 n⌋ 1。完全二叉树中编号为 i 的节点左孩子编号 2i右孩子编号 2i1父节点编号 ⌊i/2⌋。这些性质不仅仅是理论还直接决定了完全二叉树可以用顺序存储。因为完全二叉树的节点编号是连续的所以你能用一个一维数组存下整棵树不需要指针。5.2 二叉树的遍历二叉树的先序、中序、后序、层序遍历是必考内容。408 选择题最常见的是已知先序 中序求后序或已知后序 中序求先序。这里有一个判断技巧中序序列必须知道否则无法唯一确定一棵二叉树。前序 中序重建二叉树的递推思路是前序第一个节点是根在中序中找到根的位置左边是左子树右边是右子树然后递归处理。// 根据先序序列 pre[] 和中序序列 in[] 重建二叉树 // 参数说明 // preL, preR 为先序区间下标inL, inR 为中序区间下标 BiTree buildTree(int preL, int preR, int inL, int inR) { if (preL preR) { return NULL; } BiTree root (BiTree)malloc(sizeof(BiTNode)); root-data pre[preL]; // 在中序中找到根节点位置 int k inL; while (in[k] ! pre[preL]) { k; } int leftLen k - inL; // 左子树节点个数 root-lchild buildTree(preL 1, preL leftLen, inL, k - 1); root-rchild buildTree(preL leftLen 1, preR, k 1, inR); return root; }遍历是很多树算法的基础。后续的线索二叉树、二叉排序树、平衡二叉树、哈夫曼树本质上都是在遍历的基础上做文章。5.3 二叉树与森林的转换408 选择题经常考一棵树转换成二叉树后它的某种遍历序列是什么。核心规则是左孩子右兄弟树转换成二叉树每个节点的第一个孩子作为左孩子第一个孩子的兄弟作为右孩子。森林转换成二叉树第一棵树的根作为根其他树的根作为第一棵树根的右子树链。一个高频结论树的先序遍历 转换后二叉树的先序遍历树的后序遍历 转换后二叉树的中序遍历。这个结论在选择题里可以直接套用能节省大量时间。5.4 哈夫曼树与哈夫曼编码哈夫曼树是带权路径长度WPL最小的二叉树。构造方法每次从节点集合中选出两个权值最小的节点作为新节点的左右孩子新节点权值为两者之和然后放回集合重复直到只剩一个节点。考试常见题型给定权值集合求哈夫曼树的 WPL。给定权值集合画出哈夫曼树并写出哈夫曼编码。判断某个编码是否是前缀编码。求 WPL 时有一个简便方法WPL 所有非叶节点的权值之和。因为每个非叶节点都被构造过程中累加过。例如权值 {2, 3, 4, 7}构造过程中新增节点权值依次为 5、9、16所以 WPL 5 9 16 30。哈夫曼编码的重要特征是没有任何一个编码是另一个编码的前缀因此解码时不需要分隔符可以唯一还原。408 常以“判断一组编码是否为合法的哈夫曼编码”命题解法就是检查前缀冲突。5.5 并查集并查集是 408 大纲中一个相对独立的内容常与图的最小生成树Kruskal 算法结合考察。并查集支持两种操作查找Find和合并Union。它的存储结构是一个双亲数组parent[i]表示节点 i 的父节点根节点的父节点指向自己或为 -1。#define MAXN 1000 int parent[MAXN]; // 初始化每个节点都是独立的集合 void init(int n) { for (int i 1; i n; i) { parent[i] -1; // 根节点用负数表示集合大小 } } // 查找根节点带路径压缩 int find(int x) { if (parent[x] 0) { return x; } // 路径压缩让路径上的所有节点直接指向根 return parent[x] find(parent[x]); } // 合并两个集合小树并入大树 void unionSet(int a, int b) { int ra find(a); int rb find(b); if (ra rb) { return; } if (parent[ra] parent[rb]) { // 注意负数比较越小表示树越大 int temp ra; ra rb; rb temp; } parent[ra] parent[rb]; parent[rb] ra; }路径压缩和按规模合并能让并查集的操作时间复杂度接近 O(1)这是 Kruskal 算法高效的原因。6. 图从存储到算法的完整链路图是数据结构中逻辑最复杂、算法最多的部分。408 对图的要求包括存储结构、遍历、最小生成树、最短路径、拓扑排序、关键路径。其中 Dijkstra、Prim、Kruskal、Floyd 这四大算法是重中之重。6.1 图的两种存储结构邻接矩阵用二维数组存储A[i][j]表示顶点 i 到顶点 j 是否有边或边的权值。优点是判断两个顶点是否相邻只需要 O(1)缺点是空间复杂度 O(n²)适合稠密图。邻接表对每个顶点建立一个链表链表中存储该顶点的所有邻接点。优点是空间复杂度 O(ne)适合稀疏图缺点是需要遍历链表才能判断两个顶点是否相邻。408 选择题常问“某个图的邻接表长什么样”或者“用邻接表和邻接矩阵分别做 BFS/DFS 的时间复杂度”。需要牢记邻接矩阵做 DFS/BFS时间复杂度 O(n²)。邻接表做 DFS/BFS时间复杂度 O(ne)。6.2 最小生成树Prim 与 Kruskal最小生成树是连通无向图中所有生成树里各边权值之和最小的那棵。Prim 算法的特点是从顶点出发每次选择当前连通集合与外部之间权值最小的边。时间复杂度 O(n²)适合稠密图。Kruskal 算法的特点是从边出发按权值从小到大选择边只要不构成回路就加入。时间复杂度 O(e·log e)适合稀疏图。判断是否构成回路就用到了并查集。一个常考结论当图中有权值相同的边时最小生成树不一定唯一。但如果所有边的权值互不相同则最小生成树唯一。6.3 最短路径Dijkstra 与 FloydDijkstra 算法用于求单源最短路径即从一个源点出发到其他所有顶点的最短路径。算法思想是贪心每次从未确定最短路径的顶点中选一个距离源点最近的顶点加入集合然后更新它的邻接点。Dijkstra 不适用于负权边这是常考点。Floyd 算法用于求所有顶点之间的最短路径核心思想是动态规划允许经过前 k 个顶点中转逐步求解。Floyd 可以处理负权边但不能有负权回路。// Floyd 算法核心代码 // 邻接矩阵 dist[i][j] 初始为边的权值不相邻为正无穷 void floyd(int n, int dist[][MAXN]) { for (int k 1; k n; k) { for (int i 1; i n; i) { for (int j 1; j n; j) { // 经过 k 点中转后距离是否变小 if (dist[i][k] dist[k][j] dist[i][j]) { dist[i][j] dist[i][k] dist[k][j]; } } } } }理解 Floyd 的关键是三层循环的顺序。最外层一定是“中转点 k”而不是 i 或 j。如果这个顺序写反求出来的就是错的。6.4 拓扑排序与关键路径拓扑排序用于有向无环图DAG输出的序列要满足每个顶点出现且只出现一次如果存在边 A→B则 A 必须排在 B 前面。实现方法每次输出一个入度为 0 的顶点然后删除它和它的出边。AOV 网顶点表示活动求拓扑排序AOE 网边表示活动求关键路径。关键路径是 AOE 网中从源点到汇点的最长路径关键路径上的活动称为关键活动。缩短关键活动可以缩短整个工期但缩短到一定程度后关键路径可能发生转移。408 真题中关键路径常以选择题形式考察需要会计算事件的最早发生时间 ve、最迟发生时间 vl以及活动的最早开始时间、最迟开始时间。7. 查找顺序表、树表与哈希表查找模块在 408 中属于“块头不大但分值稳定”的内容。重点关注折半查找、二叉排序树、平衡二叉树、哈希表。7.1 折半查找与判定树折半查找要求查找表有序且采用顺序存储。平均查找长度 O(log n)但插入删除不方便。折半查找的过程可以画成一棵判定树。判定树是一棵平衡二叉树树的高度决定了最坏情况下的比较次数。对于 n 个元素折半查找最多比较 ⌊log2 n⌋ 1 次。408 选择题可能会给出折半查找的判定树让你求某个元素的比较次数。7.2 二叉排序树 BST二叉排序树左子树所有节点值小于根右子树所有节点值大于根中序遍历得到递增序列。BST 最重要的考点是删除操作删除叶子节点直接删除。删除只有一个孩子的节点让孩子顶替被删节点。删除有两个孩子的节点用被删节点的中序前驱或中序后继代替它然后删除那个前驱/后继节点。一个常见误区是“把左子树最大的节点替换上去之后忘记处理该节点的左子树”。实际上左子树最大节点要么是叶子要么只有左孩子所以替换后的删除操作是简单的。BST 的查找效率与树的高度相关。最坏情况下插入序列有序BST 退化成单链表查找复杂度 O(n)。这就引出了平衡二叉树。7.3 平衡二叉树 AVL平衡二叉树要求任意节点的左右子树高度差绝对值不超过 1。插入节点后从插入点向上找第一个不平衡的节点然后根据不平衡模式进行 LL、RR、LR、RL 旋转。LL右旋。RR左旋。LR先左旋后右旋。RL先右旋后左旋。408 考试常让你画出插入若干节点后的平衡二叉树或者计算平衡二叉树的最小节点数。这里有一个公式值得记忆高度为 h 的平衡二叉树至少需要的节点数 N(h) N(h-1) N(h-2) 1其中 N(0) 0N(1) 1。这个公式和斐波那契数列很像常用来手算最小节点数。7.4 哈希表哈希表通过散列函数把关键字映射到存储位置理想情况下查找 O(1)。408 必考内容集中在散列函数的构造除留余数法 H(key) key % pp 通常取不大于表长的质数。冲突处理方法开放定址法线性探测、平方探测、再散列和链地址法。装填因子 α 表中记录数 / 表长。平均查找长度 ASL 的手动计算分为查找成功和查找失败两种情况。线性探测法容易产生“堆积”现象因为发生冲突时关键字会占据本来不属于它的位置。链地址法把冲突元素放在同一个链表里不会堆积但需要额外空间。// 链地址法哈希表节点定义 typedef struct HashNode { int key; struct HashNode *next; } HashNode; // 哈希表一个指针数组每个元素是一条链表的头指针 #define HASHSIZE 13 HashNode *hashTable[HASHSIZE]; // 用除留余数法计算哈希地址 int hash(int key) { return key % HASHSIZE; }408 选择题中哈希表题目通常需要你手工模拟哈希表的构建过程。记住线性探测的规则是“遇到空位就放找不到就往后找绕一圈回到起点还没有就表满”而查找失败时的比较次数要一直数到空位置为止。8. 排序算法对比记忆逐一攻破排序是数据结构中代码量最大、算法思想最多的部分。408 对排序的要求是掌握每一种排序算法的过程、时间复杂度、空间复杂度、稳定性并会手工模拟一趟排序过程。8.1 排序算法总览表这张表建议反复默写排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入O(n²)O(n²)O(1)稳定折半插入O(n²)O(n²)O(1)稳定希尔排序O(n^1.3) 左右O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定快速排序O(n·log n)O(n²)O(log n)不稳定简单选择O(n²)O(n²)O(1)不稳定堆排序O(n·log n)O(n·log n)O(1)不稳定归并排序O(n·log n)O(n·log n)O(n)稳定基数排序O(d(nr))O(d(nr))O(r)稳定注意快速排序最坏情况发生在每次划分都极度不均匀时比如序列已经有序。此时每次划分只确定一个元素的位置退化为 O(n²)。但快排的平均性能是所有排序算法中最好的这是它被称为“快排”的原因。8.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); } }408 选择题经常问“经过一趟快排后哪些元素已经处于最终位置”。答案是基准元素一定在最终位置而且所有划分元素都满足“左边都比它小右边都比它大”。8.3 堆排序堆排序是选择排序的优化用到了完全二叉树的性质。大根堆中每个节点的值都大于等于其左右孩子小根堆则相反。堆排序的关键操作是“下沉”和“建堆”。给你一个数组建初始大根堆的步骤从最后一个非叶节点开始即下标 n/2依次向前做下沉调整。// 以 i 为根调整为大根堆 // n 为堆中元素个数 void adjustDown(int a[], int i, int n) { int val a[i]; // 暂存当前节点值 for (int j 2 * i; j n; j * 2) { if (j n a[j] a[j 1]) { j; // 选择较大的孩子 } if (val a[j]) { break; } a[i] a[j]; // 孩子上移 i j; } a[i] val; } // 堆排序先建堆再依次输出堆顶 void heapSort(int a[], int n) { for (int i n / 2; i 1; i--) { adjustDown(a, i, n); // 建初始堆 } for (int i n; i 1; i--) { int temp a[1]; // 堆顶与末尾交换 a[1] a[i]; a[i] temp; adjustDown(a, 1, i - 1); // 重新调整 } }堆排序常考的点堆的插入新节点插入末尾向上调整、建堆时间复杂度 O(n)、堆排序时间复杂度 O(n·log n)、堆排序不稳定。9. 408 真题的考察方式与复习策略了解“怎么考”才知道“怎么复习”。408 数据结构部分的真题主要有两类第一类选择题约 11 道。覆盖范围广从基础概念到复杂算法都有。常见的命题角度有给一段代码问时间复杂度。给一个数据结构问它的存储特点或操作结果。给一个场景要求选择最优数据结构。让手动模拟排序算法的一趟过程。给一个图求最小生成树、最短路径或关键路径。判断某个数据结构的性质是否成立。选择题往往考查的是“计算”和“模拟”而不是死记概念。所以复习时一定要动手画图、动手推演不能只看不练。第二类综合应用题约 2 道。数据结构在 408 中一般有两道大题常见形式是第一道大题通常是线性表或二叉树相关的算法设计题用 C 语言写出算法思路和代码或者补全代码。第二道大题通常是图或排序相关的综合题要求分析算法过程、统计时间空间复杂度或者解决一个具体的应用问题。综合题的评分方式是“按步骤给分”所以在考场上即使写不出完整代码也要把算法思路、数据结构定义、关键步骤写清楚。9.1 高效复习路线建议如果你从现在开始准备数据结构建议按下面的阶段推进基础阶段约 4 周构建知识框架。对照本文的知识地图先过一遍教材或视频每学完一个模块就做对应的基础题。这个阶段不求快但求把每个原理搞清楚。核心任务是理解“存储结构 操作”的对应关系。强化阶段约 3 周刷题 手写代码。开始刷 408 真题和题库中的选择题、算法题。每道题都要尝试手动模拟过程。特别是排序、图算法、哈希表查找过程不要在草稿纸上跳步完整模拟一到两遍考试时才能稳定输出。冲刺阶段约 2 周按真题套卷限时练习。这时候不要只做数据结构单科题要按整套 408 真题的时间来模拟。数据结构部分控制在 50 到 60 分钟内完成。做完后重点复盘错题确定是概念不清、计算失误还是审题偏差。9.2 数据结构与其他 408 科目的联系408 的四门科目之间是有联动关系的。复习数据结构时可以注意以下联系数据结构 计算机组成原理栈的实现与函数调用栈、数的原码补码表示与数据类型的存储、Cache 与局部性原理对数据访问效率的影响。数据结构 操作系统进程调度中的队列、内存管理中的页表类哈希表思想、文件系统的索引结构与 B 树。数据结构 计算机网络路由算法的本质是在图上求最短路径TCP 滑动窗口和缓冲区本质上也是队列的应用。如果你能在复习时把这些跨科目联系点串起来不但能加深对数据结构的理解还能顺便复习其他科目事半功倍。10. 高频易错点与避坑指南结合历届考生和期末复习常犯的错误这里整理一份避坑清单易错点错误认知正确理解循环队列长度计算直接用 rear - front应使用 (rear - front MaxSize) % MaxSize树转二叉树后序遍历结果不变树的后序对应二叉树的中序KMP next 数组next[j] 是“最长相等前后缀长度”next[j] 是最长相等前后缀长度 1完全二叉树存储所有二叉树都能顺序存储只有完全二叉树才能用顺序存储且不浪费空间折半查找前提链表也可以折半查找折半查找必须随机访问链表不行哈希表删除线性探测法可以直接删除记录直接删除会破坏探测链需要“软删除”标记快速排序最坏情况随机数据时最坏初始序列有序/逆序时最坏堆排序建堆时间认为建堆是 O(n·log n)自底向上建堆总复杂度 O(n)Dijkstra 算法可以处理负权边Dijkstra 基于贪心不适用于负权边拓扑排序结果唯一拓扑序列唯一同时存在多个入度为 0 的顶点时拓扑序列不唯一这十个易错点几乎每年都会以某种形式出现在选择题或分析题中。建议你把这张表抄在笔记扉页每次做题前扫一眼形成条件反射。11. 总结与下一步行动写到这里408 数据结构的主要脉络已经全部梳理了一遍。我们沿着“数据结构 存储结构 操作集合”这条主线把线性表、栈、队列、串、树、图、查找、排序串成了一张完整的知识网。这张网既是复习的索引也是查漏补缺的清单。下一步你可以做三件事第一凭记忆画出你自己的知识地图。不要看书也不要看笔记就凭记忆写能写多少写多少。写完之后对照本文找出那些你没写出来或者写得模糊的部分这些就是你当前最大的提分点。第二针对薄弱模块做专项练习。如果树这块薄弱就把遍历、重建、线索化、BST 删除、AVL 旋转、哈夫曼编码一次性练透。不要“雨露均沾”要集中火力突破薄弱环节。第三把核心代码手写一遍。数据结构的关键不是“看懂”而是“能写出来”。限时 15 分钟手写快速排序或二叉树中序遍历然后对照标准答案检查细节。这个过程重复三到五次考场上你会非常自信。数据结构是一门“开窍之后越学越顺”的科目。如果你正在为 408 考研焦虑或者被期末的算法题折磨不要怕按图索骥逐个模块击穿。掌握好这些原型算法和数据结构你赢下的不只是数据结构这一科而是整个 408 的地基。