简介严蔚敏《数据结构C语言版 第2版》学习者常需要配套的算法答案与可运行源码这份资源正为此整理覆盖算法设计题参考答案与书中算法源码适合正在啃教材、备考或需要动手验证数据结构的本科生、考研党及自学者。源码基于CLion 2020~2021环境配置配套CMake构建脚本按部署说明打开即可直接编译运行。资源包为RAR压缩格式大小约3.14MB平台未单独标注文件总数内容以C/C源文件、CMake构建脚本、ReadMe说明文档为主压缩包内同时提供五本经典算法/数据结构书籍的下载链接作为赠品。作者在原始答案基础上对部分算法做了优化纠正了参考答案中的错误并针对可能触发的bug、触发条件、不同实现方法、优化思路与执行过程给出了详细注释便于读者对照理解算法细节、排查问题并拓展思路。目前已有1220人浏览学习适合需要结合代码深入掌握数据结构核心考点、同时希望获得可靠答案与源码参考的读者。1. 严蔚敏《数据结构》C语言版第2版把算法设计题答案和书中算法源码当成工程来整理才能真跑通考研408的复习资料里严蔚敏《数据结构C语言版》第2版始终带着一种“让人又爱又恨”的气质书不算厚可课后每道算法设计题都够你折腾一晚上。网上流传的“算法设计题答案”和“书中算法源码”版本很多但大部分因为少了公共头文件、用类C的伪代码代替完整实现复制到编辑器里根本编译不过。与其背一堆跑不起来的答案不如按工程的方法来把答案当成小程序去编译把书中算法源码一章一章整理成可复现的项目。这篇笔记会从考点拆分、环境搭建、两道高频题的完整实现一直讲到常见的移植坑和验证技巧适合正在备考数据结构考研或赶数据结构期末复习的本科生也适合想用C语言把数据结构重新打一遍底子的开发者。2. 严蔚敏《数据结构》算法设计题在考什么按章拆考点答案才有方向算法设计题最让人焦虑的地方不是“不会写”而是“不知道考什么”。严蔚敏这本书的习题安排其实非常有规律每章后面出现的算法设计题都集中在几个固定的数据操作上。这一章先把整本书的考点地图铺开然后给出我在做历年真题和数据结构期末题时总结出来的解题判断顺序最后放一段可以直接套用的答案骨架。这套思路走通之后你再回头看网上那些答案就能分清哪些能抄、哪些抄了反而被扣分。2.1 数据结构 C 语言版第2版从线性表到排序高频算法题的分布地图严蔚敏这本书的章节安排是教材级别的经典第2章线性表、第3章栈和队列、第4章串、第5章数组和广义表、第6章树和二叉树、第7章图、第9章查找、第10章内部排序。课后题里专门用大篇幅引导读者去实现的往往是“结构 操作”的组合而不是孤立的语法题。我按自己复习时用的顺序把高频考点整理成下面这张表你对照着就能定位自己卡在哪一章。章节核心结构算法设计题高频考点第2章 线性表顺序表、单链表插入删除、有序表合并、就地逆置、循环链表判空第3章 栈和队列顺序栈、链栈、循环队列括号匹配、表达式求值、循环队列判空判满第4章 串顺序串、KMP 串模式匹配、next 数组计算第5章 数组和广义表二维数组、稀疏矩阵三元组对称矩阵压缩存储、稀疏矩阵转置第6章 树和二叉树二叉链表、线索二叉树、哈夫曼树递归遍历、非递归遍历、求深度、哈夫曼编码第7章 图邻接矩阵、邻接表DFS、BFS、拓扑排序、最小生成树第9章 查找顺序表、二叉排序树、哈希表折半查找、二叉排序树构建、哈希冲突线性探测第10章 内部排序顺序表直接插入、冒泡、快速排序划分、堆排序、归并排序这张表看起来不复杂但把它和近十年的考研数据结构真题、各校的数据结构期末题对齐后就会发现408统考那道“图和数组”的大题算法部分几乎都能归到第7章或第5章考研数据结构里的手写算法题常考的也总是快排划分、非递归中序、链表逆置这几类。整理答案时按“结构操作”归类比按页数翻书有效得多。我的排序习惯是先把线性表、二叉树、图、排序四块当成必须熟练的考点来练串和查找次之课上没在这些章节下功夫的人往往在第一个非递归遍历实现那里直接翻车。2.2 拿到一道算法设计题先按“结构、指针、边界、复杂度”四关走一遍很多同学拿到算法设计题的第一反应是打开编译器把语法写出来这个习惯很耽误事。严书里的题大多是“思路级”描述不是“语法级”描述比如“设计算法将两个有序链表合并成一个有序链表”它没有告诉你p、q两个指针怎么走也没告诉你空链表怎么处理。我一般会在草稿纸上先过四关第一关是结构。题目处理的是顺序表还是链表是数组还是二叉树是邻接表还是邻接矩阵。结构决定你能不能用随机访问比如顺序表可以按下标直接定位第 i 个元素单链表只能从头开始走两者的时间复杂度完全不是一个数量级。第二关是指针。如果要修改链表头或树的根C语言需要二级指针如果只是遍历一级指针就够。很多网上答案的错误都出在这一步把LNode *L传进函数里在函数内修改了L本身回到主函数后链表纹丝不动。为什么因为参数是值传递函数内部改的只是指针副本外面根本感知不到。第三关是边界。表空、表满、只有一个结点、链表循环、指针为 NULL、插入位置在末尾这些边界条件至少要在草稿上列一遍。很多考研真题的“玄学丢分”不是算法主体错而是没写if (L NULL) return ERROR这类保护被扣掉边界分。第四关是复杂度。题目写了时间复杂度 O(n) 而你写出一个双层循环 O(n^2)就算能运行答案在评分标准里也不合格。排序算法尤其明显内部排序章节的常考题就是手写一趟快排的划分过程或者写堆排序的筛选算法这要求你对每步操作的次数心里有数。把这四关在纸上过两分钟往往比在调试器里看半小时输出更管用。我常跟人说算法设计题答案写得漂不漂亮不取决于语法熟练度而取决于这几个前置判断有没有做扎实。2.3 一套可套用的算法答案骨架先定义状态再写遍历最后补边界按我的经验书里所有算法设计题答案都可以套到一个固定骨架上定义返回状态、定义元素类型、定义结构体然后写操作函数最后在主程序里验证。下面这段顺序表插入的代码就是从严书第2章顺序表实现改成的标准 C 版本抄到本地就能编译运行。#include stdio.h #include stdlib.h #define MAXSIZE 100 #define OK 1 #define ERROR 0 typedef int Status; /* 函数返回状态 */ typedef int ElemType; /* 元素类型可换成 char/float 等 */ typedef struct { ElemType data[MAXSIZE]; int length; } SqList; Status ListInsert(SqList *L, int i, ElemType e) { int k; if (L NULL) return ERROR; if (L-length MAXSIZE) return ERROR; if (i 1 || i L-length 1) return ERROR; /* i 从 1 计 */ for (k L-length; k i; k--) { L-data[k] L-data[k - 1]; } L-data[i - 1] e; L-length; return OK; }这段骨架里最需要注意的是for (k L-length; k i; k--)这行它代表从后往前移动数据确保data[k-1]的值不会被尚未处理的覆盖操作冲掉。i是逻辑位置从 1 开始但数组下标从 0 开始所以最后赋值时用i - 1。三个if判断分别覆盖“空指针”“表满”“插入位置非法”三种边界这是很多网传答案缺失的部分。把它们补齐后这套骨架既可以在第2章用也可以推广到第7章图、第10章排序的算法源码移植里只要把SqList换成对应的结构体其他逻辑保持一致。3. 让书中算法源码在本机跑起来VS Code GCC 的最小 C 环境搭建书上的算法源码和能编译运行的工程源码之间隔着一条很宽的河。严蔚敏这本书的算法描述默认读者已经理解了 C 语言于是大量公共类型和关键边界被省略了。你如果直接复制到编译器里看到的是一堵红色的报错墙。本章先把问题拆开再给出一套最小工程配置让你在 VS Code 里用 GCC 把书里的算法源码跑起来同时保留调试能力。3.1 严版源码“不能直接编译”的四个原因先说清楚再动手我见过的初学者报错九成可以归到四个原因里。第一个原因是公共类型缺失。Status、ElemType、OK、ERROR、TRUE、FALSE、OVERFLOW这些符号在书的算法描述里频繁出现但教材正文不会给一份完整的头文件。你只复制一段算法编译器自然认为这些是未定义的类型和常量。第二个原因是类 C 的语法约束。书上写线性表插入函数时用ListInsert(L, i, e)这里的L在 C 里是引用在 C 里却是“取地址”操作。如果按 C 语言编译直接写L会把结构体地址传进去与函数形参不匹配于是报错正确写法是形参用SqList *L调用时传L。第三个原因是结构体定义不完整。链表算法里的LNode、二叉树里的BiTNode、图里的ArcNode这些结构体的完整定义不在算法源码段里而在教材前面的章节中。你单独复制算法段时编译器只能看到一个声明无法分配内存。第四个原因是边界省略严重。为了提高可读性书里很多算法省去了判空、判满、越界检查。本地练习时如果反复越界程序可能“碰巧不崩”但输出是错的或者在离开函数后被系统检测到栈破坏。这四个问题合在一起让严书源代码需要一个“补环境”的过程而补环境的步骤恰好能帮你把 C 语言基础重新练一遍。3.2 最小工程结构一个公共头文件ds.h加一个测试源文件为了不再重复补环境我建议给整本书单独建一个目录里面维护两份文件一个是公共头文件ds.h一个是针对当前算法的测试源文件。公共头文件集中解决第一个和第四个原因里的公共定义测试源文件解决结构体和主函数的问题。先建ds.h内容如下#ifndef DS_H #define DS_H #include stdio.h #include stdlib.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int ElemType; #endiftypedef int Status把函数返回状态统一成整数类型typedef int ElemType把元素类型统一成整数类型这是最省事的默认选择。实际题目里如果要处理字符或浮点数你可以在这个文件里修改ElemType然后重新编译所有引用它的结构体都会跟着切换。#ifndef DS_H和#endif是头文件保护防止多个.c文件同时包含它时出现重复定义错误这套写法在后续所有章节都建议保留。再写一个极简的测试文件list_test.c验证公共头文件是否生效#include ds.h #define MAXSIZE 100 typedef struct { ElemType data[MAXSIZE]; int length; } SqList; int main() { SqList list {{0}, 0}; int i; for (i 0; i 5; i) { list.data[list.length] i * i; } for (i 0; i list.length; i) { printf(%d , list.data[i]); } printf(\n); return 0; }SqList list {{0}, 0}是复合初始化{{0}, 0}中第一对花括号给整个数组清零第二个 0 给length字段赋初值。这样做的意义在于你必须在没有显式赋值前确认length不是垃圾值否则后面所有依赖length的循环都会脱离预期。编译运行如果输出0 1 4 9 16说明公共头文件、结构体定义、编译链路都正常。3.3 VS Code 里运行 C 代码的配置与编译命令很多人卡在“不知道按什么键运行C代码”上这也是我被问到最多的问题之一。我现在的习惯是 VS Code 加 GCC因为这套组合既能覆盖 Windows 也能覆盖 Linux 虚拟机而且调试体验比老式 IDE 更直观。在 Windows 上先安装一个带 GCC 的编译环境MSYS2 或 MinGW-w64 都可以安装后把gcc.exe所在目录加入系统 PATH。在 Linux 上一般自带 gcc用gcc --version检查。VS Code 里安装 Microsoft 的 C/C 扩展然后新建终端输入以下命令gcc -g -Wall list_test.c -o list_test ./list_test-g生成调试信息-Wall打开大多数编译警告-o指定输出文件名。很多网上教程只写gcc list_test.c结果编译通过但运行时报段错误原因就是没有-Wall暴露数组越界等可疑操作。编译时如果有红色波浪线提示Status未定义回头检查#include ds.h是否写在文件第一行或者ds.h是否真的与.c文件在同一个目录下。如果编译后运行.out文件时提示权限不足Linux 下要执行chmod x list_testWindows 下直接运行list_test.exe即可。这套命令虽然简单却是整个数据结构源码移植过程中每次都要重复的最小闭环。4. 两道高频算法设计题的手把手实现顺序表倒置与非递归前序遍历纸上谈兵讲完这一章进入实战。我挑选的是各校“数据结构期末复习”和“考研数据结构”里出现频率极高的两道题一道来自第2章线性表的顺序表倒置一道来自第6章二叉树的非递归前序遍历。这两道题足够小但能覆盖严书移植过程中最典型的几个难点边界判断、空间复杂度控制、递归转非递归时的状态维护。每道题都按“题目分析、源码实现、逻辑参数说明、可验证输出”的顺序展开你可以对照着自己写一份。4.1 顺序表倒置双指针交换实现 O(1) 空间复杂度题目背景在很多教材里都出现过设顺序表 L 已存放 n 个整数设计算法把 L 中的元素倒置要求辅助空间尽量少。这里的考点有两个一个是你知道倒置的本质是“首尾交换”另一个是你用几个临时变量完成任务。如果重新开一个新数组再拷贝回去时间复杂度和空间复杂度都是 O(n)虽然结果对但在严书课后题的标准下不算优解。代码实现如下#include ds.h #define MAXSIZE 100 typedef struct { ElemType data[MAXSIZE]; int length; } SqList; Status ReverseSq(SqList *L) { int low, high, temp; if (L NULL) return ERROR; if (L-length 1) return OK; low 0; high L-length - 1; while (low high) { temp L-data[low]; L-data[low] L-data[high]; L-data[high] temp; low; high--; } return OK; }逻辑说明用两个下标从两端往中间夹每次交换一对元素。low high作为循环条件让奇数个元素的中间元素自然保持不动偶数个元素则最后一次交换正好配对。temp是唯一额外使用的变量所以空间复杂度为 O(1)时间复杂度为 O(n)。相比用for循环写n/2次交换这个版本直接用两个下标控制边界更清晰也更容易在草稿纸上验证。参数说明low和high是顺序表的下标严格从 0 到length-1temp的类型要与ElemType保持一致如果以后把ElemType改成结构体这个变量也要相应改成结构体类型。对L-length 1的处理是对“空表”和“单元素表”的兜底防止无意义的交换消耗。如果题目额外要求返回逆置后的新顺序表而不改变原表则需要在函数内部malloc一个新表并在函数外free。4.2 二叉树前序遍历非递归版用栈模拟系统调用栈第6章最常见的手写算法题之一是把前序遍历从递归版本改成非递归版本。递归版本只有几行但在树很深时系统递归栈可能溢出更重要的是考试明确要求考你的栈控制能力。前序遍历顺序是“根、左、右”用栈实现时记忆口诀是“先压右再压左”。源码如下#include ds.h #include stdlib.h typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void PreOrderNonRecursive(BiTree root) { BiTNode *stack[100]; int top -1; BiTNode *p; if (root NULL) return; stack[top] root; while (top 0) { p stack[top--]; printf(%d , p-data); if (p-rchild ! NULL) { stack[top] p-rchild; } if (p-lchild ! NULL) { stack[top] p-lchild; } } }逻辑说明先将根节点入栈随后进入循环每次弹出一个节点并打印它的值。因为栈是后进先出想让左子树先被访问就必须在压栈时把右孩子先压进去、左孩子后压进去这样左孩子在栈顶下一次循环先出栈。整个过程显式地维护了一个“下一步要处理谁”的栈替代了系统递归调用时的隐式栈。严书在介绍非递归遍历时会强调“递归过程转换为循环过程”关键点就在这里。参数说明stack[100]是定长数组适合题目给定的有限深度场景如果树的深度可能超过 100建议改用动态数组或链栈。top从 -1 开始表示空栈压栈时先top弹栈时取stack[top--]这组约定必须记牢。p-rchild和p-lchild的判断缺一不可漏掉任意一个都会在碰到空子树时把空指针压入栈中导致下次循环访问空指针的 data 报段错误。如果有同学在这里踩坑多半是先压左孩子后压右孩子输出顺序变成“根、右、左”答案方向性错误。4.3 用测试代码验证答案倒置输出、前序输出一步都不能少前面两段只是函数实现算法设计题答案是否成立必须跑一个完整程序验证。把两个函数连同main写进同一个.c文件是常见的做法我还会额外加一组空链表、空树测试避免“只测正常情况”带来的假阳性。#include ds.h #include stdio.h #include stdlib.h #define MAXSIZE 100 typedef struct { ElemType data[MAXSIZE]; int length; } SqList; typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; Status ReverseSq(SqList *L) { int low, high, temp; if (L NULL) return ERROR; if (L-length 1) return OK; low 0; high L-length - 1; while (low high) { temp L-data[low]; L-data[low] L-data[high]; L-data[high] temp; low; high--; } return OK; } void PreOrderNonRecursive(BiTree root) { BiTNode *stack[100]; int top -1; BiTNode *p; if (root NULL) return; stack[top] root; while (top 0) { p stack[top--]; printf(%d , p-data); if (p-rchild ! NULL) stack[top] p-rchild; if (p-lchild ! NULL) stack[top] p-lchild; } } int main() { SqList list {{1, 2, 3, 4, 5}, 5}; int i; ReverseSq(list); for (i 0; i list.length; i) { printf(%d , list.data[i]); } printf(\n); BiTNode n1, n2, n3; n1.data 1; n1.lchild n2; n1.rchild n3; n2.data 2; n2.lchild NULL; n2.rchild NULL; n3.data 3; n3.lchild NULL; n3.rchild NULL; PreOrderNonRecursive(n1); printf(\n); return 0; }这段代码在前面函数的基础上补上了main和测试数据。SqList list {{1, 2, 3, 4, 5}, 5}直接初始化数组和长度省去逐个赋值的冗长代码。二叉树用三个局部变量临时构造n1作为根传入输出应该是1 2 3其中2是左孩子3是右孩子。测试用的树很小所以不需要释放内存如果换成一棵用malloc动态分配的较大树主函数结束前要记得按后序释放所有节点否则提交到数据结构实验报告系统里会被内存泄漏检测工具标红。5. 移植严蔚敏书中代码常见的坑四个高频问题与排查顺序把严书源码和网传答案搬到本地时每个人都会遇到几个固定“玄学”时刻编译不过、运行崩溃、输出不对、结果脏数据。这一章把最常见的四个坑按“现象、原因、解决”呈现每条都是可以直接照着做的排查路径后面遇到相同报错时能省下大量时间。5.1 反复提示Status、ElemType未定义公共头文件到底加没加现象从网上下载的算法设计题答案复制到 VS Code 后用 GCC 编译报错集中在文件开头比如error: unknown type name Status、error: OK undeclared。原因网上答案一般只粘贴了算法函数没有公共头文件。严书里的Status、ElemType、OK、ERROR是全书共用的抽象类型教材没有提供标准头文件你的工程里如果不定义它们编译自然失败。解决确认ds.h已经按第3章的写法创建并在每个.c文件头部写#include ds.h。如果结构体也提示未定义比如SqList、BiTree说明该结构体定义还在原始的源文件里需要一并复制到当前文件的typedef区域。另一个隐蔽情况是文件明明写了#include ds.h但ds.h的目录不在当前编译路径里这时要把#include ds.h改成带相对路径的写法例如#include ../common/ds.h或者直接把ds.h放到与.c文件相同的目录下。5.2 链表操作没效果传引用变成了传指针副本现象写单链表插入函数void Insert(LNode *L, int i, ElemType e)在函数内部用L L-next移动指针算法结束后回到main链表头没有变插入操作像没发生一样。原因C 语言是值传递形参LNode *L只是实参指针的一个副本。函数内对L本身的赋值只修改了副本不会修改调用者的指针但如果通过L-next修改节点内部的 next 字段因为L和外部指针指向同一块内存修改会保留。问题就出在“要修改的是链表头指针本身”还是“修改指针指向的节点内容”。解决当算法需要修改链表的头指针时形参必须改成二级指针void Insert(LNode **L, int i, ElemType e)调用时传L。如果算法只是遍历链表找位置、修改某个节点的next那一级指针就够用。严书教材里InitList(L)的写法对应的是 C 引用换成 C 语言时这条规则必须记牢。这个坑不仅在链表章节出现二叉树的插入、删除、构造算法里凡是可能改变根节点位置的函数都要考虑是否使用二级指针。5.3 非递归中序和前序输出混乱栈里存的除了节点还要存“状态”现象自己实现非递归中序遍历时把节点指针入栈弹栈后立刻打印结果输出顺序变成先根后左完全不像中序遍历。原因前序遍历在第一次遇到节点时打印所以弹栈后直接打印是对的中序遍历需要在“从左子树返回时”打印光靠节点地址无法区分“第一次经过”和“访问完成后返回”。如果不保存额外状态程序就会在第一次遇到节点时做出错误动作。解决常规中序非递归写法是不把节点打印动作放在弹栈时完成的而是用一个工作指针p不断向左深入把路径上的节点都压进栈当p为空时弹出一个节点打印再把p指向它的右子树继续下一轮。栈里保存的是“待返回的祖先节点”p本身负责推进方向。理解了这个逻辑你再去写后序非递归就会明白为什么后序只能用“标记位”或“双栈法”来做。这个点在考研数据结构里堪称高频陷阱值得单独刷两遍。5.4 程序结果不对却不崩检查点要加在赋值语句后面而不是函数末尾现象算法代码能编译、能运行但输出数字错得离谱。比如顺序表倒置后输出5 3 -12345 2 1中间出现垃圾值或者链表合并后丢失了后半段。原因垃圾值往往说明越界访问了未初始化的内存。在循环里下标计算错了比如把n-1-i写成n-i第一次循环访问了data[n]而最后一格正好是未初始化的越界位置。编译器不一定报错因为 C 语言不检查数组下标函数结束时数据已经被污染。解决在每轮循环的关键赋值后插入一行临时打印例如printf(i%d, change %d-%d\n, i, L-data[low], L-data[high]);跑完一遍就能看到是哪一轮、哪个下标越界。确认后用调试器在赋值语句处打断点观察low、high和temp值。排查结束后删除调试打印再重新编译。遇到过几次这种情况后你会发现调试器看的中间状态远比“满屏 printf”高效养成这个习惯后面章节的图遍历、哈夫曼编码等长算法会好查很多。6. 用“最小用例 复杂度核对”验证算法答案把源码整理成自己的复习手册算法题答案写完之后最忌讳的是扔到一边不再理。我见过很多人期末时拿着打印的一沓“答案”背但那些答案并没有在自己电脑上跑过背下来也是一知半解遇到变体仍然不会。后来我给自己定了一条习惯每道题实现完至少跑三样东西——最小用例、边界用例、复杂度核对。最小用例很好理解顺序表倒置我只放一个元素验证输出还是它本身非递归前序遍历我只建一个根节点验证输出只有根。这些用例跑通了至少说明函数骨架方向正确。边界用例则覆盖空表、空树、满表、只有一个节点、链表中两个节点这类极端情况。把这两组用例写进test_xxx.c以后改动代码后重新编译一遍能立刻发现回归问题。复杂度核对也很关键。严书的课后题里经常明确要求“时间复杂度 O(n)、空间复杂度 O(1)”答案里出现双重循环时要在注释里写明它是什么量级。为了避免过一阵自己都看不懂我通常会在函数开头加一行注释/* ReverseSq: 时间复杂度 O(n), 空间复杂度 O(1), 边界: 空表/单元素表直接返回 */这行注释既是给复习看也是给考试时“省写”用的备忘。然后把实现完成的源码按章归类chapter2_sqlist/、chapter6_tree/、chapter7_graph/每个目录里保留ds.h、源文件和解题思路注释。复习阶段打开目录就能按“结构操作”的思路快速过一遍比重新翻教材找算法快得多。我之前吃过亏自以为把答案背下来了考场上被一句“写出非递归中序遍历”变体打懵。现在凡是树相关的遍历我都会把递归版、非递归版、后序的双栈版都各自实现一遍并给实现过程打了断点把每一步指针变化都看明白。这确实花时间但踏实。希望这个整理和验证的方法能帮到你让你在严蔚敏《数据结构》的算法设计题上少踩几个坑多拿几分踏实。本文还有配套的精品资源点击获取