数据结构复习地图：从线性表到图算法的核心代码与易错点

简介：这份数据结构课程代码包面向正在学习数据结构与算法的计算机专业学生及自学者，以Java语言实现课程中的核心知识点，帮助读者把抽象理论落到可运行的代码上。包内共78个文件，以74个Java源文件为主体，辅以3个txt说明与1个md文档，压缩包约66KB，体量轻便、便于随课查阅。内容覆盖数组、单双链表与循环链表、栈与队列、稀疏数组、递归与迷宫回溯、冒泡插入选择希尔快速归并等排序算法、线性与二分及斐波那契查找、哈希表、二叉树与线索树、哈夫曼与二叉排序树，以及贪心、KMP、Floyd、Dijkstra、Kruskal、Prim、动态规划、马踏棋盘和汉诺塔等常用算法，并附有图结构的实现示例。已有762人学习，适合按章节对照教材逐模块阅读源码、动手复刻并调试，在理解存储结构与算法思路的同时积累可复用的编码经验。

1. 数据结构课程代码：一张从线性表到图算法的复习地图

很多人复习数据结构的方式是打开课件从头翻，翻到平衡树就卡住，翻到图算法直接放弃，最后只记住几个名词。真正的问题不在记性，而在于没有一张能挂住所有知识点的地图。数据结构这门课的主线其实很清晰：先解决数据怎么存（线性表、栈、队列、串、树、图），再解决数据怎么用（查找、排序），中间贯穿的是复杂度分析和存储结构的选择。这份课程代码资源覆盖的正是这条主线上的核心实现，适合正在系统学这门课、或者考前需要把代码和概念对齐的人。复习时最该先问自己的不是某个算法怎么写，而是这个结构为什么这样设计、换一种存储方式代价在哪里。把这条线捋顺，后面每一章都只是往地图上填格子。

2. 线性结构：顺序表、链表、栈与队列的实现要点

线性结构是整门课的地基，也是考试里出现频率最高、最容易在细节上丢分的部分。顺序表和链表不是两个孤立的知识点，而是一组对照关系：同样一个插入操作，顺序表要移动元素，链表要改指针，代价完全不同。复习这一块的关键不是背代码，而是能说清每种操作的时间复杂度从哪来、边界条件怎么处理。

2.1 顺序表与链表的对照复习

顺序表用一段连续空间存数据，支持随机访问，按下标取值是 O(1)，但插入和删除平均要移动一半元素，代价是 O(n)。链表用节点加指针串起来，访问第 i 个元素必须从头走，是 O(n)，但已知位置的前提下插入删除只改指针，是 O(1)。这个对照关系几乎每年都会以选择题或复杂度分析题的形式出现。

复习时容易忽略的是「已知前驱」这个前提。单链表删除一个节点之所以是 O(1)，前提是你已经拿到了它的前驱；如果只给节点本身，还得先找前驱，又退回 O(n)。这类前提条件在判断题里经常被拿来做文章。

下面是一段带头节点的单链表插入实现，重点看指针修改的顺序：

// 在节点 p 之后插入新节点 s，带头节点写法 int insertAfter(ListNode *p, int value) { if (p == NULL) return 0; // 参数校验，防止空指针 ListNode *s = (ListNode *)malloc(sizeof(ListNode)); if (s == NULL) return 0; // 内存分配失败要返回，不能直接解引用 s->data = value; s->next = p->next; // 先接后继，顺序不能反 p->next = s; // 再改前驱指向 return 1; }

这段代码的关键在最后两行的顺序：必须先把新节点的 next 指向 p 的后继，再让 p 的 next 指向新节点。如果反过来写，p 原来的后继就丢了，链表直接断掉。这是链表题里最经典的血泪经验，考试写伪代码时顺序错了照样扣分。参数 p 是插入位置的前驱节点，value 是待插入数据，返回值用 0/1 表示成功失败，这种风格在课程代码里很常见，复习时要能读懂而不是死记。

2.2 栈与队列：受限线性表的两种形态

栈和队列本质上是操作受限的线性表，一个后进先出，一个先进先出。复习时不要把它们当成新结构，而要抓住「限制在哪」：栈只允许在栈顶操作，队列只允许队尾进、队头出。顺序栈要关注栈满和栈空的判断条件，循环队列要关注队空队满的区分方式，这是这一节的两个重点。

循环队列最容易被问倒的地方是「怎么区分队空和队满」。因为 front 和 rear 相等时既可能是空也可能是满，常见做法是牺牲一个存储单元：队空条件是 front == rear，队满条件是 (rear + 1) % MAXSIZE == front。这个「牺牲一个单元」的设计思路要能讲出来，而不是只记住公式。

#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front, rear; } SqQueue; int enqueue(SqQueue *q, int x) { if ((q->rear + 1) % MAXSIZE == q->front) return 0; // 队满，牺牲一个单元 q->data[q->rear] = x; q->rear = (q->rear + 1) % MAXSIZE; // 取模实现循环 return 1; }

取模运算是循环队列的灵魂，它把线性的数组下标折回环状。复习时建议手推一遍入队出队过程，画几个格子标上 front 和 rear，比背公式管用得多。栈这边则要重点看括号匹配、表达式求值这类应用，它们是把栈用起来的典型场景，也是编程题的高频来源。

3. 树与二叉树：遍历、存储与常见操作的复习重点

树是数据结构里难度陡增的一章，从线性关系跳到层次关系，很多人的卡点就在这里。二叉树是树的重点，因为它的结构规整、性质多、可考的点密集。复习这一章要抓住三条线：性质与存储、遍历、以及由遍历衍生出的操作。把这三条线理清，平衡树、堆这些扩展结构才有落脚点。

3.1 二叉树的性质与存储结构

二叉树有几个必须记牢的性质：第 i 层最多有 2^(i-1) 个节点，深度为 k 的二叉树最多有 2^k - 1 个节点，叶子节点数 n0 与度为 2 的节点数 n2 满足 n0 = n2 + 1。最后这条关系推导不难但特别爱考，复习时要能自己推一遍：节点总数 n = n0 + n1 + n2，边数 n - 1 = n1 + 2n2，两式联立就得到 n0 = n2 + 1。

存储结构上，完全二叉树适合用顺序存储，下标关系是父节点 i 的左孩子为 2i、右孩子为 2i+1（从 1 开始编号）。一般二叉树用链式存储，每个节点含数据域和左右孩子指针。这里容易混淆的是「完全二叉树」和「满二叉树」：满二叉树每层都满，完全二叉树只要求最后一层从左到右连续。顺序存储省空间的前提是完全二叉树，普通二叉树用数组存会浪费大量空位，这个前提条件在选择题里经常被隐去。

3.2 四种遍历与由遍历序列还原树

二叉树的遍历分深度优先的先序、中序、后序，以及广度优先的层序。前三种的区别只在访问根节点的时机：先序是根左右，中序是左根右，后序是左右根。递归写法几乎一模一样，只差一行访问语句的位置，所以复习时不要分开背，而要抓住「访问时机」这一个变量。

void inorder(TreeNode *root) { if (root == NULL) return; // 递归出口，空树直接返回 inorder(root->left); // 遍历左子树 visit(root); // 访问根节点，换到前面就是先序，换到后面就是后序 inorder(root->right); // 遍历右子树 }

把 visit 那一行挪位置就能得到另外两种遍历，这就是三种深度优先遍历的统一视角。层序遍历则要借助队列：根入队，出队时访问并把左右孩子入队，循环到队空。这个「用队列实现层序」的搭配是常考点，也顺带复习了队列的应用。

由遍历序列还原二叉树是这一章的重难点。核心结论是：先序加中序、后序加中序可以唯一确定一棵二叉树，但先序加后序不行。原因是中序能区分左右子树，先序和后序只能确定根的位置。复习时要练熟「先序第一个是根，在中序里找到根，左边是左子树、右边是右子树，递归处理」这个流程，手推两三棵树比看十遍讲解有效。

3.3 线索二叉树与哈夫曼树的应用场景

线索二叉树解决的是「找前驱后继要重新遍历」的问题，做法是把空的左指针指向中序前驱、空的右指针指向中序后继，用标志位区分指针和孩子。复习时重点理解它为什么存在，而不是死记线索化的代码细节。哈夫曼树则是带权路径长度最短的二叉树，构造方法是每次取权值最小的两个节点合并，常用于编码场景，权值大的字符编码短。这两个结构都属于「知道为什么用、能说清构造过程」就够应对大部分题目的类型。

4. 图与查找排序：从存储结构到算法选择的易错点

图和查找排序是课程后半段的两大块，前者结构复杂、算法多，后者直接对应实际问题的解法选择。这两块放在一起复习有个好处：图的很多算法依赖队列、栈、优先队列这些前面学过的结构，查找排序又反复用到复杂度的比较，正好把整门课串起来。

4.1 图的存储与两种遍历

图有两种基本存储方式：邻接矩阵和邻接表。邻接矩阵用二维数组表示边，适合稠密图，判断两点是否相邻是 O(1)，但空间是 O(n²)。邻接表用数组加链表，适合稀疏图，空间是 O(n+e)，但判断相邻要遍历链表。选择哪种存储，取决于图的稠密程度和你要做的操作，这个「按场景选结构」的思路是复习时最该建立的。

图的遍历分深度优先和广度优先，DFS 借助递归或栈，BFS 借助队列。两者都能用来判断连通性，但用途不同：DFS 适合找路径、判环，BFS 适合求无权图的最短路径。复习时要把「为什么 BFS 能求最短路径」想清楚：它是按层扩展的，第一次到达某点时的层数就是最少边数。

4.2 最小生成树与最短路径的算法选择

最小生成树有两个经典算法：Prim 和 Kruskal。Prim 从一个顶点出发，每次选连接已选集合和未选集合的最小边，适合稠密图，复杂度 O(n²)。Kruskal 把所有边排序，每次选不构成环的最小边，适合稀疏图，复杂度 O(e log e)。两者的选择依据就是图的稠密程度，这个对应关系要能脱口而出。

最短路径方面，Dijkstra 解决单源、非负权的最短路径，Floyd 解决多源最短路径。Dijkstra 不能处理负权边，这是最容易被忽略的限制条件，考试里经常用一道带负权边的题来设陷阱。Floyd 的三重循环顺序也有讲究，中间点必须放在最外层，写反了结果就错。

// Floyd 核心三重循环，k 必须在最外层 for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];

k 放最外层的原因是：它表示「允许经过前 k 个点作为中间点」这一轮松弛，必须逐轮放开中间点集合，才能保证每轮用的是上一轮的完整结果。这个细节很多人背了代码却没理解，换个写法就翻车。

4.3 查找与排序的复杂度对照

查找部分重点是折半查找和二叉排序树。折半查找要求有序且顺序存储，复杂度 O(log n)，这个「顺序存储」的前提常被忽略，链表上没法折半。二叉排序树查找的平均复杂度是 O(log n)，但退化成链表时是 O(n)，所以才有平衡树的出现。

排序部分要把常见算法的时间复杂度、空间复杂度和稳定性列成一张表来记，这是复习性价比最高的动作。

这张表要能默写，尤其是快排最坏 O(n²)、归并需要额外空间、堆排序不稳定这几个点。稳定性指的是相等元素排序后相对次序是否保持，这个概念在选择题里经常和复杂度混在一起考。

5. 易错点清单：五个最容易翻车的地方

复习到后期，拉开差距的往往不是会不会，而是细节上有没有踩坑。下面这几条是梳理下来发现丢分最集中的地方，每条都按「错在哪、为什么错、怎么补」来说。

易错点一：循环队列的队空队满判断。很多人只记住 front == rear 是队空，却忘了队满也可能是这个条件，结果判断逻辑写反。漏的原因是没理解「牺牲一个单元」的设计动机。补的办法是画图手推：空队列时 front 和 rear 指向同一位置，每入队一个 rear 后移，当 rear 的下一个位置就是 front 时说明满了，所以队满条件是 (rear+1)%MAXSIZE == front。

易错点二：链表插入删除的指针顺序。插入时先改新节点的指针再改前驱，删除时要先保存待删节点再改指针，顺序反了就会断链或内存泄漏。漏的原因是背代码时没关注语句之间的依赖关系。补的办法是每次写链表操作前，先在纸上画出三个节点的指针走向，确认没有节点失去引用再落笔。

易错点三：Dijkstra 用于负权边。这是概念性错误，Dijkstra 的贪心前提是「已确定的最短路径不会再被更新」，负权边会破坏这个前提。漏的原因是只记算法流程不记适用条件。补的办法是把每个算法的限制条件单独列一行，Dijkstra 对应「非负权」，Floyd 对应「可有负权但不能有负环」，做题前先看条件再选算法。

易错点四：Floyd 三重循环的顺序。中间点 k 放最外层，写成 i 或 j 在最外层结果就错。漏的原因是照抄代码不理解每层循环的含义。补的办法是记住 k 代表「逐步放开中间点集合」，它必须是外层的那一轮，i 和 j 只是在这一轮里枚举起点终点。

易错点五：遍历序列还原树时先序加后序。很多人以为任意两种遍历都能还原树，实际上先序加后序无法唯一确定。漏的原因是没有理解中序的独特作用：只有中序能划分左右子树。补的办法是记牢「必须含中序」这个条件，遇到先序加后序的题直接判断为不唯一。

提示：这五条建议单独抄在一页纸上，考前只看这一页，比重新翻一遍书效率高得多。

6. 复习清单：把代码和概念对齐的查漏补缺法

复习到最后阶段，最有效的方式不是再看一遍教材，而是拿一份清单逐项自测，能讲清楚就打勾，讲不清楚就回去补。下面这份清单按模块组织，每一项都对应一个可检验的动作，而不是模糊的「掌握某某」。

自测时有个技巧：不要只看代码能不能跑，而要问自己「如果参数换成边界值会怎样」。比如链表操作传入空指针、循环队列入队到满、二叉树退化成单链，这些边界才是考试和实际写代码时真正翻车的地方。把每个结构的边界条件单独过一遍，比刷十道常规题更能查漏。

另一个习惯是把复杂度分析和代码实现绑在一起记。看到一段代码，先估它的时间空间复杂度，再看它用了什么结构、为什么这样选。这个动作练熟了，选择题里的复杂度分析、编程题里的结构选择都会顺很多。梳理下来会发现，数据结构真正难的不是某个算法本身，而是「在什么条件下选什么结构」这个判断力，而判断力只能靠一次次对照和自测养出来。

我自己的教训是早期复习只背代码不看适用条件，结果考试遇到带负权边的题直接套 Dijkstra，白白丢分。从那以后我每次复习一个算法，都强制先写一行它的适用条件和限制，再去看实现。希望这份清单能帮到你，把散落的知识点收成一张能用的地图。

本文还有配套的精品资源，点击获取