作为在数据结构这门课上从背了忘、忘了背到最终形成自己知识框架的过来人我深知一份好的笔记对学习有多重要。市面上教材很多严蔚敏老师的C语言版、李春葆老师的教材都是经典但对于初学者来说最常遇到的问题不是没有资料而是资料太多太散学完一章忘了前一章。这篇笔记整理的思路不是我一个人闭门造车的产物而是结合了408考研大纲、期末复习重点和实际编码经验反复打磨出来的。如果你正在准备期末考试、考研408或者单纯想把这门硬课学扎实这篇文章应该能给你一个清晰的地图。我整理笔记有个原则不抄书只做知识点的二次加工。也就是说笔记记录的必须是经过自己理解、重新表述、并且标注了为什么这样设计的内容。单纯把教材目录搬到笔记软件里没有任何意义那只是换个地方存了一遍原文。真正有价值的笔记是当你翻到某一页时能立刻想起来当时卡在哪个点上、用了什么类比才想通、写代码踩过什么坑。1. 数据结构的宏观认知为什么这门课既要背又要想很多人学数据结构最大的误区就是把这门课当文科背。链表有几种、二叉树遍历有几种、排序算法时间复杂度表背得滚瓜烂熟但一到手写代码就懵。另一部分人则相反觉得一切都要从零推导连红黑树旋转都要当场证明一遍效率极低。我的经验是数据结构这门课有一个背与想的平衡点。1.1 那些必须背下来的内容时间复杂度和空间复杂度分析是必须形成肌肉记忆的。不是说你要背下来某个算法是O(n)还是O(log n)而是看到代码结构脑子里能立刻反射出复杂度量级。比如看到while循环里变量每次乘2立刻想到O(log n)看到双重循环嵌套且都是线性增长立刻想到O(n²)。这个能力考场上不可能临时推导必须在平时刷题时反复强化。常见的复杂度排序必须滚瓜烂熟O(1) O(log n) O(n) O(n log n) O(n²) O(n³) O(2ⁿ) O(n!)。我自己的记忆技巧是把它和实际生活场景对应O(1)是翻一本字典的某一页O(log n)是二分查找电话簿O(n)是逐页翻书找一句话O(n log n)是整理一堆扑克牌O(n²)是两两比较所有人的生日。1.2 那些必须想明白的内容为什么数组的插入是O(n)而链表的插入是O(1)为什么快排最坏情况退化到O(n²)为什么哈希表的冲突解决方式会影响查找性能这些问题靠背是背不出来的必须理解数据结构的底层存储方式和访问逻辑。我用一个生活化类比来理解数组和链表的本质区别数组就像电影院里的固定座位每个人座位号连续你想在第5排和第6排之间加一个人所有人都得往后挪一个位置——这就是插入O(n)的由来。链表就像游乐园里排队的游客每个人都只记得下一个人是谁想插队只需要让前面的人记住你你再记住后面的人——这就是插入O(1)的由来。但代价是链表想找第10个人只能从队头一个一个数过去数组却可以直接算出第10个座位在哪。笔记里专门有一页记录这些本质区别用表格做对比对比项数组链表存储方式连续内存分散内存指针连接随机访问O(1)直接计算地址O(n)必须遍历插入/删除O(n)需要移动元素O(1)只需修改指针空间开销无需额外指针空间每个节点需要额外指针缓存友好性高局部性原理低节点可能分散这张表看起来简单但我在上面花了很多功夫才真正理解缓存友好性是什么意思。后来学了计算机组成原理才明白数组的连续内存让CPU缓存命中率更高而链表的节点在堆里到处乱跳每次访问都可能缓存失效。数据结构的学习确实需要这样横向打通知识点。2. 线性表、栈与队列从结构到工具的思维转变线性表是数据结构的地基栈和队列则是地基上最常用的两种工具。很多初学者学完这一章觉得内容少无非是链表数组的增删改查但学完后面对括号匹配、表达式求值、循环队列判满判空时又看不懂代码。问题出在你没有把栈和队列从存储结构上升为解决问题的手段。2.1 链表头节点到底加不加链表这块很多教材一开始就抛出一个让初学者困惑的问题单链表要不要头节点严蔚敏老师的C语言版本里几乎所有链表操作都带头节点让第一个节点的操作逻辑和后面的节点统一起来。但如果你自己写代码可能会发现不带头节点也写得通。我个人的建议是做题和考试时采用带头节点的写法。原因不只是教材导向更是因为它让代码逻辑更统一。带头节点后空表判断从 head NULL 变成 head-next NULL插入和删除第一个实际节点时不用单独修改头指针代码分支更少不容易出错。笔记里我把带头节点和每头节点的差异整理成了对照带头节点头指针指向固定的头节点头节点数据域不存有效数据。空表判断 head-next NULL。不带头节点头指针直接指向第一个有效节点。空表判断 head NULL插入删除首节点时要修改头指针本身需要传入二级指针或返回新头指针。实际做题时这两种写法在LeetCode或其他OJ平台看到的题解里经常混用但如果你能熟练掌握带头节点的写法绝大多数链表题都能顺下来。真正容易踩坑的是双链表的插入和删除顺序很多初学者写双链表插入时先改前驱指针发现节点断链了。我总结了一个铁律——双链表插入先搞定新节点的前后连接再断开原来的连接。2.2 栈的应用那几道用栈实现的经典题栈这块我觉得最有价值的不是栈本身的代码实现太简单了而是它的三个经典应用场景括号匹配、表达式求值、函数调用栈的模拟。括号匹配是入门体验栈后进先出特性的第一道坎。逻辑说起来很简单遇到左括号就入栈遇到右括号就弹出栈顶元素检查匹不匹配。但实际写代码时有个细节特别容易忽略——遍历完整表达式后栈必须是空的才算合法。比如(()这个情况左括号永远等不到右括号如果你只看配对过程会发现每一步都匹配成功但最后栈里还剩一个左括号。这个细节我在笔记里用红色标注了因为期末考场和笔试中这类边界条件就是区分度所在。表达式求值分为中缀转后缀和后缀表达式求值两步。中缀转后缀的规则教材上写了一大段但我整理成了4句话规律操作数直接输出。栈顶运算符优先级低于当前运算符时当前运算符入栈否则弹出栈顶运算符输出。遇到左括号直接入栈遇到右括号弹出栈内元素直到左括号左括号不输出。扫描结束后依次弹出栈中剩余运算符。如果你在看这部分笔记时手边有纸笔强烈建议手动模拟几遍。尤其是中缀转后缀这个操作刷20个表达式的模拟量比看10遍教材都有用。2.3 队列循环队列的浪费一个空间设计循环队列是线性结构章节最容易被扣分的地方。很多初学者困惑为什么循环队列判空是 front rear判满是 (rear 1) % MAXSIZE front它们看起来是一模一样的关系啊这个问题的根源在于如果允许队列满时 rear front那和队列空就无法区分了。所以标准的循环队列设计人为牺牲一个存储单元让队满的状态变成 rear 恰好走到 front 的前一个位置。换句话说队列实际能存放的元素个数是 MAXSIZE - 1。从为什么角度理解这个设计比记住公式强得多。我在笔记里画了循环队列的入队和出队方向示意图并在旁边写了一段体会循环队列本质上是用取模运算把线性数组卷成一个环取模操作是理解所有循环结构的关键。front 指向队首元素rear 指向队尾元素的下一个位置入队时元素放进 rear 位置然后 rear (rear 1) % MAXSIZE出队时取出 front 元素然后 front (front 1) % MAXSIZE这两个操作模式高度对称写代码时不容易记混。双端队列这个关键词在热搜里很靠前说明很多人也在找它的笔记。双端队列其实就是允许两端都能插入和删除的队列输入受限的双端队列只允许一端插入输出受限的双端队列只允许一端删除。它最直观的应用场景是窗口滑动类问题比如在固定长度的滑动窗口里维护最大或最小值用双端队列能做到O(n)的线性复杂度这个思路是LeetCode上很多hard题的解法基础。3. 树与二叉树递归思维的分水岭树这一章是数据结构学习路上第一个真正的分水岭。前四章学线性结构思维方式还是遍历标记到树这里突然要求你学会递归思维——一个节点的问题可以拆成左右子树的问题层层嵌套最后归约到空节点这个基本情况。很多同学就是从二叉树开始发现这门课变难了。3.1 二叉树的遍历先序、中序、后序到底在干什么遍历这件事光看伪代码很容易产生我懂了的错觉。先序遍历先访问根再遍历左子树再遍历右子树——三句话而已。但真让你画一个递归过程很多人会发现自己的递归栈在脑子里转不过来。我的经验是遍历问题的核心在于理解程序调用栈的深入与回归。每次递归调用都会把当前函数的状态压入调用栈等子树递归完成后再弹栈恢复现场继续往下执行。我笔记里专门用一个三层二叉树的例子手写了每一步递归调用时栈的状态变化。整个过程写下来从根节点A出发递归左子树BB再递归左子树DD是叶子节点返回然后B递归右子树E……当你能完整画出这个调用栈的进出过程二叉树遍历就再也不是背代码了而是真正理解了递归的底层逻辑。关于三种遍历的关系还有一个非常实用的结论已知中序先序可以唯一确定一棵二叉树已知中序后序也可以但只知道先序后序不行。原因是先序(或后序)能确定根的位置而中序能根据根把左右子树的范围划分开两者配合才能确定唯一的树结构。这个考点在期末和考研里几乎是必出的务必理解而不是硬背。3.2 树的存储结构双亲、孩子、兄弟为什么最终选了孩子兄弟法树的存储结构在教材上讲了三种双亲表示法、孩子表示法、孩子兄弟表示法。很多同学学到这里觉得繁琐认为只要会用就行。但如果你去看408考研的历年考题这块的出题频率比你想象的高得多。因为它考的不是背书而是你对逻辑结构如何映射到存储结构的理解能力。三种方式的核心区别我整理成了一段话双亲表示法只记录每个节点的父节点下标找父节点是O(1)但找孩子要遍历整个数组适合认祖归宗类操作。孩子表示法每个节点维护一个孩子链表找孩子快但找父节点难而且链表操作多。孩子兄弟表示法把一棵普通的树用每个节点只记录第一个孩子和下一个兄弟的方式转换成二叉树存储。这样可以把树的问题统一归约到二叉树问题复用二叉树的所有成熟算法。孩子兄弟法是最优雅的方案它彻底打通了树和二叉树两个世界。很多时候你看到一个二叉树算法的应用场景很困惑比如怎么用二叉树存储森林背后的原理就是孩子兄弟法。我把这个方法在笔记里单独开了一节配了转换示意图从爷爷辈的一棵三叉树转换到兄弟链后你能够看到每个节点的左指针指向第一个孩子右指针指向下一个兄弟树的层数信息被压缩进指针结构里。3.3 二叉排序树与平衡因子为什么旋转是必要的二叉排序树BST的定义很简单左子树所有节点值小于根右子树所有节点值大于根。但它的性能完全取决于树的形状一棵极度倾斜的BST可能退化成一个链表查找复杂度从O(log n)变成O(n)。AVL树平衡二叉树的引入就是为了解决这个退化问题它的核心机制是平衡因子——左子树高度减右子树高度绝对值不能超过1。一旦插入或删除节点导致某个节点平衡因子绝对值超过1就要通过旋转操作恢复平衡。四种旋转LL型右旋、RR型左旋、LR型先左后右、RL型先右后左。笔记里我把自己摸索出来的记忆方法写了下来LL型只看三个节点一直偏左的形态解决办法是找到中间那个节点提起来当根另外两个挂到两边。不一定非要记忆每个指针怎么改而是从哪个节点失衡失衡形态是连续向左还是连续向右出发去判断旋转类型。多画几次旋转示意图后你会形成一种手感做题时不用反复推导。3.4 哈夫曼树从带权路径长度最小理解编码本质哈夫曼树这一节如果只记构造方法就太亏了它的应用场景——哈夫曼编码——是信息论里一个绝美的应用。给定一组字符及出现频率用哈夫曼树构造出每个字符的二进制编码要求整体编码长度最短而且每个字符的编码不能是另一个字符编码的前缀。构造过程一句话概括每次从森林里选两个权值最小的树合并新根权值为二者之和放回森林重复直到只剩一棵树。这个过程用优先队列最小堆实现非常自然每次取两个最小元素合并后push回去复杂度是O(n log n)。哈夫曼编码前缀编码的特性是因为每个字符都在叶子节点上没有任何字符的编码路径会经过另一个字符的编码。如果某个字符是另一个字符的祖先节点那它的编码就会成为另一个的前缀解码时会产生歧义。保证字符对应叶子节点就是哈夫曼编码正确性的根基。4. 图论算法从遍历到最短路径的思维升级图是数据结构里概念最多、算法最密集的一章。邻接矩阵、邻接表、十字链表、邻接多重表、DFS、BFS、Prim、Kruskal、Dijkstra、Floyd、拓扑排序、关键路径……一个学期最后几周的高强度内容全在这一章。如果前面的树学得扎实图其实可以看作树的一般化——树是只有一条路径连接的图图是多对多的关系网络。4.1 存储结构的选择邻接矩阵和邻接表怎么权衡邻接矩阵是二维数组存储顶点间关系判断两个顶点是否相邻是O(1)但存储空间是O(V²)对稀疏图非常浪费。邻接表为每个顶点挂一个链表存储空间是O(VE)但判断两个顶点是否相邻需要顺着链表找最坏O(V)。选哪个我的经验总结成一句话稠密图用矩阵稀疏图用表。但在实际笔试中题目通常会给你一个具体的图让你画出存储结构这时候你需要熟练掌握两种表示法的绘图规范。尤其是邻接表每个顶点后的链表节点顺序如果题目没有说明一般按输入顺序或顶点编号递增顺序排列即可但如果题目明确说了按某种顺序一定要严格遵守。4.2 最小生成树Prim与Kruskal的核心差异最小生成树算法有两个经典实现Prim和Kruskal。Prim算法的思路是从一个点开始扩张领地初始选定一个顶点加入集合U每次从连接U和V-U的边里挑一条权值最小的边把新顶点并入U重复直到所有顶点都在U里。这个过程中U始终是一棵连通的树所以每次选边时不会产生环。Kruskal算法则是全局选边把所有边按权值排序从小到大逐条加入只要加入后不形成环就保留直到选了V-1条边。Kruskal不会维护一个当前连通区域所以它的关键操作是判断一条边的两个端点是否已经连通——这个操作用并查集实现就是O(α(n))非常高效。我在笔记里专门对比过这两者选边时的差异Prim是点视角适合稠密图用邻接矩阵或堆优化Kruskal是边视角适合稀疏图边数少排序成本可控。考研里如果给一个具体的图让你求最小生成树两种方法都要会手工模拟并且能说明每一步选择的依据。4.3 最短路径Dijkstra不能有负权边Floyd可以最短路径算法是图论的大魔王章节。Dijkstra算法用贪心策略每次从未确定最短路径的顶点里选出当前距离最小的并松弛它的邻接边。Dijkstra的正确性依赖一个前提所有边的权值非负。如果存在负权边先被确定的顶点可能在后面被一条负权边绕近导致算法失效。Floyd算法则完全不同它动态规划地枚举所有中间顶点用三维循环实际代码里通常压缩成二维滚动数组更新任意两点间的最短路径。Floyd能处理负权边但不能有负权回路。它的时间复杂度是O(V³)所以只适合顶点数不多的场景。我犯过的错误和大多数人一样一开始没搞清楚松弛操作到底在干什么。松弛的本质就是检查经过中间点k会不会比直接走更短。如果 dis[i][j] dis[i][k] dis[k][j]就更新 dis[i][j]。当你真正理解了以k为中间点这句话Floyd的代码就只是一层固定格式的循环嵌套。4.4 拓扑排序与关键路径有向无环图的应用拓扑排序是对有向无环图DAG的顶点的一种线性排列要求每条边的起点都在终点之前。算法思路很朴素每次找一个入度为0的顶点输出然后删除它及其出边更新剩余顶点的入度重复。这个过程用队列或栈实现如果最终输出的顶点数量小于总顶点数说明图中存在环拓扑排序失败。在408考研中拓扑排序经常和判断一个有向图是否有环结合出题也经常和DFS的递归栈标记方法对比。两种方法各有适用场景拓扑排序适合输出一个合法序列而DFS三色标记法白、灰、黑可以顺便做环检测。关键路径的问题是AOE网边表示活动的有向无环图边的权值表示活动持续时间求从源点到汇点的最长路径因为整个工程的完工时间取决于最长的那条路径也就是瓶颈路径。求关键路径需要先算事件的最早开始时间和最迟开始时间两者的差为0的事件组成关键路径。5. 查找与排序期末和考研的兵家必争之地查找和排序是数据结构考试里最细的部分。二分查找的下标变化、哈希冲突处理、快排的划分过程、堆排序的调整过程每一个都是高频考点。我见过太多同学顺序表、链表学得好好的到了排序这里开始晕头转向因为排序算法涉及大量的手动模拟过程一步错步步错。5.1 折半查找那些教材没明说的细节折半查找二分查找的前提是顺序存储且有序。代码逻辑很简单但有两个细节很多人没注意第一中点取法。标准写法是 mid (low high) / 2但更好的写法是 mid low (high - low) / 2因为前一种写法在 low high 特别大时可能整型溢出。这个细节在考研机试或面试手写代码时会被问到。第二查找判定树。折半查找的过程可以用一棵二叉判定树表示树中每个节点代表一次中点的比较。这棵树的形态揭示了折半查找的时间复杂度O(log n)和平均查找长度。考研題经常给出判定树让你计算ASL平均查找长度或者反过来问你对长度为n的有序表折半查找最多比较几次。计算ASL是这一节的常见题型我记了公式成功时的ASL等于各层节点数乘以对应层次之和除以节点总数失败时的ASL等于各外节点空孩子位置的层次之和除以失败可能的总数。这里如果不画判定树几乎是算不对的所以无论平时练习还是考场都建议动手画出完整的判定树。5.2 哈希表冲突处理方式是期末必考哈希表的考点集中在哈希函数设计和冲突处理。常见的冲突处理方法有开放定址法线性探测、平方探测、再哈希法和链地址法。线性探测的问题在于容易产生堆积一旦某块区域填满了后续冲突的键都会往后推移形成聚集区导致查找变慢。平方探测通过步长的平方变化减少堆积但有一个限制条件装填因子不能太大否则可能无法找到空位。链地址法最直观每个哈希槽挂一个链表冲突的元素直接链在后面查找时遍历链表即可。期末笔试最常考的操作是给定一组关键字和哈希函数、表长、冲突处理方式让你画出哈希表并计算成功/失败的平均查找长度。这类题没有任何捷径只能老老实实地按顺序插入每个关键字记录每个关键字比较的次数。我在笔记里用红笔标注了一个易错点删除哈希表中的元素时线性探测法不能直接物理删除因为会切断后续元素的探测链只能做懒惰删除标记。这个问题在应用题和概念题里经常出现。5.3 五种排序必须熟练到随手就能模拟排序算法是数据结构笔记里最干货的部分。期末和考研要求掌握的排序包括插入排序直接插入、希尔、交换排序冒泡、快速、选择排序简单选择、堆排序、归并排序、基数排序。这里我不打算把每个算法都详细贴一遍那是教材干的事我更想分享的是怎么通过对比把它们一次性记住。八大排序的核心区别我用这张表高度概括排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性直接插入O(n²)O(n²)O(1)稳定希尔排序O(n^1.3~2)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²)触发条件是每次划分都极度不平衡比如数组本身有序且每次选第一个元素作枢轴。5.4 快排和堆排复习时我踩过的坑快速排序的划分过程是笔试手写模拟的重灾区。我犯过的错误是用两个指针从两端交替扫描时方向搞反了或者移动条件写错。正确流程是选一个枢轴通常取第一个元素从右往左找比枢轴小的元素找到后填入左侧空位再从左往右找比枢轴大的元素找到后填入右侧空位交替进行直到左右指针相遇把枢轴放进去。一次划分完成后枢轴左边都小于等于它右边都大于等于它。每趟划分之后枢轴元素就固定不动了这个递归过程是分而治之的直观体现。堆排序对我来说是另一个难点。建堆和堆调整的代码需要下沉操作把当前节点和它的左右孩子比较找到最大的那个大顶堆如果不满足堆性质就交换然后继续下沉。笔试里经常要求对一个小顶堆插入一个元素后演示堆的调整过程这需要你非常熟练地掌握完全二叉树用数组存储时节点i的左孩子是2i1、右孩子是2i2、父节点是(i-1)/2这三个下标公式。我自己的经验是堆排序不要只看文字描述必须自己在纸上画一个数组对应的完全二叉树然后模拟从最后一个非叶子节点开始向上逐个调整的建堆过程。当你能独立完成一次建堆和三次调整不犯错这部分才算真正过关。6. 持续更新机制如何让笔记真正成为长期资产前面说了很多知识层面的整理思路最后想聊聊笔记本身怎么维护。数据结构内容量大很多同学学期初写得兴致勃勃几周后就荒废了。我自己的笔记能持续更新到现在靠的是一套不算复杂的更新机制。6.1 为每个知识点打三种标签我最初整理笔记时所有内容平铺直叙复习时根本抓不住重点。后来改成在每节开头打标签效果立竿见影。标签分三类必考、易错和联系。必考标签标注那些历年真题、期末考试卷反复出现的知识点比如二叉树遍历、Dijkstra算法、快排划分过程。易错标签标注那些自己曾经做错过的具体细节比如循环队列判满条件、(rear1)%MAXSIZE、拓扑排序只适用于DAG。联系标签标注两个看似无关的知识点之间的桥比如孩子兄弟表示法树的存储和二叉树之间是互转关系用栈实现深度优先遍历、用队列实现广度优先遍历。这三个标签让复习变成带着优先级扫描而不是从头到尾读一遍。6.2 每次学完必须产出三件套给自己定了个规矩每学完一个新的数据结构强制要求产出三样东西一张手工绘制的示意图比如链表的指针变化、二叉树的递归遍历过程、最小生成树的选边过程。一段自己写的、能运行的代码哪怕是书上的例题也要手敲一遍不能复制。一个给别人讲的段落用大白话解释这个数据结构解决了什么问题典型应用是什么。这三样东西做下来比读十遍教材都有用。尤其是第三条很多概念你觉得懂了但真让你讲出来会发现自己组织语言都困难。我笔记里很多类比和记忆技巧都是在这个环节里琢磨出来的。6.3 定期重构笔记是活的我的笔记更新频率大概是这样的每学完一章补充一次每做完一套题补充错题涉及的知识点每个月底花半小时通读之前的笔记把发现的新联系补充进去。这个月底重构环节经常带来惊喜——当你学完图和排序之后回头看栈和队列会发现很多之前没看到的联系。比如递归就是用栈实现的BFS为什么能用队列实现而DFS更适合用栈或递归。这种跨章节的联系只有在你对整个课程有了全局视野后才会浮现出来。如果有人问我数据结构这门课到底怎么学我的回答是把笔记当作一个可以反复迭代的存根而不是一次性的成品。第一遍学习时笔记粗糙一点没关系关键是每个知识点都留下自己理解的痕迹。后面每次复习、做题、写代码时发现有新的体会就回去修改旧的段落让笔记始终处于接近当前认知水平的状态。持续更新这四个字从来不在于更新得多频繁而在于每一次更新的方向都是朝向更深的理解。这篇笔记会继续更新下去下一批打算补充的内容包括考研408真题里图论编程题的常见套路、B树和B树的对比笔记、以及用Python的pandas库从工程角度理解数据结构中的索引到底是怎么用树和哈希实现加速查找的。希望这份笔记整理的思路能给你的数据结构学习带来一些有用的参考。