之前学数据结构忘得差不多了现在再巩固下老实说大部分学过数据结构的人都会有同样的处境上课时以为自己懂了考试前熬夜背了考完两周再问自己“链表和数组到底差在哪”脑子里只剩一句“反正就是存数据的东西”。这种“学过就忘”太正常了因为数据结构这门课本质上不是背出来的是敲代码敲出来的、画图画出来的、错题错出来的。我这次重新回炉把当年欠下的账一笔一笔补上整个过程走下来最大的感受是数据结构不值得“学”值得“用”而“用”的意思就是——每看到一个结构你都得能回答三个问题它解决什么问题它凭什么比另一个结构快它的代价藏在哪儿这篇文章就把我这轮回炉复习的思路、实操过程和踩坑记录完整写下来所有内容都以“重新巩固数据结构”为核心展开适合考完就忘的在校生、准备408考研的选手、还有工作后想补基础的开发者。不需要你基础多好只要你愿意打开编辑器跟着敲一遍效果一定比翻十遍PPT强。1. 整体复习思路先找“手感”再谈“体系”1.1 忘的不是概念是“手感”很多人复习数据结构第一反应是翻书、看知识点总结、抄笔记结果看三天就放弃了。原因是概念本身不难难的是你失去了“数据在内存里到底怎么摆”的想象力。数组是连续的内存块链表是东一块西一块靠指针串起来的栈是只从一个口进出的线性结构树是有了分支的节点集合——这些文字描述谁都能读懂但做题和写代码的时候你脑补不出内存图就会卡在“为什么这里要判空”“为什么这里要传二级指针”。所以我的第一轮复习完全放弃了看大段文字改用“看图画图”的方式。不管什么结构先把它在草稿纸上画成方框和箭头数组就画一排格子链表就画几个方框加箭头栈就画一个开口向上的容器。画完以后再想操作插入一个元素格子怎么动箭头怎么改。这个过程大概花两天时间就能把“手感”找回来。1.2 以题带学、以码带背找回手感之后我做了个决定不按目录顺序复习而是按“高频面试题考研真题课程实验”三个清单驱动。原因很简单数据结构内部是高度关联的你单背“二叉树的前序遍历怎么递归”不如直接做一道“用非递归实现前序遍历”的题后者逼你把栈和树一起搞明白。我把复习路径拆成了三层第一层线性结构数组、链表、栈、队列、双端队列所有内容围绕“指针怎么指”“边界怎么卡”。第二层树形结构二叉树、二叉搜索树、堆理解递归本质学会把递归改迭代。第三层图、查找、排序重点放在复杂度推导和算法之间的对比。每层要求自己完成三件事画结构图、写代码实现、跑通测试用例。三件事都做完了才允许进入下一层。这个节奏比起从头翻书高效得多而且不容易产生“看了后面忘了前面”的挫败感。2. 核心知识点逐个过结构、操作、复杂度2.1 线性结构数组不一定快链表不一定慢先说说最容易被误解的数组和链表。很多人以为数组就是“快”、链表就是“慢”其实这个印象错得很远。数组的随机访问是O(1)但插入和删除平均是O(n)因为要搬动后续元素链表恰好相反一旦定位到节点插入和删除是O(1)但查找是O(n)而且每个节点还要额外存指针内存开销更大。我复习时重点做了链表反转、合并两个有序链表、判断链表是否有环这三个经典题目。链表反转尤其关键迭代写法三行代码就能搞定但第一次写很容易绕晕struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL, *curr head, *next; while (curr) { next curr-next; curr-next prev; prev curr; curr next; } return prev; }这个代码的核心就一句话每次只改一个指针方向用next变量提前保存后继节点。画图时要把三个指针prev、curr、next的位置标清楚否则写十次错十次。2.2 栈、队列与双端队列边界条件是灵魂栈和队列在考研和面试里出现频率极高但很多人栽在边界条件上。栈先入后出队列先入先出双端队列Deque则是两端都能入队出队。双端队列在最新热词里频繁出现不是没道理的因为它在滑动窗口最大值、单调队列、回文判断等场景里特别好用。我自己实现双端队列时踩过一个典型的坑判空条件。如果是用数组实现循环双端队列front和rear的移动必须取模而且判空和判满不能用同一种方式。常见做法是浪费一个存储位置来区分空和满判空front rear判满(rear 1) % capacity front很多人用“front rear”同时判空和判满结果插入到一半队列就报错。这个问题在实验报告里出现率很高值得单独画图理解。2.3 树与二叉树递归的本质是“相信子问题”二叉树是很多人“放弃治疗”的地方因为递归的调用栈太抽象。我自己当时的顿悟点是不要试图跟踪每一层递归只关心“当前节点要做什么”和“子问题是什么”。前序遍历的递归当前节点只做一件事——先访问自己再让孩子去做同样的操作。层序遍历BFS则是另一种思维要把“一层一层”的感觉落实到队列上。核心代码很固定void levelOrder(struct TreeNode* root) { if (!root) return; struct TreeNode* queue[1000]; int head 0, tail 0; queue[tail] root; while (head tail) { struct TreeNode* node queue[head]; visit(node); if (node-left) queue[tail] node-left; if (node-right) queue[tail] node-right; } }这里其实用到了队列的先进先出特性把“每一层的节点”依次弹出同时把下一层节点挂到尾部。画图时建议用“按层画队列”的方式我当时在草稿纸上画了三层二叉树入队出队的全过程彻底理解了BFS。2.4 图结构存储方式和遍历比路径算法更基础图这块408和期末都喜欢考邻接矩阵、邻接表的存储以及DFS/BFS在两种存储下的时间复杂度。邻接矩阵适合稠密图判断两点是否连通是O(1)但存稀疏图浪费空间邻接表适合稀疏图遍历一个节点的所有邻居很自然但判断任意两点连通要遍历链表。两者没有绝对好坏只看场景。复习图的时候我建议先把DFS/BFS用邻接表实现一遍再对比矩阵实现的差异。实际过程中最容易错的是“节点是否已访问”的标记位置DFS要在入栈前标记BFS要在入队前标记。如果出栈/出队时才标记同一个节点会被重复处理轻则浪费时间重则无限循环。2.5 查找与排序复杂度不是背出来的是推出来的排序算法是复习的重点也是很多人最头疼的地方。八个常见排序插排、希尔、冒泡、快排、选择、堆排、归并、基数不用全背但要能分类比较类排序和非比较类排序稳定排序和不稳定排序最好、最坏、平均时间复杂度。我用一个表格把高频的几个整理了出来排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定插入排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定这个表每个元素都值得推一下尤其是快排的“最坏情况O(n^2)”怎么来的答案每次选的基准都是最大或最小元素退化成了每次划分只减少一个元素。我复习时专门写了一个“每次取末尾元素为基准”的退化版本输入一个已经排好序的数组肉眼可见变慢。查找方面二分查找的边界条件是最大痛点。我自己的经验是把区间定义成“左闭右开”这样循环条件写while (l r)中间值计算写mid l (r - l) / 2整体好记很多。3. 实操过程把“回忆”变成“代码”3.1 环境选择C语言还是Python复习数据结构的第一个实操问题就是用什么语言写代码。如果你考研408或者课程要求C语言那必须用C虽然指针繁琐但能逼你理解底层细节。如果只是为了理解概念或者面试刷题Python更友好毕竟链表、树这些结构写起来没有那么多内存管理的干扰。我的建议是理解概念用Python深挖细节用C。比如链表反转用Python写可能只关注逻辑用C写你才会注意到“为什么反转链表时要先保存后继节点”因为你不保存改了当前节点的next之后后面那一段内存你就找不到了。我自己是先用C写一遍再用Python去对比验证逻辑两种语言的差异本身就是很好的学习材料。3.2 三个必写的小项目链表反转、双端队列、快速排序如果只给你三天时间巩固数据结构我会让你写这三个东西它们覆盖了指针操作、循环边界、递归和分治。第一个是链表反转前面已经给了C代码。第二个是双端队列建议用数组实现循环版本完整代码核心部分如下class Deque: def __init__(self, capacity): self.capacity capacity self.data [None] * capacity self.front 0 self.rear 0 self.size 0 def is_full(self): return self.size self.capacity def is_empty(self): return self.size 0 def add_front(self, value): if self.is_full(): raise Exception(Deque is full) self.front (self.front - 1) % self.capacity self.data[self.front] value self.size 1 def add_rear(self, value): if self.is_full(): raise Exception(Deque is full) self.data[self.rear] value self.rear (self.rear 1) % self.capacity self.size 1第三个是快速排序我用的是“填坑法”这个思路最好理解先把基准值从数组里拿出来空出一个位置然后从右往左找比基准小的填到左边空位从左往右找比基准大的填到右边空位最后基准归位。这三个写完之后建议顺手画一遍每个操作的指针/索引变化图。代码跑通不是目的脑内动态模拟才是。3.3 实验报告与笔记怎么整理才不白写很多人写数据结构实验报告就是“代码贴上去截图运行结果”这等于没写。我这次复习特别注重要把“设计思路”和“测试用例”两部分补齐。设计思路不要写“定义一个结构体”而要写清楚为什么这个结构需要这个字段为什么插入时要先判断满为什么删除时要返回被删的值测试用例也有讲究。不要只测一个正向用例要找边界空表插入、满表插入、删除最后一个元素、队列front和rear相遇……这些用例才是实验报告里最能体现水平的地方也是老师重点看的部分。4. 常见问题与排查技巧实录4.1 野指针、越界与死循环这三兄弟是写数据结构代码最容易遇见的bug。野指针多半是因为链表删除节点之后没有把原指针置空或者free之后还去访问越界多半是循环边界搞错尤其是二分查找的lr可能溢出必须写成l (r-l)/2死循环则经常发生在BFS/DFS的访问标记位置不对或者链表的循环条件写成了while (curr-next ! NULL)导致最后一个节点没处理。我自己排查时有一个习惯凡是无限循环先检查循环指针每一步有没有前进凡是段错误先检查有没有访问NULL-next。这两个习惯帮我省了大量时间。4.2 复杂度算不清楚怎么办复杂度是所有期末题和考研题绕不开的坎。算不清楚的本质是不知道“操作次数”怎么数。比如双层嵌套循环里面只有一个简单语句那复杂度通常就是外层的n乘以内层的n。但要小心内层循环的边界是不是动态的比如插入排序内层循环虽然嵌套但平均比较次数是n/2所以复杂度还是O(n^2)。我的建议是不要死记复杂度公式而是先写出算法最核心的循环或递归式然后把“操作次数”逐步展开。快排的时间复杂度推导就是经典T(n) 2T(n/2) O(n)用主定理直接得到O(n log n)。会写递归式比背结论可靠一百倍。4.3 教程和参考书的取舍复习时手边通常会有几本资料严蔚敏的教材、王道数据结构、李春葆的习题集还有各种PDF和期末复习资料。我的体验是一本教材打底、一本考研辅导做题型、一套真题练手感就够了不要囤十份资料然后每份都只翻开头。如果你目标是考研408王道是主流选择优点是知识点梳理和题型归类很到位但有些解法为了应试会牺牲代码完整性建议配合教材补充底层原理。如果你课程使用李春葆的教材一定要去找对应的学习指导和勘误汇总因为习题集里有不少打印错误一个人硬啃容易被误导。期末复习则以学校的历年试卷为准时间不够时优先刷题不要死磕还没考过的冷门内容。5. 四周回炉计划从遗忘到能输出5.1 每周目标与检查标准如果你现在也处于“忘得差不多了”的状态可以参考我这个四周计划第一周线性表与栈队列。重点写链表反转、双端队列、循环队列目标是不看任何资料白板写出完整可运行的代码。检查标准能在10分钟内完成链表反转无编译错误。第二周树与递归。重点写二叉树前中后序遍历递归版和非递归版、层序遍历、求树的高度。检查标准能用非递归方式实现中序遍历并讲清楚栈的作用。第三周图与搜索。重点用邻接表写DFS和BFS并统计图中连通分量个数。检查标准能画出邻接表结构并写出带visited数组标记的完整代码。第四周查找与排序。重点写二分查找、快速排序、归并排序并完成一个小型对比实验随机生成一万个整数分别用三种排序跑一遍记录时间。检查标准能用口语解释快排为什么最坏O(n^2)以及归并为什么稳定。这个计划最大的特点是可以容忍反复遗忘。前两周写过的链表反转第四周可能又生疏了没关系再画一次图再写一遍。巩固本来就是循环往复的过程。5.2 避坑清单与独家小技巧最后分享几个复习数据结构时别人不太会明说但实际非常好用的技巧每学一个结构就写一个“5分钟速写”。就是合上所有资料用白纸画图加关键代码把这结构讲给空气听。能讲明白才算真明白。故意写错再故意debug。我复习时会把链表反转的next顺序故意写错然后观察输出如何变再反过来推理指针状态。这种“逆向debug”比看十个正确例子都深刻。用LeetCode的简单题当习题集。不用刷很多每天两三道简单题比做十页纸质题更能巩固真实能力。比如“合并两个有序链表”“有效的括号”“二叉树的最大深度”这三道就足够把三个大块复习串联起来。整理一份自己的“错题表”而不是笔记。表格里只记录“哪里错了、为什么会错、正确思路是什么”。临考前看三遍这张表比看一整本PPT有效。数据结构这门课说穿了就是“基础结构抽象思维工程细节”的组合。重新巩固的过程未必轻松但每当你发现“原来队列还能这么用”“原来快排的退化是这么回事”的时候那种串联感会非常上瘾。我已经把该踩的坑和该画的图都揉在这篇文章里了接下来轮到你打开编辑器亲手试一遍。
数据结构回炉巩固：从链表、二叉树到快速排序的实战复习指南
之前学数据结构忘得差不多了现在再巩固下老实说大部分学过数据结构的人都会有同样的处境上课时以为自己懂了考试前熬夜背了考完两周再问自己“链表和数组到底差在哪”脑子里只剩一句“反正就是存数据的东西”。这种“学过就忘”太正常了因为数据结构这门课本质上不是背出来的是敲代码敲出来的、画图画出来的、错题错出来的。我这次重新回炉把当年欠下的账一笔一笔补上整个过程走下来最大的感受是数据结构不值得“学”值得“用”而“用”的意思就是——每看到一个结构你都得能回答三个问题它解决什么问题它凭什么比另一个结构快它的代价藏在哪儿这篇文章就把我这轮回炉复习的思路、实操过程和踩坑记录完整写下来所有内容都以“重新巩固数据结构”为核心展开适合考完就忘的在校生、准备408考研的选手、还有工作后想补基础的开发者。不需要你基础多好只要你愿意打开编辑器跟着敲一遍效果一定比翻十遍PPT强。1. 整体复习思路先找“手感”再谈“体系”1.1 忘的不是概念是“手感”很多人复习数据结构第一反应是翻书、看知识点总结、抄笔记结果看三天就放弃了。原因是概念本身不难难的是你失去了“数据在内存里到底怎么摆”的想象力。数组是连续的内存块链表是东一块西一块靠指针串起来的栈是只从一个口进出的线性结构树是有了分支的节点集合——这些文字描述谁都能读懂但做题和写代码的时候你脑补不出内存图就会卡在“为什么这里要判空”“为什么这里要传二级指针”。所以我的第一轮复习完全放弃了看大段文字改用“看图画图”的方式。不管什么结构先把它在草稿纸上画成方框和箭头数组就画一排格子链表就画几个方框加箭头栈就画一个开口向上的容器。画完以后再想操作插入一个元素格子怎么动箭头怎么改。这个过程大概花两天时间就能把“手感”找回来。1.2 以题带学、以码带背找回手感之后我做了个决定不按目录顺序复习而是按“高频面试题考研真题课程实验”三个清单驱动。原因很简单数据结构内部是高度关联的你单背“二叉树的前序遍历怎么递归”不如直接做一道“用非递归实现前序遍历”的题后者逼你把栈和树一起搞明白。我把复习路径拆成了三层第一层线性结构数组、链表、栈、队列、双端队列所有内容围绕“指针怎么指”“边界怎么卡”。第二层树形结构二叉树、二叉搜索树、堆理解递归本质学会把递归改迭代。第三层图、查找、排序重点放在复杂度推导和算法之间的对比。每层要求自己完成三件事画结构图、写代码实现、跑通测试用例。三件事都做完了才允许进入下一层。这个节奏比起从头翻书高效得多而且不容易产生“看了后面忘了前面”的挫败感。2. 核心知识点逐个过结构、操作、复杂度2.1 线性结构数组不一定快链表不一定慢先说说最容易被误解的数组和链表。很多人以为数组就是“快”、链表就是“慢”其实这个印象错得很远。数组的随机访问是O(1)但插入和删除平均是O(n)因为要搬动后续元素链表恰好相反一旦定位到节点插入和删除是O(1)但查找是O(n)而且每个节点还要额外存指针内存开销更大。我复习时重点做了链表反转、合并两个有序链表、判断链表是否有环这三个经典题目。链表反转尤其关键迭代写法三行代码就能搞定但第一次写很容易绕晕struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL, *curr head, *next; while (curr) { next curr-next; curr-next prev; prev curr; curr next; } return prev; }这个代码的核心就一句话每次只改一个指针方向用next变量提前保存后继节点。画图时要把三个指针prev、curr、next的位置标清楚否则写十次错十次。2.2 栈、队列与双端队列边界条件是灵魂栈和队列在考研和面试里出现频率极高但很多人栽在边界条件上。栈先入后出队列先入先出双端队列Deque则是两端都能入队出队。双端队列在最新热词里频繁出现不是没道理的因为它在滑动窗口最大值、单调队列、回文判断等场景里特别好用。我自己实现双端队列时踩过一个典型的坑判空条件。如果是用数组实现循环双端队列front和rear的移动必须取模而且判空和判满不能用同一种方式。常见做法是浪费一个存储位置来区分空和满判空front rear判满(rear 1) % capacity front很多人用“front rear”同时判空和判满结果插入到一半队列就报错。这个问题在实验报告里出现率很高值得单独画图理解。2.3 树与二叉树递归的本质是“相信子问题”二叉树是很多人“放弃治疗”的地方因为递归的调用栈太抽象。我自己当时的顿悟点是不要试图跟踪每一层递归只关心“当前节点要做什么”和“子问题是什么”。前序遍历的递归当前节点只做一件事——先访问自己再让孩子去做同样的操作。层序遍历BFS则是另一种思维要把“一层一层”的感觉落实到队列上。核心代码很固定void levelOrder(struct TreeNode* root) { if (!root) return; struct TreeNode* queue[1000]; int head 0, tail 0; queue[tail] root; while (head tail) { struct TreeNode* node queue[head]; visit(node); if (node-left) queue[tail] node-left; if (node-right) queue[tail] node-right; } }这里其实用到了队列的先进先出特性把“每一层的节点”依次弹出同时把下一层节点挂到尾部。画图时建议用“按层画队列”的方式我当时在草稿纸上画了三层二叉树入队出队的全过程彻底理解了BFS。2.4 图结构存储方式和遍历比路径算法更基础图这块408和期末都喜欢考邻接矩阵、邻接表的存储以及DFS/BFS在两种存储下的时间复杂度。邻接矩阵适合稠密图判断两点是否连通是O(1)但存稀疏图浪费空间邻接表适合稀疏图遍历一个节点的所有邻居很自然但判断任意两点连通要遍历链表。两者没有绝对好坏只看场景。复习图的时候我建议先把DFS/BFS用邻接表实现一遍再对比矩阵实现的差异。实际过程中最容易错的是“节点是否已访问”的标记位置DFS要在入栈前标记BFS要在入队前标记。如果出栈/出队时才标记同一个节点会被重复处理轻则浪费时间重则无限循环。2.5 查找与排序复杂度不是背出来的是推出来的排序算法是复习的重点也是很多人最头疼的地方。八个常见排序插排、希尔、冒泡、快排、选择、堆排、归并、基数不用全背但要能分类比较类排序和非比较类排序稳定排序和不稳定排序最好、最坏、平均时间复杂度。我用一个表格把高频的几个整理了出来排序算法平均时间复杂度最坏时间复杂度空间复杂度稳定性冒泡排序O(n^2)O(n^2)O(1)稳定插入排序O(n^2)O(n^2)O(1)稳定选择排序O(n^2)O(n^2)O(1)不稳定快速排序O(n log n)O(n^2)O(log n)不稳定归并排序O(n log n)O(n log n)O(n)稳定堆排序O(n log n)O(n log n)O(1)不稳定这个表每个元素都值得推一下尤其是快排的“最坏情况O(n^2)”怎么来的答案每次选的基准都是最大或最小元素退化成了每次划分只减少一个元素。我复习时专门写了一个“每次取末尾元素为基准”的退化版本输入一个已经排好序的数组肉眼可见变慢。查找方面二分查找的边界条件是最大痛点。我自己的经验是把区间定义成“左闭右开”这样循环条件写while (l r)中间值计算写mid l (r - l) / 2整体好记很多。3. 实操过程把“回忆”变成“代码”3.1 环境选择C语言还是Python复习数据结构的第一个实操问题就是用什么语言写代码。如果你考研408或者课程要求C语言那必须用C虽然指针繁琐但能逼你理解底层细节。如果只是为了理解概念或者面试刷题Python更友好毕竟链表、树这些结构写起来没有那么多内存管理的干扰。我的建议是理解概念用Python深挖细节用C。比如链表反转用Python写可能只关注逻辑用C写你才会注意到“为什么反转链表时要先保存后继节点”因为你不保存改了当前节点的next之后后面那一段内存你就找不到了。我自己是先用C写一遍再用Python去对比验证逻辑两种语言的差异本身就是很好的学习材料。3.2 三个必写的小项目链表反转、双端队列、快速排序如果只给你三天时间巩固数据结构我会让你写这三个东西它们覆盖了指针操作、循环边界、递归和分治。第一个是链表反转前面已经给了C代码。第二个是双端队列建议用数组实现循环版本完整代码核心部分如下class Deque: def __init__(self, capacity): self.capacity capacity self.data [None] * capacity self.front 0 self.rear 0 self.size 0 def is_full(self): return self.size self.capacity def is_empty(self): return self.size 0 def add_front(self, value): if self.is_full(): raise Exception(Deque is full) self.front (self.front - 1) % self.capacity self.data[self.front] value self.size 1 def add_rear(self, value): if self.is_full(): raise Exception(Deque is full) self.data[self.rear] value self.rear (self.rear 1) % self.capacity self.size 1第三个是快速排序我用的是“填坑法”这个思路最好理解先把基准值从数组里拿出来空出一个位置然后从右往左找比基准小的填到左边空位从左往右找比基准大的填到右边空位最后基准归位。这三个写完之后建议顺手画一遍每个操作的指针/索引变化图。代码跑通不是目的脑内动态模拟才是。3.3 实验报告与笔记怎么整理才不白写很多人写数据结构实验报告就是“代码贴上去截图运行结果”这等于没写。我这次复习特别注重要把“设计思路”和“测试用例”两部分补齐。设计思路不要写“定义一个结构体”而要写清楚为什么这个结构需要这个字段为什么插入时要先判断满为什么删除时要返回被删的值测试用例也有讲究。不要只测一个正向用例要找边界空表插入、满表插入、删除最后一个元素、队列front和rear相遇……这些用例才是实验报告里最能体现水平的地方也是老师重点看的部分。4. 常见问题与排查技巧实录4.1 野指针、越界与死循环这三兄弟是写数据结构代码最容易遇见的bug。野指针多半是因为链表删除节点之后没有把原指针置空或者free之后还去访问越界多半是循环边界搞错尤其是二分查找的lr可能溢出必须写成l (r-l)/2死循环则经常发生在BFS/DFS的访问标记位置不对或者链表的循环条件写成了while (curr-next ! NULL)导致最后一个节点没处理。我自己排查时有一个习惯凡是无限循环先检查循环指针每一步有没有前进凡是段错误先检查有没有访问NULL-next。这两个习惯帮我省了大量时间。4.2 复杂度算不清楚怎么办复杂度是所有期末题和考研题绕不开的坎。算不清楚的本质是不知道“操作次数”怎么数。比如双层嵌套循环里面只有一个简单语句那复杂度通常就是外层的n乘以内层的n。但要小心内层循环的边界是不是动态的比如插入排序内层循环虽然嵌套但平均比较次数是n/2所以复杂度还是O(n^2)。我的建议是不要死记复杂度公式而是先写出算法最核心的循环或递归式然后把“操作次数”逐步展开。快排的时间复杂度推导就是经典T(n) 2T(n/2) O(n)用主定理直接得到O(n log n)。会写递归式比背结论可靠一百倍。4.3 教程和参考书的取舍复习时手边通常会有几本资料严蔚敏的教材、王道数据结构、李春葆的习题集还有各种PDF和期末复习资料。我的体验是一本教材打底、一本考研辅导做题型、一套真题练手感就够了不要囤十份资料然后每份都只翻开头。如果你目标是考研408王道是主流选择优点是知识点梳理和题型归类很到位但有些解法为了应试会牺牲代码完整性建议配合教材补充底层原理。如果你课程使用李春葆的教材一定要去找对应的学习指导和勘误汇总因为习题集里有不少打印错误一个人硬啃容易被误导。期末复习则以学校的历年试卷为准时间不够时优先刷题不要死磕还没考过的冷门内容。5. 四周回炉计划从遗忘到能输出5.1 每周目标与检查标准如果你现在也处于“忘得差不多了”的状态可以参考我这个四周计划第一周线性表与栈队列。重点写链表反转、双端队列、循环队列目标是不看任何资料白板写出完整可运行的代码。检查标准能在10分钟内完成链表反转无编译错误。第二周树与递归。重点写二叉树前中后序遍历递归版和非递归版、层序遍历、求树的高度。检查标准能用非递归方式实现中序遍历并讲清楚栈的作用。第三周图与搜索。重点用邻接表写DFS和BFS并统计图中连通分量个数。检查标准能画出邻接表结构并写出带visited数组标记的完整代码。第四周查找与排序。重点写二分查找、快速排序、归并排序并完成一个小型对比实验随机生成一万个整数分别用三种排序跑一遍记录时间。检查标准能用口语解释快排为什么最坏O(n^2)以及归并为什么稳定。这个计划最大的特点是可以容忍反复遗忘。前两周写过的链表反转第四周可能又生疏了没关系再画一次图再写一遍。巩固本来就是循环往复的过程。5.2 避坑清单与独家小技巧最后分享几个复习数据结构时别人不太会明说但实际非常好用的技巧每学一个结构就写一个“5分钟速写”。就是合上所有资料用白纸画图加关键代码把这结构讲给空气听。能讲明白才算真明白。故意写错再故意debug。我复习时会把链表反转的next顺序故意写错然后观察输出如何变再反过来推理指针状态。这种“逆向debug”比看十个正确例子都深刻。用LeetCode的简单题当习题集。不用刷很多每天两三道简单题比做十页纸质题更能巩固真实能力。比如“合并两个有序链表”“有效的括号”“二叉树的最大深度”这三道就足够把三个大块复习串联起来。整理一份自己的“错题表”而不是笔记。表格里只记录“哪里错了、为什么会错、正确思路是什么”。临考前看三遍这张表比看一整本PPT有效。数据结构这门课说穿了就是“基础结构抽象思维工程细节”的组合。重新巩固的过程未必轻松但每当你发现“原来队列还能这么用”“原来快排的退化是这么回事”的时候那种串联感会非常上瘾。我已经把该踩的坑和该画的图都揉在这篇文章里了接下来轮到你打开编辑器亲手试一遍。
