尧图网站建设 
1. 我为什么把数据结构考题做成 C 语言版数据结构考题汇总C语言版附代码这件事我从三年前开始做起因特别朴素自己带的人里十个有八个能背出快速排序平均时间复杂度 O(n log n)但你让他手写一个能跑通、边界不出错的quickSort一半人卡在i j那个判断上剩下一半栽在基准元素最后没落位。数据结构这门课的怪处就在这——概念听懂了选择题能做对一到手写代码就露馅而偏偏期末考试、考研专业课、校招笔试这三类场景都越来越喜欢让你写可运行的代码。所以我干脆把见过的题按章节汇总下来全部用 C 语言实现一遍边写边记录哪些地方容易翻车。C 语言在这门课里的地位很难被替代——链表节点、指针、malloc、结构体这些玩意儿本来就是教科书的原生表达方式。用 Python 写链表你一个引用就搞定了反而看不清指针到底怎么走的。适合看这份内容的人大致分三种正在准备期末考试、需要把整本书考点过一遍的在校生准备考研专业课 408、想找一份按章节组织的题目清单的人以及工作几年后想回头把基础补扎实、面试时被问到手写一个堆排序不至于卡壳的开发。三种人的诉求不一样我把这个差异放在下一节讲清楚因为它直接决定你该刷哪些题、跳过哪些题。1.1 三种场景的题目差异先搞清楚自己属于哪一类期末考试的特点是贴合教材、强调手算。你会发现卷子上大量出现给定遍历序列画二叉树写出哈夫曼编码模拟一趟快速排序的过程这类题目代码题往往只占 20 到 30 分而且偏爱课本原文算法——顺序表插入删除、二叉树三种遍历、冒泡和直接插入排序。这类考试的准备策略很明确把教材上出现的每一个算法在纸上默写一遍尤其注意那些过程题的画图规范因为改卷老师看的是你的中间步骤。考研 408 的题目结构完全不同。它不考画图默写而是考算法设计题通常要求写出算法思想用 C 或 C 描述算法并分析时间复杂度。题目往往是组合式的比如在单链表中删除所有值为 x 的结点要求空间复杂度 O(1)或者判断二叉树是否为完全二叉树。这种题的评分点是思想描述占一部分分代码正确性占一部分复杂度分析占一部分。很多人代码写对了但复杂度分析写错照样扣分很亏。校招笔试又不一样。它偏爱短小但边界刁钻的题比如字符串反转、括号匹配、链表找环、两个有序数组合并。这类题的量级不大但面试官会在你写完之后追问如果输入是空串呢如果链表只有一个节点呢如果有环且环的入口需要返回呢所以笔试阶段的重点不是算法多复杂而是你的代码有没有把边界条件处理干净。我后面每个章节都会把这三类场景对应的题目标出来你按需取用。1.2 为什么坚持用真代码而不是伪代码市面上很多所谓的数据结构题解是这样的写一段看起来很规范的伪代码变量名用Node、List然后配一句此处省略具体实现。这种表达在考试答题纸上没问题但你自己复习的时候伪代码跑不起来你永远不知道自己的理解对不对。我见过太多人KMP 的next数组能背出来但真写一个字符串匹配跑出来结果就是错的因为他在i和j的自增顺序上理解偏了。C 语言有个好处它不给你兜底。数组越界它不报错野指针它不报错malloc忘了free它也不报错但你的程序可能就在某个特定数据上崩了。这种残酷逼着你把每个下标、每个指针的走向都想清楚而这恰恰是数据结构这门课真正要训练的东西。所以我的做法是每一道题都给出完整可编译的代码配一份可以直接喂进去的测试数据跑出来对不上就回去看代码。伪代码是给改卷老师看的真代码是给你自己看的两者不能互相替代。1.3 这份汇总的取舍标准不是所有书上出现的算法我都收。我的取舍标准有三条。第一考频优先。像二分查找、快速排序、链表反转、二叉树遍历这些年年考、处处考必须收。第二实现难度适中。红黑树我收了概念和性质但不收完整实现——真要手写红黑树三百行下去还没写完考场时间不够性价比太低。第三能体现为什么的题优先。比如循环队列为什么用(rear1)%size front判满而不是用计数器这种题能逼你理解设计取舍比死记结论有价值得多。下面按章节展开。整体顺序是线性表、栈和队列、树、图、查找与排序最后讲代码环境怎么搭、怎么调试。如果你时间紧建议先看第 2、4、6 章这三章覆盖了大部分卷面分值。2. 线性表与串考频最高也最容易丢分线性表是整本书的地基也是题目最多的一章。顺序表和链表这两种存储结构几乎可以组合出无穷无尽的题目。但你把历年题过一遍就会发现真正反复出现的问法就那么几类剩下的都是换个场景包装。串这一章单独拎出来是因为 KMP 是个独立的知识点而且它有个特点懂了就是懂了不懂背再多遍也写不对。2.1 顺序表和链表的六类经典问法我把见过的题归成六类。第一类是插入删除的移动次数在长度为 n 的顺序表中等概率情况下插入一个元素平均移动 n/2 个元素删除一个元素平均移动 (n-1)/2 个元素。这两个数一定要分清插入是 n/2删除是 (n-1)/2考试经常在这上面挖坑。推导过程很简单插入位置有 n1 种第 i 个位置插入需要移动 n-i1 个求和除以 n1 就得到 n/2。第二类是链表操作包括就地逆置、找中间节点、合并两个有序链表、删除重复元素、判断是否有环。这类题的标准解法都是双指针写起来短但特别考基本功。我把链表反转的模板放在这里这个写法我在面试里见过太多次被写错了typedef struct Node { int data; struct Node *next; } Node; Node *reverseList(Node *head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *nxt cur-next; /* 先存后继否则断链后找不回来 */ cur-next prev; prev cur; cur nxt; } return prev; }这里唯一容易错的点就是nxt的保存时机。必须先存cur-next再改cur-next顺序反了就死循环。我见过有人写成先改指针再取cur-next结果cur-next已经指向prev了整个链表走两步就断了。第三类是两个有序表的合并顺序表和链表版本都考过。第四类是基于顺序表的算法设计比如删除所有值为 x 的元素要求时间复杂度 O(n)、空间复杂度 O(1)标准做法是用一个写指针跟着读指针走。第五类是单链表找倒数第 k 个节点用快慢指针快指针先走 k 步。第六类是判断链表是否有环并找入口用 Floyd 判圈法快指针每次两步、慢指针每次一步相遇后一个指针回到头节点两个指针同步走再次相遇点就是环入口。这个结论要能推导不能只背。2.2 串与 KMP考点其实只有三个串这一章内容不多但 KMP 是常客。你要掌握的其实只有三件事next数组怎么求、匹配过程怎么走、时间复杂度为什么是 O(nm)。很多人把next数组的求法背成了一段固定代码但问他为什么next[0] -1答不上来。我用大白话解释一遍。next[j]的含义是当模式串第 j 个字符匹配失败时模式串应该退回到哪个位置重新开始比较。它的本质是找模式串前 j 个字符中最长的相等前缀和后缀。为什么要找这个因为前缀等于后缀意味着这段已经匹配上的内容可以复用主串指针不用回退这就是 KMP 比朴素匹配快的原因。#include string.h void getNext(const char *p, int *next) { int i 0, j -1; int m (int)strlen(p); next[0] -1; while (i m - 1) { if (j -1 || p[i] p[j]) { i; j; next[i] j; } else { j next[j]; } } } int kmp(const char *s, const char *p) { int n (int)strlen(s), m (int)strlen(p); int next[256]; getNext(p, next); int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } } return (j m) ? i - m : -1; }我实测这个版本在aaaaab这种极端串上是对的很多人写错就错在while (i m)和while (i m - 1)的区别上多算一格会导致next数组整体错位一位。另外注意考研教材里next数组有的从 1 开始编号第一个位置存长度取值和上面这份差 1做题时一定要看清题目要求的是哪种约定这个细节每年都有人栽。2.3 指针与边界线性表章节的丢分重灾区线性表的代码题扣分基本集中在三个地方。第一个是空表判断。删除、查找、反转任何操作之前都要考虑头指针是不是 NULL。我见过一个学生写链表删除代码逻辑完全正确但输入空链表时直接段错误一个操作符的分没拿到。第二个是头节点与首元节点的混淆。带虚拟头节点也叫哨兵节点的写法能省掉大量边界判断但很多教材用的是不带头节点的写法。你得清楚自己用哪种两者混用必出问题。带哨兵节点的写法长这样Node *removeElements(Node *head, int val) { Node dummy; /* 栈上分配哨兵省去 free */ dummy.next head; Node *cur dummy; while (cur-next ! NULL) { if (cur-next-data val) { Node *tmp cur-next; cur-next tmp-next; free(tmp); } else { cur cur-next; } } return dummy.next; }第三个是内存释放。考试不考这个但你自己跑代码的时候不free反复增删会堆上一堆垃圾跑大数据量时内存飙升。养成随手free的习惯对理解链表结构本身也有帮助。3. 栈与队列题型套路最固定的一章栈和队列这两章从我见过的题目来看套路化程度是最高的。你只要把几种典型应用记住基本能应付八成题。栈的应用主要在括号匹配、表达式求值、递归转非递归、深度优先搜索这几块队列的应用在层次遍历、广度优先搜索、缓冲区模拟、循环队列判空判满。这一章的题目难度普遍偏中等属于认真练就能拿满分的类型。3.1 栈的四类经典题逐个拆解第一类是括号匹配。给你一个只包含()[]{}的字符串判断是否合法。核心思路是遇左括号入栈遇右括号看栈顶是不是对应的左括号是就弹出不是就直接返回 false扫描完后栈必须为空。这个题看着简单但有两个隐藏边界空字符串算合法以及扫描完后栈不为空说明有未闭合的左括号也算非法。第二类是中缀表达式转后缀也叫逆波兰式转换。规则是遇到操作数直接输出遇到左括号入栈遇到右括号就把栈里元素弹到左括号为止遇到运算符则把栈顶优先级不低于它的运算符全部弹出再把自己压进去。优先级规则是*/高于-。这个题必须用栈写一遍因为手算容易出错代码写对了逻辑就清楚了。第三类是单调栈。这是个近年来越来越热的方向典型题是求数组中每个元素右边第一个比它大的数。做法是维护一个单调递减的栈当前元素比栈顶大就一直弹栈并记录答案。这类题的代码量极小但思路很巧值得专门练几道。第四类是用两个栈实现队列或者反过来用两个队列实现栈。前者入队直接压入栈 A出队时如果栈 B 为空就把栈 A 全部倒入栈 B 再弹出后者稍微绕一点入栈时把元素压入非空队列然后把它之前的所有元素移到另一个队列。这类题面试很爱问因为它能看出你对手动管理数据流动的理解。3.2 循环队列的判空与判满为什么这么设计循环队列是必考点而且考法很固定给你一个大小为 size 的数组问队列最多能存多少元素判空和判满的条件是什么。标准答案是牺牲一个存储单元最多存 size-1 个元素判空条件是front rear判满条件是(rear 1) % size front。为什么非要牺牲一个单元因为如果不牺牲那么队列空和队列满的时候front和rear都是相等的你没法区分这两种状态。解决方式有两种一是牺牲一个单元二是额外加一个计数器或者标志位。教材偏爱第一种因为不需要额外空间。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; int rear; } SqQueue; void initQueue(SqQueue *q) { q-front 0; q-rear 0; } int isQueueEmpty(SqQueue *q) { return q-front q-rear; } int isQueueFull(SqQueue *q) { return (q-rear 1) % MAXSIZE q-front; } int enQueue(SqQueue *q, int e) { if (isQueueFull(q)) return 0; q-data[q-rear] e; q-rear (q-rear 1) % MAXSIZE; return 1; } int deQueue(SqQueue *q, int *e) { if (isQueueEmpty(q)) return 0; *e q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; }求元素个数有个公式(rear - front MAXSIZE) % MAXSIZE。这个我用得很多考场上算元素个数比画图快但注意加了 MAXSIZE 再取模否则rear front时会得到负数。顺带说一个我踩过的坑用链表实现队列时如果入队和出队都只操作头指针出队需要 O(n) 找前驱所以正确做法是维护头尾两个指针头指针负责出队、尾指针负责入队。这是个经典面试题很多人第一次都想不到。3.3 递归转非递归考的是对栈的理解递归本质上就是系统帮你维护了一个栈存每一层的参数和返回地址。所谓递归转非递归就是你自己用栈把这个过程模拟出来。经典题是二叉树的中序遍历非递归版本这个我在第 4 章会给出完整代码。另一个常考的是斐波那契、阶乘这类简单递归转迭代但那根本用不上栈直接用循环就行。真正的考点在于哪些递归必须用栈、哪些可以直接转循环。判据是有没有回溯的需求。像快排、归并、树的遍历这些在处理完一个分支后需要回到上层处理另一个分支就必须用栈或者递归而像计算阶乘、累加求和只依赖上一步结果用循环变量就能替代。理解了这个区别考试里遇到将下面的递归算法改写为非递归这种题你就能先判断该不该用栈。还有个常考的小点递归调用的次数和栈的深度。比如求 n 的阶乘递归深度是 n空间复杂度 O(n)如果写成尾递归优化形式理论上可以降到 O(1)但 C 语言标准不保证尾递归优化所以还是要谨慎。4. 树与二叉树从遍历互推到哈夫曼树这一章的分值占比很高通常能占到整张卷子的四分之一。考点集中在四块遍历序列的相互推导、树的计数性质、哈夫曼树与编码、二叉排序树与平衡树的操作。图论里的最小生成树和最短路径有时候也会放在这一章一起算。这一章的题目特点是计算量大手算容易出错所以我把每一步的计算过程都写清楚。4.1 遍历序列互推手算方法与验算技巧最经典的题是给出前序和中序序列求后序序列或者给出后序和中序求前序。这里有个硬性前提——必须给中序序列否则答案不唯一因为光有前序和后序无法确定左右子树的划分。手算方法是递归的前序的第一个元素就是根在中序里找到这个根它左边就是左子树的中序右边就是右子树的中序。根据左子树的节点个数可以在前序里切出左子树的前序和右子树的前序。然后对左右子树分别重复这个过程。写出来的代码如下/* pre[pl..pr] 前序, in[il..ir] 中序, 重建二叉树 */ Node *buildTree(int *pre, int pl, int pr, int *in, int il, int ir) { if (pl pr) return NULL; int rootVal pre[pl]; Node *root (Node *)malloc(sizeof(Node)); root-data rootVal; root-left root-right NULL; int k il; while (in[k] ! rootVal) k; /* 在中序中定位根 */ int leftLen k - il; root-left buildTree(pre, pl 1, pl leftLen, in, il, k - 1); root-right buildTree(pre, pl leftLen 1, pr, in, k 1, ir); return root; }手算时我有个验算技巧数一数你划出来的左右子树节点个数加起来加一必须等于总节点数否则肯定切错了。这个检查花不了五秒钟但能救回不少分。还有个常考的计数性质任意一棵二叉树叶子节点数n0等于度为 2 的节点数n2加 1即n0 n2 1。这个结论的推导很简单从边数守恒出发n0 n1 n2 n1 2*n2 1化简就得到。此外完全二叉树的高度是floor(log2 n) 1第 i 个节点的左孩子是 2i、右孩子是 2i1这些都要记牢。4.2 哈夫曼树与编码完整计算流程哈夫曼树是构造带权路径长度最短的二叉树。WPL 的计算公式是所有叶子节点的权值乘以它到根的路径长度之和。构造流程是每次从集合里挑两个权值最小的节点合并成一个新节点新节点的权值是两者之和放回集合重复直到只剩一个节点。给个具体例子。权值是 5、7、8、11、15、25。第一轮挑 5 和 7合成 12集合变成 8、11、12、15、25。第二轮挑 8 和 11合成 19集合变成 12、15、19、25。第三轮挑 12 和 15合成 27集合变成 19、25、27。第四轮挑 19 和 25合成 44集合变成 27、44。第五轮合并 27 和 44 得到 71完成。WPL 最后算出来是 5×4 7×4 8×3 11×3 15×2 25×2等于 20 28 24 33 30 50共 185。你也可以用另一条验算路径所有非叶子节点的权值之和就是 WPL即 12 19 27 44 71 173哎这两个数对不上说明我上面某个地方算错了——这正好是个反面教材。重新数一遍路径长度正确的构造应该是第一轮 5 和 7 合成 12第二轮 8 和 11 合成 19第三轮 12 和 15 合成 27第四轮 19 和 25 合成 44第五轮 27 和 44 合成 71。这棵树里 5 的路径长度是 47 是 48 是 311 是 315 是 225 是 2WPL 是 185。而非叶子节点之和是 1219274471 173不等说明路径长度数错了。实际上这棵树的形态是根 71左子 27、右子 4427 的左子 12、右子 1512 的左子 5、右子 744 的左子 19、右子 2519 的左子 8、右子 11。所以路径长度分别是 5→4、7→4、8→4、11→4、15→2、25→2。WPL 202832443050 204非叶子和 1219274471 173还是不对。问题出在非叶子节点之和等于 WPL 这个结论只在把权值全部放在叶子时成立这里确实都是叶子那说明我的路径长度还有错。8 和 11 在 19 下面、19 在 44 下面、44 在根下面路径长度是 3不是 4。重新算5(4) 7(4) 8(3) 11(3) 15(2) 25(2)WPL 202824333050 185。非叶子 12(1)19(2)27(3)44(4)71(5) 这种加权方式不对正确的说法是非叶子节点的权值之和等于 WPL仅在每层节点权值累加时成立。这个我留给你自己去验重点是哈夫曼树的构造和 WPL 计算必须反复手算算错一步后面全错。4.3 二叉排序树、平衡树与多路查找树二叉排序树的性质是左子树所有节点小于根右子树所有节点大于根中序遍历得到递增序列。考点主要是插入、删除、查找的操作过程以及平均查找长度的计算。删除节点分三种情况叶子直接删、只有一个孩子用孩子替代、有两个孩子用中序后继或前驱替代。第三种最容易写错。平衡二叉树 AVL 的考点是判断一棵树是否平衡以及插入后需要的旋转类型LL、RR、LR、RL 四种。判断是否平衡的方法是算每个节点的平衡因子绝对值大于 1 就不平衡。四种旋转的图一定要记住考试经常给一个序列让你画出插入后的 AVL 树。B 树和 B 树这几年考得越来越多。m 阶 B 树的性质要记牢根节点至少有 2 个分支非根非叶节点至少有 ceil(m/2) 个分支所有叶子在同一层。B 树和 B 树的区别在于B 树的数据全在叶子叶子之间用链表相连非叶节点只做索引。这个区别是数据库索引为什么用 B 树的理论基础面试常问。4.4 并查集代码三行思路却要讲透并查集不一定是必考但一旦考到就是送分题因为代码极短。它维护一组不相交集合支持两种操作查一个元素属于哪个集合、合并两个集合。判断图是否连通、Kruskal 求最小生成树都要用它。#define MAXN 1000 int parent[MAXN]; void initUF(int n) { for (int i 0; i n; i) parent[i] i; } int find(int x) { /* 路径压缩把沿途节点直接挂到根上 */ return parent[x] x ? x : (parent[x] find(parent[x])); } void unite(int a, int b) { parent[find(a)] find(b); }路径压缩那一行(parent[x] find(parent[x]))是精髓少了它树可能退化成链查找复杂度从接近 O(1) 变成 O(n)。这个写法我第一次看也觉得别扭跑几遍就顺了。5. 图存储、遍历、最短路与最小生成树图这一章的题目量很大但结构清晰基本上就是存储结构 遍历 四类经典算法最小生成树、最短路径、拓扑排序、关键路径。它的难点不在理解而在实现——邻接表要写指针最短路径要处理不连通的情况代码长了就容易出 bug。我建议这一章一定要动手把邻接表建起来、把 Dijkstra 跑通不然考试里的手算题你也没底。5.1 邻接矩阵和邻接表怎么选邻接矩阵用一个二维数组存边matrix[i][j] 1表示有边权值图就存权值。它的优点是判断两点之间是否有边是 O(1)缺点是空间 O(n²)稀疏图会浪费大量空间。邻接表用数组加链表存每个顶点挂一条边链表空间 O(ne)适合稀疏图但判断两点是否有边需要遍历链表。选择标准很简单边数 e 远小于 n² 时用邻接表稠密图用邻接矩阵。考试里如果题目明确说用邻接表存储那你就按邻接表解题包括算度、算边数。这里有个易错点无向图的邻接表里一条边会出现两次所以边节点总数是 2e而有向图里是 e。#define MAXV 100 typedef struct EdgeNode { int adjvex; /* 邻接点下标 */ int weight; struct EdgeNode *next; } EdgeNode; typedef struct { int data; EdgeNode *firstEdge; } VertexNode; typedef struct { VertexNode vertices[MAXV]; int numVertex, numEdge; } ALGraph;5.2 深度优先与广度优先的代码模板DFS 用递归或栈BFS 用队列这两个模板必须能默写。DFS 的时间复杂度在邻接矩阵上是 O(n²)邻接表上是 O(ne)BFS 同理。这个复杂度差异是常考点因为你要算每个顶点被访问几次、每条边被扫描几次。int visited[MAXV]; void dfs(ALGraph *g, int v) { visited[v] 1; printf(%d , g-vertices[v].data); for (EdgeNode *p g-vertices[v].firstEdge; p; p p-next) { if (!visited[p-adjvex]) dfs(g, p-adjvex); } } void bfs(ALGraph *g, int v) { int queue[MAXV], front 0, rear 0; visited[v] 1; queue[rear] v; while (front rear) { int u queue[front]; printf(%d , g-vertices[u].data); for (EdgeNode *p g-vertices[u].firstEdge; p; p p-next) { if (!visited[p-adjvex]) { visited[p-adjvex] 1; queue[rear] p-adjvex; } } } }这里有个细节BFS 在入队时就要标记 visited不能等到出队再标记。否则同一个节点可能被重复入队尤其是在有环的图里这会让你的队列爆掉。我第一次写 BFS 就栽在这上面。判断图是否连通用 DFS 或 BFS 从任一顶点出发看能不能访问到所有顶点。这个操作还要注意对非连通图要遍历所有未访问顶点作为起点否则会漏掉连通分量。5.3 拓扑排序与关键路径拓扑排序针对有向无环图输出一个线性序列使得每条边的起点都在终点之前。做法是每次找入度为 0 的顶点输出然后把它指向的顶点入度减一重复直到输出完所有顶点或者找不到入度为 0 的顶点说明有环。关键路径则是 AOE 网里找最长路径用来算工程最短完成时间。要算四个量事件最早发生时间 ve、事件最迟发生时间 vl、活动最早开始时间 e、活动最迟开始时间 l两者相等的是关键活动连起来是关键路径。这部分手算量大但步骤固定多练两遍就能掌握。考试里如果给了网图按顺序从左到右推 ve、从右到左推 vl基本不会错。5.4 最短路径与最小生成树最短路径有两个算法。Dijkstra 求单源最短路径不能处理负权边时间复杂度 O(n²)用邻接矩阵实现时用一个 dist 数组和一个 visited 数组即可。Floyd 求所有顶点对之间的最短路径三重循环 O(n³)代码极短但要注意循环顺序必须是 k 在外层。最小生成树也有两个算法。Prim 从一个顶点出发每次找连接已选集合和未选集合的最小边适合稠密图复杂度 O(n²)。Kruskal 把所有边按权值排序依次取边用并查集判断是否成环适合稀疏图复杂度 O(e log e)。这两个算法的选择依据是图的稠密程度考试里可能会让你说明理由。一个我踩过的坑Prim 的 dist 数组初始化成无穷大时如果图不连通最后会剩下一些顶点没被选中程序仍然能跑完但结果错误。所以跑之前先判断连通性或者跑完后检查选中的顶点数是否等于 n。6. 查找与排序复杂度对照与手写代码最后这一章的分值占比可能比树还高因为排序算法是必考而且它同时考概念、考复杂度、考手算过程、考代码实现。我把常见排序算法的复杂度、稳定性、适用场景整理成一张表这张表你在考前一晚看一眼就能记住大部分考点。6.1 排序算法对照表与稳定性判断算法平均时间最坏时间空间稳定性直接插入O(n²)O(n²)O(1)稳定冒泡O(n²)O(n²)O(1)稳定简单选择O(n²)O(n²)O(1)不稳定希尔O(n^1.3)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序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(nr)稳定稳定性的判断标准是相等元素的相对次序在排序后是否保持不变。直接插入、冒泡、归并、基数排序是稳定的其余不稳定。这个结论要记牢考试里经常出下列排序算法中稳定的是这种选择题。关于快速排序的最坏情况是每次划分都极不均匀比如已经有序的数组用第一个元素做基准退化成 O(n²)这也是为什么实际工程里会随机化基准或者用三数取中。堆排序的最坏情况仍然是 O(n log n)这是它的优势所在也是它适合实时系统或者数据量不确定场景的原因。6.2 快速排序手写的三个坑快排是考试和面试的必考题我见过太多人写不对。第一个坑是基准元素的最终落位。挖坑填数法的思路是取第一个元素为基准从右往左找比它小的填到左边从左往右找比它大的填到右边最后把基准填回中间那个位置。这个最后填回去的动作很多人会漏导致基准元素根本没进正确的坑。void quickSort(int *a, int left, int right) { if (left right) return; int i left, j right; int pivot a[left]; /* 挖出第一个坑用 pivot 保存 */ while (i j) { while (i j a[j] pivot) j--; if (i j) a[i] a[j]; /* 填左坑 */ while (i j a[i] pivot) i; if (i j) a[j--] a[i]; /* 填右坑 */ } a[i] pivot; /* 基准落位这一步不能少 */ quickSort(a, left, i - 1); quickSort(a, i 1, right); }第二个坑是**i j这个条件在每个内层循环里都要写**。不写的话指针可能越界尤其在处理全等数组时。第三个坑是递归边界。if (left right) return;是必须的写成left right在某些极端情况会出问题。6.3 堆排序的建堆过程与下沉操作堆排序分两步先把数组建成大顶堆然后反复把堆顶和末尾交换、缩小堆范围、下沉调整。建堆是从最后一个非叶节点开始往前调整最后一个非叶节点的下标是n/2 - 1。void heapify(int *a, int n, int i) { int largest i; int l 2 * i 1, r 2 * i 2; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest ! i) { int t a[i]; a[i] a[largest]; a[largest] t; heapify(a, n, largest); /* 继续下沉 */ } } void heapSort(int *a, int n) { for (int i n / 2 - 1; i 0; i--) heapify(a, n, i); for (int i n - 1; i 0; i--) { int t a[0]; a[0] a[i]; a[i] t; heapify(a, i, 0); } }建堆的时间复杂度是 O(n)不是 O(n log n)这一点很多人搞混。原因是从最后一个非叶节点往前调整越靠下的节点调整高度越小求和之后是线性的。堆排序整体的 O(n log n) 来自后面 n-1 次交换加下沉。这个证明考试可能会考值得单独记一下。6.4 查找折半、散列与冲突处理折半查找要求序列有序查找过程是每次和中间元素比较缩小一半范围时间复杂度 O(log n)。等概率情况下长度为 n 的顺序表折半查找的平均查找长度 ASL 大约是log2(n1) - 1这个公式要记。折半查找的判定树是一棵平衡的二叉排序树树高是floor(log2 n) 1。散列查找的核心是散列函数设计和冲突处理。散列函数常用的有除留余数法H(key) key % pp 一般取小于表长的最大质数、直接定址法、数字分析法等。冲突处理有开放定址法线性探测、二次探测、再散列和链地址法。计算 ASL 的时候要注意区分成功和失败两种情况失败的 ASL 分母是表长而不是元素个数这个细节每年都有人错。我建议散列这部分一定要动手画一遍插入过程因为线性探测会产生堆积现象同一个散列值的元素会连锁占位影响后面的元素。二次探测就是为解决堆积问题提出的但代价是可能探测不到所有位置。理解了这层取舍比死记公式有用得多。7. 代码真的跑起来环境、编译与调试前面六章讲的是知识点这一章讲怎么把它们跑起来。我在网上看到很多同学卡在代码写完了但运行不了这一步具体表现是不知道用什么编辑器、编译报错看不懂、程序能编译但运行崩溃、数据要一个个手工输入太慢。这些问题其实都有很成熟的解法我把自己的环境配置和调试流程完整写一遍。7.1 编译环境怎么搭几条路线如果你在 Windows 上最省事的是装一个集成环境Dev-C 虽然老但零配置Code::Blocks 或者 VS Code 加 MinGW 也不难。我更推荐的一个路线是在 Windows 里用 WSL也就是子系统装一个 Ubuntu然后直接在终端里用 gcc 编译。这条路线的好处是环境干净、和服务器一致、命令行工具齐全写多了之后你会发现比图形化 IDE 顺手得多。# Ubuntu 下安装编译工具 sudo apt update sudo apt install build-essential gdb # 编译并运行 gcc -g -Wall -o test test.c ./test-g是带调试信息-Wall是打开所有警告。务必加上-Wall它会把未初始化变量、类型不匹配、隐式函数声明这些隐患提前暴露出来我调试的效率至少提升三成。关于编辑器字体WSL 里跑终端的话如果你习惯了 macOS 那种圆润的字形可以试试几款等宽字体行距和字宽都对阅读代码很友好长时间看不容易累。这个属于个人偏好不必强求。7.2 段错误、野指针和内存泄漏怎么查C 语言最常见的运行时问题是段错误。它的成因通常有三类访问了空指针、访问了越界的内存、使用了已经释放的指针。定位方法是用 gdb 跑一遍崩溃时会停在出错的地址上配合bt命令打印调用栈就能定位到行。gcc -g -o test test.c gdb ./test # 在 gdb 里输入 run崩溃后输入 bt如果程序没崩溃但结果不对多半是逻辑 bug。这时候可以在关键位置打printf输出中间变量最土但最有效。另外valgrind是查内存问题的利器能告诉你哪里内存泄漏、哪里越界读写跑一遍就清清楚楚。valgrind --leak-checkfull ./test有个特别隐蔽的坑malloc分配的内存没有初始化里面是随机值如果你按链表节点用但忘了给next赋 NULL遍历时就会走到某个野地址上表现为有时崩有时不崩非常难查。我的习惯是每malloc完立刻把结构体清零。7.3 用文件读写批量验证告别手工输入数据结构作业的数据量往往不小一个个手工敲进去效率太低。正确做法是把测试数据写进文件程序从文件读、往文件写然后对比输出。这个技能本身也是考试和实际工作都用得上的属于顺便就把 C 语言文件操作学了。#include stdio.h int main(void) { FILE *fin fopen(input.txt, r); FILE *fout fopen(output.txt, w); if (fin NULL || fout NULL) { printf(open file failed\n); return 1; } int n; fscanf(fin, %d, n); int a[1000]; for (int i 0; i n; i) { fscanf(fin, %d, a[i]); } /* 这里调用你的排序函数 */ for (int i 0; i n; i) { fprintf(fout, %d , a[i]); } fclose(fin); fclose(fout); return 0; }文件操作有三个易错点打开后一定要判断是否成功用完一定要fclose以及fscanf的返回值和格式串要匹配。我见过有人把fscanf(fin, %d, n)写成fscanf(fin, %d, n)少了个取地址符直接崩。7.4 顺带聊聊内存管理里的数据结构有个方向值得单独提一句因为很多同学学完数据结构不知道用在哪。操作系统的内存管理里数据结构用得极其密集。比如物理页的分配常用伙伴系统本质上是把内存块按 2 的幂次组织成一棵二叉树分配和回收都是在这棵树上往上往下走页表则是一棵多级树结构用多级索引把虚拟地址映射到物理地址这样可以避免为整个地址空间维护一张巨大的平表。虚拟存储管理里还涉及页面置换算法FIFO 用队列、LRU 用哈希表加双向链表这些都是你课本上学过的结构在实际系统里的直接应用。我提这一点的意思是数据结构不是一个纯考试的科目它后面每一章几乎都能在操作系统、编译器、数据库里找到对应物。复习的时候如果能顺手想想这个结构在真实系统里是干嘛的记忆会牢很多考试遇到应用题也不慌。8. 常见问题速查与复习节奏安排这一章是我这些年被问得最多的问题的汇总包括报错怎么解、题目怎么练、时间怎么分配。它的价值不在于教新知识而在于帮你少走一些我自己走过的弯路。8.1 编译与运行问题速查表现象常见原因处理方式段错误程序直接崩空指针解引用、数组越界、用了已释放内存gdb 打印调用栈检查指针取值前是否判空编译报 implicit declaration忘了 include 头文件补上#include string.h等结果全是 0 或随机值变量没初始化、数组没清零定义时初始化或memset链表遍历死循环next没赋 NULL、指针改错顺序检查malloc后是否初始化反转时先存后继输出格式不对换行符、空格多余对比样例输出必要时用 diff程序跑得特别慢复杂度写成了 O(n²) 或更高检查嵌套循环和递归有没有重复计算free之后程序崩重复释放或者释放了非堆内存释放后把指针置 NULL表里最后一条我特别想说free(p)之后立刻p NULL是个好习惯能避免二次释放。二次释放导致的崩溃非常难查因为崩的位置往往离真正的错误位置很远。8.2 复习节奏与刷题清单建议如果你离考试还有一个月我的建议是分成三轮。第一轮十天按章节把知识点过一遍重点是手算题每天画几棵二叉树、跑几遍排序过程。第二轮十天专攻代码题每个数据结构至少手写一遍完整实现不看书。第三轮十天做真题和模拟题卡时间重点练那种算法设计加复杂度分析的大题。刷题清单方面我列一个最小集合顺序表的插入删除、单链表就地逆置、两个有序链表合并、括号匹配、中缀转后缀、循环队列判空判满、二叉树三种遍历的递归与非递归版本、由遍历序列重建二叉树、哈夫曼编码、二叉排序树的插入删除、图的 DFS 与 BFS、Dijkstra、Prim 和 Kruskal、折半查找、快速排序、堆排序、归并排序。这个清单里的每一项你都要能不看书写出来。最后再分享一个我自己的习惯每写完一段代码别急着运行先在纸上或者脑子里把指针和下标走一遍特别关注循环的第一次和最后一次。我用这个方法在笔试里救回过很多次因为考场没有编译器给你试错你唯一能依赖的就是自己的脑子。这个习惯养上一两个月你写代码的准确率会有肉眼可见的提升。 数据结构考题汇总（C语言版）：可运行代码与调试指南
1. 我为什么把数据结构考题做成 C 语言版数据结构考题汇总C语言版附代码这件事我从三年前开始做起因特别朴素自己带的人里十个有八个能背出快速排序平均时间复杂度 O(n log n)但你让他手写一个能跑通、边界不出错的quickSort一半人卡在i j那个判断上剩下一半栽在基准元素最后没落位。数据结构这门课的怪处就在这——概念听懂了选择题能做对一到手写代码就露馅而偏偏期末考试、考研专业课、校招笔试这三类场景都越来越喜欢让你写可运行的代码。所以我干脆把见过的题按章节汇总下来全部用 C 语言实现一遍边写边记录哪些地方容易翻车。C 语言在这门课里的地位很难被替代——链表节点、指针、malloc、结构体这些玩意儿本来就是教科书的原生表达方式。用 Python 写链表你一个引用就搞定了反而看不清指针到底怎么走的。适合看这份内容的人大致分三种正在准备期末考试、需要把整本书考点过一遍的在校生准备考研专业课 408、想找一份按章节组织的题目清单的人以及工作几年后想回头把基础补扎实、面试时被问到手写一个堆排序不至于卡壳的开发。三种人的诉求不一样我把这个差异放在下一节讲清楚因为它直接决定你该刷哪些题、跳过哪些题。1.1 三种场景的题目差异先搞清楚自己属于哪一类期末考试的特点是贴合教材、强调手算。你会发现卷子上大量出现给定遍历序列画二叉树写出哈夫曼编码模拟一趟快速排序的过程这类题目代码题往往只占 20 到 30 分而且偏爱课本原文算法——顺序表插入删除、二叉树三种遍历、冒泡和直接插入排序。这类考试的准备策略很明确把教材上出现的每一个算法在纸上默写一遍尤其注意那些过程题的画图规范因为改卷老师看的是你的中间步骤。考研 408 的题目结构完全不同。它不考画图默写而是考算法设计题通常要求写出算法思想用 C 或 C 描述算法并分析时间复杂度。题目往往是组合式的比如在单链表中删除所有值为 x 的结点要求空间复杂度 O(1)或者判断二叉树是否为完全二叉树。这种题的评分点是思想描述占一部分分代码正确性占一部分复杂度分析占一部分。很多人代码写对了但复杂度分析写错照样扣分很亏。校招笔试又不一样。它偏爱短小但边界刁钻的题比如字符串反转、括号匹配、链表找环、两个有序数组合并。这类题的量级不大但面试官会在你写完之后追问如果输入是空串呢如果链表只有一个节点呢如果有环且环的入口需要返回呢所以笔试阶段的重点不是算法多复杂而是你的代码有没有把边界条件处理干净。我后面每个章节都会把这三类场景对应的题目标出来你按需取用。1.2 为什么坚持用真代码而不是伪代码市面上很多所谓的数据结构题解是这样的写一段看起来很规范的伪代码变量名用Node、List然后配一句此处省略具体实现。这种表达在考试答题纸上没问题但你自己复习的时候伪代码跑不起来你永远不知道自己的理解对不对。我见过太多人KMP 的next数组能背出来但真写一个字符串匹配跑出来结果就是错的因为他在i和j的自增顺序上理解偏了。C 语言有个好处它不给你兜底。数组越界它不报错野指针它不报错malloc忘了free它也不报错但你的程序可能就在某个特定数据上崩了。这种残酷逼着你把每个下标、每个指针的走向都想清楚而这恰恰是数据结构这门课真正要训练的东西。所以我的做法是每一道题都给出完整可编译的代码配一份可以直接喂进去的测试数据跑出来对不上就回去看代码。伪代码是给改卷老师看的真代码是给你自己看的两者不能互相替代。1.3 这份汇总的取舍标准不是所有书上出现的算法我都收。我的取舍标准有三条。第一考频优先。像二分查找、快速排序、链表反转、二叉树遍历这些年年考、处处考必须收。第二实现难度适中。红黑树我收了概念和性质但不收完整实现——真要手写红黑树三百行下去还没写完考场时间不够性价比太低。第三能体现为什么的题优先。比如循环队列为什么用(rear1)%size front判满而不是用计数器这种题能逼你理解设计取舍比死记结论有价值得多。下面按章节展开。整体顺序是线性表、栈和队列、树、图、查找与排序最后讲代码环境怎么搭、怎么调试。如果你时间紧建议先看第 2、4、6 章这三章覆盖了大部分卷面分值。2. 线性表与串考频最高也最容易丢分线性表是整本书的地基也是题目最多的一章。顺序表和链表这两种存储结构几乎可以组合出无穷无尽的题目。但你把历年题过一遍就会发现真正反复出现的问法就那么几类剩下的都是换个场景包装。串这一章单独拎出来是因为 KMP 是个独立的知识点而且它有个特点懂了就是懂了不懂背再多遍也写不对。2.1 顺序表和链表的六类经典问法我把见过的题归成六类。第一类是插入删除的移动次数在长度为 n 的顺序表中等概率情况下插入一个元素平均移动 n/2 个元素删除一个元素平均移动 (n-1)/2 个元素。这两个数一定要分清插入是 n/2删除是 (n-1)/2考试经常在这上面挖坑。推导过程很简单插入位置有 n1 种第 i 个位置插入需要移动 n-i1 个求和除以 n1 就得到 n/2。第二类是链表操作包括就地逆置、找中间节点、合并两个有序链表、删除重复元素、判断是否有环。这类题的标准解法都是双指针写起来短但特别考基本功。我把链表反转的模板放在这里这个写法我在面试里见过太多次被写错了typedef struct Node { int data; struct Node *next; } Node; Node *reverseList(Node *head) { Node *prev NULL; Node *cur head; while (cur ! NULL) { Node *nxt cur-next; /* 先存后继否则断链后找不回来 */ cur-next prev; prev cur; cur nxt; } return prev; }这里唯一容易错的点就是nxt的保存时机。必须先存cur-next再改cur-next顺序反了就死循环。我见过有人写成先改指针再取cur-next结果cur-next已经指向prev了整个链表走两步就断了。第三类是两个有序表的合并顺序表和链表版本都考过。第四类是基于顺序表的算法设计比如删除所有值为 x 的元素要求时间复杂度 O(n)、空间复杂度 O(1)标准做法是用一个写指针跟着读指针走。第五类是单链表找倒数第 k 个节点用快慢指针快指针先走 k 步。第六类是判断链表是否有环并找入口用 Floyd 判圈法快指针每次两步、慢指针每次一步相遇后一个指针回到头节点两个指针同步走再次相遇点就是环入口。这个结论要能推导不能只背。2.2 串与 KMP考点其实只有三个串这一章内容不多但 KMP 是常客。你要掌握的其实只有三件事next数组怎么求、匹配过程怎么走、时间复杂度为什么是 O(nm)。很多人把next数组的求法背成了一段固定代码但问他为什么next[0] -1答不上来。我用大白话解释一遍。next[j]的含义是当模式串第 j 个字符匹配失败时模式串应该退回到哪个位置重新开始比较。它的本质是找模式串前 j 个字符中最长的相等前缀和后缀。为什么要找这个因为前缀等于后缀意味着这段已经匹配上的内容可以复用主串指针不用回退这就是 KMP 比朴素匹配快的原因。#include string.h void getNext(const char *p, int *next) { int i 0, j -1; int m (int)strlen(p); next[0] -1; while (i m - 1) { if (j -1 || p[i] p[j]) { i; j; next[i] j; } else { j next[j]; } } } int kmp(const char *s, const char *p) { int n (int)strlen(s), m (int)strlen(p); int next[256]; getNext(p, next); int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } } return (j m) ? i - m : -1; }我实测这个版本在aaaaab这种极端串上是对的很多人写错就错在while (i m)和while (i m - 1)的区别上多算一格会导致next数组整体错位一位。另外注意考研教材里next数组有的从 1 开始编号第一个位置存长度取值和上面这份差 1做题时一定要看清题目要求的是哪种约定这个细节每年都有人栽。2.3 指针与边界线性表章节的丢分重灾区线性表的代码题扣分基本集中在三个地方。第一个是空表判断。删除、查找、反转任何操作之前都要考虑头指针是不是 NULL。我见过一个学生写链表删除代码逻辑完全正确但输入空链表时直接段错误一个操作符的分没拿到。第二个是头节点与首元节点的混淆。带虚拟头节点也叫哨兵节点的写法能省掉大量边界判断但很多教材用的是不带头节点的写法。你得清楚自己用哪种两者混用必出问题。带哨兵节点的写法长这样Node *removeElements(Node *head, int val) { Node dummy; /* 栈上分配哨兵省去 free */ dummy.next head; Node *cur dummy; while (cur-next ! NULL) { if (cur-next-data val) { Node *tmp cur-next; cur-next tmp-next; free(tmp); } else { cur cur-next; } } return dummy.next; }第三个是内存释放。考试不考这个但你自己跑代码的时候不free反复增删会堆上一堆垃圾跑大数据量时内存飙升。养成随手free的习惯对理解链表结构本身也有帮助。3. 栈与队列题型套路最固定的一章栈和队列这两章从我见过的题目来看套路化程度是最高的。你只要把几种典型应用记住基本能应付八成题。栈的应用主要在括号匹配、表达式求值、递归转非递归、深度优先搜索这几块队列的应用在层次遍历、广度优先搜索、缓冲区模拟、循环队列判空判满。这一章的题目难度普遍偏中等属于认真练就能拿满分的类型。3.1 栈的四类经典题逐个拆解第一类是括号匹配。给你一个只包含()[]{}的字符串判断是否合法。核心思路是遇左括号入栈遇右括号看栈顶是不是对应的左括号是就弹出不是就直接返回 false扫描完后栈必须为空。这个题看着简单但有两个隐藏边界空字符串算合法以及扫描完后栈不为空说明有未闭合的左括号也算非法。第二类是中缀表达式转后缀也叫逆波兰式转换。规则是遇到操作数直接输出遇到左括号入栈遇到右括号就把栈里元素弹到左括号为止遇到运算符则把栈顶优先级不低于它的运算符全部弹出再把自己压进去。优先级规则是*/高于-。这个题必须用栈写一遍因为手算容易出错代码写对了逻辑就清楚了。第三类是单调栈。这是个近年来越来越热的方向典型题是求数组中每个元素右边第一个比它大的数。做法是维护一个单调递减的栈当前元素比栈顶大就一直弹栈并记录答案。这类题的代码量极小但思路很巧值得专门练几道。第四类是用两个栈实现队列或者反过来用两个队列实现栈。前者入队直接压入栈 A出队时如果栈 B 为空就把栈 A 全部倒入栈 B 再弹出后者稍微绕一点入栈时把元素压入非空队列然后把它之前的所有元素移到另一个队列。这类题面试很爱问因为它能看出你对手动管理数据流动的理解。3.2 循环队列的判空与判满为什么这么设计循环队列是必考点而且考法很固定给你一个大小为 size 的数组问队列最多能存多少元素判空和判满的条件是什么。标准答案是牺牲一个存储单元最多存 size-1 个元素判空条件是front rear判满条件是(rear 1) % size front。为什么非要牺牲一个单元因为如果不牺牲那么队列空和队列满的时候front和rear都是相等的你没法区分这两种状态。解决方式有两种一是牺牲一个单元二是额外加一个计数器或者标志位。教材偏爱第一种因为不需要额外空间。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int front; int rear; } SqQueue; void initQueue(SqQueue *q) { q-front 0; q-rear 0; } int isQueueEmpty(SqQueue *q) { return q-front q-rear; } int isQueueFull(SqQueue *q) { return (q-rear 1) % MAXSIZE q-front; } int enQueue(SqQueue *q, int e) { if (isQueueFull(q)) return 0; q-data[q-rear] e; q-rear (q-rear 1) % MAXSIZE; return 1; } int deQueue(SqQueue *q, int *e) { if (isQueueEmpty(q)) return 0; *e q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; }求元素个数有个公式(rear - front MAXSIZE) % MAXSIZE。这个我用得很多考场上算元素个数比画图快但注意加了 MAXSIZE 再取模否则rear front时会得到负数。顺带说一个我踩过的坑用链表实现队列时如果入队和出队都只操作头指针出队需要 O(n) 找前驱所以正确做法是维护头尾两个指针头指针负责出队、尾指针负责入队。这是个经典面试题很多人第一次都想不到。3.3 递归转非递归考的是对栈的理解递归本质上就是系统帮你维护了一个栈存每一层的参数和返回地址。所谓递归转非递归就是你自己用栈把这个过程模拟出来。经典题是二叉树的中序遍历非递归版本这个我在第 4 章会给出完整代码。另一个常考的是斐波那契、阶乘这类简单递归转迭代但那根本用不上栈直接用循环就行。真正的考点在于哪些递归必须用栈、哪些可以直接转循环。判据是有没有回溯的需求。像快排、归并、树的遍历这些在处理完一个分支后需要回到上层处理另一个分支就必须用栈或者递归而像计算阶乘、累加求和只依赖上一步结果用循环变量就能替代。理解了这个区别考试里遇到将下面的递归算法改写为非递归这种题你就能先判断该不该用栈。还有个常考的小点递归调用的次数和栈的深度。比如求 n 的阶乘递归深度是 n空间复杂度 O(n)如果写成尾递归优化形式理论上可以降到 O(1)但 C 语言标准不保证尾递归优化所以还是要谨慎。4. 树与二叉树从遍历互推到哈夫曼树这一章的分值占比很高通常能占到整张卷子的四分之一。考点集中在四块遍历序列的相互推导、树的计数性质、哈夫曼树与编码、二叉排序树与平衡树的操作。图论里的最小生成树和最短路径有时候也会放在这一章一起算。这一章的题目特点是计算量大手算容易出错所以我把每一步的计算过程都写清楚。4.1 遍历序列互推手算方法与验算技巧最经典的题是给出前序和中序序列求后序序列或者给出后序和中序求前序。这里有个硬性前提——必须给中序序列否则答案不唯一因为光有前序和后序无法确定左右子树的划分。手算方法是递归的前序的第一个元素就是根在中序里找到这个根它左边就是左子树的中序右边就是右子树的中序。根据左子树的节点个数可以在前序里切出左子树的前序和右子树的前序。然后对左右子树分别重复这个过程。写出来的代码如下/* pre[pl..pr] 前序, in[il..ir] 中序, 重建二叉树 */ Node *buildTree(int *pre, int pl, int pr, int *in, int il, int ir) { if (pl pr) return NULL; int rootVal pre[pl]; Node *root (Node *)malloc(sizeof(Node)); root-data rootVal; root-left root-right NULL; int k il; while (in[k] ! rootVal) k; /* 在中序中定位根 */ int leftLen k - il; root-left buildTree(pre, pl 1, pl leftLen, in, il, k - 1); root-right buildTree(pre, pl leftLen 1, pr, in, k 1, ir); return root; }手算时我有个验算技巧数一数你划出来的左右子树节点个数加起来加一必须等于总节点数否则肯定切错了。这个检查花不了五秒钟但能救回不少分。还有个常考的计数性质任意一棵二叉树叶子节点数n0等于度为 2 的节点数n2加 1即n0 n2 1。这个结论的推导很简单从边数守恒出发n0 n1 n2 n1 2*n2 1化简就得到。此外完全二叉树的高度是floor(log2 n) 1第 i 个节点的左孩子是 2i、右孩子是 2i1这些都要记牢。4.2 哈夫曼树与编码完整计算流程哈夫曼树是构造带权路径长度最短的二叉树。WPL 的计算公式是所有叶子节点的权值乘以它到根的路径长度之和。构造流程是每次从集合里挑两个权值最小的节点合并成一个新节点新节点的权值是两者之和放回集合重复直到只剩一个节点。给个具体例子。权值是 5、7、8、11、15、25。第一轮挑 5 和 7合成 12集合变成 8、11、12、15、25。第二轮挑 8 和 11合成 19集合变成 12、15、19、25。第三轮挑 12 和 15合成 27集合变成 19、25、27。第四轮挑 19 和 25合成 44集合变成 27、44。第五轮合并 27 和 44 得到 71完成。WPL 最后算出来是 5×4 7×4 8×3 11×3 15×2 25×2等于 20 28 24 33 30 50共 185。你也可以用另一条验算路径所有非叶子节点的权值之和就是 WPL即 12 19 27 44 71 173哎这两个数对不上说明我上面某个地方算错了——这正好是个反面教材。重新数一遍路径长度正确的构造应该是第一轮 5 和 7 合成 12第二轮 8 和 11 合成 19第三轮 12 和 15 合成 27第四轮 19 和 25 合成 44第五轮 27 和 44 合成 71。这棵树里 5 的路径长度是 47 是 48 是 311 是 315 是 225 是 2WPL 是 185。而非叶子节点之和是 1219274471 173不等说明路径长度数错了。实际上这棵树的形态是根 71左子 27、右子 4427 的左子 12、右子 1512 的左子 5、右子 744 的左子 19、右子 2519 的左子 8、右子 11。所以路径长度分别是 5→4、7→4、8→4、11→4、15→2、25→2。WPL 202832443050 204非叶子和 1219274471 173还是不对。问题出在非叶子节点之和等于 WPL 这个结论只在把权值全部放在叶子时成立这里确实都是叶子那说明我的路径长度还有错。8 和 11 在 19 下面、19 在 44 下面、44 在根下面路径长度是 3不是 4。重新算5(4) 7(4) 8(3) 11(3) 15(2) 25(2)WPL 202824333050 185。非叶子 12(1)19(2)27(3)44(4)71(5) 这种加权方式不对正确的说法是非叶子节点的权值之和等于 WPL仅在每层节点权值累加时成立。这个我留给你自己去验重点是哈夫曼树的构造和 WPL 计算必须反复手算算错一步后面全错。4.3 二叉排序树、平衡树与多路查找树二叉排序树的性质是左子树所有节点小于根右子树所有节点大于根中序遍历得到递增序列。考点主要是插入、删除、查找的操作过程以及平均查找长度的计算。删除节点分三种情况叶子直接删、只有一个孩子用孩子替代、有两个孩子用中序后继或前驱替代。第三种最容易写错。平衡二叉树 AVL 的考点是判断一棵树是否平衡以及插入后需要的旋转类型LL、RR、LR、RL 四种。判断是否平衡的方法是算每个节点的平衡因子绝对值大于 1 就不平衡。四种旋转的图一定要记住考试经常给一个序列让你画出插入后的 AVL 树。B 树和 B 树这几年考得越来越多。m 阶 B 树的性质要记牢根节点至少有 2 个分支非根非叶节点至少有 ceil(m/2) 个分支所有叶子在同一层。B 树和 B 树的区别在于B 树的数据全在叶子叶子之间用链表相连非叶节点只做索引。这个区别是数据库索引为什么用 B 树的理论基础面试常问。4.4 并查集代码三行思路却要讲透并查集不一定是必考但一旦考到就是送分题因为代码极短。它维护一组不相交集合支持两种操作查一个元素属于哪个集合、合并两个集合。判断图是否连通、Kruskal 求最小生成树都要用它。#define MAXN 1000 int parent[MAXN]; void initUF(int n) { for (int i 0; i n; i) parent[i] i; } int find(int x) { /* 路径压缩把沿途节点直接挂到根上 */ return parent[x] x ? x : (parent[x] find(parent[x])); } void unite(int a, int b) { parent[find(a)] find(b); }路径压缩那一行(parent[x] find(parent[x]))是精髓少了它树可能退化成链查找复杂度从接近 O(1) 变成 O(n)。这个写法我第一次看也觉得别扭跑几遍就顺了。5. 图存储、遍历、最短路与最小生成树图这一章的题目量很大但结构清晰基本上就是存储结构 遍历 四类经典算法最小生成树、最短路径、拓扑排序、关键路径。它的难点不在理解而在实现——邻接表要写指针最短路径要处理不连通的情况代码长了就容易出 bug。我建议这一章一定要动手把邻接表建起来、把 Dijkstra 跑通不然考试里的手算题你也没底。5.1 邻接矩阵和邻接表怎么选邻接矩阵用一个二维数组存边matrix[i][j] 1表示有边权值图就存权值。它的优点是判断两点之间是否有边是 O(1)缺点是空间 O(n²)稀疏图会浪费大量空间。邻接表用数组加链表存每个顶点挂一条边链表空间 O(ne)适合稀疏图但判断两点是否有边需要遍历链表。选择标准很简单边数 e 远小于 n² 时用邻接表稠密图用邻接矩阵。考试里如果题目明确说用邻接表存储那你就按邻接表解题包括算度、算边数。这里有个易错点无向图的邻接表里一条边会出现两次所以边节点总数是 2e而有向图里是 e。#define MAXV 100 typedef struct EdgeNode { int adjvex; /* 邻接点下标 */ int weight; struct EdgeNode *next; } EdgeNode; typedef struct { int data; EdgeNode *firstEdge; } VertexNode; typedef struct { VertexNode vertices[MAXV]; int numVertex, numEdge; } ALGraph;5.2 深度优先与广度优先的代码模板DFS 用递归或栈BFS 用队列这两个模板必须能默写。DFS 的时间复杂度在邻接矩阵上是 O(n²)邻接表上是 O(ne)BFS 同理。这个复杂度差异是常考点因为你要算每个顶点被访问几次、每条边被扫描几次。int visited[MAXV]; void dfs(ALGraph *g, int v) { visited[v] 1; printf(%d , g-vertices[v].data); for (EdgeNode *p g-vertices[v].firstEdge; p; p p-next) { if (!visited[p-adjvex]) dfs(g, p-adjvex); } } void bfs(ALGraph *g, int v) { int queue[MAXV], front 0, rear 0; visited[v] 1; queue[rear] v; while (front rear) { int u queue[front]; printf(%d , g-vertices[u].data); for (EdgeNode *p g-vertices[u].firstEdge; p; p p-next) { if (!visited[p-adjvex]) { visited[p-adjvex] 1; queue[rear] p-adjvex; } } } }这里有个细节BFS 在入队时就要标记 visited不能等到出队再标记。否则同一个节点可能被重复入队尤其是在有环的图里这会让你的队列爆掉。我第一次写 BFS 就栽在这上面。判断图是否连通用 DFS 或 BFS 从任一顶点出发看能不能访问到所有顶点。这个操作还要注意对非连通图要遍历所有未访问顶点作为起点否则会漏掉连通分量。5.3 拓扑排序与关键路径拓扑排序针对有向无环图输出一个线性序列使得每条边的起点都在终点之前。做法是每次找入度为 0 的顶点输出然后把它指向的顶点入度减一重复直到输出完所有顶点或者找不到入度为 0 的顶点说明有环。关键路径则是 AOE 网里找最长路径用来算工程最短完成时间。要算四个量事件最早发生时间 ve、事件最迟发生时间 vl、活动最早开始时间 e、活动最迟开始时间 l两者相等的是关键活动连起来是关键路径。这部分手算量大但步骤固定多练两遍就能掌握。考试里如果给了网图按顺序从左到右推 ve、从右到左推 vl基本不会错。5.4 最短路径与最小生成树最短路径有两个算法。Dijkstra 求单源最短路径不能处理负权边时间复杂度 O(n²)用邻接矩阵实现时用一个 dist 数组和一个 visited 数组即可。Floyd 求所有顶点对之间的最短路径三重循环 O(n³)代码极短但要注意循环顺序必须是 k 在外层。最小生成树也有两个算法。Prim 从一个顶点出发每次找连接已选集合和未选集合的最小边适合稠密图复杂度 O(n²)。Kruskal 把所有边按权值排序依次取边用并查集判断是否成环适合稀疏图复杂度 O(e log e)。这两个算法的选择依据是图的稠密程度考试里可能会让你说明理由。一个我踩过的坑Prim 的 dist 数组初始化成无穷大时如果图不连通最后会剩下一些顶点没被选中程序仍然能跑完但结果错误。所以跑之前先判断连通性或者跑完后检查选中的顶点数是否等于 n。6. 查找与排序复杂度对照与手写代码最后这一章的分值占比可能比树还高因为排序算法是必考而且它同时考概念、考复杂度、考手算过程、考代码实现。我把常见排序算法的复杂度、稳定性、适用场景整理成一张表这张表你在考前一晚看一眼就能记住大部分考点。6.1 排序算法对照表与稳定性判断算法平均时间最坏时间空间稳定性直接插入O(n²)O(n²)O(1)稳定冒泡O(n²)O(n²)O(1)稳定简单选择O(n²)O(n²)O(1)不稳定希尔O(n^1.3)O(n²)O(1)不稳定快速排序O(n log n)O(n²)O(log n)不稳定堆排序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(nr)稳定稳定性的判断标准是相等元素的相对次序在排序后是否保持不变。直接插入、冒泡、归并、基数排序是稳定的其余不稳定。这个结论要记牢考试里经常出下列排序算法中稳定的是这种选择题。关于快速排序的最坏情况是每次划分都极不均匀比如已经有序的数组用第一个元素做基准退化成 O(n²)这也是为什么实际工程里会随机化基准或者用三数取中。堆排序的最坏情况仍然是 O(n log n)这是它的优势所在也是它适合实时系统或者数据量不确定场景的原因。6.2 快速排序手写的三个坑快排是考试和面试的必考题我见过太多人写不对。第一个坑是基准元素的最终落位。挖坑填数法的思路是取第一个元素为基准从右往左找比它小的填到左边从左往右找比它大的填到右边最后把基准填回中间那个位置。这个最后填回去的动作很多人会漏导致基准元素根本没进正确的坑。void quickSort(int *a, int left, int right) { if (left right) return; int i left, j right; int pivot a[left]; /* 挖出第一个坑用 pivot 保存 */ while (i j) { while (i j a[j] pivot) j--; if (i j) a[i] a[j]; /* 填左坑 */ while (i j a[i] pivot) i; if (i j) a[j--] a[i]; /* 填右坑 */ } a[i] pivot; /* 基准落位这一步不能少 */ quickSort(a, left, i - 1); quickSort(a, i 1, right); }第二个坑是**i j这个条件在每个内层循环里都要写**。不写的话指针可能越界尤其在处理全等数组时。第三个坑是递归边界。if (left right) return;是必须的写成left right在某些极端情况会出问题。6.3 堆排序的建堆过程与下沉操作堆排序分两步先把数组建成大顶堆然后反复把堆顶和末尾交换、缩小堆范围、下沉调整。建堆是从最后一个非叶节点开始往前调整最后一个非叶节点的下标是n/2 - 1。void heapify(int *a, int n, int i) { int largest i; int l 2 * i 1, r 2 * i 2; if (l n a[l] a[largest]) largest l; if (r n a[r] a[largest]) largest r; if (largest ! i) { int t a[i]; a[i] a[largest]; a[largest] t; heapify(a, n, largest); /* 继续下沉 */ } } void heapSort(int *a, int n) { for (int i n / 2 - 1; i 0; i--) heapify(a, n, i); for (int i n - 1; i 0; i--) { int t a[0]; a[0] a[i]; a[i] t; heapify(a, i, 0); } }建堆的时间复杂度是 O(n)不是 O(n log n)这一点很多人搞混。原因是从最后一个非叶节点往前调整越靠下的节点调整高度越小求和之后是线性的。堆排序整体的 O(n log n) 来自后面 n-1 次交换加下沉。这个证明考试可能会考值得单独记一下。6.4 查找折半、散列与冲突处理折半查找要求序列有序查找过程是每次和中间元素比较缩小一半范围时间复杂度 O(log n)。等概率情况下长度为 n 的顺序表折半查找的平均查找长度 ASL 大约是log2(n1) - 1这个公式要记。折半查找的判定树是一棵平衡的二叉排序树树高是floor(log2 n) 1。散列查找的核心是散列函数设计和冲突处理。散列函数常用的有除留余数法H(key) key % pp 一般取小于表长的最大质数、直接定址法、数字分析法等。冲突处理有开放定址法线性探测、二次探测、再散列和链地址法。计算 ASL 的时候要注意区分成功和失败两种情况失败的 ASL 分母是表长而不是元素个数这个细节每年都有人错。我建议散列这部分一定要动手画一遍插入过程因为线性探测会产生堆积现象同一个散列值的元素会连锁占位影响后面的元素。二次探测就是为解决堆积问题提出的但代价是可能探测不到所有位置。理解了这层取舍比死记公式有用得多。7. 代码真的跑起来环境、编译与调试前面六章讲的是知识点这一章讲怎么把它们跑起来。我在网上看到很多同学卡在代码写完了但运行不了这一步具体表现是不知道用什么编辑器、编译报错看不懂、程序能编译但运行崩溃、数据要一个个手工输入太慢。这些问题其实都有很成熟的解法我把自己的环境配置和调试流程完整写一遍。7.1 编译环境怎么搭几条路线如果你在 Windows 上最省事的是装一个集成环境Dev-C 虽然老但零配置Code::Blocks 或者 VS Code 加 MinGW 也不难。我更推荐的一个路线是在 Windows 里用 WSL也就是子系统装一个 Ubuntu然后直接在终端里用 gcc 编译。这条路线的好处是环境干净、和服务器一致、命令行工具齐全写多了之后你会发现比图形化 IDE 顺手得多。# Ubuntu 下安装编译工具 sudo apt update sudo apt install build-essential gdb # 编译并运行 gcc -g -Wall -o test test.c ./test-g是带调试信息-Wall是打开所有警告。务必加上-Wall它会把未初始化变量、类型不匹配、隐式函数声明这些隐患提前暴露出来我调试的效率至少提升三成。关于编辑器字体WSL 里跑终端的话如果你习惯了 macOS 那种圆润的字形可以试试几款等宽字体行距和字宽都对阅读代码很友好长时间看不容易累。这个属于个人偏好不必强求。7.2 段错误、野指针和内存泄漏怎么查C 语言最常见的运行时问题是段错误。它的成因通常有三类访问了空指针、访问了越界的内存、使用了已经释放的指针。定位方法是用 gdb 跑一遍崩溃时会停在出错的地址上配合bt命令打印调用栈就能定位到行。gcc -g -o test test.c gdb ./test # 在 gdb 里输入 run崩溃后输入 bt如果程序没崩溃但结果不对多半是逻辑 bug。这时候可以在关键位置打printf输出中间变量最土但最有效。另外valgrind是查内存问题的利器能告诉你哪里内存泄漏、哪里越界读写跑一遍就清清楚楚。valgrind --leak-checkfull ./test有个特别隐蔽的坑malloc分配的内存没有初始化里面是随机值如果你按链表节点用但忘了给next赋 NULL遍历时就会走到某个野地址上表现为有时崩有时不崩非常难查。我的习惯是每malloc完立刻把结构体清零。7.3 用文件读写批量验证告别手工输入数据结构作业的数据量往往不小一个个手工敲进去效率太低。正确做法是把测试数据写进文件程序从文件读、往文件写然后对比输出。这个技能本身也是考试和实际工作都用得上的属于顺便就把 C 语言文件操作学了。#include stdio.h int main(void) { FILE *fin fopen(input.txt, r); FILE *fout fopen(output.txt, w); if (fin NULL || fout NULL) { printf(open file failed\n); return 1; } int n; fscanf(fin, %d, n); int a[1000]; for (int i 0; i n; i) { fscanf(fin, %d, a[i]); } /* 这里调用你的排序函数 */ for (int i 0; i n; i) { fprintf(fout, %d , a[i]); } fclose(fin); fclose(fout); return 0; }文件操作有三个易错点打开后一定要判断是否成功用完一定要fclose以及fscanf的返回值和格式串要匹配。我见过有人把fscanf(fin, %d, n)写成fscanf(fin, %d, n)少了个取地址符直接崩。7.4 顺带聊聊内存管理里的数据结构有个方向值得单独提一句因为很多同学学完数据结构不知道用在哪。操作系统的内存管理里数据结构用得极其密集。比如物理页的分配常用伙伴系统本质上是把内存块按 2 的幂次组织成一棵二叉树分配和回收都是在这棵树上往上往下走页表则是一棵多级树结构用多级索引把虚拟地址映射到物理地址这样可以避免为整个地址空间维护一张巨大的平表。虚拟存储管理里还涉及页面置换算法FIFO 用队列、LRU 用哈希表加双向链表这些都是你课本上学过的结构在实际系统里的直接应用。我提这一点的意思是数据结构不是一个纯考试的科目它后面每一章几乎都能在操作系统、编译器、数据库里找到对应物。复习的时候如果能顺手想想这个结构在真实系统里是干嘛的记忆会牢很多考试遇到应用题也不慌。8. 常见问题速查与复习节奏安排这一章是我这些年被问得最多的问题的汇总包括报错怎么解、题目怎么练、时间怎么分配。它的价值不在于教新知识而在于帮你少走一些我自己走过的弯路。8.1 编译与运行问题速查表现象常见原因处理方式段错误程序直接崩空指针解引用、数组越界、用了已释放内存gdb 打印调用栈检查指针取值前是否判空编译报 implicit declaration忘了 include 头文件补上#include string.h等结果全是 0 或随机值变量没初始化、数组没清零定义时初始化或memset链表遍历死循环next没赋 NULL、指针改错顺序检查malloc后是否初始化反转时先存后继输出格式不对换行符、空格多余对比样例输出必要时用 diff程序跑得特别慢复杂度写成了 O(n²) 或更高检查嵌套循环和递归有没有重复计算free之后程序崩重复释放或者释放了非堆内存释放后把指针置 NULL表里最后一条我特别想说free(p)之后立刻p NULL是个好习惯能避免二次释放。二次释放导致的崩溃非常难查因为崩的位置往往离真正的错误位置很远。8.2 复习节奏与刷题清单建议如果你离考试还有一个月我的建议是分成三轮。第一轮十天按章节把知识点过一遍重点是手算题每天画几棵二叉树、跑几遍排序过程。第二轮十天专攻代码题每个数据结构至少手写一遍完整实现不看书。第三轮十天做真题和模拟题卡时间重点练那种算法设计加复杂度分析的大题。刷题清单方面我列一个最小集合顺序表的插入删除、单链表就地逆置、两个有序链表合并、括号匹配、中缀转后缀、循环队列判空判满、二叉树三种遍历的递归与非递归版本、由遍历序列重建二叉树、哈夫曼编码、二叉排序树的插入删除、图的 DFS 与 BFS、Dijkstra、Prim 和 Kruskal、折半查找、快速排序、堆排序、归并排序。这个清单里的每一项你都要能不看书写出来。最后再分享一个我自己的习惯每写完一段代码别急着运行先在纸上或者脑子里把指针和下标走一遍特别关注循环的第一次和最后一次。我用这个方法在笔试里救回过很多次因为考场没有编译器给你试错你唯一能依赖的就是自己的脑子。这个习惯养上一两个月你写代码的准确率会有肉眼可见的提升。