数据结构考试复习：C语言手写核心代码与算法设计题实战

1. 考卷上的数据结构，到底在考什么

翻开任何一份数据结构试卷，你会发现真正拉开差距的从来不是选择题。数据结构这门课的分数结构很有意思，前面那些概念题、判断题、复杂度选择，认真背两轮基本都能拿到七成以上，但最后那道二十分左右的算法设计题，往往才是决定你是六十分还是八十五分的地方。我见过太多人把王道数据结构电子版翻烂，遍历、排序、查找的知识点总结抄了好几页，结果一上手写代码，指针就飞了，循环边界就错了，考试时间全耗在调一个数组越界上。

这就是为什么标题里我特意强调"附代码"。数据结构用 C语言描述不是随便选的，它的每个抽象概念最终都要落到结构体、指针和内存上。链表是"结构体指针串起来的一串节点"，栈是"一个数组加一个栈顶下标"，树是"带两个指针的结构体"，图是"二维数组或者指针数组"。你不亲手把这些写出来，考试时脑子里就只有名词没有形状，题目稍微变个说法你就懵了。

下面这张表是我根据近几年期末复习和考研数据结构的常见卷面结构整理的，可以对着它安排复习优先级：

我自己的复习策略是：把每一类结构单独建一个.c文件，从零把它写出来、编译通过、手动构造几组垃圾数据跑一遍。这个过程看着笨，但它同时解决三件事——你记住了结构体定义、你记住了边界条件、你还顺便练了 C语言指针。数据结构学习里最值钱的就是这种"肌肉记忆"，考场上你不需要回忆，手先写出来了。

还有一点，很多人复习时喜欢追求"最优解"，比如链表题一定要用快慢指针，排序一定要写非递归。但考试评卷往往看的是思路是否完整、代码是否可运行。一个能跑通的朴素解法，比一个卡在半截的"最优解"分数高得多。所以下面的代码我都尽量先给能直接跑的版本，再补充可以拿加分的优化思路。

2. 线性表与链表：指针题占分最高，也最容易翻车

2.1 顺序表和链表的取舍不是背出来的

复习线性表最先遇到的对比题就是顺序表和链表的选择。很多人死记"链表插入删除快、顺序表随机访问快"，但考试会问你更细的场景，比如"频繁在表尾插入、很少删除、需要按下标查询，选哪个"。这时候你要能立刻答出顺序表，并说清楚为什么：表尾插入在顺序表里是 O(1)（不考虑扩容），而链表还要先遍历到尾。

顺序表里有个必考的小计算：长度为 n 的顺序表，插入一个元素平均要移动多少个？答案是 n/2；删除一个元素平均要移动 (n-1)/2 个。这两个数字不要死背，自己用"插入位置从 1 到 n+1，各自移动 n-i+1 个元素，求和再除以 n+1"推一遍，考场上忘了能当场算出来。

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; // 左括号必须全部匹配掉 }

中缀转后缀也是必考。规则是：操作数直接输出，运算符与栈顶比较优先级，栈顶优先级不低于当前运算符就弹出，左括号一律入栈，右括号一直弹到左括号为止。这套规则背下来容易，但考场上手动推一个a+b*c-d这样的式子还是容易乱，建议平时至少手推十组。

3.2 循环队列三种判满方案

循环队列的判空判满是填空和简答的高频点。核心矛盾是front == rear既可能是空也可能是满，所以要引入额外信息区分。常见有三种方案：

考试默认第一种。实现时最容易写错的是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，右孩子是 2i+1，父节点是 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个元素，它们就是左子树的所有节点，所以前序里从pl+1开始连续leftLen个元素就是左子树的前序。这个下标关系一旦搞混，建出来的树形状就是错的，而它往往不会编译报错，只会遍历结果不对，非常费时间。

4.3 哈夫曼树和哈夫曼编码

哈夫曼树的考题一般是给一组权值，让你画树、算 WPL（带权路径长度）。构造方法是从小到大取两个权值合并，把它们的和放回集合继续取，直到只剩一个节点。WPL 就是所有叶子节点的权值乘以其路径长度之和，也可以理解成所有非叶节点的权值之和，这两个算法结果一样，用后者算更快。

提示：算哈夫曼树时先把权值排序写下来，每合并一次就更新这一组数，用草稿纸一步步画，比在脑子里跳步靠谱得多。左右子树谁大谁小不影响 WPL，但考点常要求左小右大，按习惯写就行。

4.4 二叉排序树和平衡树

二叉排序树要求左子树全部小于根、右子树全部大于根。查找、插入、删除都基于这条性质。删除是最麻烦的，分三种情况：叶子直接删，单孩子用孩子顶替，双孩子找中序前驱或后继替换。这三种情况一定要能默写判断逻辑。

平衡二叉树（AVL）的考点一般停留在理论上：四种旋转类型的识别。LL 型右旋一次，RR 型左旋一次，LR 型先左后右，RL 型先右后左。看到"插入后不平衡"，先找最小不平衡子树的根，再看插入位置在根的哪个方向，判断类型。这部分不要求写完整代码，但要在简答题里判断正确。

5. 图：存储结构的选择决定了后续算法的复杂度

5.1 邻接矩阵和邻接表怎么选

图的存储是后面所有算法的地基。邻接矩阵用一个二维数组，a[i][j]表示 i 到 j 有没有边；邻接表每个顶点挂一个链表，只存实际存在的边。

考试常问"一个有一百个顶点、两百条边的图适合用哪种"，答案显然是邻接表，因为邻接矩阵要一万个格子，实际只有四百个位置非零。反过来，如果要频繁判断两个点之间有没有边，邻接矩阵更划算。

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 排序算法对比表

排序这一章的知识点密度特别高，一张表能覆盖大半分数：

稳定性判断有个小技巧：只要发生"隔着好几个元素交换"的操作，通常就不稳定。选择排序会因为把后面的小元素直接甩到前面而打乱顺序，快排因为分治跨越交换而不稳定，堆排序因为堆顶和堆尾交换而不稳定。

6.2 快排和堆排必须能手写

快速排序是考得最多的排序算法，核心是 partition：

int 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 落在 0，41 落在 8，53 落在 9，46 落在 2，30 原本落在 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、堆调整。把这七八段代码练到不用思考就能写出来，考场上你就能把精力放在理解题意和设计思路上，而不是临时拼凑语法。

我自己的做法是考前一周，每天挑两个模板默写一遍，写完拿编译器跑一组数据验证。默写和敲键盘的感觉不一样，手写代码没有补全提示，更容易暴露你对分号、括号、指针符号的记忆漏洞。数据结构这东西，看会了和写出来之间隔着一整条河，只有真正动过手，考试那天心里才有底。