简介：严蔚敏《数据结构（C语言版）习题集》全答案是一份面向计算机专业学生、考研及自学者的一站式习题解答文档，帮助读者逐题对照算法思路与C语言实现，巩固数据结构核心知识。压缩包内共1个PDF文件，大小约431KB，便于下载后直接阅读或打印。目前已有10389人学习浏览，受到较多学习者认可。内容覆盖第一章绪论、第二章线性表等经典习题，包含冒泡排序、斐波那契序列、结构体与枚举、数组边界处理、多项式求值等典型题目的完整代码与简要分析，兼顾原理讲解和代码落地。由于答案按章节组织、思路清晰，既能用于课后自测与查漏补缺，也可作为考研复习或期末备考的速查资料。
1. 这份习题集为什么值得一本正经地刷两遍
严蔚敏老师的《数据结构（C语言版）》大多数科班生手里都有，但真正把它当成"能动手验算"的书来读的人不多。多数人翻开目录看到线性表、树、图、查找、排序，顺手能把概念背出来，真到用C语言把一个双向循环链表的插入写对、把平衡二叉树旋转的角度算明白，就又卡住了。这本习题集的价值恰好不在"记住定义"，而在逼迫你把每个抽象结构落实成指针、数组下标和递归边界。我一般建议两类人认真刷：一类是准备算法岗位笔试、需要在纸上快速写对代码的应届生，另一类是工作三五年后想把自己零散的经验重新对齐到经典数据结构框架上的工程师。客观讲，出版社或课程组流传的"全答案"PDF在内容版本上差异很大——有的带注释、有的只有代码、有的连时间复杂度分析都缺，直接照抄意义有限。更稳妥的做法是把它当成题目来源，自己先解，再用答案对边界条件和空间复杂度。本文按"解题视角—典型结构—复杂度临界—验证方法"的路径，把这本习题集在C语言环境下的打开方式讲清楚。
2. 算法设计题的作答规范：答案"对"不等于"能得分"
习题集里大量题目是"编写算法，实现某某操作"。这些题没有唯一解，评分时看的是结构是否清晰、边界是否完整、复杂度是否达标。用"能跑出正确结果"作为唯一标准，恰恰是刷题最常踩的坑。
2.1 判卷视角下的四个评分维度
我和做过这门课助教的同事聊过，批改算法题基本看四件事：变量命名是否可读、是否先处理空表或空树、循环条件是否依赖长度而不是指针本身、以及空间上有没有无谓的拷贝。答案PDF里很多解法的价值不在代码本身，而在它对这些维度的取舍。以顺序表删除一段连续元素为例：
// 删除顺序表L中从位置i开始长度为k的元素 typedef struct { int *elem; int length; int listsize; } SqList; Status ListDelete_Sq(SqList *L, int i, int k) { if (i < 1 || k < 0 || i + k - 1 > L->length) { return ERROR; // 表头表尾边界统一在这里挡掉 } for (int pos = i + k - 1; pos < L->length; pos++) { L->elem[pos - k] = L->elem[pos]; // 前移长度为k的窗口 } L->length -= k; return OK; }这段代码里的pos - k覆盖了"待删除块右侧元素逐个左移"的全部改动，k为0时循环体不执行，length不变。相比先把第i个元素逐个左移k次的写法，这种窗口移动的语义更接近"整块搬迁"，也更好解释复杂度是O(n)而不是O(n·k)。
2.2 从答案反推"题目到底在考什么"
习题集每个章节的编排有内在顺序：线性表的题集中在"在指定位置插入/删除/合并"，栈和队列的题集中在"用两个栈模拟队列""循环队列的判定"这种结构变换上。看答案时重点不是逐行看懂，而是标出每道题的考点标签，比如：
| 考点 | 典型题面信号 | 答案里常出现的动作 |
|---|---|---|
| 指针操作 | 带头结点/不带头结点 | 判断p->next而非p |
| 递归树 | 先序/中序/后序 | 递归出口写在函数第一行 |
| 空间复杂度 | "不使用额外数组" | 原地倒置/两两交换 |
| 边界设计 | 多个长度参数 | 先在纸上画i、k的区间图 |
这样刷完一章，你会发现自己能总结出题规律——这比背下几十个函数签名有用得多。
2.3 一道题的价值密度怎么判断
不是所有题目都值得花四十分钟死磕。我自己的筛选方法是：题面里出现"设计一个算法使得时间复杂度为O(n)"这种显式约束的，优先级最高；只写"完成插入操作"的，如果思路三分钟就能想到，直接看答案确认边界即可。习题集的PDF版本通常会把这两种题混排，所以你第一遍刷时最好按"约束强→边界多→纯实现"的顺序排序，而不是从第1题按到第n题。
3. 线性表、栈和队列：指针边界就是全部的考点
这章是整本习题集的分母。链表题哪怕改用Java或Python写，核心逻辑仍然不变，但C语言强迫你手动管理结点内存，反而把"谁指向谁"这件事暴露得更清楚。
3.1 带头结点 vs 不带头结点：两种代码风格的分水岭
习题集里"建立单链表""逆置链表""合并有序链表"这类题，答案通常默认带头结点。带头结点的好处是插入和删除不必单独处理表头指针，统一用p = L; while (p->next)的节奏扫描。不带头结点的版本在头插法时每次都要L = newNode，代码更短，但写错概率更高。
3.1.1 就地逆置单链表的三个指针循环
// 带头结点逆置：把数据结点一个个摘下，头插回链表 void ReverseList(LinkList L) { Node *p = L->next; // p指向第一个数据结点 Node *q = NULL; // 暂存后继 L->next = NULL; // 断开头结点，链表变空 while (p) { q = p->next; // 先保留下一个要处理的结点 p->next = L->next; // 当前结点头插到链表最前端 L->next = p; p = q; } }这里最容易被忽略的是循环体内的赋值顺序：q = p->next必须在p->next被改写之前执行。如果把两行顺序颠倒，第三个结点就再也找不回来了。答案里常见的变体是用p->next临时存下一个结点，那样空间少一个指针，但可读性明显下降，实际评分时并不加分。
3.1.2 为什么循环队列的"牺牲一个单元"是标准答案
习题集里有一类经典题：设计循环队列，要求区分队空和队满。教科书式答案牺牲一个存储单元，用(rear + 1) % MAXSIZE == front判断队满。我的建议是，如果题目没限制额外变量，加一个size计数器更不容易写错——因为判空和判满条件变成size == 0和size == MAXSIZE，且入队出队时只需要维护同一个计数器，不需要关心front和rear的相对位置。两种做法在答案PDF里都有，评分时"用size计数"往往被归为"设计合理但非书内默认思路"，不会扣分，反而更容易在面试中体现你清楚两种方案各自要付的代价。
3.2 栈的应用题：中缀转后缀和括号匹配的代码差异
习题集在栈的章节必有一组"表达式求值"和"括号匹配"的题。许多答案在括号匹配时用一个整型计数器来代替真正的栈，但题目明确要求"利用栈"时，这种简化会失分。
// 括号匹配：只有(和)，用栈实现 int MatchBrackets(char *s) { SqStack stack; InitStack(&stack); for (int i = 0; s[i] != '\0'; i++) { if (s[i] == '(') { Push(&stack, s[i]); } else if (s[i] == ')') { if (StackEmpty(&stack)) return 0; // 右括号多出来了 char top; Pop(&stack, &top); } } return StackEmpty(&stack); // 左括号多出来时stack非空 }注意这里每一个return 0都要先判断栈是否为空，而不是只做电平计数。因为表达式里的括号必须严格嵌套，(()))这种输入如果用计数器判断，到最后一个右括号时才可能发现负数，而中间步骤等于提前放过了多种错误序列。栈式匹配的另一个优势是：如果题目扩展到{ [ ( ] ) }，只需要加配对判断，不需要改数据结构。
4. 树与图：从递归形式到遍历框架的进阶
树和图是习题集最厚的部分，也是"看着答案都懂、合上书就懵"的重灾区。这个章节的题不再考单一操作，而是考你对递归出口、访问时机和状态标记的组合能力。
4.1 二叉树遍历框架：前中后序的差别只在visit的位置
很多答案给出这样的标准递归：
void PreOrder(BiTree T) { if (T) { visit(T->data); // 前序：先访问根 PreOrder(T->lchild); PreOrder(T->rchild); } }把visit移到中间就是中序，移到后面就是后序。习题集里真正拉开差距的不是这三种简单遍历，而是"非递归遍历""层次遍历"和"根据遍历序列重建二叉树"。
4.1.1 非递归中序遍历：栈里存的是"还没访问的左子树"
非递归中序的标准写法是：从根开始，一路压左孩子，压到左子树为空后弹出访问，再把指针移到右孩子，重复整个过程。答案PDF里普遍用这种双循环结构：
void InOrder_NonRecursive(BiTree T) { SqStack S; InitStack(&S); BiTree p = T; while (p || !StackEmpty(&S)) { if (p) { Push(&S, p); // 左子树先压栈 p = p->lchild; } else { Pop(&S, &p); // 左子树到头，弹栈访问 visit(p->data); p = p->rchild; // 处理后转向右子树 } } }这里最容易出错的是每次Pop之后p = p->rchild，如果右孩子为空，while外层会再次进入else分支继续弹栈；如果右孩子非空，则会再次进入内层的左压过程。整个写法可以背下来，但要理解栈里永远存储着"祖先链"，而不是某个时刻的全部结点。
4.1.2 层次遍历与二叉树层序重建的对应关系
层次遍历用队列实现，每出一个结点就将其左右孩子入队。习题集里相关的变体包括"求二叉树宽度"和"判断是否为完全二叉树"。
int TreeWidth(BiTree T) { if (!T) return 0; Queue Q; InitQueue(&Q); EnQueue(&Q, T); int width = 0; while (!QueueEmpty(&Q)) { int count = QueueLength(&Q); // 当前层结点数 if (count > width) width = count; for (int i = 0; i < count; i++) { BiTree p; DeQueue(&Q, &p); if (p->lchild) EnQueue(&Q, p->lchild); if (p->rchild) EnQueue(&Q, p->rchild); } } return width; }注意这里必须先取QueueLength(&Q)再用for循环消费完整个当前层，否则出队过程中长度不断变化，会把两层混在一起。这个"按层快照"的模式在树形结构的BFS里非常通用，图的最短路径层数统计也用它。
4.2 图的两种遍历：DFS栈还是递归，BFS队列的入队时机
图章节的题集中在"邻接矩阵 vs 邻接表的选择""DFS和BFS代码""最小生成树、最短路径"。习题集答案里，DFS的邻接表实现常常直接用递归，因为递归本身就是栈；而邻接矩阵实现时用visited数组标记，这恰恰是题目的第一个考点。
void DFS_AMGraph(AMGraph G, int v, int visited[]) { visited[v] = 1; visit(G.vexs[v]); for (int w = 0; w < G.vexnum; w++) { if (G.arcs[v][w] != 0 && !visited[w]) { DFS_AMGraph(G, w, visited); // 递归深入 } } }这个函数有两个必须提的点：一是递归前必须先置visited再进入下一层，如果在递归深处才标记，会重复访问祖先结点；二是邻接矩阵的DFS复杂度固定为O(n²)，不管图里实际边有多少条。习题集里的真题经常问"为什么邻接表的DFS时间复杂度和矩阵不同"，答案就是邻接矩阵的for循环扫描了整行。 图搜索中对visited的检查时机，是区分理解深浅的分水岭。
4.3 连通分量与生成树：答案里常见的省略说明
习题集里"求连通分量个数"的常见做法是对每个未访问顶点调用一次DFS或BFS，调用次数就是连通分量数量。很多答案的代码只有主函数和visited数组的声明，却省略了"整个图的顶点可能不是连通图"这个前提。实际阅卷时，直接用顶点循环覆盖所有起点的人拿满分，而只写一个DFS的只能说明你记住了遍历本身，没理解图的结构。这个意识和代面试中的"岛屿数量"完全一致。
5. 查找和排序：答案里反复出现的复杂度临界点
查找和排序章节的答案最适合用来核对"理论上限与实际实现"之间的差距。习题集里哈希表、二叉排序树、快速排序、堆排序、归并排序几乎是固定套餐，而这些题恰好也是"数据结构C语言版"热词里检索量最大的部分。
5.1 顺序查找和折半查找：边界条件不看死记，看区间表示
折半查找的坑集中在while条件、left和right的更新方式上。习题集答案里最常见的是左闭右闭区间写法：
int BinarySearch(int a[], int n, int key) { int left = 0, right = n - 1; while (left <= right) { int mid = left + (right - left) / 2; // 防溢出写法 if (a[mid] == key) return mid; else if (a[mid] < key) left = mid + 1; else right = mid - 1; } return -1; }两个细节值得对比：left + (right - left) / 2等价于(left + right) / 2，但在数组很大时避免整型溢出；而while (left <= right)对应左闭右闭区间，若改成while (left < right)，则返回位置需要额外考虑。习题集的答案通常不会给你这两种变体，只给一种，但真正考试时的选择题会考这两个边界条件的正误，所以看答案时要主动做"把LEFT改成RIGHT、把<=改成<"的自测。
5.2 二叉排序树的删除：三种情况的完整处理
删除结点是查找章节的重头戏。答案里把被删结点分成三类：叶子结点、只有左或右子树、左右子树都存在。第三种情况的标准做法是"用左子树最大结点或右子树最小结点替换被删结点，然后删除那个替换结点"。写这道题时，我建议用指针的三层结构实现，否则特别容易多写代码：
BiTree DeleteBST(BiTree T, int key) { if (!T) return T; if (key < T->data) { T->lchild = DeleteBST(T->lchild, key); // 递归到左子树 } else if (key > T->data) { T->rchild = DeleteBST(T->rchild, key); // 递归到右子树 } else { if (!T->lchild) { BiTree temp = T->rchild; free(T); return temp; // 只有右子树或无子树 } else if (!T->rchild) { BiTree temp = T->lchild; free(T); return temp; // 只有左子树 } else { BiTree minNode = T->rchild; while (minNode->lchild) minNode = minNode->lchild; T->data = minNode->data; // 用右子树最小值覆盖 T->rchild = DeleteBST(T->rchild, T->data); // 删除右子树里那个最小值结点 } } return T; }递归返回新子树根这个手法，让父结点的指针能自动接到删除后的结果，不需要额外写父亲指针。很多"全答案PDF"喜欢用二级指针改变原结点，思路更省内存，但可读性差很多。我一般推荐上面的递归替换写法，因为它的结构直接展示了"每一次递归都返回一个完整的子树根"，与后续讲到AVL树的旋转调整时也衔接得上。
5.3 排序章节的必背结论：稳定性的判定不看代码看"等值元素的相对次序"
习题集里"请分析各排序算法的稳定性"这类问答，在C语言版的习题集里经常出成填空题。直接记结论：插入排序、冒泡排序、归并排序和基数排序是稳定的；简单选择排序、快速排序和堆排序不稳定。快速排序的不稳定例子是枢轴交换后跨越了等值元素，堆排序的不稳定来自堆调整时父子交换可能改变相同键值元素的相对顺序，而"简单选择排序不稳定"这个结论很多人会记错——因为"选择"听起来像是按次序来的。
| 排序算法 | 平均时间 | 最坏时间 | 空间 | 稳定性 |
|---|---|---|---|---|
| 直接插入 | O(n²) | O(n²) | O(1) | 稳定 |
| 快速排序 | O(nlogn) | O(n²) | O(logn) | 不稳定 |
| 简单选择 | O(n²) | O(n²) | O(1) | 不稳定 |
| 堆排序 | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
| 归并排序 | O(nlogn) | O(nlogn) | O(n) | 稳定 |
这张表的意义不只是背，而是用于选型：内存紧张选堆排序，要求稳定选归并，数据基本有序选插入。习题集后面有几道综合应用题，会给出一个数组让你"分别写出每一步的排序过程"，这类题只有亲手演算一遍才能过关，光看答案是没用的。
5.4 哈希表的查找长度：平均查找长度的计算是纯算术，别者在代码里找
哈希章节的题目通常给出一组关键字、一个表长和一个哈希函数，然后要求计算线性探测再散列或链地址法下的平均查找长度。计算时要注意：查找成功时比较次数等于"探测次数"，而查找失败时要从每个哈希位置出发，一直探测到空位为止。答案PDF里这段往往只有结果没有过程，容易让人误以为ASL很抽象，实际就是加减乘除。我在刷题时会先在草稿纸上画出表的下标槽位，把每个关键字的探测路径标出来，再数总比较次数。这个方法对"哈希排序"这类热词下的题目也适用。
6. 用测试代码验证习题答案的边界情况
最后一章回到一个非常务实的习惯：拿到书上的答案代码时，不要直接用肉眼判断对错，把它们编译执行一遍，并且主动构造边界测试，往往能发现答案印刷或排版中的笔误。很多"习题集全答案"PDF是从早期版本扫描或重排的，代码可能存在括号缺失、变量名错位，甚至是"mid = (low+high)/2"这种在极端输入下溢出的写法。下面这个流程可以帮你在十分钟内验证一小节的所有答案。
6.1 最小验证环境：gcc + 一个带断言的主函数
我自己习惯的做法是：把习题答案复制到一个answer_check.c里，然后再写一个test_answer.c，用assert测试边界。
#include <stdio.h> #include <assert.h> #include <string.h> // 测试折半查找的边界：空数组、单元素数组、目标不存在 int BinarySearch(int a[], int n, int key); // 声明习题答案函数 void test_binary_search(void) { int empty[] = {0}; assert(BinarySearch(empty, 0, 5) == -1); // 空数组必然返回-1 int one[] = {3}; assert(BinarySearch(one, 1, 3) == 0); // 单元素命中 assert(BinarySearch(one, 1, 4) == -1); // 单元素不命中 int arr[] = {1, 3, 5, 7, 9, 11}; assert(BinarySearch(arr, 6, 1) == 0); // 最左边界 assert(BinarySearch(arr, 6, 11) == 5); // 最右边界 assert(BinarySearch(arr, 6, 6) == -1); // 不存在且位于区间中间 printf("binary search boundary tests passed\n"); } int main(void) { test_binary_search(); return 0; }编译命令为gcc -g -Wall -Werror answer_check.c test_answer.c -o check，加上-Wall -Werror后，任何未初始化变量或比较类型不匹配都会被拦截。上面的测试故意覆盖了"空数组""单元素""左右端点""中间不存在"四种情况，比随便跑一个正常输入要有效得多。
6.2 链表和树结构如何构造"最小复现场景"
验证链表的逆置和二叉树的删除时，不能靠手打几十行数据，我会直接写一个从数组建链表的工具函数：
LinkList ListFromArray(int arr[], int n) { LinkList L = (Node*)malloc(sizeof(Node)); L->next = NULL; Node *tail = L; for (int i = 0; i < n; i++) { Node *newNode = (Node*)malloc(sizeof(Node)); newNode->data = arr[i]; newNode->next = NULL; tail->next = newNode; tail = newNode; } return L; }配合题目场景，把K取1、n、n+1三种情况分别传入。链表逆置时特别要测长度为0、1、2三种情况，这是循环里指针跟踪最容易错的地方。对二叉树删除，我一般先建一棵只有根、只有左子树、只有右子树、左右子树都存在的四棵树分别调用删除函数，看看返回值是不是符合预期。这样做的另一个好处是：如果书里答案是错的，你的用例可以直接定位到是哪一行出了问题。
6.3 输出可测性：把遍历结果序列化
树的遍历题目直接print到标准输出很难断言结果，我统一把它们序列化成字符串或int数组再比较。例如中序遍历时，用一个全局数组收集访问顺序，然后在测试里用memcmp比较。这个方法同样适用于图的BFS和DFS顺序判断。做完这些，再看一遍章节答案里的时间复杂度分析，就能形成"代码正确、边界正确、复杂度也正确"的完整判断。习题集PDF说到底只是静态资源，真正值钱的是这些静态答案在你环境里被编译、被测试、被修正的过程。
本文还有配套的精品资源，点击获取
