数据结构与算法学习笔记：把“看懂”变成“会用”的整理思路

1. 这份笔记到底在记什么

很多人问我，数据结构与算法这门课到底该怎么学，笔记又该怎么记。说实话，我见过太多同学的笔记本，要么是老师 PPT 的复刻机，要么是《算法导论》的浓缩版，抄了一堆定义和伪代码，合上本子脑子还是一片空白。

我自己的定位很明确：这份笔记不是教材的搬运工，而是把"看懂"变成"会用"的转换器。它记录的是我踩过的坑、归纳过的套路、画过的图，还有那些"当时死活想不通、后来恍然大悟"的关键点。如果你正在准备考研 408、刷 LeetCode、应付数据结构实验报告，或者单纯想把这门基础课学扎实，这份笔记的整理思路应该能帮你少走很多弯路。

先交代一下这份笔记覆盖的范围。数据结构部分，从线性表、栈、队列、串、树、图，到查找和排序，基本上是国内教材的标准章节。算法部分，除了配套的暴力枚举、递归回溯、剪枝、动态规划、贪心，我还额外补充了 KMP、折半查找的典型例题、堆排序的手算模拟、普利姆和克鲁斯卡尔求最小生成树这些高频考点。全程用 C/C++ 描述，偶尔用 Python 验证思路，因为考研和期末考的代码题大多以 C 系语言为主，而 Python 适合快速验证算法行为和画图看效果。

核心原则只有一条：每个知识点必须回答三个问题——它解决什么问题，它的代价是什么，它在什么场景下会被吊打。记不住这三件事，背再多代码也是白背。

2. 整体设计思路：把零散知识串成一张网

2.1 为什么不能按目录平铺直叙地记

刚入门的时候我也犯过这个错，按教材章节老老实实记：数组、链表、栈、队列、树……每个章节单独记，看起来井井有条，实际上毫无关联。学到图的最短路径时，突然发现迪杰斯特拉算法和之前学的贪心策略有关；学到堆排序时，才发现完全二叉树这个"老朋友"还有这种玩法。这时候回头翻笔记，发现前面记的东西跟后面完全连不起来，等于白记。

后来我把笔记的底层逻辑改成了一条主线：物理结构 → 逻辑结构 → 操作效率 → 算法设计策略。不管线性表还是图，不管查找还是排序，都按这条线梳理。比如数组和链表，先看它们在内存里怎么存（物理结构），再抽象成线性表（逻辑结构），然后比较插入、删除、查找的时间复杂度（操作效率），最后落到"什么时候用数组、什么时候用链表"这个决策问题上。这样每一章都不是孤岛，而是同一套思维框架在不同场景下的应用。

2.2 笔记的三大支柱：图、表、代码

我翻了很多高分笔记，发现做得好的都有共性：图、表、代码三件套齐全。

图，指的是手绘图解，不是截 PPT 图。树的旋转、图的遍历过程、快速排序的分区过程，这些动起来才能理解的东西，静帧文字很难讲清楚。我习惯用纸笔画一遍，再贴到笔记里。比如红黑树的插入修复分了三种情况，每种情况左旋右旋怎么转，不画图光看文字真的会绕晕。

表，指的是各类复杂度对比表、适用场景对照表、易混淆概念辨析表。比如各排序算法的时间复杂度、空间复杂度、稳定性，一张表全看清。查找算法里顺序查找、折半查找、分块查找的对比，树和图里各种遍历方式的对比，都适合用表格来沉淀。

代码，不是抄完整实现，而是记录"骨架 + 关键边界条件"。完整代码教材和网上都有，笔记里只需要留核心逻辑和最容易出错的那几行，比如 KMP 的 next 数组求法、归并排序的 merge 边界、链表的头插尾插指针变换。这样复习的时候一眼就能抓住重点，不需要重新读一遍几百行的完整代码。

2.3 章节之间的关联怎么记

我在笔记每个章节开头会留一个小区域，叫"本章与前文的接口"。学树的时候，我会提一句"树是递归结构的天然载体，前面的栈可以实现递归转非递归"；学图的时候，我会标注"图的深度优先遍历基于栈的思想，和树的先序遍历是同一套逻辑；广度优先遍历基于队列，和树的层序遍历对应"。这些连接点看起来不起眼，但正是它们把零散的知识织成了网，后期复习效率会高很多。

3. 核心细节解析：从操作到原理

3.1 带头节点和不带头节点的链表，到底差在哪

这是很多初学者绕不过去的坎。先给结论：带头节点纯粹是为了统一操作逻辑，省掉对"空表"和"首元节点"的特殊判断。

想象一下不带头节点的单链表，要在第一个位置插入节点，你得修改头指针，函数里得写if (p == head) head = newNode;这种分支。而如果有一个头节点（data 域不用，只当哨兵），无论插哪里，都是"找到前驱节点，改它的 next"这一个套路，不需要判断是不是插在第一个。删除同理，带头节点的链表删除第一个有效节点和不带头节点的逻辑完全一致，都是改前驱的 next，而如果不带头节点，删除第一个节点也要特殊处理头指针。

我用一张对照表沉淀了这个问题：

考研和期末考试特别喜欢考这个对比，考的不是你能不能写代码，而是你知不知道为什么。这就是笔记里要重点记录的东西。

3.2 栈和队列，两个"工具人"的自我修养

栈和队列本身并不复杂，但它们是后面很多算法的基石。我在笔记里给它们起了个外号叫"操作受限的线性表"，这样理解起来特别快：它们本质还是线性表，只不过栈只允许在一端插入删除（后进先出），队列只允许一端插一端删（先进先出）。

很多人不理解为什么要有这种限制。我的理解是：限制操作恰恰是它们的价值所在。栈天然适合"嵌套"结构的问题，比如函数调用、括号匹配、表达式求值；队列天然适合"公平排队"的问题，比如任务调度、树的层序遍历、图的广度优先遍历。

笔记里我记得最认真的一个点是循环队列的判空和判满。因为顺序实现的队列如果用完整个数组，会有假溢出问题，所以用取模运算让队尾绕回开头。但这样一来，判空是front == rear，判满也是front == rear，就矛盾了。常规解法是牺牲一个存储单元，让队满条件变成(rear + 1) % MaxSize == front，这样队列最多只能存 MaxSize-1 个元素。这个"为什么少一个格子"的问题，几乎每年都有同学在群里问。

3.3 递归与非递归的互相转换

递归是树的天然伴侣，因为树本身就是递归定义的。但考试和面试常常要求你写出非递归版本，这背后其实是"手动维护栈"的思想。

以二叉树的中序遍历为例，递归版本极其简单：

void inorder(TreeNode* root) { if (!root) return; inorder(root->left); visit(root); inorder(root->right); }

非递归版本就是自己用一个栈模拟系统栈：

void inorder(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur = cur->left; } cur = st.top(); st.pop(); visit(cur); cur = cur->right; } }

这里的关键理解是：递归版本里，系统帮你记住了每个节点的返回地址和局部状态，非递归版本就是你亲自把这些状态压栈。我在笔记里画了一张"访问路径图"，用箭头标出每个节点入栈和出栈的时机，这个图我建议每个人都要亲手画一遍，画完中序遍历非递归就再也忘不掉了。

4. 核心算法的笔记怎么记才有效

4.1 排序算法：不能只背代码，要背"过程图"

排序是数据结构里最热闹的一块，冒泡、选择、插入、希尔、归并、快排、堆排，七种经典算法够喝一壶。我的经验是：不要死记代码，要把每一趟排序的结果都写出来。是的，每一趟。因为考试最爱考的就是"给一个序列，写出第三趟冒泡排序后的结果"，或者"给一个序列，写出快速排序第一趟划分的结果"。这类题如果只看过代码没手算过，考场上就慌了。

比如快排第一趟划分：

初始序列：49 38 65 97 76 13 27 以49为基准，low从左边找比49大的，high从右边找比49小的 第一趟结果：27 38 13 49 76 97 65

这个"挖坑填数"的过程，我建议在笔记里画六步左右的快照，标出 low 和 high 指针的移动方向，这是理解快排本质最快的路径。

堆排序则是另一个重灾区。建堆、调整，每一轮交换是什么状态，必须完全模拟一遍。大根堆：（自调整）因为只能是文字描述。我笔记里记了一个口诀："建堆从下往上调，排序从上往下换"。建堆是从最后一个非叶节点开始往前逐个调整，保证每个子树都是堆；排序时把堆顶和最后一个元素交换，堆规模减一，再从上往下调整恢复堆。这两句话能解决大部分"堆排序过程搞不清"的问题。

4.2 查找算法：重点永远在"比较次数"

查找这一章的核心考点就是折半查找。折半查找的前提是有序表，优点是查找效率高，缺点是不适合链表结构（因为需要随机访问）。笔记里必记的是它的判定树——把每次比较的中间位置画成一棵二叉树，这样查找任意元素最多比较多少次一目了然。

例题要好好分析这个序列：

有序序列：7 10 13 16 19 29 32 33 37 41 43

查找 37 的过程，判定树的路径是：先和 29 比（mid 指向第 6 个元素），再和 37 比（mid 指向第 9 个元素），命中。总共比较 2 次。而如果查一个序列中不存在的元素，比如查 30，就要一路比到叶子节点的空指针。折半查找的时间复杂度是 O(log₂n)，但这是随机访问前提下的结论，链表上做折半查找没有意义。

ASL（平均查找长度）的计算也是高频题。成功情况下的 ASL 等于判定树中所有"内部节点"的层数求和除以节点数；失败情况下的 ASL 等于所有"外部节点"的层数求和除以外部节点数。这个要分清，考试经常在这里抖机灵。

4.3 KMP 算法：next 数组到底怎么求

KMP 是串这一章最劝退的知识点，但一旦搞懂 next 数组的本质，它就再也不会成为难点。next[i] 的含义是：当模式串第 i 位失配时，i 指针应该回退到的位置，或者等价地说，是模式串前 i-1 位中"最长相等前后缀的长度加 1"。

求 next 数组我推荐用递推的方式理解：

// 模式串 t 的 next 数组求法，j 表示当前已匹配长度 int next[MAXN]; next[0] = -1; // 哨兵，方便判失配 int i = 0, j = -1; while (i < t.length()) { if (j == -1 || t[i] == t[j]) { i++; j++; next[i] = j; } else { j = next[j]; } }

笔记里必须手算一遍。以ABABABB为例，逐个求 next 值。这个过程中最难理解的是失配时j = next[j]这行代码——它其实在用"已匹配部分"的最长相等前后缀来减少无谓的比较。我的技巧是把它和暴力匹配算法对比着看：暴力匹配失配时主串指针回溯到本次起始位置的下一个，KMP 则保持主串指针不回溯，只让模式串指针跳转，这就是 KMP 比暴力算法快的原因。

4.4 图：从遍历到最短路径的层层递进

图这一章是数据结构里信息密度最大的，考试分值也高。我的笔记思路分四层组织：

第一层是存储结构，邻接矩阵和邻接表必须对比记。邻接矩阵适合稠密图，判断任意两个顶点是否相邻是 O(1)；邻接表节省空间，但判断相邻关系要遍历链表，最坏 O(n)。从顶点找邻边，邻接表完胜；判断两顶点是否相连，邻接矩阵完胜。这几个结论要能脱口而出。

第二层是遍历，深度优先（DFS）和广度优先（BFS）一定要记住它们的辅助结构：DFS 用栈（或递归），BFS 用队列。遍历序列的生成过程务必在笔记中画出模拟步骤。值得注意的是，图的连通分量个数可以通过 DFS 或 BFS 的次数来统计——每启动一次遍历，就说明发现了一个新的连通分量。

第三层是最短路径。迪杰斯特拉算法（单源最短路径）是贪心思想的典型应用，每轮选一个离源点最近且未被访问的点，然后松弛它的邻居。弗洛伊德算法（全源最短路径）是动态规划，三重循环，d[i][j] = min(d[i][j], d[i][k]+d[k][j])。笔记里要强调：迪杰斯特拉不能处理负权边，弗洛伊德可以（只要没有负权环）。这个考点几乎每年都会以选择题或简答题的形式出现。

第四层是生成树。普利姆算法从一个顶点出发，每次选"已经在树中的点"到"不在树中的点"的最短边，适合稠密图；克鲁斯卡尔算法把所有边按权排序，从小到大选不构成环的边，适合稀疏图。而判断"是否构成环"用的是并查集，这又是一个跨章节的知识点，我在笔记里把它们串在一起记。

4.5 经典算法思路：剪枝、贪心与动态规划的边界

算法策略这块，我在笔记里分了三个典型家族：

回溯算法的核心是"尝试-撤销"。N 皇后、全排列、组合求和，都是这个套路。剪枝是回溯的加速器，本质上就是提前判断这条路继续走也不会产生合法解，直接放弃。比如组合求和问题里，如果当前和已经超过 target，就没必要继续递归了，这就是最简单的剪枝。我在笔记里记了一个通用框架：

void backtrack(当前状态) { if (当前状态是合法解) { 记录解; return; } for (每个可选操作) { 做选择; backtrack(新状态); 撤销选择; } }

这个框架能解一大片回溯类题目，但要注意剪枝条件通常要写在 for 循环里面，"做选择之前先判断"，而不是等到递归进去再判断，否则递归层数会白白增加。

动态规划和贪心的区别，我用一句话总结：贪心是每一步做当前看起来最优的选择，不回头；动态规划是枚举所有可能的子问题，择优保留。贪心的经典例子是活动选择问题、哈夫曼编码；动态规划的经典例子是 0-1 背包、最长公共子序列。做动态规划题，笔记里一定要写清楚状态定义和状态转移方程，这两个东西写清楚了，代码就是翻译的事。

5. 实验报告与上机实操：笔记怎么反哺代码

5.1 从笔记到代码：三步走

很多同学笔记记得很漂亮，一到写代码就卡壳。我的方法是从笔记提炼一个"代码撰写三步走"：

第一步，把笔记里的算法思路画成流程图。图不用画得很正式，关键是标注清楚循环条件和退出条件，特别是边界情况（空表、单节点、满队列）。

第二步，把流程图里的每个节点翻译成代码骨架。这一步不要追求一次写对，先写主逻辑，把边界情况留到第二步。

第三步，对着笔记里的"易错点清单"逐一检查。我笔记里常驻的清单包括：单链表的指针顺序（先接后面再接前面）、树的递归终止条件（空指针判断）、快排的区间划分（left < right 才递归）、KMP 的 next 数组初始化。

5.2 实验报告怎么写才能得高分

数据结构实验报告是很多学校的硬性要求，但大多数同学写成了代码粘贴板。我的经验是，报告的重点应该在"设计思路"和"结果分析"上。

设计思路部分，要写清楚你选择了哪种数据结构、为什么选它、时间复杂度是多少、有没有考虑过替代方案。比如图书管理系统，你用顺序表而不用链表，理由可以是访问频繁、很少插入删除，顺序表能发挥随机访问优势。

结果分析部分，要贴运行截图并给出分析：输入什么数据、输出什么结果、正确性如何验证、性能是否符合预期。特别建议做一个"测试用例表"，把普通用例、边界用例（空表、满表、重复数据）都覆盖到，老师一看就知道你认真测过了。

还有一个万人踩的坑：实验报告里严禁大段贴代码。除非老师明确要求，否则贴核心代码片段（比如关键数据结构和核心算法）就够了，要贴的是提炼过的精华，不是整份 main.cpp。我见过太多实验报告，二十页纸有十八页是代码，剩下的两页是运行截图，这种报告本质上等于没写设计、没写分析。

5.3 Python 验证思路，C++ 完成交付

我的习惯是，复杂算法先用 Python 快速验证，再用 C++ 写出正式代码。原因很简单，Python 写起来快、调试容易、可视化方便，特别适合验证"这个思路到底对不对"。而 C++ 的优势在于贴近底层、指针操作直观、考研和刷题平台都认。

比如写 A* 算法，我先用 Python 把启发式搜索的逻辑跑通，把每一步 open list 和 closed list 的变化打印出来，确认路径没问题之后，再用 C++ 重写。两个语言的差异点集中在手动内存管理和 STL 使用上，这样的对照还能加深对语言本身特性的理解。

6. 常见问题与考场避坑实录

6.1 为什么我的快排死循环了

这是排序代码里最经典的问题。快排的 partition 函数如果写得不严谨，在遇到重复元素或区间只有一个元素时，可能出现无限递归或数组越界。

我自己的版本是这么写的，注意 while 循环里的边界条件：

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; }

易错点有两个。第一，内层 while 必须加low < high条件，否则 high 可能一路减到数组左端之外，访问越界。第二，为什么等于 pivot 的元素也要跳过？如果不跳，遇到全部相等的数组时，两个指针会反复交换，虽然不会死循环但会造成大量无效操作，效率退化到近似 O(n²)。如果是极端重复元素的场景，可以换用三路快排，但考试和竞赛一般不至于这么卷。

6.2 树的递归遍历，传参传引用还是传值

这是一个特别容易在 C++ 里翻车的问题。递归遍历树的节点计数函数，如果写成void count(TreeNode* root, int cnt)，cnt 传的是值拷贝，每个递归层都在修改自己那一份副本，回到上一层就丢了。正确写法是传引用void count(TreeNode* root, int& cnt)，或者返回 int 值层层累加：

int count(TreeNode* root) { if (!root) return 0; return 1 + count(root->left) + count(root->right); }

这个坑看着低级，但我见过不止一个同学在考场或面试中翻车。笔记里最好把这个现象标注成"经典 C++ 误区：递归计数必须是返回值累加或引用传参"。

6.3 面试和考试里那些"口头算法题"

很多算法不是让你写完整代码，而是讲思路。这时候笔记里的"场景-算法映射表"就派上用场了。我整理过一张速查表，这里分享核心部分：

这张表的价值在于，看到问题特征就能第一时间锁定算法方向，而不是现场瞎试。我特别想强调的是单调栈这个工具，它看起来冷门，但"下一个更大元素""每日温度""接雨水"这些经典题全是它的主场，笔试面试出现频率极高。笔记里单独给它开了一节：单调栈维护的是"从栈底到栈顶单调递减/递增"的序列，新元素入栈前，所有栈顶能它弹出的元素都能确定它们"右边第一个比它大/小的元素"，这个思想一旦理解，一堆题就通了。

6.4 期末复习的黄金七天安排

如果你只剩一周准备期末考试，我的建议是前四天按章节刷笔记的图和表，后三天直接刷真题和小题。具体安排是这样的：

第一天：线性表 + 栈 + 队列。重点复习链表的各种操作、循环队列判满判空、中缀转后缀表达式。 第二天：树和二叉树。遍历序列互推、哈夫曼树、二叉排序树和平衡树的概念。 第三天：图。邻接矩阵/邻接表、DFS/BFS 序列、迪杰斯特拉手算、普利姆/克鲁斯卡尔手算。 第四天：查找 + 排序。折半查找判定树、ASL 计算、快排和堆排的手算过程。 第五到七天：做真题。每套真题做完，把错题对应的知识点回笔记里大圈标记，考前只看大圈的部分。

这个安排的核心逻辑是：数据结构期末考试的难点基本都集中在"手算过程"上，不太会考你现场写一个跳表之类的高级内容。所以笔记中带图的章节，都是复习的重点，不要眼高手低。

7. 几个我反复强调的经验

第一，笔记一定要有自己的图。教材上的图是别人的理解，你亲手画的才是你自己的。画图的过程本质上是模拟算法执行的过程，这个模拟做过一遍，比背十遍文字都管用。

第二，复杂度分析不能只记结论，要会推导。比如堆排序为什么是 O(n log n)：建堆需要 O(n)（从下往上调整，大部分元素只在很浅的层移动），但 n 次堆调整每次是 O(log n)，所以整体是 O(n log n)。记推导过程才能在考试中灵活应对变体题。

第三，算法之间是会"串门"的。优先级队列用堆实现，图的迪杰斯特拉用优先级队列优化，最小生成树的克鲁斯卡尔用并查集判环，哈夫曼编码也是贪心。笔记里这些跨章节的连接点，正是考试中综合题的出题源泉。不要孤立地学每一章，人为制造知识割裂。

第四，也是最重要的一条：这份笔记不是用来"收藏"的，是用来反复翻、反复改的。我每次刷完新题，都会回笔记里补充一个变体或者标注一个新的易错点。半年下来，笔记会比最初厚一倍，但那才是它真正值钱的样子。

我在实际使用中还有一个受益颇多的习惯：每周日晚会抽出半小时，把这周刷题或者复习中遇到的错误集中誊一份到笔记前面，给每一条标注上"我为什么当初会这么想"。这个习惯坚持三个月之后，我发现自己的错误越来越集中，大部分都在几类固定误区里打转。把这些误区挨个消灭掉，数据结构和算法的基础就真的瓷实了。希望这些经验也能让你的学习笔记真正变成一面墙，而不是一摞纸。