先说明一下背景。数据结构这门课，几乎是计算机专业所有学生都躲不开的一座山，不管是期末突击、考研二战，还是秋招面试前临时抱佛脚，“数据结构 + 算法代码”这两个词一出现，就意味着背不完的定义、画不完的图、写不完的代码。很多同学的问题不是不努力，而是知识点太散、代码和概念对不上，复习了两周，最后连“带头结点的单链表头插法”和“尾插法”的区别都没完全吃透。
我花了不少时间把《数据结构》的知识点重新梳理了一遍，把散落在教材、课程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，否则超过数组上界就访问越界了。考试中经常给一个 MaxSize=5 的队列，让你模拟入队出队过程并写出 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((V+E) 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旁边可以注明“防止 left+right 溢出”，下一次自己看时就能快速抓住重点。
代码管理还有一个很实用的技巧：为每种模板写一个“最小可运行示例”，里面只包含一个 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 常见错误与避坑技巧汇总
最后把这些年积累的“踩坑经验”集中整理一下，希望大家少走弯路。
- 数组越界是手写代码里最高频的错误，尤其是循环里用到
i+1、i-1、rear+1时，一定要检查边界条件。 - 递归算法一定要想清楚“递归出口”，否则栈溢出。树形结构的递归出口通常是
if (!root) return ...。 - 链表操作中，修改节点 next 指针的顺序非常重要。先断开、再连接，连接时如果覆盖了原节点地址，就会导致断链。
- 快排的最坏情况是每次划分都把基准选到最大或最小元素上，解决思路是“三数取中”或者随机选择基准。
- 哈希表用链地址法时，头插法虽然代码简洁，但会改变同义词链表的顺序；如果题目要求输出链表的顺序，一定要看清是头插还是尾插。
- 堆排序、希尔排序、选择排序都不稳定，只有插入排序、冒泡排序、归并排序是稳定的，这个点在选择题里的出现频率高到令人发指。
- Dijkstra 算法不能处理带负权边的图，遇到负权图要想到 Bellman-Ford 或 SPFA，这也是很多题目故意设置的陷阱。
- 动态规划压缩空间后，内层循环的遍历方向要仔细分析：0-1背包倒序是为了保证每个物品只用一次，完全背包正序则是允许物品重复使用，这两个写法几乎每年都有人搞混。
我个人在实际操作中的体会是：数据结构这门课，最大的难点不是某个具体的算法，而是知识之间的网状联系。链表、栈、队列、树、图看起来是五座分开的山，但爬上去之后会发现它们之间有很多隧道——树的层序遍历要用队列，图的 DFS 可以看作二叉树的先序遍历推广，并查集本质上是森林，哈希表的扩容思想又和动态数组相似。把这些联系打通之后，复习效率会发生质的飞跃。
最后再分享一个小技巧：考前冲刺阶段，不要再看“厚书”，也不要再刷“新题”，把你自己整理的数据结构模板库从头到尾手写一遍。写完一个，合上手机，试着用 30 秒把它的时间复杂度和适用场景讲给自己听。这个过程坚持三天，上考场或者面试时你会发现自己对知识点的掌控感完全不同，很多东西即使忘了细节，也能顺着那套“逻辑—存储—运算”的框架迅速推理出来。数据结构这些东西，说到底不是靠背的，是靠“理顺关系”来拿分的。
