简介《数据结构C语言版|第2版严蔚敏》配套的算法设计题答案与书中算法源码是一份面向高校学生、考研者及算法初学者的学习资料。作者基于CLion 2020~2021环境开发按CMake配置部署后可直接运行对书中部分算法进行了优化逐一纠正了参考答案中的错误并围绕可能出现的bug触发条件、算法的不同实现方法与优化思路、执行过程给出详尽说明。压缩包以rar格式打包整体大小约3.14MB内含C语言源文件、CMake工程配置以及ReadMe说明文档便于在CLion中调试、对照学习。目前已有1220人学习浏览适合需要系统梳理数据结构核心算法、验证课后习题答案的读者也可作为期末复习或备考的参考材料。此外ReadMe中还附赠了五本经典算法或数据结构书籍的下载链接方便进一步拓展知识体系。1. 严蔚敏《数据结构》C语言版第2版把算法设计题答案和书中源码一次性跑起来的正确姿势学严蔚敏《数据结构》C语言版第2版的人大多都停在同一个地方算法设计题答案拿到了但对着参考答案敲进电脑不是编译报错就是运行崩溃根本没法验证自己理解得对不对。这份资源不是普通的答案文档而是用 CLion 2020~2021 配好 CMake 的 C 语言工程把书里的核心算法和常见试题答案都改成了能直接编译运行的源码参考答案里有问题的地方做了修正像 KMP、二叉树遍历、排序这些内容还在注释里补充了 bug 触发条件、优化思路和执行过程。适合期末复习、课后刷题、以及想把书上伪代码变成可运行程序的人。2. 环境部署与 CMake 工程从 CLion 打开第一个算法到跑通2.1 为什么选 CLion 而不是 Dev-C 或 VS严蔚敏书上的算法基本上是伪代码教材光盘里的老源码也大多是基于 VC6.0 写的。拿到新电脑上编译常见问题包括头文件路径不兼容、NULL没定义、malloc返回值没有强转、甚至在 C 工程里把 C 代码当 C 编译。CLion 在初始化纯 C 工程时CMake 会明确指定 C 语言标准不会引入 C 的异常处理、模板和命名空间机制这样书里那些用 C99 语法写的代码不会被误报。另一个原因是指针调试。数据结构这门课百分之八十的难点在链表、树、图上CLion 的调试器可以随时查看指针指向的地址、结构体成员的值、栈上递归调用的层级比用printf逐步打印猜问题要快得多。学算法题不是只看最终输出还要看遍历过程CLion 的 Watch 窗口能直接把p-next拉出来看这一点是 Dev-C 和大部分在线编译工具做不到的。所以在复现这类 C 语言算法源码时优先推荐 CLion 加 CMake 的组合。资源包里的 CMakeLists.txt 已经写好构建描述用 CLion 打开会自动加载不需要手工敲编译命令。2.2 部署步骤与 CMake 参数设置解压下载的压缩包后先找一个纯英文路径放工程目录例如D:\ds-clang然后用 CLion 直接打开这个目录。CLion 会自动识别CMakeLists.txt加载整个工程。如果之前打开过其他工程建议先在 File - Settings 里确认 Toolchains 使用的是 MinGW 或 Visual Studio不要默认选到远程服务器上。打开后等待 CMake 自动生成构建配置右下角提示 Reload 时点一下。接下来重点看 CMakeLists.txt 的关键配置资源中的写法大致如下cmake_minimum_required(VERSION 3.15) project(DataStructureCLang C) set(CMAKE_C_STANDARD 99) set(CMAKE_C_STANDARD_REQUIRED ON) include_directories(include) add_executable(ds_main main.c src/sqlist.c src/linklist.c src/kmp.c src/tree.c src/sort.c src/graph.c )逻辑说明project(DataStructureCLang C)里的C表示工程只按 C 语言编译这能避免 CLion 在文件后缀是.c时依然借用 C 编译器的一些严格检查。CMAKE_C_STANDARD 99是必须的因为严蔚敏书中的很多代码写了for(int i0;;)、变长数组这类 C99 特性如果标准被默认成 C90编译就会报 for loop initial declarations are only allowed in C99。参数说明如果机器缺少math.h链接可以在 add_executable 下面加一行target_link_libraries(ds_main m)书里的排序算法和树算法一般用不到math.h但假如你后面自己补写二分查找、AVL 树时用了abs之类函数就需要这行。include_directories(include)的作用是把所有自定义头文件统一放在 include 目录下源文件引用时写成#include sqlist.h就能找到不用写繁琐的相对路径。如果在 CMake 配置时报错说找不到编译器检查 CLion 是否安装了 C 编译器套件。MinGW 需要把bin目录加到系统环境变量 Path 里装好之后在 Terminal 输入gcc --version能输出版本号就说明工具链通了。2.3 用最小测试程序确认环境没问题环境是否真的能跑建议先别碰那些大算法。直接新建一个main.c写入一个极简的测试程序确认编译和运行链路是通的。#include stdio.h int main(void) { printf(ds-clang env ok\n); return 0; }这段代码不需要任何头文件和链接项。如果它能输出一行文字就说明 CLion、CMake、C 编译器三个环节全部正常。如果这一步就报错大概率是 Toolchain 路径不对而不是代码本身的问题。我一般会把这个文件放成main.c把算法源文件分批加入 CMake target。这样每次只验证某一个模块比如先只加sqlist.c和linklist.c跑通后再逐步引入树、图、排序避免一开始几十个文件一起编译报错信息混在一起无法定位。资源包里默认是全部放进 target 的但并没有强制一次全跑完阅读时完全可以根据自己的复习进度在 CMakeLists 中临时注释掉不相关的源文件。提示main.c里通常只保留一个入口函数。书里的算法设计题答案大多是函数片段没法单独运行这个资源把它们组织成模块每个模块内自带test或demo入口然后在主函数里按菜单方式调用这样既能单模块调试也能整体演示。3. 算法源码的正确打开方式从伪代码到可运行 C 代码的转换与优化3.1 结构体定义、初始化与销毁三件事严蔚敏书中的数据结构定义都用了抽象数据类型比如顺序表是SqList链表是LinkList树是BiTree。转换成实际可运行代码时最容易被忽略的是封装边界。一个完整的算法题解必须包含三部分数据结构定义、初始化函数、销毁或释放函数。很多参考答案只写了一个核心算法函数却在main里直接定义结构体变量后不调用初始化导致运行时出现随机值。以下面的单链表初始化为例typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; void InitList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); if (*L NULL) { exit(1); } (*L)-next NULL; }这里的LinkList *L是二级指针因为需要在函数内部修改实参的指向。常见的错误写法是用LinkList L然后直接L-next NULL这只会改动形参副本主函数里的L依然是野指针随后一旦访问L-next就会崩溃。初始化必须检查malloc的返回值。参考答案里通常不写这个判断实际运行时内存分配失败的概率很低但一旦失败就是空指针程序对(*L)-next赋值时会直接段错误。加入exit(1)是为了让错误尽早暴露而不是让程序带着坏指针继续运行。3.2 KMP 算法优化next 数组从 -1 开始还是从 0 开始KMP 是严蔚敏书里的重头戏也是课后习题和期末考试常客。书上给出的 next 数组定义有好几种版本最常见的是以 0 开始的也有教材把next[1] 0作为初始值。资源里我推荐用 -1 版本的实现因为它在模式串失配时对 j 的更新更容易理解也基本不需要特殊处理。void get_next(const char *T, int *next) { int i 0; int j -1; next[0] -1; while (T[i] ! \0) { if (j -1 || T[i] T[j]) { i; j; next[i] j; } else { j next[j]; } } } int KMP(const char *S, const char *T, int pos) { int i pos; int j 0; int next[80] {0}; get_next(T, next); while (S[i] ! \0 T[j] ! \0) { if (j -1 || S[i] T[j]) { i; j; } else { j next[j]; } } if (T[j] \0) { return i - j; } return -1; }逻辑说明get_next中j初始化为 -1next[0]也是 -1这表示第一个字符失配时主串指针 i 前移子串指针 j 回到 -1下一轮循环时j变成 0重新从头比较。这种写法的优点是不需要额外判断j 0时的行为循环条件里统一用j -1作为重新开始的口令。参数说明next[80]的数组长度我临时给了固定值。实际工程里应该根据模式串长度动态分配写成int *next (int *)malloc((strlen(T) 1) * sizeof(int))。pos是主串中开始匹配的下标习题里常见的需求是从第几个位置开始查找这个资源保留了 pos 参数方便直接复用到算法设计题。优化思路方面这份资源里在get_next后增加了一个对被验证过的nextval数组的说明。nextval[i]是为了解决一种特殊情况当T[i] T[next[i]]时即使失配跳到 next 位置那里的字符还是一样的必然再次失配。于是可以继续向前跳一步减少无效比较。期末考试如果考到 KMP 的优化这个点必须写出来。3.3 参考答案错误的典型纠正以二叉树深度和顺序表删除为例资源中把参考答案里的错误一一纠正过。这里列两个我在书中答案中经常见到的错误类型。第一个是二叉树求深度。很多答案写成int Depth(BiTree T) { if (T NULL) { return 0; } return max(Depth(T-lchild), Depth(T-rchild)) 1; }这个函数本身是对的但参考答案错在没有定义max宏或者错误地写成了Depth(T-lchild) Depth(T-rchild) ? Depth(T-lchild) : Depth(T-rchild)。后者虽然也能运行但递归调用了两次Depth每一层都会重复遍历子树时间复杂度从 O(n) 恶化到 O(2^n)。资源里给出了修正版本int max(int a, int b) { return a b ? a : b; } int TreeDepth(BiTree T) { if (T NULL) { return 0; } int leftDepth TreeDepth(T-lchild); int rightDepth TreeDepth(T-rchild); return max(leftDepth, rightDepth) 1; }关键改动是先保存左右子树的深度再比较不重复递归。第二个是顺序表的删除算法。参考答案通常直接:ElemType e L.data[i]; for (int j i; j L.length - 1; j) { L.data[j] L.data[j 1]; } L.length--; return e;这个写法没有检查i是否在有效范围内。如果i L.lengthL.data[j 1]会越界。实际复现时需要在方法最前面做以下判断if (i 0 || i L.length) { return -1; }资源中对类似问题都做了边界检查并在注释里标明了触发条件传入的下标恰好等于最后一个元素位置、空表删除、单链表在尾节点删除后没有置空等。4. 避坑指南严蔚敏第2版C语言源码复现中的常见问题与排查4.1 现象销毁链表时访问 p-next 造成崩溃刚把参考答案里的DestroyList抄进工程运行到一半程序就崩溃报错信息通常是Segmentation fault或者 CLion 直接定位到p-next那一行。原因参考答案的销毁函数经常写成free(p); p p-next;这是错的。free(p)已经把当前节点内存释放了再去取p-next属于访问已释放内存编译器不会立即报错但下一次分配内存后就会翻车。解决释放当前节点之前先把下一个节点地址保存下来while (p ! NULL) { LinkList q p-next; free(p); p q; }这段代码的顺序不能反过来否则q永远取不到有效地址。从那以后我每次销毁链表都强制先写q p-next再写free(p)。4.2 现象CMake 报 undefined reference toInitList工程中单独测试链表模块时编译能过链接时报undefined reference to某个函数例如InitList。原因头文件linklist.h被main.c包含了但src/linklist.c没有加入add_executable。CMake 的链接阶段只链接 target 里列出的源文件缺少的源文件自然找不到。解决打开 CMakeLists.txt把src/linklist.c补进add_executable然后重新 Reload。排查时先看报错函数在哪一个.c文件里定义再确认那个.c文件是否出现在 CMake 配置中。也可以用 cmake 的提示信息辅助定位CLion 的 Messaging Window 里会列出Target ds_main is missing a source file。4.3 现象运行结果和书上不一致有时完全空白输入数据后没有任何输出或者输出的顺序和预期差一大截。最常见的是用scanf(%d, n)读入后程序立刻跳过后续循环连printf都没执行。原因scanf从输入缓冲区读数据时如果缓冲区里有残留换行符或者读取失败后没有清理后面的输入操作就会直接失败。特别是对照答案反复调试时人肉输入的空格、回车都会成为隐藏字符。解决每次scanf后检查返回值或者在读取前清空缓冲区scanf(%d, n); while (getchar() ! \n);这段代码的作用是把缓冲区中第一行剩下的字符全部消费掉。严格来说while (getchar() ! \n)在读到 EOF 时可能死循环但放在练习代码里够用。更稳妥的做法是用fgets读取整行再用sscanf解析资源中不少演示入口是这么处理的。4.4 现象CLion 输出中文乱码调试信息也乱运行结果里的中文提示变成了一片乱码比如当前节点data: 3显示成褰撳墠鑺傜偣。原因CLion 默认使用 UTF-8 编码而 Windows 控制台默认使用 GBK 编码。程序在 UTF-8 环境下编译在 GBK 控制台输出字符编码必然冲突。解决在 CLion 的 File Encoding 里把工程编码设为GBK或者统一改成UTF-8并在运行配置里添加环境变量。我一般会在代码开头设置兜底方案不加system(chcp 65001)而是在 CLion 的 Run Configuration 中把控制台编码切换为 UTF-8。如果不想改配置就把所有提示性字符串写成英文或拼音这是最省事的办法。4.5 现象参考答案使用SString直接赋值编译报类型错误有的答案里写了SString S hello;严蔚敏书中的SString是char SString[MAXSTRLEN 1]这种写法在 C 语言里不允许对数组直接赋值编译报 array type char [20] is not assignable。原因答案把 Pascal 或伪代码的赋值习惯搬到了 C 里。数组类型本身不是可修改的左值不能用整体赋值。解决使用strcpy或者strncpy。考虑边界建议用char S[MAXSTRLEN 1]; strncpy(S, hello, MAXSTRLEN); S[MAXSTRLEN] \0;strncpy不会自动补结束符所以最后手动给S[MAXSTRLEN]置\0能避免因为字符串过长而丢失结束符。资源里所有涉及字符串赋值的位置都改成了这种写法。5. 算法优化与执行过程说明从暴力枚举到 KMP、排序与递归追踪5.1 暴力枚举和 KMP 的复杂度边界课后习题里经常会出现字符串匹配相关的题比较典型的解法是暴力枚举。下面这段是最朴素的写法int BruteForce(const char *S, const char *T, int pos) { int i pos; int j 0; while (S[i] ! \0 T[j] ! \0) { if (S[i] T[j]) { i; j; } else { i i - j 1; j 0; } } if (T[j] \0) { return i - j; } return -1; }逻辑说明i - j 1是回溯操作主串指针回到本次匹配起始位置的下一个字符模式串指针归零。这个写法在理想情况下是 O(nm)但遇到S aaaaaaaaab、T aab这类数据时每一轮比较几乎都走到最后才发现失配总比较次数接近 O(n*m)。资源中给出的 KMP 优化点关键是把 j 的回退从 从头开始 改成 跳到 next[j]使得主串指针 i 永不回头。刷题时如果题目要求在长文本中统计短串出现次数暴力法大概率超时KMP 才是最稳的方案。5.2 排序算法的实现差异与参数细节排序一章是期末复习的重灾区。资源里同时实现了冒泡、快排和堆排序并对快排做了取中位数和随机化处理。下面给一份普通的快速排序递归实现void QuickSort(int A[], int low, int high) { if (low high) { int pivot A[low]; int i low; int j high; while (i j) { while (i j A[j] pivot) { --j; } A[i] A[j]; while (i j A[i] pivot) { i; } A[j] A[i]; } A[i] pivot; QuickSort(A, low, i - 1); QuickSort(A, i 1, high); } }参数说明low和high是闭区间下标调用时写QuickSort(arr, 0, n-1)。循环中必须写和不能只写或否则遇到大量重复元素时i 和 j 会卡在原地递归无法推进。这种写法每次把基准值挖出来通过左右填坑完成一次划分。如果数据是基本有序的数组固定取A[low]作为基准会让快排退化成 O(n²)。优化方式是改成三数取中int mid low (high - low) / 2; if (A[low] A[mid]) swap(A[low], A[mid]); if (A[low] A[high]) swap(A[low], A[high]); if (A[mid] A[high]) swap(A[mid], A[high]); swap(A[mid], A[low]);代码含义先把 low、mid、high 三个位置的数值排序取中间值作为基准再换到low位置这样可以规避有序数组带来的最坏情况。资源里把这段逻辑写在注释里因为它直接影响排序性能。堆排序在严蔚敏书里属于理解优先、代码可以后放的内容但考试常考建堆过程。资源中实现采用了大顶堆排序时把堆顶和堆尾交换再对剩余部分HeapAdjust执行过程注释里画了数组下标换位关系方便读者对照手动模拟。5.3 递归算法执行过程的观察方法很多习题要求写出递归过程的输出顺序比如汉诺塔、二叉树先序遍历、Fibonacci。只看源码很难理解资源中给出的做法是额外保留一个深度参数把递归层数打印出来void PreOrder(BiTree T, int depth) { if (T NULL) { return; } printf(depth%d data%d\n, depth, T-data); PreOrder(T-lchild, depth 1); PreOrder(T-rchild, depth 1); }调用时从PreOrder(T, 1)开始。这样每一行输出都带深度信息可以在控制台里直接还原递归栈的进入顺序。初学者如果觉得输出还是不好理解可以用 CLion 左侧的调试器在PreOrder函数入口加断点每次暂停时观察T的指向。调试器的 Call Stack 面板会显示完整的函数调用链这是教科书上画了很久的递归示意图在真实程序中的样子。5.4 赠品资源与扩展方向资源包的ReadMe.txt里提供了五本经典算法与数据结构书籍的补充材料。这部分不参与 CMake 构建需要单独打开文件查看。我建议的顺序是先把严蔚敏书中每章的Status、ElemType等抽象类型搞清楚再去看那五本书中对应的章节。数据结构是 C 语言指针应用的大杂烩只看不练很快就会遗忘。每章至少保证动手运行两个示例一个按书上的原始思路实现一个用自己优化过的方式实现对比两者的输出和时间消耗。6. 验证方法用最小测试骨架和调试器过一遍每道算法题6.1 给每个算法题配一个固定测试入口我自己的习惯是每道算法设计题都不直接调main而是单独建一个assert测试函数。比如验证顺序表删除void test_delete_sequence() { SqList L; InitList(L); for (int i 1; i 5; i) { ListInsert(L, i, i); } int e 0; Status ret ListDelete(L, 3, e); assert(ret OK); assert(e 3); assert(L.length 4); printf(test_delete_sequence pass\n); }这样每次改动算法后只要跑一遍测试函数就可以定位是哪一个操作改坏了。条件允许时再对边界情况补一组测试删除第 0 个、删除最后一个、空表删除。资源里没有把这些写成完整的单元测试框架但我强烈建议刷题时保留这一段因为参考答案的入口函数通常只验证正常情况边界条件才是最容易被算法题考察的地方。6.2 用调试器确认链表的每个 next 状态验证链表、树这类指针密集型算法光看输出不够。比如反转链表输出结果可能正确但指针指向不一定符合预期。在函数主循环加断点每执行一次就在 Watch 窗口输入p、next查看地址和data是否成链条关系。这一步很朴素但能避免很多这次能跑、换一组数据就崩的隐患。6.3 期末复习时的资源组织顺序刷题时我会按下面这个顺序使用资源章节必做算法题建议验证方式线性表顺序表插入删除、单链表逆置测试边界输入 调试器观察指针栈和队列括号匹配、循环队列判空溢出打印每次出入栈状态串KMP 与 next 数组计算对照手工计算 next 验证返回值树先序中序推导结构、求深度递归断点 Call Stack 观察图邻接表构造、DFS/BFS画状态表对比输出顺序排序快排、堆排打印每次划分后的数组这张表对应的核心做法是每完成一个章节把该章算法题的入口函数都调用一次确保在调试器里至少完整跑通一遍。我当年就是偷懒跳过了栈那章结果后期图算法里的 DFS 递归怎么都理解不透后来老老实实回来补课才把递归函数和栈帧的关系串起来。从那以后我每学完一个章节都强制把习题答案在调试器里手动走一遍而不是只看输出对不对。希望帮到你。本文还有配套的精品资源点击获取