先说明一下背景。数据结构这门课几乎是计算机专业所有学生都躲不开的一座山不管是期末突击、考研二战还是秋招面试前临时抱佛脚“数据结构 算法代码”这两个词一出现就意味着背不完的定义、画不完的图、写不完的代码。很多同学的问题不是不努力而是知识点太散、代码和概念对不上复习了两周最后连“带头结点的单链表头插法”和“尾插法”的区别都没完全吃透。我花了不少时间把《数据结构》的知识点重新梳理了一遍把散落在教材、课程PPT、刷题网站里的核心内容压缩成下面这份笔记。它不追求把每一行代码都贴上来而是把“常考常新”的知识点和“真正需要手写出来”的算法代码模板放在一起用“考什么、怎么写、为什么这么写”的思路拆开讲。非常适合期末紧急复习、考研二轮知识梳理、以及面试前快速过一遍底子的朋友直接参考也可以当作随时翻阅的速查手册。1. 整体内容设计与知识点架构拆解1.1 数据结构到底在学什么很多人一开始学数据结构容易陷入“今天学链表、明天学树、后天学图”的局部视角里学完一章忘一章。实际上数据结构的整条主线非常清晰用什么方式把数据组织起来并且在这种组织方式上高效地做增删改查。这句话拆开就是三件事——逻辑结构、存储结构、运算。逻辑结构回答的是“数据之间是什么关系”一共四类线性结构一对一比如链表、栈、队列、树形结构一对多比如二叉树、B树、图形结构多对多比如有向图、无向图以及集合数据之间除了同属一个大集合之外没有其他关系比如哈希表里的桶。存储结构回答的是“这些关系在内存里怎么落地”最常见的就是顺序存储数组、链式存储节点指针、索引存储和散列存储。运算则是每一种结构上要支持的基本操作比如链表的插入删除、树的遍历、图的找最短路径。之所以强调这三层关系是因为很多题目考的就是“同一逻辑结构用不同存储方式实现时的差异”。比如逻辑上都是“栈”用顺序栈实现入栈是s.data[s.top] x用链栈实现入栈是s-next p; p-next s。两种写法的考点完全不同。只有脑子里先搭好“逻辑—存储—运算”这个框架后面的代码才不是死记硬背而是顺着结构自然推出来的。1.2 复习主线与资料搭配思路如果你现在打开一本教材比如严蔚敏的《数据结构C语言版》从头开始一页一页翻效率其实不高。我比较推荐的思路是把复习分成三遍走每遍的侧重点不一样。第一遍按章节顺序过知识点只看概念和示意图搞清楚“这种结构长什么样、解决什么问题”不需要陷入具体代码。第二遍做横向对比把线性表、树、图这三种结构放在一起对比它们的存储方式、遍历方式、时间复杂度和典型应用这一遍是考研“大题”和面试“为什么”的关键。第三遍回到代码模板把每种结构的核心算法手写一遍写到不用看参考答案也能默写出来的程度。资料方面本科教材严蔚敏版、王道版本均可适合打底但代码风格偏教学化《大话数据结构》更适合零基础入门例子多、语言轻松。如果你目标是刷题面试那以LeetCode/HDU上的实战题为主再配合一份整理好的算法模板。我个人建议一定要有一份属于自己的“代码模板库”不是网上抄来的大而全而是自己每写一遍就精简一次的那种考前翻它效率最高。2. 线性结构核心考点与代码实现2.1 顺序表与链表从结构对比到手写细节线性表是数据结构的地基顺序表和链表两种实现方式几乎每个考试和面试都会涉及。先看对比维度顺序表数组链表存储方式逻辑相邻即物理相邻通过指针链接逻辑相邻节点随机访问O(1)直接下标取O(n)需要从头遍历插入删除平均O(n)需要移动元素O(1)指针修改但查找位置是O(n)空间分配静态分配扩容代价高按需分配灵活但每个节点有指针开销适用场景读多写少、需要频繁按位置访问写多读少、长度不确定的场景这个表格就是一道送分题。但真正拉开差距的是代码。链表里我认为最值得反复手写的三个模板是反转单链表、快慢指针找中间节点/判断环、合并两个有序链表。// 反转单链表迭代法核心是三个指针 struct ListNode* reverseList(struct ListNode* head) { struct ListNode *prev NULL, *curr head; while (curr) { struct ListNode *next curr-next; // 先保存下一个节点 curr-next prev; // 当前节点指向前一个完成局部反转 prev curr; // prev移动到当前节点 curr next; // curr移动到原下一个节点 } return prev; }这段代码虽然短但很多人写的时候会忘记保存next导致断链。建议每次默写时都在心里过一遍“三指针接力”的过程先存后指再移动。再补充一个“哨兵节点”技巧在处理链表头节点可能被修改的问题时比如删除指定元素、合并两个表先在头部加一个dummy节点最后返回dummy-next可以省掉大量判断头指针是否为空的逻辑。这个方法我在面试里用过很多次实测非常稳。2.2 栈与队列出题最灵活的“小容器”栈和队列的知识点不多但题型特别杂几乎每个学校期末卷子都少不了它们。栈的特点是后进先出LIFO考法集中在括号匹配、表达式求值、递归转非递归队列的特点是先进先出FIFO考法集中在循环队列、约瑟夫环、树的层序遍历。先说栈。括号匹配是硬题思路就是把左括号入栈遇到右括号时弹出栈顶元素检查是否匹配最后再看栈是否为空。表达式求值有两个层次简单版本是“中缀转后缀”用栈维护运算符优先级复杂版本是直接双栈求值一个栈存数字、一个栈存运算符。递归转非递归的本质其实就是用栈手动模拟系统递归调用栈理解了这一点递归转非递归就不是背模板而是顺着代码逻辑自己搭栈。循环队列是另一个高频考点。核心是理解“牺牲一个存储单元”来区分队空和队满// 循环队列常用判空/判满方式 // 队空条件front rear // 队满条件(rear 1) % MaxSize front // 入队rear (rear 1) % MaxSize; // 出队front (front 1) % MaxSize;这里最容易错的是忘记取模。由于数组下标会“绕回去”每次移动都要% MaxSize否则超过数组上界就访问越界了。考试中经常给一个 MaxSize5 的队列让你模拟入队出队过程并写出 rear、front 的最终值本质上考的就是取模运算和队满判断只要心里有一张“环形数组”的示意图基本不会丢分。2.3 查找与排序手写必考算法与性能对比查找和排序是整个数据结构的“算法重心”也是笔试题的常客。查找部分核心是二分查找虽然代码很短但边界条件极其容易写错。我在实际写题时习惯用“左闭右闭”的写法这样逻辑最清晰// 二分查找左闭右闭写法 int binarySearch(int nums[], int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; // 防溢出写法 if (nums[mid] target) return mid; else if (nums[mid] target) left mid 1; else right mid - 1; } return -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)稳定手写排序里快排和归并是最常要求现场写的。快排的关键在于Partition函数很多面试题还会让你解释“为什么快排平均是 O(n log n)、最坏是 O(n²)”——核心就是基准元素划分的均匀程度。归并排序则要会用“先递归拆分、再合并两个有序数组”的思路通常配合求逆序对问题一起出现难度直接上一个台阶。在这里提醒一点别只背代码一定要能“模拟过程”。比如给一个数组[49, 38, 65, 97, 76]让你写出第一趟快排后的结果。这类题考的就是对指针移动过程的理解而不是代码本身考前可以找几道排序模拟题手动演练几遍。3. 树与图非线性结构重难点突破3.1 二叉树遍历由遍历序列互推一棵树的干货法二叉树是数据结构里“性价比”最高的一章内容多、题量大但规律也非常明显。无论是期末考试还是刷题第一关就是遍历。先序根左右、中序左根右、后序左右根、层序逐层从左到右这四种遍历的递归实现几乎一样区别只是访问时机不同一定要做到“闭着眼睛也能写出来”。非递归遍历看起来复杂但本质是用栈模拟递归过程。先序和中序的非递归写法非常接近只是访问节点的时机不同后序最麻烦常见做法是额外记录“上次访问的节点”或者用双栈技巧。层序遍历需要借助队列每趟先记录当前队列长度再处理这一层的节点配合一个level数组就能自然地实现树的层次输出。另一个高频题型是“由先序中序 / 后序中序构造唯一二叉树”。核心依据是先序/后序确定根节点中序划分左子树和右子树。比如先序第一个元素一定是根在中序里找到这个根它左边的子序列是左子树的中序右边是右子树的中序再回到先序序列按照左右子树长度切分递归进行。关于这类题我的建议是别只看答案一定自己画一遍推导过程因为面试时画图和文字推导比写代码更能体现理解深度。3.2 二叉搜索树与堆有序性的两种不同玩法二叉搜索树BST的规则很简单左子树所有节点值小于根右子树所有节点值大于根。它最大的特性是中序遍历结果是有序序列这个结论可以秒杀很多题目。比如“验证一棵二叉树是否是 BST”最简单的做法就是中序遍历检查序列是否严格递增。BST 的删除操作是重点分三种情况叶子节点直接删只有一个孩子就让孩子顶上来有两个孩子就用右子树的最小节点或左子树的最大节点替换被删节点再删除那个替身节点。堆和 BST 虽然都是树形结构但组织逻辑完全不同。堆只要求父节点和孩子节点满足大小关系不要求左右子树之间有严格的顺序约束。正因为这个“半有序”特性堆可以在 O(1) 时间找到最大值/最小值特别适合实现优先队列和堆排序。堆的核心操作是“上浮”和“下沉”// 向下调整以大顶堆为例 void siftDown(int arr[], int n, int i) { int largest i; int left 2 * i 1, right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { swap(arr[i], arr[largest]); siftDown(arr, n, largest); } }堆排序的建堆、调整、排序三步本质上就是在反复做“下沉”操作。需要注意堆排序不稳定这一点在选择题里经常出现。3.3 图存储、遍历与最短路径全搞定图这一章的内容量很大但考法相对固定。存储结构首选邻接矩阵和邻接表前者适合稠密图判断两点是否相邻的时间为 O(1)但空间是 O(n²)后者适合稀疏图遍历某个顶点的所有邻居更高效但查询两点是否相邻需要遍历链表。图遍历的核心框架是 DFS 和 BFS。一定要掌握“visited 数组”标记已访问节点否则会陷入死循环。DFS 常常配合回溯思想使用而 BFS 天然适合求无权图的最短路径层数就是步数。最短路径环节Dijkstra 算法是重中之重。它的思想是贪心每次从未确定的节点中找当前距离最小的节点然后松弛它的所有邻居。朴素实现是 O(V²)优化后可以用小顶堆维护“当前距离最小的节点”复杂度降到 O((VE) log V)。Floyd 算法适合多源最短路径三重循环的代码非常短但要注意最外层循环的是中间节点 k。最小生成树里Prim 适合稠密图Kruskal 适合稀疏图且结合了并查集思想。拓扑排序则专门解决有向无环图的应用场景。图这部分内容逻辑性很强我建议每学完一个算法就找一个可视化工具看一遍动态过程比如 Dijkstra 的“逐层扩散”和 Kruskal 的“不断加边”看几次之后代码就不是背出来的而是自然而然写出来的。4. 哈希、串与常见算法范式串联4.1 哈希表构造、冲突处理和装填因子哈希表之所以能在 O(1) 平均时间内完成查找核心是把元素的关键字通过哈希函数直接映射到存储地址。理解哈希表的重点不在“怎么存”而在“冲突了怎么办”。常用的冲突处理方法有开放定址法和链地址法。开放定址法里线性探测法冲突了就往后找空位最简单但容易产生聚集平方探测法可以缓解聚集再哈希法需要准备多个哈希函数。链地址法把同义词放在同一个链表中简单直观在工程和考试中都非常常见。装填因子 α 表中记录数 / 表长α 越大表示表越满、冲突概率越高。线性探测法查找成功的平均查找长度约为 (1 1/(1-α))/2这个公式在很多教材里都会出现建议理解推导过程而不是死记。哈希表的实际应用非常广统计词频、去重、缓存 LRU、布隆过滤器底层都离不开哈希的思维。面试里更容易出现的是“手写一个简易哈希表”要求实现插入、删除、查找三个操作这时候链地址法最好写直接用“数组 链表”的结构数组下标是哈希后的结果链表节点存放键值对。代码模板可以参考typedef struct Node { int key; int val; struct Node *next; } Node; #define SIZE 10007 Node* buckets[SIZE]; // 全局数组每个位置是一条链 int hash(int key) { return (key % SIZE SIZE) % SIZE; } void put(int key, int val) { int idx hash(key); Node *cur buckets[idx]; while (cur) { if (cur-key key) { cur-val val; return; } cur cur-next; } Node *newNode (Node*)malloc(sizeof(Node)); newNode-key key; newNode-val val; newNode-next buckets[idx]; buckets[idx] newNode; // 头插法 }4.2 分治、回溯、贪心、动态规划四大算法模板串讲很多资料会把“算法设计”单独列一章但从实际考试和面试来看常考的无非是四大模板。分治法的核心是“分解—解决—合并”典型代表是归并排序、快速排序和最近点对问题。回溯法本质是 DFS 状态恢复求解排列、组合、子集问题时尤其好用。一个通用模板是做出选择、递归进入下一层、撤销选择。贪心算法则是在每一步都做当前看起来最优的选择难点不是写代码而是证明局部最优能推出全局最优典型题目有活动安排、哈夫曼编码、Prim/Kruskal。动态规划是很多人的心头痛但其实只要抓住几步就不会乱定义状态、确定状态转移方程、初始化、确定遍历顺序。以 0-1 背包为例状态dp[i][j]表示前 i 个物品放入容量为 j 的背包的最大价值状态转移方程是dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])含义就是“不放第 i 个”和“放第 i 个”两种决策取最大值。代码实现时要用滚动数组压缩空间压缩后内层循环必须倒序遍历这一点很容易漏一旦写错结果就是错的。还有一个容易被忽略但十分重要的模板是并查集它虽然不是“算法设计”章节的常客但几乎已经成为面试和算法竞赛的基础工具。核心就两个操作查找根节点带路径压缩和合并两个集合按秩合并。代码非常短但能解决大量与集合归属有关的问题。4.3 算法代码管理从会写到能手写的基本习惯如果说上面的知识点是“学什么”那这一小节想聊的是“怎么写”。我在辅导学生和带新人时发现很多朋友看答案都懂但一合上书就写不出来问题往往出在“从来没有把代码当作品来管理”。第一点是坚持手写而不是只复制粘贴。写算法题时先自己在纸上画思路、写核心代码再对照参考代码查漏第二是建立一份自己的代码模板库按“数据结构名称—核心操作—边界条件”的方式归档。比如链表常考模板放一个文件树的遍历模板放一个文件以后复习时直接翻自己的模板比翻书快得多第三是写注释时不要解释“这句代码在做什么”而要写“为什么要这样做”。比如mid left (right - left) / 2旁边可以注明“防止 leftright 溢出”下一次自己看时就能快速抓住重点。代码管理还有一个很实用的技巧为每种模板写一个“最小可运行示例”里面只包含一个 main 函数和一组现成测试数据。这样面试或考试前想快速验证某个模板是否记得对直接跑一遍就行不用临时去拼数据构造。5. 高频题型速查 实战避坑经验5.1 考研/期末常见题型与高频考点结合近几年的考试风格我整理了下面这些最常考的题型建议大家每一条都能做到“看到就能想到解题方向”。题型核心考点解题提示时间复杂度计算循环嵌套、递归方程识别循环执行次数用主定理或展开法线性表综合题逆置、删除重复元素、合并有序表优先考虑双指针/哨兵节点树的遍历序列互推由先序/后序 中序构造树中序划分左右子树先/后序确定根哈夫曼树构建最小堆合并、WPL计算每次取两个最小节点画树后计算带权路径长度图的深度/广度遍历序列visited数组变化过程顺序遍历注意候选邻接点的访问先后最短路径模拟Dijkstra每轮更新过程画表格记录dist数组和已确定集合排序过程模拟快排/堆排/归并第一趟结果手动模拟指针移动或堆调整过程哈希表构造冲突次数、ASL计算根据哈希函数和冲突处理方式逐元素填入5.2 面试高频题与解题套路如果是为面试准备题型会更偏向“代码落地 思路沟通”。链表环检测Floyd判圈算法几乎是必考题核心思路就是一个快指针每次走两步、一个慢指针每次走一步如果链表有环两者必定相遇二叉搜索树转有序双向链表本质上就是中序遍历遍历到每个节点时把当前节点和前驱节点互相链接“前K个高频元素”考验的是哈希统计 小顶堆堆的大小保持为 K堆顶就是当前第 K 高频的元素手写快排或堆排则考察基本功是否扎实。还有一个高频场景是“从输入规模反推算法复杂度”。面试官经常给一个数据范围比如“n 10^5”让你决定应该用 O(n log n) 还是 O(n²) 的算法。这个判断其实有规律n 在 10^5 量级时O(n log n) 是安全的O(n²) 基本会超时n 在几千量级时 O(n²) 勉强可行如果 n 是 10^9 级别那大概率要想到数学公式、二分或者 O(n) 的线性解法。5.3 常见错误与避坑技巧汇总最后把这些年积累的“踩坑经验”集中整理一下希望大家少走弯路。数组越界是手写代码里最高频的错误尤其是循环里用到i1、i-1、rear1时一定要检查边界条件。递归算法一定要想清楚“递归出口”否则栈溢出。树形结构的递归出口通常是if (!root) return ...。链表操作中修改节点 next 指针的顺序非常重要。先断开、再连接连接时如果覆盖了原节点地址就会导致断链。快排的最坏情况是每次划分都把基准选到最大或最小元素上解决思路是“三数取中”或者随机选择基准。哈希表用链地址法时头插法虽然代码简洁但会改变同义词链表的顺序如果题目要求输出链表的顺序一定要看清是头插还是尾插。堆排序、希尔排序、选择排序都不稳定只有插入排序、冒泡排序、归并排序是稳定的这个点在选择题里的出现频率高到令人发指。Dijkstra 算法不能处理带负权边的图遇到负权图要想到 Bellman-Ford 或 SPFA这也是很多题目故意设置的陷阱。动态规划压缩空间后内层循环的遍历方向要仔细分析0-1背包倒序是为了保证每个物品只用一次完全背包正序则是允许物品重复使用这两个写法几乎每年都有人搞混。我个人在实际操作中的体会是数据结构这门课最大的难点不是某个具体的算法而是知识之间的网状联系。链表、栈、队列、树、图看起来是五座分开的山但爬上去之后会发现它们之间有很多隧道——树的层序遍历要用队列图的 DFS 可以看作二叉树的先序遍历推广并查集本质上是森林哈希表的扩容思想又和动态数组相似。把这些联系打通之后复习效率会发生质的飞跃。最后再分享一个小技巧考前冲刺阶段不要再看“厚书”也不要再刷“新题”把你自己整理的数据结构模板库从头到尾手写一遍。写完一个合上手机试着用 30 秒把它的时间复杂度和适用场景讲给自己听。这个过程坚持三天上考场或者面试时你会发现自己对知识点的掌控感完全不同很多东西即使忘了细节也能顺着那套“逻辑—存储—运算”的框架迅速推理出来。数据结构这些东西说到底不是靠背的是靠“理顺关系”来拿分的。