简介：严蔚敏《数据结构（C语言版）》第二版算法设计题答案与书中算法源码包，适配CLion 2020~2021开发环境，面向正在学习数据结构、需要对照参考答案与源码进行验证的本科生、考研读者，以及需要应对期末考试的在校生。压缩包大小仅三点一四兆字节，内含C语言源码、CMake构建配置及使用说明文档，已有超过一千二百人次浏览学习。作者结合书中章节顺序，对部分算法进行了优化，并逐一纠正参考答案中的错误；同时将可能触发的bug及其触发条件、算法不同实现方法、优化思路以及执行过程，以批注形式详细说明；对于常见运行异常，也给出了主动规避与排错建议。读者可直接部署CMake工程运行验证，也可在阅读答案时同步查看对应源码与提示，便于跟踪函数调用过程，适合作为课后自学、作业自查与考研复习的辅助材料。附赠的五本经典算法或数据结构书籍链接已打包在说明文档中，方便拓展阅读。
1. 严蔚敏《数据结构》第二版的算法设计题与源码：这本教材的答案为什么值得自己重做一遍
很多人在期末周或考研复习时抱着严蔚敏这本《数据结构（C语言版）》第二版，翻到每章结尾的算法设计题就开始发怵：书上的伪代码怎么改都编译不过，“源码版”到底长什么样也不清楚。这本书的算法描述用的是类C的ADT语言，和真正能跑的C程序隔着三层墙——类型要自己typedef、引用要改成指针、函数指针和内存管理都要重新补全。这篇文章要落地的就是这三件事：把书中算法源码落成可运行文件，把算法设计题的答案按题型拆成通用套路，再用GDB和断言验证它确实对。适合人群很明确：在准备数据结构期末复习、数据结构考研或408的人，以及那些靠实验报告拿学分但不想抄错代码的学生。
2. 把书中伪代码改造成可运行源码：顺序表、链表和二叉树的最小样例
2.1 为什么书上的代码不能直接编译：伪代码与C语言的三个错位
严蔚敏教材的算法描述是ADT风格的类C语言，它优先表达逻辑，不保证能喂给编译器。最常见的三处错位是Status和ElemType这种自定义类型、传参用的引用&，还有malloc的返回值与强制类型转换。这三处不处理，gcc第一行就会报错。
| 书中的伪代码惯用写法 | 纯C可运行落地写法 | 要这么改的原因 |
|---|---|---|
| Status | typedef int Status，配合OK/ERROR宏 | 书中Status是抽象返回类型，C编译器不认识 |
| ElemType | typedef int ElemType | 让线性表、树、图的元素类型可统一替换 |
| 函数参数写ElemType &e | 写成ElemType *e，调用处传&e | &是C++引用语法，纯C不支持 |
| malloc不写类型转换 | (ElemType *)malloc(sizeof(ElemType)*cap) | 旧标准下void*隐式转换会有警告，显式转换更稳 |
我一般会在每个.c文件的顶部放一个“可编译最小骨架”：头文件、类型定义、OK/ERROR宏、打印函数。这样每个算法题的源码文件都能单独编译，不用依赖工程配置。这个习惯后来帮我省了很多事，因为实验报告和复试上机都要求你交一个能直接跑的.c文件。
2.2 顺序表：InitList 与 ListInsert 的落地改写
顺序表的核心是数组加长度加容量三个字段。书中ListInsert的插入逻辑依赖“从尾到头后移”的写法，这对新手是个大坑：如果从头开始后移，后面的元素会被覆盖掉。正确的移动方向只有一个，就是从最后一个元素开始，逐个往后挪。
#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 #define OK 1 #define ERROR 0 typedef int Status; typedef int ElemType; typedef struct { ElemType *data; // 堆上分配的数组 int length; // 当前元素个数 int capacity; // 分配容量 } SqList; Status InitList(SqList *L, int cap) { L->data = (ElemType *)malloc(sizeof(ElemType) * cap); if (!L->data) return ERROR; L->length = 0; L->capacity = cap; return OK; } Status ListInsert(SqList *L, int pos, ElemType e) { int i; if (pos < 1 || pos > L->length + 1) return ERROR; // 合法位置是 1..length+1 if (L->length >= L->capacity) return ERROR; // 容量不足，简化处理不扩容 for (i = L->length; i >= pos; i--) { L->data[i] = L->data[i - 1]; // 从最后一个元素开始后移 } L->data[pos - 1] = e; // 序号转下标要减1 L->length++; return OK; } int main(void) { SqList L; InitList(&L, MAXSIZE); ListInsert(&L, 1, 10); ListInsert(&L, 2, 20); printf("length=%d, first=%d\n", L.length, L.data[0]); free(L.data); // 堆内存记得释放 return 0; }逻辑说明：Status在这里是int的别名，返回OK或ERROR比返回void更能表达插入是否成功；pos是题面里的序号，从1开始，而数组下标从0开始，所以写数据时要用pos-1；后移循环从L->length开始，每轮把前一个位置的值复制到当前位置，这样不会覆盖还没移动的元素。参数说明：cap是初始容量，MAXSIZE取100对大多数课后题够用；如果题目要求“动态扩容”，把容量不足时的ERROR分支改成realloc重新分配即可，这也是顺序表这章常考的变体。
2.3 链表逆置和二叉树遍历：指针操作与回调函数
单链表就地逆置是第2章算法设计题的高频题，核心是头插法加一个q指针保存后继。没有q，p->next被改写后就找不到下一个结点了。
typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; void ReverseList(LinkList *L) { // 就地逆置带头结点的单链表 LNode *p = (*L)->next; // p 指向第一个数据结点 LNode *q; (*L)->next = NULL; // 先把新链表置空，准备头插 while (p != NULL) { q = p->next; // q 保存后继，防止断链 p->next = (*L)->next; // 头插法：新结点插到头结点后面 (*L)->next = p; p = q; } }逻辑说明：为什么用二级指针LinkList *L？因为ReverseList要修改头指针的next域，如果只传LinkList L，函数内改的是形参副本，调用结束后原链表纹丝不动。这是C语言指针最经典的坑。参数说明：这里假设是带头结点的链表，考试时看清题面有没有“带头结点”四个字；不带头结点时逻辑大体相同，但开头要单独处理第一个结点的next改为NULL。
二叉树遍历设计题的答案几乎都要用函数指针。书中visit(T->data)这种写法，在纯C里要按照回调函数的标准形式声明参数。
typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; // 左右孩子指针 } BiTNode, *BiTree; void PreOrder(BiTree T, void (*visit)(ElemType)) { if (T) { visit(T->data); PreOrder(T->lchild, visit); PreOrder(T->rchild, visit); } }逻辑说明：递归出口是T为空，visit把访问操作解耦——同一套遍历代码，你只需要换visit的实现，就能变成求深度、数叶子、打印全部元素等多个版本。参数说明：void (*visit)(ElemType)是一个函数指针，调用时传一个自己写的print函数进来，例如void print_elem(ElemType e) { printf("%d ", e); }，然后调用PreOrder(root, print_elem)。函数指针是很多数据结构设计题答案的骨架，不会用的话，树的题会写得很吃力。
这一章做下来，如果按上面的骨架重写10个文件，大约一个晚上能完成。边改边编译，才能发现书中代码省略了多少类型信息。手边备一份按这个思路整理的源码版，是省时间的正路。
3. 算法设计题答案的拆解思路：查找、排序与图遍历的通用套路
3.1 算法设计题的五类高频题型与答案组织方式
结合考研数据结构和408的真题风格，严蔚敏每章结尾的算法设计题虽然变化多，但题型能按数据组织方式归成五类。我习惯用一个表格把它们框起来，然后逐类补代码。
| 题型 | 对应章节 | 核心考点 | 答案验收标准 |
|---|---|---|---|
| 顺序表/链表改造 | 第2章线性表 | 插入、删除、逆置、合并 | 空表、单元素、重复值都正确 |
| 栈和队列模拟 | 第3章栈和队列 | 括号匹配、双栈模拟队列 | 出栈/出队顺序正确 |
| 树的性质计算 | 第6章树和二叉树 | 深度、叶子数、相似性、层次遍历 | 空树返回0，递归不越界 |
| 图遍历与拓扑 | 第7章图 | DFS/BFS非递归、邻接表、拓扑排序 | 结点不漏、不重，入度处理正确 |
| 排序与查找改造 | 第9章查找、第10章内部排序 | 折半查找、快排改进、堆排序 | 复杂度不劣化，稳定性说明清楚 |
按这个表把每个题目整理成“题目一句话、思路三步、可运行代码、边界用例”四段式，数据结构实验报告和期末复习都能直接复用这个结构。我见过很多人拿着答案抄，抄完连题目要考什么都说不清，根源就是答案组织得太散，没有按题型归类。
3.2 查找类设计题：折半查找的非递归写法与二叉排序树判断
折半查找是第9章必考设计题，非递归写法比递归更常被要求上机。关键是维护一个循环不变量：目标只可能存在于闭区间[low, high]里。每轮比较后收缩区间，直到区间为空。
int BinarySearch(int a[], int n, int key) { int low = 0, high = n - 1, mid; while (low <= high) { mid = low + (high - low) / 2; // 防止 low+high 整数溢出 if (a[mid] == key) return mid; else if (a[mid] < key) low = mid + 1; else high = mid - 1; } return -1; // 查找失败 }逻辑说明：mid = low + (high - low) / 2，这个写法比(low+high)/2更安全，low和high都很接近上限时后者可能溢出。循环条件是low <= high而不是low < high，否则当区间只剩一个元素时会漏判。参数说明：数组a必须是有序的，n是长度，key是待查值；如果题面说“下标从1开始”，那high要改成n，返回时也要处理好下标偏移。查找失败返回-1是常见约定，也有考场要求返回0，以题面为准。
二叉排序树判断本身就是设计题答案里的一个固定模式：中序遍历序列严格递增，树就是BST。实现时用全局变量保存上一个访问值。
int pre = -1; // 初始值要小于树里所有元素 int flag = 1; // 一旦发现逆序就置0 void InOrderCheck(BiTree T) { if (T && flag) { InOrderCheck(T->lchild); if (T->data <= pre) flag = 0; // 要求严格递增，相等也不行 pre = T->data; InOrderCheck(T->rchild); } }逻辑说明：这个思路把“判断性质”转化成了“遍历序列校验”，代码量比递归比较左右子树小很多。flag的作用是短路——已经判定不是BST了，就不要再往下递归。参数说明：如果树内允许重复值即非严格递增，把条件改成T->data < pre即可，但题目如果说“二叉排序树”默认是严格递增，考生需要在答案开头写清假设。这里初始pre设成-1，如果元素可能为负，用INT_MIN更稳。
3.3 图遍历设计题：邻接表定义与DFS非递归实现
图这一章的设计题，直接考邻接表定义的居多。先把结构体定义写对，后面代码才不飘。邻接表 = 顶点数组 + 每条边的弧结点链。
#define MAXV 100 typedef struct ArcNode { // 边表结点 int adjvex; // 邻接顶点编号 struct ArcNode *next; // 下一条边 } ArcNode; typedef struct VNode { // 顶点表结点 int data; ArcNode *first; // 第一条边 } VNode; typedef struct { VNode adjlist[MAXV]; int n, e; // 顶点数、边数 } AdjGraph;逻辑说明：这条定义链是图章节所有算法的基础。first指向第一条边，访问某个顶点的所有邻居就是沿这条链走下去。参数说明：如果边带权，ArcNode里加一个int weight字段；MAXV按题目最大顶点数定，上机题一般给到100够用，更大就改成动态分配。
DFS递归转非递归，用栈保存待访问结点，visited数组防止重复入栈。这个转换是图设计题里最容易翻车的地方，因为访问顺序和递归版不完全一样，但结点了不漏这个要求必须满足。
void DFS(int v, int visited[], AdjGraph *G) { int stack[MAXV], top = -1; ArcNode *p; visited[v] = 1; stack[++top] = v; while (top >= 0) { v = stack[top--]; printf("%d ", v); for (p = G->adjlist[v].first; p; p = p->next) { if (!visited[p->adjvex]) { visited[p->adjvex] = 1; // 入栈前标记，避免重复入栈 stack[++top] = p->adjvex; } } } }逻辑说明：和递归版的一个明显差异是，非递归版是入栈时立刻标记visited，而不是出栈时标记。如果出栈才标记，同一个顶点可能被周围多个邻居重复压栈，栈会膨胀一倍，还可能死循环。参数说明：visited数组初始全0，调用前由外部创建；栈大小按顶点数定，这里用MAXV，严格做法是malloc一个G->n大小的数组。拓扑排序是另一个套路：统计入度，入度为0的顶点入栈，每出栈一个顶点就把它所有邻接点的入度减1，减到0再次入栈，最后出栈序列就是拓扑序列。判断有环的办法是记录出栈顶点数，少于顶点总数说明有环。
这些图的答案正确性不好肉眼判断，最稳的是打印访问序列，再写一个校验函数确认每个结点恰好出现一次，这个验证方法放到第5章统一讲。
4. 严蔚敏书中源码移植避坑：从引用符号到内存泄漏的五个常见问题
4.1 现象：gcc报错 expected ‘;’ before ‘e’，指到一个奇怪的&符号
原因是严蔚敏书里的函数参数大量使用ElemType &e这种C++引用写法，纯C编译器不识别参数列表里的&。解决方法是把形参里的&改成指针，对应实参处加&取地址。例如书上的DeleteElem(L, e)如果写作ElemType &e，落地就改成ElemType *e，调用处写成DeleteElem(&L, &e)。这个坑几乎每个照着书上代码敲的人都会踩一遍，我当年在实验课上卡了二十分钟才反应过来是语言语法问题，不是算法问题。
4.2 现象：程序能跑，但循环一万次后内存越来越少，或Valgrind报definitely lost
原因是删除链表时只free了头结点，数据结点全漏了；或者顺序表退出前忘了free(L.data)。解决方法是遍历链表逐个释放：先用q保存下一个结点，再free当前结点，最后把头指针置NULL。顺序表则在main函数return前补一句free(L.data)。记住free之后如果不置NULL，后续误用就成了野指针翻车现场。这个坑在写“清空链表”这类设计题时几乎是必经之路，写完顺手跑一次Valgrind能少懊恼半天。
4.3 现象：printf打印的顺序和实际执行顺序不一致，或者程序结束后才一次性输出
原因是stdout在交互终端下是行缓冲，重定向到文件或管道时变成全缓冲，输出内容积压在文件缓冲区里没刷出来。解决方法是每条调试输出都带\n，必要时调用fflush(stdout)强制刷缓冲。另外连着用scanf和getchar时，前面输入残留的换行符会被下一次读取吞掉，这也是缓冲区相关的常见玄学。遇到“输出顺序不对”先别怀疑算法，先看是不是缓冲问题，很多刚学C语言基础的人在这里浪费时间。
4.4 现象：链表反转题里的a = ++b这类表达式看不懂，甚至算出错值
原因是C语言里a=++b是先自增再赋值，和a=b++完全两回事。书中源码有时把指针后移和取数据写在同一行，阅读负担很大。解决方法是不要追求一行写完，把p = p->next;和q = p->next;拆开成两步写，可读性和正确率都上去。这是我的一点血泪经验，考场上手写代码时，多写一行不会扣分，写错一个运算符直接零分。
4.5 现象：VSCode里源码报“无法打开源文件 stdio.h”，或虚拟机Ubuntu里gcc都找不到
原因是编辑器没有配置includePath，或者系统里确实没装build-essential。解决方法是先执行sudo apt install build-essential确认gcc存在，再在VSCode的c_cpp_properties.json里设置includePath和compilerPath。
{ "configurations": [ { "name": "Linux", "includePath": ["${workspaceFolder}/**", "/usr/include"], "defines": [], "compilerPath": "/usr/bin/gcc", "cStandard": "c11" } ], "version": 4 }逻辑说明：includePath告诉IntelliSense头文件在哪里，compilerPath指向gcc可执行文件。配置好后重载窗口，红波浪线就会消失。参数说明：如果用的是Windows下的MinGW，路径改成你的编译器实际安装目录；macOS用户则写成/usr/bin/clang。这个文件配好后一劳永逸，之后再遇到“无法打开源文件”就知道是路径问题，不是代码问题。
这些坑有个共同规律：都不是算法逻辑本身的错，而是书的伪代码语言和C编译器语言之间存在翻译层。建立一套“先编译、后看输出、再谈算法”的检查顺序，能省掉大量玄学排查时间。
5. 验证算法设计题答案：从GDB断点到408机试的完整闭环
5.1 用断言和边界用例做回归验证
算法设计题答案写完，第一件事不是看打印结果，而是写断言。assert能在条件不满足时直接终止并报告行号，比肉眼扫输出可靠得多。常见做法是给每个函数配一个小测试函数，把正常用例、空输入、单元素、重复值全部跑一遍。
#include <assert.h> void test_reverse(void) { LinkList L = CreateList(5); // 创建一个 1 2 3 4 5 的链表 ReverseList(&L); assert(GetLength(L) == 5); // 长度不能变 assert(GetFirst(L) == 5); // 反转后第一个元素必须是 5 printf("test_reverse passed\n"); }逻辑说明：断言函数的返回值或状态，程序没崩就说明这一项过了。每次改动算法后跑一遍全部测试，回归成本几乎为零。参数说明：CreateList、GetLength、GetFirst这些函数按题目自行实现，测试函数只关注结果不关注过程。边界用例至少覆盖空表、单元素表、两个元素表和全是重复值的表，这四种情况能拦下八成隐蔽bug。
5.2 GDB：在源码层面观察指针到底指到哪
VSCode的调试器底层也是GDB，命令行会了，图形界面自然懂。编译时加-g生成调试信息，然后gdb进入交互界面。
gcc -g -o test test.c gdb ./test (gdb) break ReverseList (gdb) run (gdb) next (gdb) print *L (gdb) print *p (gdb) backtrace (gdb) quit逻辑说明：break在函数入口停住，run跑到断点，next单步执行，print *L能直接看到头结点next指向是否已经改变。当递归树题写崩时，backtrace看调用栈能快速定位是哪个递归层出了问题。参数说明：-g是生成调试信息的关键参数，没有这个符号表，print命令只能输出地址，看不到结构体内容。GDB这套命令十分钟就能上手，但能救命的场景往往是考前最后一晚。
提示：调试链表和二叉树时，print一个结构体指针不如print *p直观，多按几次print能看到指针指向的结点内容。
5.3 对接考研数据结构与408：答案怎么才算“过”
很多读者买这本书是为了数据结构考研、408专业课或数据结构期末复习。单纯把答案抄出来不算完，要按三关验收。第一关是边界关：空输入、单元素、最大规模都能跑；第二关是复杂度关：设计题题面明确要求O(n)或O(log n)时，答案里不能出现嵌套循环；第三关是表达关：机试按函数接口给分时，函数签名要和题面一致，比如题目要返回下标，答案就不能返回指针。
交叉验证的办法也很简单：拿王道单科书对应章节的题目，把严蔚敏教材里验证过的算法跑一遍伪输入；再把PTA上的字符串逆序、冒泡排序、完数这类C语言基础题当作热身，它们本质是那一章设计题的低配版。这样验证过的答案，才敢写进实验报告。408和考研数据结构不会直接考“背答案”，但会把同一套算法换一个数据组织方式再考一遍，所以按题型整理答案比按题号整理答案更有价值。
6. 把严蔚敏习题答案沉淀成自己的算法模板仓库
到这里，最值得做的下一步不是继续刷题，而是把验证过的代码整理成自己的模板仓库。我一般按章节建目录，从第2章线性表一路放到内部排序，每个文件只放一个算法设计题的“题目一句话、思路三步、可运行代码、边界用例”，文件开头写清楚编译命令和踩过的坑。以后做实验报告、期末复习、考研数据结构或准备408，直接翻这个仓库比翻书快得多。
整理时有个口味上的建议：优先保留自己亲手调通的版本，不要保留书上的伪代码原文。伪代码是参考，能跑的是答案。格式统一成函数接口在前、静态逻辑在后、main函数里只留测试断言，这样复试上机时直接把函数抠出来贴到考场代码里就能用。配合翁恺的练习题或谭浩强教材的习题做二次交叉验证，覆盖的题型会更广。
我自己的教训是，当年抄书上的算法抄得很爽，考前三天试着编译那一整段，才发现到处是引用符号和malloc缺转换，那个晚上基本没睡。后来坚持“写完一个文件就立刻gcc编译”，才把这些坑从玄学变成流程。这个方向值不值得投入？如果你在准备数据结构期末复习或考研，答案是值得——它把一本需要脑补的教材变成一套能跑、能验、能复用的本地工程。希望帮到你。
本文还有配套的精品资源，点击获取
