1. 考卷上的数据结构到底在考什么翻开任何一份数据结构试卷你会发现真正拉开差距的从来不是选择题。数据结构这门课的分数结构很有意思前面那些概念题、判断题、复杂度选择认真背两轮基本都能拿到七成以上但最后那道二十分左右的算法设计题往往才是决定你是六十分还是八十五分的地方。我见过太多人把王道数据结构电子版翻烂遍历、排序、查找的知识点总结抄了好几页结果一上手写代码指针就飞了循环边界就错了考试时间全耗在调一个数组越界上。这就是为什么标题里我特意强调附代码。数据结构用 C语言描述不是随便选的它的每个抽象概念最终都要落到结构体、指针和内存上。链表是结构体指针串起来的一串节点栈是一个数组加一个栈顶下标树是带两个指针的结构体图是二维数组或者指针数组。你不亲手把这些写出来考试时脑子里就只有名词没有形状题目稍微变个说法你就懵了。下面这张表是我根据近几年期末复习和考研数据结构的常见卷面结构整理的可以对着它安排复习优先级卷面题型常见分值主要考点是否必须动手写选择题20-30概念辨析、复杂度、存储结构对比否但要对代码有画面感填空题10-20求遍历序列、求平均查找长度、求 WPL否判断题10稳定性、判空判满条件、性质定理否简答与画图15-25画哈夫曼树、画邻接表、画判定树半动手算法设计题20-30链表操作、树的遍历、排序实现必须动手我自己的复习策略是把每一类结构单独建一个.c文件从零把它写出来、编译通过、手动构造几组垃圾数据跑一遍。这个过程看着笨但它同时解决三件事——你记住了结构体定义、你记住了边界条件、你还顺便练了 C语言指针。数据结构学习里最值钱的就是这种肌肉记忆考场上你不需要回忆手先写出来了。还有一点很多人复习时喜欢追求最优解比如链表题一定要用快慢指针排序一定要写非递归。但考试评卷往往看的是思路是否完整、代码是否可运行。一个能跑通的朴素解法比一个卡在半截的最优解分数高得多。所以下面的代码我都尽量先给能直接跑的版本再补充可以拿加分的优化思路。2. 线性表与链表指针题占分最高也最容易翻车2.1 顺序表和链表的取舍不是背出来的复习线性表最先遇到的对比题就是顺序表和链表的选择。很多人死记链表插入删除快、顺序表随机访问快但考试会问你更细的场景比如频繁在表尾插入、很少删除、需要按下标查询选哪个。这时候你要能立刻答出顺序表并说清楚为什么表尾插入在顺序表里是 O(1)不考虑扩容而链表还要先遍历到尾。维度顺序表单链表存储方式连续内存离散节点加指针随机访问O(1)O(n)插入删除O(n)需移动元素O(1)前提是已知前驱空间开销可能预留过多每节点多一个指针缓存友好度高低顺序表里有个必考的小计算长度为 n 的顺序表插入一个元素平均要移动多少个答案是 n/2删除一个元素平均要移动 (n-1)/2 个。这两个数字不要死背自己用插入位置从 1 到 n1各自移动 n-i1 个元素求和再除以 n1推一遍考场上忘了能当场算出来。2.2 单链表就地逆置三行核心逻辑要刻进脑子单链表逆置是算法设计题里出现频率极高的一类。带头结点的链表逆置本质是把每个节点依次头插到 head 后面typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 带头结点的单链表就地逆置 LinkList Reverse(LinkList head) { LNode *p head-next; // p 指向第一个数据节点 head-next NULL; // 先断开后面靠头插重建 while (p ! NULL) { LNode *q p-next; // 先存住后继否则断链后找不回来 p-next head-next; head-next p; p q; } return head; }这里的顺序不能错先存q p-next再改p-next最后移动p。我当年写错最多的地方就是先把p-next改了然后p p-next直接指向自己死循环不说还看不出错在哪。这个先保存后继再改指针的习惯是所有链表题的通则删节点、拆链表、合并链表都用得上。2.3 快慢指针一道题会了能套十道快慢指针是链表题的分水岭。判断有环、找中间节点、找倒数第 k 个节点全靠它。核心思想是让两个指针以不同速度走快的到头了或者追上慢的了就能得到位置信息。// 找中间节点偶数个节点时返回靠前的那个 LNode *FindMid(LinkList head) { LNode *slow head-next, *fast head-next; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; } // 找倒数第 k 个节点不存在返回 NULL LNode *FindKthFromEnd(LinkList head, int k) { LNode *fast head-next; for (int i 0; i k; i) { if (fast NULL) return NULL; // 链表长度不足 k fast fast-next; } LNode *slow head-next; while (fast ! NULL) { slow slow-next; fast fast-next; } return slow; } // 判断是否有环Floyd 判圈 int HasCycle(LinkList head) { LNode *slow head, *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) return 1; } return 0; }写这类题的时候最容易出错的是循环条件。while (fast ! NULL fast-next ! NULL)里的两个判断缺一不可少了任何一个遇到空链表或者单节点链表时fast-next-next就会访问空指针。C语言里访问空指针不一定立刻报错可能读到一堆垃圾值这种题一旦出错很难靠调试发现只能靠写的时候条件写全。2.4 链表题的几个隐藏坑第一个坑是头结点。很多教材的链表带头结点有些题又不要头结点答题前务必看清楚题干里结构体的定义别自己想当然。带头结点的好处是插入删除第一个数据节点不用特判所以考试里默认带头结点的情况居多。第二个坑是释放内存的顺序。删除节点时如果先free(p)再想访问p-next那就是标准的使用后释放错误程序行为不可预测。正确写法是先存后继再 free。第三个坑是尾节点的next没置空。用头插法建完链表最后一个节点的next必须显式给 NULL否则遍历时可能跑到内存深处的野指针上考试时表现为输出莫名其妙的一串数很难定位。提示链表题写完拿三个输入验证——空表、只有一个节点、有重复数据的表。这三组能过基本就没问题了。3. 栈和队列边界判断是命门3.1 顺序栈的入栈出栈顺序顺序栈用数组加一个top下标就能实现约定top -1表示空栈。入栈是先top再赋值出栈是先取值再top--这两个顺序搞反栈顶元素就会错位。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; } SqStack; void InitStack(SqStack *s) { s-top -1; } int StackEmpty(SqStack *s) { return s-top -1; } int Push(SqStack *s, int x) { if (s-top MAXSIZE - 1) return 0; // 栈满 s-data[s-top] x; return 1; } int Pop(SqStack *s, int *x) { if (s-top -1) return 0; // 栈空 *x s-data[s-top--]; return 1; }栈的经典应用是括号匹配。思路很直白遇到左括号入栈遇到右括号就看栈顶是不是对应的左括号最后栈必须为空。int BracketMatch(const char *s) { char st[256]; int top -1; for (int i 0; s[i] ! \0; i) { char c s[i]; if (c ( || c [ || c {) { st[top] c; } else if (c ) || c ] || c }) { if (top -1) return 0; // 右括号多了 char t st[top--]; if ((c ) t ! () || (c ] t ! [) || (c } t ! {)) return 0; } } return top -1; // 左括号必须全部匹配掉 }中缀转后缀也是必考。规则是操作数直接输出运算符与栈顶比较优先级栈顶优先级不低于当前运算符就弹出左括号一律入栈右括号一直弹到左括号为止。这套规则背下来容易但考场上手动推一个ab*c-d这样的式子还是容易乱建议平时至少手推十组。3.2 循环队列三种判满方案循环队列的判空判满是填空和简答的高频点。核心矛盾是front rear既可能是空也可能是满所以要引入额外信息区分。常见有三种方案方案判空条件判满条件代价牺牲一个存储单元front rear(rear1)%M front少用一个空间加 size 计数器size 0size M多一个变量加 tag 标记rear front 且 tag 0rear front 且 tag 1多一个变量考试默认第一种。实现时最容易写错的是rear的推进它一定要取模不能直接自增#define QMAX 100 typedef struct { int data[QMAX]; int front, rear; } SqQueue; void InitQueue(SqQueue *q) { q-front q-rear 0; } int QueueEmpty(SqQueue *q) { return q-front q-rear; } int QueueFull(SqQueue *q) { return (q-rear 1) % QMAX q-front; } int EnQueue(SqQueue *q, int x) { if (QueueFull(q)) return 0; q-data[q-rear] x; q-rear (q-rear 1) % QMAX; // 先放数据再动指针 return 1; } int DeQueue(SqQueue *q, int *x) { if (QueueEmpty(q)) return 0; *x q-data[q-front]; q-front (q-front 1) % QMAX; return 1; }有个很隐蔽的错法入队时先动rear再存数据这样第一个元素会被写在下标 1 而不是 0判满判空的逻辑就全乱了。记住先存后动和先取后动队列就稳了一半。3.3 栈和队列互相实现还有一类题喜欢考两个栈实现队列和两个队列实现栈。前者的核心是一个入栈一个出栈出栈为空时把入栈全部倒过来后者更绕一点因为队列是先进先出需要一个队列当搬运工。这类题考察的是你对两种结构顺序特性的理解画个图把元素流动走一遍就清楚了不用背代码。4. 树与二叉树遍历反推和哈夫曼是必考三件套4.1 遍历序列怎么反推二叉树的遍历是所有考题里出得最密的。前序、中序、后序、层次前三个是递归定义层次用队列实现。反推题的一般套路是前序第一个元素或后序最后一个元素一定是根拿着根去中序里切分左右子树然后递归。这个套路能解决绝大多数给两个序列求第三个的题目。已知能否唯一确定关键点前序 中序能前序首元素是根后序 中序能后序末元素是根前序 后序不能无法区分单子树方向层次 中序能层次首元素是根前序加后序不能唯一确定这是判断题的常客原因是当某个节点只有一个孩子时你分不清它在左还是在右。顺序存储的完全二叉树还有一组必背性质若节点编号从 1 开始节点 i 的左孩子是 2i右孩子是 2i1父节点是 i/2。另外叶子节点数 n0 和度为 2 的节点数 n2 满足n0 n2 1这条性质结合节点总数能推出很多题目。4.2 遍历代码和建树代码递归遍历几乎是送分但非递归的中序遍历经常考因为它把栈和树的遍历结合起来了。typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void PreOrder(BiTree T) { if (T) { printf(%c , T-data); PreOrder(T-lchild); PreOrder(T-rchild); } } // 非递归中序遍历一路向左压栈弹一个就往右走 void InOrderNoRec(BiTree T) { BiTree st[100]; int top -1; BiTree p T; while (p ! NULL || top ! -1) { while (p ! NULL) { st[top] p; p p-lchild; } p st[top--]; printf(%c , p-data); p p-rchild; } }由前序和中序建树是算法设计题里很典型的一道它把递归和数组下标切分结合起来// pre[pl..pr] 是前序in[il..ir] 是中序下标均为闭区间 BiTree Build(char pre[], int pl, int pr, char in[], int il, int ir) { if (pl pr) return NULL; BiTree root (BiTree)malloc(sizeof(BiTNode)); root-data pre[pl]; int k il; while (in[k] ! pre[pl]) k; // 在中序里找根的位置 int leftLen k - il; // 左子树节点个数 root-lchild Build(pre, pl 1, pl leftLen, in, il, k - 1); root-rchild Build(pre, pl leftLen 1, pr, in, k 1, ir); return root; }这里leftLen的推导必须想清楚中序里根的左边有k - il个元素它们就是左子树的所有节点所以前序里从pl1开始连续leftLen个元素就是左子树的前序。这个下标关系一旦搞混建出来的树形状就是错的而它往往不会编译报错只会遍历结果不对非常费时间。4.3 哈夫曼树和哈夫曼编码哈夫曼树的考题一般是给一组权值让你画树、算 WPL带权路径长度。构造方法是从小到大取两个权值合并把它们的和放回集合继续取直到只剩一个节点。WPL 就是所有叶子节点的权值乘以其路径长度之和也可以理解成所有非叶节点的权值之和这两个算法结果一样用后者算更快。提示算哈夫曼树时先把权值排序写下来每合并一次就更新这一组数用草稿纸一步步画比在脑子里跳步靠谱得多。左右子树谁大谁小不影响 WPL但考点常要求左小右大按习惯写就行。4.4 二叉排序树和平衡树二叉排序树要求左子树全部小于根、右子树全部大于根。查找、插入、删除都基于这条性质。删除是最麻烦的分三种情况叶子直接删单孩子用孩子顶替双孩子找中序前驱或后继替换。这三种情况一定要能默写判断逻辑。平衡二叉树AVL的考点一般停留在理论上四种旋转类型的识别。LL 型右旋一次RR 型左旋一次LR 型先左后右RL 型先右后左。看到插入后不平衡先找最小不平衡子树的根再看插入位置在根的哪个方向判断类型。这部分不要求写完整代码但要在简答题里判断正确。5. 图存储结构的选择决定了后续算法的复杂度5.1 邻接矩阵和邻接表怎么选图的存储是后面所有算法的地基。邻接矩阵用一个二维数组a[i][j]表示 i 到 j 有没有边邻接表每个顶点挂一个链表只存实际存在的边。维度邻接矩阵邻接表空间O(V²)O(VE)判断两点是否有边O(1)O(度数)遍历某点的所有邻边O(V)O(度数)适合图类型稠密图稀疏图考试常问一个有一百个顶点、两百条边的图适合用哪种答案显然是邻接表因为邻接矩阵要一万个格子实际只有四百个位置非零。反过来如果要频繁判断两个点之间有没有边邻接矩阵更划算。5.2 深度优先和广度优先DFS 用递归或栈BFS 用队列两者都要维护一个visited数组防止重复访问。#define MAXV 100 typedef struct ArcNode { int adjvex; struct ArcNode *next; } ArcNode; typedef struct VNode { int data; ArcNode *first; } VNode, AdjList[MAXV]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; int visited[MAXV]; void DFS(ALGraph *G, int v) { visited[v] 1; printf(%d , G-vertices[v].data); for (ArcNode *p G-vertices[v].first; p; p p-next) if (!visited[p-adjvex]) DFS(G, p-adjvex); } void BFS(ALGraph *G, int v) { int q[MAXV], front 0, rear 0; visited[v] 1; q[rear] v; while (front rear) { int u q[front]; printf(%d , G-vertices[u].data); for (ArcNode *p G-vertices[u].first; p; p p-next) { if (!visited[p-adjvex]) { visited[p-adjvex] 1; q[rear] p-adjvex; } } } }BFS 的一个关键细节是入队时就标记 visited。如果等到出队才标记同一个顶点可能被多个邻居重复入队虽然结果还对但复杂度会退化这是很多同学的失分点。5.3 拓扑排序和最短路径拓扑排序适用于有向无环图做法是维护每个顶点的入度把入度为零的顶点依次入队并删除它的出边同时把邻接点的入度减一。如果最后输出的顶点数小于总顶点数说明图里有环。这道题结合队列和图的存储是综合题的常客。最小生成树有 Prim 和 Kruskal 两种。Prim 从任意顶点出发每次选连接已选集合和未选集合的最短边复杂度 O(V²)适合稠密图Kruskal 把所有边排序后从小到大依次加入用并查集判断是否成环复杂度 O(E log E)适合稀疏图。最短路径的 Dijkstra 算法必须掌握。它用一个 dist 数组记录源点到各点的当前最短距离每轮选出未访问点中 dist 最小的那个用它去松弛邻居重复直到所有点都被访问。要注意 Dijkstra 不能处理负权边这是判断题的常见陷阱。6. 查找与排序稳定性清单和哈希冲突是拉分项6.1 排序算法对比表排序这一章的知识点密度特别高一张表能覆盖大半分数算法平均时间最坏时间空间稳定性直接插入O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定简单选择O(n²)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(r)稳定稳定性判断有个小技巧只要发生隔着好几个元素交换的操作通常就不稳定。选择排序会因为把后面的小元素直接甩到前面而打乱顺序快排因为分治跨越交换而不稳定堆排序因为堆顶和堆尾交换而不稳定。6.2 快排和堆排必须能手写快速排序是考得最多的排序算法核心是 partitionint Partition(int a[], int low, int high) { int pivot a[low]; // 取第一个元素为基准 while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; while (low high a[low] pivot) low; a[high] a[low]; } a[low] pivot; return low; } void QuickSort(int a[], int low, int high) { if (low high) { int p Partition(a, low, high); QuickSort(a, low, p - 1); QuickSort(a, p 1, high); } }堆排序稍微绕一点堆调整是核心。下面是下标从 1 开始的大顶堆版本void HeapAdjust(int a[], int k, int n) { int t a[k]; for (int i 2 * k; i n; i * 2) { if (i n a[i] a[i 1]) i; // 取较大的孩子 if (t a[i]) break; a[k] a[i]; k i; } a[k] t; } void HeapSort(int a[], int n) { for (int i n / 2; i 1; i--) HeapAdjust(a, i, n); // 建堆 for (int i n; i 1; i--) { int t a[1]; a[1] a[i]; a[i] t; // 堆顶与末尾交换 HeapAdjust(a, 1, i - 1); // 重新调整前 i-1 个 } }建堆一定要从n/2往下调整因为编号大于n/2的节点都是叶子本身已经满足堆性质不用调。这个起点写错建出来的就不是堆后面全乱。6.3 哈希表和平均查找长度哈希表的考点集中在冲突处理和 ASL 计算。除留余数法就是取模开放地址法的线性探测是冲突了就往后一格一格找链地址法是同一个位置拉一条链表。平均查找长度 ASL 要分别算成功和失败两种情况。举个具体的例子表长 11哈希函数H(key) key % 11依次插入 22、41、53、46、30用线性探测。22 落在 041 落在 853 落在 946 落在 230 原本落在 8冲突后探测到 10。成功情况下的查找次数分别是 1、1、1、1、3总次数 7除以元素个数 5 得到 ASL 成功为 1.4。这类题只要把每一步落点写清楚基本不会错。提示算哈希 ASL 时画一张表格列出下标和对应的关键字再数每个关键字找了几次。失败情况的 ASL 则要看从每个初始位置出发直到空位需要比较几次不要和成功情况搞混。7. 上机答题时才明白的几个教训先说个真实经历。我有个同学复习时把每章的伪代码都背了考场上看到链表逆置题特别开心写满了半页纸结果评卷时被扣了一大半分。原因是他的函数定义里struct LNode的next写成了int类型编译其实过不了只是笔试看不见编译错误。从那以后我养成了一个习惯每写一个结构体定义先检查字段类型和指针星号这是数据结构 C语言版里最基础也最容易被忽略的细节。第二个教训是边界条件。链表题要考虑空表、单节点数组题要考虑长度 0 和长度 1树题要考虑空树和只有一个节点的树栈和队列要考虑判空判满。这些情况在纸面上不会主动提醒你但评卷人一定会看你的循环条件有没有防住。我建议写任何循环前先在草稿纸上标出进入循环的初始状态和退出循环的终止条件很多死循环和越界就是这么提前发现出来的。第三个是内存管理。考试里可能会要求你用malloc建节点那么建完最好顺手写一句检查虽然笔试不跑但能体现工程意识BiTree node (BiTree)malloc(sizeof(BiTNode)); if (node NULL) return NULL; // 分配失败直接返回第四是时间分配。我一般建议算法设计题留足三十分钟以上先把思路用一两句注释写下来再填代码。想不清楚就写能跑通的朴素解别为了炫技卡在一半。曾经有同学在快排的优化上纠结了二十分钟结果后面的链表题没时间写得不偿失。最后一个经验是关于模板。数据结构里真正能形成模板的东西不多但有几个是值得背的链表的头插和尾插、快慢指针、二叉树的递归遍历、非递归中序、图的 DFS 和 BFS、快排 partition、堆调整。把这七八段代码练到不用思考就能写出来考场上你就能把精力放在理解题意和设计思路上而不是临时拼凑语法。我自己的做法是考前一周每天挑两个模板默写一遍写完拿编译器跑一组数据验证。默写和敲键盘的感觉不一样手写代码没有补全提示更容易暴露你对分号、括号、指针符号的记忆漏洞。数据结构这东西看会了和写出来之间隔着一整条河只有真正动过手考试那天心里才有底。 数据结构考试复习：C语言手写核心代码与算法设计题实战
1. 考卷上的数据结构到底在考什么翻开任何一份数据结构试卷你会发现真正拉开差距的从来不是选择题。数据结构这门课的分数结构很有意思前面那些概念题、判断题、复杂度选择认真背两轮基本都能拿到七成以上但最后那道二十分左右的算法设计题往往才是决定你是六十分还是八十五分的地方。我见过太多人把王道数据结构电子版翻烂遍历、排序、查找的知识点总结抄了好几页结果一上手写代码指针就飞了循环边界就错了考试时间全耗在调一个数组越界上。这就是为什么标题里我特意强调附代码。数据结构用 C语言描述不是随便选的它的每个抽象概念最终都要落到结构体、指针和内存上。链表是结构体指针串起来的一串节点栈是一个数组加一个栈顶下标树是带两个指针的结构体图是二维数组或者指针数组。你不亲手把这些写出来考试时脑子里就只有名词没有形状题目稍微变个说法你就懵了。下面这张表是我根据近几年期末复习和考研数据结构的常见卷面结构整理的可以对着它安排复习优先级卷面题型常见分值主要考点是否必须动手写选择题20-30概念辨析、复杂度、存储结构对比否但要对代码有画面感填空题10-20求遍历序列、求平均查找长度、求 WPL否判断题10稳定性、判空判满条件、性质定理否简答与画图15-25画哈夫曼树、画邻接表、画判定树半动手算法设计题20-30链表操作、树的遍历、排序实现必须动手我自己的复习策略是把每一类结构单独建一个.c文件从零把它写出来、编译通过、手动构造几组垃圾数据跑一遍。这个过程看着笨但它同时解决三件事——你记住了结构体定义、你记住了边界条件、你还顺便练了 C语言指针。数据结构学习里最值钱的就是这种肌肉记忆考场上你不需要回忆手先写出来了。还有一点很多人复习时喜欢追求最优解比如链表题一定要用快慢指针排序一定要写非递归。但考试评卷往往看的是思路是否完整、代码是否可运行。一个能跑通的朴素解法比一个卡在半截的最优解分数高得多。所以下面的代码我都尽量先给能直接跑的版本再补充可以拿加分的优化思路。2. 线性表与链表指针题占分最高也最容易翻车2.1 顺序表和链表的取舍不是背出来的复习线性表最先遇到的对比题就是顺序表和链表的选择。很多人死记链表插入删除快、顺序表随机访问快但考试会问你更细的场景比如频繁在表尾插入、很少删除、需要按下标查询选哪个。这时候你要能立刻答出顺序表并说清楚为什么表尾插入在顺序表里是 O(1)不考虑扩容而链表还要先遍历到尾。维度顺序表单链表存储方式连续内存离散节点加指针随机访问O(1)O(n)插入删除O(n)需移动元素O(1)前提是已知前驱空间开销可能预留过多每节点多一个指针缓存友好度高低顺序表里有个必考的小计算长度为 n 的顺序表插入一个元素平均要移动多少个答案是 n/2删除一个元素平均要移动 (n-1)/2 个。这两个数字不要死背自己用插入位置从 1 到 n1各自移动 n-i1 个元素求和再除以 n1推一遍考场上忘了能当场算出来。2.2 单链表就地逆置三行核心逻辑要刻进脑子单链表逆置是算法设计题里出现频率极高的一类。带头结点的链表逆置本质是把每个节点依次头插到 head 后面typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 带头结点的单链表就地逆置 LinkList Reverse(LinkList head) { LNode *p head-next; // p 指向第一个数据节点 head-next NULL; // 先断开后面靠头插重建 while (p ! NULL) { LNode *q p-next; // 先存住后继否则断链后找不回来 p-next head-next; head-next p; p q; } return head; }这里的顺序不能错先存q p-next再改p-next最后移动p。我当年写错最多的地方就是先把p-next改了然后p p-next直接指向自己死循环不说还看不出错在哪。这个先保存后继再改指针的习惯是所有链表题的通则删节点、拆链表、合并链表都用得上。2.3 快慢指针一道题会了能套十道快慢指针是链表题的分水岭。判断有环、找中间节点、找倒数第 k 个节点全靠它。核心思想是让两个指针以不同速度走快的到头了或者追上慢的了就能得到位置信息。// 找中间节点偶数个节点时返回靠前的那个 LNode *FindMid(LinkList head) { LNode *slow head-next, *fast head-next; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; } return slow; } // 找倒数第 k 个节点不存在返回 NULL LNode *FindKthFromEnd(LinkList head, int k) { LNode *fast head-next; for (int i 0; i k; i) { if (fast NULL) return NULL; // 链表长度不足 k fast fast-next; } LNode *slow head-next; while (fast ! NULL) { slow slow-next; fast fast-next; } return slow; } // 判断是否有环Floyd 判圈 int HasCycle(LinkList head) { LNode *slow head, *fast head; while (fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; if (slow fast) return 1; } return 0; }写这类题的时候最容易出错的是循环条件。while (fast ! NULL fast-next ! NULL)里的两个判断缺一不可少了任何一个遇到空链表或者单节点链表时fast-next-next就会访问空指针。C语言里访问空指针不一定立刻报错可能读到一堆垃圾值这种题一旦出错很难靠调试发现只能靠写的时候条件写全。2.4 链表题的几个隐藏坑第一个坑是头结点。很多教材的链表带头结点有些题又不要头结点答题前务必看清楚题干里结构体的定义别自己想当然。带头结点的好处是插入删除第一个数据节点不用特判所以考试里默认带头结点的情况居多。第二个坑是释放内存的顺序。删除节点时如果先free(p)再想访问p-next那就是标准的使用后释放错误程序行为不可预测。正确写法是先存后继再 free。第三个坑是尾节点的next没置空。用头插法建完链表最后一个节点的next必须显式给 NULL否则遍历时可能跑到内存深处的野指针上考试时表现为输出莫名其妙的一串数很难定位。提示链表题写完拿三个输入验证——空表、只有一个节点、有重复数据的表。这三组能过基本就没问题了。3. 栈和队列边界判断是命门3.1 顺序栈的入栈出栈顺序顺序栈用数组加一个top下标就能实现约定top -1表示空栈。入栈是先top再赋值出栈是先取值再top--这两个顺序搞反栈顶元素就会错位。#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; } SqStack; void InitStack(SqStack *s) { s-top -1; } int StackEmpty(SqStack *s) { return s-top -1; } int Push(SqStack *s, int x) { if (s-top MAXSIZE - 1) return 0; // 栈满 s-data[s-top] x; return 1; } int Pop(SqStack *s, int *x) { if (s-top -1) return 0; // 栈空 *x s-data[s-top--]; return 1; }栈的经典应用是括号匹配。思路很直白遇到左括号入栈遇到右括号就看栈顶是不是对应的左括号最后栈必须为空。int BracketMatch(const char *s) { char st[256]; int top -1; for (int i 0; s[i] ! \0; i) { char c s[i]; if (c ( || c [ || c {) { st[top] c; } else if (c ) || c ] || c }) { if (top -1) return 0; // 右括号多了 char t st[top--]; if ((c ) t ! () || (c ] t ! [) || (c } t ! {)) return 0; } } return top -1; // 左括号必须全部匹配掉 }中缀转后缀也是必考。规则是操作数直接输出运算符与栈顶比较优先级栈顶优先级不低于当前运算符就弹出左括号一律入栈右括号一直弹到左括号为止。这套规则背下来容易但考场上手动推一个ab*c-d这样的式子还是容易乱建议平时至少手推十组。3.2 循环队列三种判满方案循环队列的判空判满是填空和简答的高频点。核心矛盾是front rear既可能是空也可能是满所以要引入额外信息区分。常见有三种方案方案判空条件判满条件代价牺牲一个存储单元front rear(rear1)%M front少用一个空间加 size 计数器size 0size M多一个变量加 tag 标记rear front 且 tag 0rear front 且 tag 1多一个变量考试默认第一种。实现时最容易写错的是rear的推进它一定要取模不能直接自增#define QMAX 100 typedef struct { int data[QMAX]; int front, rear; } SqQueue; void InitQueue(SqQueue *q) { q-front q-rear 0; } int QueueEmpty(SqQueue *q) { return q-front q-rear; } int QueueFull(SqQueue *q) { return (q-rear 1) % QMAX q-front; } int EnQueue(SqQueue *q, int x) { if (QueueFull(q)) return 0; q-data[q-rear] x; q-rear (q-rear 1) % QMAX; // 先放数据再动指针 return 1; } int DeQueue(SqQueue *q, int *x) { if (QueueEmpty(q)) return 0; *x q-data[q-front]; q-front (q-front 1) % QMAX; return 1; }有个很隐蔽的错法入队时先动rear再存数据这样第一个元素会被写在下标 1 而不是 0判满判空的逻辑就全乱了。记住先存后动和先取后动队列就稳了一半。3.3 栈和队列互相实现还有一类题喜欢考两个栈实现队列和两个队列实现栈。前者的核心是一个入栈一个出栈出栈为空时把入栈全部倒过来后者更绕一点因为队列是先进先出需要一个队列当搬运工。这类题考察的是你对两种结构顺序特性的理解画个图把元素流动走一遍就清楚了不用背代码。4. 树与二叉树遍历反推和哈夫曼是必考三件套4.1 遍历序列怎么反推二叉树的遍历是所有考题里出得最密的。前序、中序、后序、层次前三个是递归定义层次用队列实现。反推题的一般套路是前序第一个元素或后序最后一个元素一定是根拿着根去中序里切分左右子树然后递归。这个套路能解决绝大多数给两个序列求第三个的题目。已知能否唯一确定关键点前序 中序能前序首元素是根后序 中序能后序末元素是根前序 后序不能无法区分单子树方向层次 中序能层次首元素是根前序加后序不能唯一确定这是判断题的常客原因是当某个节点只有一个孩子时你分不清它在左还是在右。顺序存储的完全二叉树还有一组必背性质若节点编号从 1 开始节点 i 的左孩子是 2i右孩子是 2i1父节点是 i/2。另外叶子节点数 n0 和度为 2 的节点数 n2 满足n0 n2 1这条性质结合节点总数能推出很多题目。4.2 遍历代码和建树代码递归遍历几乎是送分但非递归的中序遍历经常考因为它把栈和树的遍历结合起来了。typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void PreOrder(BiTree T) { if (T) { printf(%c , T-data); PreOrder(T-lchild); PreOrder(T-rchild); } } // 非递归中序遍历一路向左压栈弹一个就往右走 void InOrderNoRec(BiTree T) { BiTree st[100]; int top -1; BiTree p T; while (p ! NULL || top ! -1) { while (p ! NULL) { st[top] p; p p-lchild; } p st[top--]; printf(%c , p-data); p p-rchild; } }由前序和中序建树是算法设计题里很典型的一道它把递归和数组下标切分结合起来// pre[pl..pr] 是前序in[il..ir] 是中序下标均为闭区间 BiTree Build(char pre[], int pl, int pr, char in[], int il, int ir) { if (pl pr) return NULL; BiTree root (BiTree)malloc(sizeof(BiTNode)); root-data pre[pl]; int k il; while (in[k] ! pre[pl]) k; // 在中序里找根的位置 int leftLen k - il; // 左子树节点个数 root-lchild Build(pre, pl 1, pl leftLen, in, il, k - 1); root-rchild Build(pre, pl leftLen 1, pr, in, k 1, ir); return root; }这里leftLen的推导必须想清楚中序里根的左边有k - il个元素它们就是左子树的所有节点所以前序里从pl1开始连续leftLen个元素就是左子树的前序。这个下标关系一旦搞混建出来的树形状就是错的而它往往不会编译报错只会遍历结果不对非常费时间。4.3 哈夫曼树和哈夫曼编码哈夫曼树的考题一般是给一组权值让你画树、算 WPL带权路径长度。构造方法是从小到大取两个权值合并把它们的和放回集合继续取直到只剩一个节点。WPL 就是所有叶子节点的权值乘以其路径长度之和也可以理解成所有非叶节点的权值之和这两个算法结果一样用后者算更快。提示算哈夫曼树时先把权值排序写下来每合并一次就更新这一组数用草稿纸一步步画比在脑子里跳步靠谱得多。左右子树谁大谁小不影响 WPL但考点常要求左小右大按习惯写就行。4.4 二叉排序树和平衡树二叉排序树要求左子树全部小于根、右子树全部大于根。查找、插入、删除都基于这条性质。删除是最麻烦的分三种情况叶子直接删单孩子用孩子顶替双孩子找中序前驱或后继替换。这三种情况一定要能默写判断逻辑。平衡二叉树AVL的考点一般停留在理论上四种旋转类型的识别。LL 型右旋一次RR 型左旋一次LR 型先左后右RL 型先右后左。看到插入后不平衡先找最小不平衡子树的根再看插入位置在根的哪个方向判断类型。这部分不要求写完整代码但要在简答题里判断正确。5. 图存储结构的选择决定了后续算法的复杂度5.1 邻接矩阵和邻接表怎么选图的存储是后面所有算法的地基。邻接矩阵用一个二维数组a[i][j]表示 i 到 j 有没有边邻接表每个顶点挂一个链表只存实际存在的边。维度邻接矩阵邻接表空间O(V²)O(VE)判断两点是否有边O(1)O(度数)遍历某点的所有邻边O(V)O(度数)适合图类型稠密图稀疏图考试常问一个有一百个顶点、两百条边的图适合用哪种答案显然是邻接表因为邻接矩阵要一万个格子实际只有四百个位置非零。反过来如果要频繁判断两个点之间有没有边邻接矩阵更划算。5.2 深度优先和广度优先DFS 用递归或栈BFS 用队列两者都要维护一个visited数组防止重复访问。#define MAXV 100 typedef struct ArcNode { int adjvex; struct ArcNode *next; } ArcNode; typedef struct VNode { int data; ArcNode *first; } VNode, AdjList[MAXV]; typedef struct { AdjList vertices; int vexnum, arcnum; } ALGraph; int visited[MAXV]; void DFS(ALGraph *G, int v) { visited[v] 1; printf(%d , G-vertices[v].data); for (ArcNode *p G-vertices[v].first; p; p p-next) if (!visited[p-adjvex]) DFS(G, p-adjvex); } void BFS(ALGraph *G, int v) { int q[MAXV], front 0, rear 0; visited[v] 1; q[rear] v; while (front rear) { int u q[front]; printf(%d , G-vertices[u].data); for (ArcNode *p G-vertices[u].first; p; p p-next) { if (!visited[p-adjvex]) { visited[p-adjvex] 1; q[rear] p-adjvex; } } } }BFS 的一个关键细节是入队时就标记 visited。如果等到出队才标记同一个顶点可能被多个邻居重复入队虽然结果还对但复杂度会退化这是很多同学的失分点。5.3 拓扑排序和最短路径拓扑排序适用于有向无环图做法是维护每个顶点的入度把入度为零的顶点依次入队并删除它的出边同时把邻接点的入度减一。如果最后输出的顶点数小于总顶点数说明图里有环。这道题结合队列和图的存储是综合题的常客。最小生成树有 Prim 和 Kruskal 两种。Prim 从任意顶点出发每次选连接已选集合和未选集合的最短边复杂度 O(V²)适合稠密图Kruskal 把所有边排序后从小到大依次加入用并查集判断是否成环复杂度 O(E log E)适合稀疏图。最短路径的 Dijkstra 算法必须掌握。它用一个 dist 数组记录源点到各点的当前最短距离每轮选出未访问点中 dist 最小的那个用它去松弛邻居重复直到所有点都被访问。要注意 Dijkstra 不能处理负权边这是判断题的常见陷阱。6. 查找与排序稳定性清单和哈希冲突是拉分项6.1 排序算法对比表排序这一章的知识点密度特别高一张表能覆盖大半分数算法平均时间最坏时间空间稳定性直接插入O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n²)O(1)不稳定冒泡排序O(n²)O(n²)O(1)稳定简单选择O(n²)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(r)稳定稳定性判断有个小技巧只要发生隔着好几个元素交换的操作通常就不稳定。选择排序会因为把后面的小元素直接甩到前面而打乱顺序快排因为分治跨越交换而不稳定堆排序因为堆顶和堆尾交换而不稳定。6.2 快排和堆排必须能手写快速排序是考得最多的排序算法核心是 partitionint Partition(int a[], int low, int high) { int pivot a[low]; // 取第一个元素为基准 while (low high) { while (low high a[high] pivot) high--; a[low] a[high]; while (low high a[low] pivot) low; a[high] a[low]; } a[low] pivot; return low; } void QuickSort(int a[], int low, int high) { if (low high) { int p Partition(a, low, high); QuickSort(a, low, p - 1); QuickSort(a, p 1, high); } }堆排序稍微绕一点堆调整是核心。下面是下标从 1 开始的大顶堆版本void HeapAdjust(int a[], int k, int n) { int t a[k]; for (int i 2 * k; i n; i * 2) { if (i n a[i] a[i 1]) i; // 取较大的孩子 if (t a[i]) break; a[k] a[i]; k i; } a[k] t; } void HeapSort(int a[], int n) { for (int i n / 2; i 1; i--) HeapAdjust(a, i, n); // 建堆 for (int i n; i 1; i--) { int t a[1]; a[1] a[i]; a[i] t; // 堆顶与末尾交换 HeapAdjust(a, 1, i - 1); // 重新调整前 i-1 个 } }建堆一定要从n/2往下调整因为编号大于n/2的节点都是叶子本身已经满足堆性质不用调。这个起点写错建出来的就不是堆后面全乱。6.3 哈希表和平均查找长度哈希表的考点集中在冲突处理和 ASL 计算。除留余数法就是取模开放地址法的线性探测是冲突了就往后一格一格找链地址法是同一个位置拉一条链表。平均查找长度 ASL 要分别算成功和失败两种情况。举个具体的例子表长 11哈希函数H(key) key % 11依次插入 22、41、53、46、30用线性探测。22 落在 041 落在 853 落在 946 落在 230 原本落在 8冲突后探测到 10。成功情况下的查找次数分别是 1、1、1、1、3总次数 7除以元素个数 5 得到 ASL 成功为 1.4。这类题只要把每一步落点写清楚基本不会错。提示算哈希 ASL 时画一张表格列出下标和对应的关键字再数每个关键字找了几次。失败情况的 ASL 则要看从每个初始位置出发直到空位需要比较几次不要和成功情况搞混。7. 上机答题时才明白的几个教训先说个真实经历。我有个同学复习时把每章的伪代码都背了考场上看到链表逆置题特别开心写满了半页纸结果评卷时被扣了一大半分。原因是他的函数定义里struct LNode的next写成了int类型编译其实过不了只是笔试看不见编译错误。从那以后我养成了一个习惯每写一个结构体定义先检查字段类型和指针星号这是数据结构 C语言版里最基础也最容易被忽略的细节。第二个教训是边界条件。链表题要考虑空表、单节点数组题要考虑长度 0 和长度 1树题要考虑空树和只有一个节点的树栈和队列要考虑判空判满。这些情况在纸面上不会主动提醒你但评卷人一定会看你的循环条件有没有防住。我建议写任何循环前先在草稿纸上标出进入循环的初始状态和退出循环的终止条件很多死循环和越界就是这么提前发现出来的。第三个是内存管理。考试里可能会要求你用malloc建节点那么建完最好顺手写一句检查虽然笔试不跑但能体现工程意识BiTree node (BiTree)malloc(sizeof(BiTNode)); if (node NULL) return NULL; // 分配失败直接返回第四是时间分配。我一般建议算法设计题留足三十分钟以上先把思路用一两句注释写下来再填代码。想不清楚就写能跑通的朴素解别为了炫技卡在一半。曾经有同学在快排的优化上纠结了二十分钟结果后面的链表题没时间写得不偿失。最后一个经验是关于模板。数据结构里真正能形成模板的东西不多但有几个是值得背的链表的头插和尾插、快慢指针、二叉树的递归遍历、非递归中序、图的 DFS 和 BFS、快排 partition、堆调整。把这七八段代码练到不用思考就能写出来考场上你就能把精力放在理解题意和设计思路上而不是临时拼凑语法。我自己的做法是考前一周每天挑两个模板默写一遍写完拿编译器跑一组数据验证。默写和敲键盘的感觉不一样手写代码没有补全提示更容易暴露你对分号、括号、指针符号的记忆漏洞。数据结构这东西看会了和写出来之间隔着一整条河只有真正动过手考试那天心里才有底。