严蔚敏《数据结构》C语言版算法设计题实战：从类C伪代码到可运行实现

简介面向严蔚敏《数据结构C语言版·第2版》的学习者这一压缩包汇集了书中算法源码与算法设计题参考答案适合备考数据结构或练习代码实现的读者在CLion 2020~2021中按CMake配置说明即可部署运行。资源采用RAR格式体积约3.14MB内部包含源码工程与题解说明文本并附有ReadMe.txt提供五本经典算法/数据结构书籍的赠阅链接。目前已有1220人下载学习内容经作者逐题推敲优化了部分书中算法纠正了参考答案中的全部错误并针对bug触发条件、不同实现方法、优化思路及执行过程给出清晰注释。这份材料能帮助读者避开常见陷阱配套可运行工程文件是将教材知识转化为编码能力的高质量辅助。1. 严蔚敏《数据结构(C语言版)》第2版算法设计题为什么要自己敲一遍严蔚敏《数据结构》(C语言版)第2版是本科数据结构和考研 408 绕不开的一本教材几乎每个学计算机的都有一本实体书或者电脑里躺着它的 pdf 扫描版。这本书有个劝退无数人的特点书里的算法全写成类 C 伪代码Status、ElemType、引用参数 都是教材自己的约定直接抄进编译器一行都跑不了。而每章后面的算法设计题又恰恰是数据结构期末复习、数据结构实验报告和考研代码题的素材来源。市面上确实有不少「算法设计题答案与书中算法源码」资料但拿到手就会发现要么答案是手写截图要么代码编译不过要么只有书里的原算法没有课后题解答。这篇笔记按「书里算法描述 → 能编译的 C 代码 → 测试验证」这条线走一遍把算法设计题落地时最高频的写法、参数约定和最典型的坑讲透。适合正在上课交实验报告的学生、刷王道数据结构的备考者以及想借这本书补 C 语言指针基本功的开发者。2. 把书里的类C代码改成能跑的程序公共头文件与顺序表实现很多人第一次打开这本书照着第 2 章的算法敲完gcc 一跑全是错然后就得出「这书代码有毛病」的结论。其实问题不在书而在于教材和可编译 C 程序之间隔着三层东西没补齐。2.1 严蔚敏版代码和标准 C 之间的三个差距第一层是宏与类型的约定缺失。书在开头统一定义了Status、ElemType、OK、ERROR、TRUE、FALSE这些东西但每个算法清单里不会重复写。你单独抄一个ListInsert编译器第一行就报unknown type name Status。这跟网上流传的「书中算法源码」质量参差是同一个原因——资源作者自己的公共头文件没贴出来或者贴了也没提醒你先编译它。第二层是引用参数。书里的SqList L是 C 写法纯 C 没有引用必须改写成SqList *L调用处变成L。很多实验报告为了省事直接把表定义成全局变量函数里改谁都能生效。这样交作业没问题但考研 408 的代码题是让你写函数全局变量这一套在考场上是要扣分的它绕过了指针这个最重要的基本功。第三层是没有测试入口。书给的是函数不是程序没有 main没有构造数据的代码。你需要自己写一个测试壳初始化表、插入数据、调用操作、打印结果。这也解释了为什么你下载的源码包经常缺东西它把最靠近「能运行」的那一层省掉了。提示拿到一份严蔚敏数据结构的源码资料先看三样东西——公共头文件有没有、引用参数怎么处理的、有没有测试 main。缺一样这份资料的价值就打折一半。2.2 公共头文件把 Status、ElemType 和返回值约定一次配齐我自己的做法是给全书所有算法配一个common.h不管哪个章节的代码第一行都是#include common.h。这个头文件其实很短/* common.h —— 严蔚敏《数据结构 C语言版》代码的公共头文件 * 所有章节的算法都依赖这里的宏和类型定义 */ #ifndef DATASTRUCT_COMMON_H #define DATASTRUCT_COMMON_H #include stdio.h #include stdlib.h #include string.h #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; /* 函数运行状态OK / ERROR / OVERFLOW */ typedef int ElemType; /* 元素类型做不同章节题目时统一改这里 */ #endif这个头文件解决的是「每个算法都假设但你找不到」的那组定义。Status统一成int函数就能返回OK或ERROR作为状态码跟书上的伪代码一一对应。ElemType默认int到串那一章改成char到广义表或者矩阵那章改成结构体只动这一行其他算法代码不用改。有个细节值得注意书里很多算法用的是动态分配的SqList里面存的是ElemType *elem不是定长数组。所以stdlib.h必须引入malloc、realloc、free全依赖它。string.h是给串那一章的StrAssign之类用的提前放进去省得每章再补。至于引用参数处理原则只有一条既然选择用 C 编译器就把书里所有L改写成*L并且把改写的这步当成练习的一部分做。你抄 20 个算法之后会发现一个规律——凡是函数内部要修改表结构、头指针、树根的都必须传指针只读不改的参数可以按值传。这个判断做多了考场上写函数签名基本不会错。2.3 顺序表完整实现动态分配、插入、就地逆置第 2 章课后算法设计题里顺序表相关的题目占了一半以上插入、删除、逆置、合并、去重。严蔚敏教材里顺序表的定义用的是动态分配我第一次照着王道那个data[MAXSIZE]定长版本写结果发现跟书上算法对不上因为书里的插入有扩容逻辑。下面这个版本跟书完全对齐#include common.h #define LIST_INIT_SIZE 100 /* 初始容量 */ #define LISTINCREMENT 10 /* 每次扩容增量 */ typedef struct { ElemType *elem; /* 存储空间基址malloc 分配 */ int length; /* 当前元素个数 */ int listsize; /* 当前已分配容量 */ } SqList; /* 构造空表 */ Status InitList(SqList *L) { L-elem (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if (L-elem NULL) return OVERFLOW; /* 分配失败 */ L-length 0; L-listsize LIST_INIT_SIZE; return OK; } /* 在位置 i从 1 开始插入元素 e */ Status ListInsert(SqList *L, int i, ElemType e) { ElemType *newbase; int k; if (i 1 || i L-length 1) return ERROR; /* 位置非法 */ if (L-length L-listsize) { /* 容量不足则扩容 */ newbase (ElemType *)realloc(L-elem, (L-listsize LISTINCREMENT) * sizeof(ElemType)); if (newbase NULL) return OVERFLOW; L-elem newbase; L-listsize LISTINCREMENT; } for (k L-length; k i; k--) L-elem[k] L-elem[k - 1]; /* 从后往前搬避免覆盖未移动元素 */ L-elem[i - 1] e; /* 数组下标比逻辑位置少 1 */ L-length; return OK; } /* 就地逆置首尾元素两两交换 */ Status ReverseSqList(SqList *L) { int i, j; ElemType tmp; if (L-length 1) return OK; /* 空表或单元素直接返回 */ for (i 0, j L-length - 1; i j; i, j--) { tmp L-elem[i]; L-elem[i] L-elem[j]; L-elem[j] tmp; } return OK; }几个参数和边界要交代清楚。i的逻辑位置从 1 计数这是书里的习惯但数组下标从 0 开始所以L-elem[i - 1]。插入合法的位置范围是1到length 1length 1表示追加到表尾这个边界最容易漏。搬移元素必须从最后一个开始往前搬如果从前往后elem[k] elem[k - 1]会把后面的值提前覆盖结果就是整段数据变成同一个值。ReverseSqList就是双指针思想的雏形一个指针从头走一个从尾走相遇即停时间复杂度 O(n)。这个思路在后面链表找中间节点、判断回文、快慢指针那一类题里反复出现值得在抄写答案的时候把它标成重点。realloc的返回值一定要判断而且要用临时变量接住——如果用L-elem realloc(...)且分配失败原来的指针就丢了这叫内存泄漏加数据丢失双重翻车。3. 线性表与栈的算法设计题链表逆置、有序表合并、括号匹配第 2 章和第 3 章的课后题翻来覆去就考几件事单链表的各种操作、有序表合并、栈和队列的应用。这几道题我建议直接背下来因为它们是后面树、图、排序章节的基础操作。3.1 单链表就地逆置迭代版必须背熟递归版要知道代价单链表逆置是数据结构 C语言 里被检索最多的一道题也是算法设计题答案里出现频率最高的。网上版本很多但最稳的还是三指针迭代法。链表节点定义跟书保持一致#include common.h typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; /* 迭代版就地逆置只改指针方向不申请新节点 */ LinkList ReverseIter(LinkList head) { LNode *prev NULL; /* 前驱初始为 NULL */ LNode *curr head; /* 当前节点 */ LNode *next; /* 后继必须先存下来 */ while (curr ! NULL) { next curr-next; /* 记住下一个节点否则改完 next 就丢了 */ curr-next prev; /* 当前节点指针调头 */ prev curr; /* 三个指针整体后移 */ curr next; } return prev; /* 原链表尾节点成为新头 */ }核心逻辑就一句话遍历时把每个节点的next指向前驱但改之前必须先保存原来的后继。漏掉next curr-next这一行链表从第二个节点开始就断了这是几乎所有新手必踩的坑。函数返回新头调用处要写成head ReverseIter(head);因为参数是值传递函数内部改head影响不到外面。递归版也经常作为答案出现/* 递归版逆置先逆置后继链表再把当前节点接上去 */ LinkList ReverseRecur(LinkList head) { LinkList newHead; if (head NULL || head-next NULL) return head; /* 空表或单节点递归基 */ newHead ReverseRecur(head-next); /* 后面的链表已经逆好了 */ head-next-next head; /* 让原来的后继节点指回自己 */ head-next NULL; /* 切断正向链接防止成环 */ return newHead; }递归版看起来简洁但有两个隐藏代价递归深度等于链表长度十万个节点的链表直接爆栈而且递归现场有很多人想不清楚head-next-next到底在操作谁。我的建议是考试写迭代版面试被问递归思路再补递归版两个都会但不迷信递归。3.2 合并两个有序链表归并排序算法的线性表预演合并两个递增有序链表这道题是归并排序算法里merge步骤的链表版本王道数据结构里也把它列为基础必会题。写法上用头节点哨兵能省掉不少空表判断/* 合并两个递增有序链表返回新链表头。a、b 会随指针移动调用后失效 */ LinkList MergeSortedList(LinkList a, LinkList b) { LinkList head (LinkList)malloc(sizeof(LNode)); /* 哨兵节点 */ LNode *tail head; /* tail 始终指向结果链表尾部 */ while (a ! NULL b ! NULL) { if (a-data b-data) { tail-next a; a a-next; } else { tail-next b; b b-next; } tail tail-next; /* 尾部指针前进 */ tail-next NULL; /* 先把末尾断干净避免尾巴挂着旧 next */ } tail-next (a ! NULL) ? a : b; /* 剩余的一段整体接上 */ return head-next; /* 跳过头节点 */ }这里的参数是两层含义a、b本身是指向节点的指针函数内重新赋值只改函数局部的拷贝所以调用方不用担心里面的值被破坏。哨兵head唯一的作用是让循环里第一次挂节点时有个可以承接的节点返回时head-next才是真正的链表头。这段代码里tail-next-next NULL也可以省略因为每次取走的节点本来就带着空尾但写上心里更踏实防止出现环形链。这道题的归并思想往后要复制两次一次是归并排序算法的数组版本一次是链表的归并排序。你会发现数组归并需要一个临时数组来回拷贝而链表归并只需要改指针省空间。这就是课后题的价值——它提前预演了第 10 章的内容。3.3 括号匹配用顺序栈处理嵌套结构的标准答法括号匹配是栈章节的入门题也是很多学校数据结构实验报告里的必选题目。它的本质是遇到左括号入栈遇到右括号跟栈顶配对配对成功弹出失败直接报错。因为嵌套结构最内层的括号最先闭合正好符合栈后进先出的特性。#include common.h /* 括号匹配括号串只包含 ( ) [ ] { } 四类 */ Status MatchBrackets(const char *s) { char stack[1024]; /* 顺序栈用数组模拟 */ int top -1; /* 栈顶下标空栈为 -1 */ int i; char left; for (i 0; s[i] ! \0; i) { if (s[i] ( || s[i] [ || s[i] {) { if (top 1023) return ERROR; /* 栈满说明嵌套太深 */ stack[top] s[i]; /* 入栈 */ } else if (s[i] ) || s[i] ] || s[i] }) { if (top 0) return FALSE; /* 右括号来了栈却是空的 */ left stack[top--]; /* 弹出栈顶左括号 */ if ((s[i] ) left ! () || (s[i] ] left ! [) || (s[i] } left ! {)) return FALSE; /* 配错了 */ } } return (top -1) ? TRUE : FALSE; /* 栈非空说明有左括号没闭合 */ }逻辑上要区分三种失败情况右括号多于左括号栈提前空左括号多于右括号循环结束栈还非空左右顺序错配比如([)]。前两种是数不对第三种是序不对。考试写这题能把三种情况分别描述清楚并写出对应判断基本就是满分答案。栈的应用不止括号匹配表达式求值、数制转换、递归改非递归都是它的场景。理解了「栈顶就是最近未处理的对象」这句话这些题其实同一个套路。4. 树和图的遍历代码从递归到显式栈再到邻接表 DFS树和图是严蔚敏教材里篇幅最重的两章也是考研算法设计题的主战场。这一章的课后题核心都围绕遍历展开二叉树的三种递归遍历、非递归遍历、按层遍历以及图的 DFS 和 BFS。这些代码的框架一旦建好后面求深度、求叶子数、找路径、判断连通性都是填空级的工作。4.1 二叉树三种递归遍历空判断比 printf 更重要二叉树的递归遍历表面上只是访问根节点的时机不同但大多数人第一次写会错在递归基上。先看框架#include common.h typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; /* 先序遍历根 - 左 - 右 */ void PreOrder(BiTree T) { if (T NULL) return; /* 空树直接返回这是递归基 */ printf(%d , T-data); PreOrder(T-lchild); PreOrder(T-rchild); } /* 中序遍历左 - 根 - 右 */ void InOrder(BiTree T) { if (T NULL) return; InOrder(T-lchild); printf(%d , T-data); InOrder(T-rchild); } /* 后序遍历左 - 右 - 根 */ void PostOrder(BiTree T) { if (T NULL) return; PostOrder(T-lchild); PostOrder(T-rchild); printf(%d , T-data); }这三个函数只有一行差别就是printf的位置。递归遍历的难点不在访问逻辑而在时刻记住「每个节点的左右子树也是一棵树」。少了if (T NULL) return;这一行递归永远不会结束最终段错误。这个空判断同时是后序题目的基础比如求二叉树深度/* 求深度左右子树深度较大者 1 */ int TreeDepth(BiTree T) { int left, right; if (T NULL) return 0; /* 空树深度为 0 */ left TreeDepth(T-lchild); right TreeDepth(T-rchild); return (left right ? left : right) 1; }求叶子数就是把「访问根节点」那步换成「判断左右孩子是否都为空」模板直接套。这类递归题最容易犯的错是把返回值丢掉TreeDepth(T-lchild);不接返回值算出来的深度全是 0。4.2 非递归中序遍历用显式栈模拟系统调用栈非递归遍历是算法设计题里区分度最高的一题因为递归调用的过程编译器帮你压栈弹栈一旦不允许递归你得自己把栈写出来。中序非递归的思路是从根出发一路向左压栈压到空弹栈访问然后转向右子树重复这个过程。/* 中序非递归显式栈保存待访问节点 */ void InOrderNonRec(BiTree T) { BiTree stack[100]; /* 栈存放节点指针 */ int top -1; BiTree p T; /* p 是当前游标 */ while (p ! NULL || top 0) { while (p ! NULL) { /* 一路沿左链入栈 */ stack[top] p; p p-lchild; } if (top 0) { /* 弹栈访问再转向右子树 */ p stack[top--]; printf(%d , p-data); p p-rchild; } } }理解这段代码要记住一个关键点p p-rchild;执行完如果右子树为空内层while不会执行直接走弹栈分支。所以外层while的条件必须是p ! NULL || top 0两个条件缺一不可。只写p ! NULL弹完栈就停了只写top 0第一次循环 p 为空根本进不来。后序非递归更麻烦因为访问根节点前必须先确认右子树处理完了。常见解法有双栈法和加lastVisited指针法考试时写双栈法更容易说清楚用两个栈先按先序遍历变体压栈弹出来倒序就是后序。这个细节很多资料讲得含糊我的建议是先把中序非递归彻底背熟它能保证你在考场上拿到基础分。4.3 图的邻接表与 DFSvisited 数组是防止死循环的命门图的存储结构首选邻接表因为它比邻接矩阵省空间稀疏图尤其明显。严蔚敏教材的邻接表定义是「顶点数组 边链表」的组合翻译成 C#include common.h #define MAX_VERTEX_NUM 20 typedef struct ArcNode { /* 边表节点 */ int adjvex; /* 该边指向的顶点下标 */ struct ArcNode *nextarc; /* 下一条边 */ } ArcNode; typedef struct VNode { /* 顶点表节点 */ char data; ArcNode *firstarc; /* 第一条依附于该顶点的边 */ } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; /* 顶点数、边数 */ } ALGraph; int visited[MAX_VERTEX_NUM]; /* 全局访问标记数组 */ /* 深度优先遍历从顶点 v 出发 */ void DFS(ALGraph *G, int v) { ArcNode *p; visited[v] 1; /* 先标记再访问 */ printf(%c , G-vertices[v].data); for (p G-vertices[v].firstarc; p ! NULL; p p-nextarc) { if (!visited[p-adjvex]) /* 只对没访问过的邻接点递归 */ DFS(G, p-adjvex); } }visited数组是整个 DFS 的灵魂。没有它图里只要有一个环递归就无限循环。注意标记的时机进入函数第一件事就是visited[v] 1不是在访问完孩子之后。如果写完递归再标记环上的两个节点会互相反复进入。关于指针遍历的写法p p-nextarc必须写在循环里很多人误写成p G-vertices[v].firstarc-nextarc结果每轮都从同一条边出发死循环。邻接表的边是插入到链表头还是尾取决于建图代码但 DFS 的逻辑不依赖顺序所以遍历结果可能不同这是正常的。BFS 就是把递归栈换成队列访问顺序从深度优先变成按层框架几乎一样课后题配套练一次就能掌握。5. 严蔚敏源码避坑清单编译失败、越界和指针丢失的排查这一章写的是我在用这本书做题、以及帮学生改实验报告时反复遇到的五个问题。每条按「现象 → 原因 → 解决」来写基本可以照着排查。5.1 编译报错unknown type name Status 和 ElemType现象gcc 编译报一连串unknown type name Status、unknown type name ElemType然后连带报几十个语法错误。原因只抄了算法片段没带上教材前文的宏定义和类型定义。所有「书中算法源码版」资料都有这个通病因为作者默认你手里有公共头文件。解决按第 2 章的common.h建文件放在同一个目录写一句#include common.h。如果你下载的源码包里没有这个头文件自己补一份不复杂。判断资料质量的一个快捷方式就是看它有没有单独提供这个公共文件。5.2 顺序表插入后数据错乱或者直接段错误现象连续用ListInsert插入 120 个元素程序跑到某个位置数据全是同一个值或者直接崩溃。原因定长数组版本里length MAXSIZE没判断元素写到了数组外面动态版本里大概率是realloc失败后直接用了原指针或者扩容条件写成了导致差一个元素就溢出。解决插入函数开头先判位置合法性再判容量。动态版本一定要用newbase接住realloc返回值分配失败返回OVERFLOW同时调试时在ListInsert里打印length和listsize一看就能定位是扩容没触发还是触发太晚。5.3 链表逆置后打印输出还是原来的旧链表现象调用了逆置函数回到 main 里打印链表结果只输出一个节点或者还是原来的顺序。原因函数参数是LinkList head这是值传递。函数内部把局部变量head改成新头了但调用处的头指针没变。这是 C 语言指针最典型的一个坑你以为传的是指针就能改但指针本身也是值。解决两种写法任选其一。要么逆置函数返回新头调用处写head ReverseIter(head);要么传二级指针void ReverseIter(LinkList *head)函数里*head重新赋值。我一般统一用返回新头的方式因为更好读而且 408 代码题里返回值是允许的。5.4 KMP 算法的 next 数组算错匹配死循环或越界现象写 kmp算法 匹配时模式串在某个位置来回跳i不前进或者访问T[j]时 j 变成负数然后越界。原因next 数组手工推的和代码算的是两套规则。严蔚敏书里 next 的定义牵扯「最长相等前后缀」的前缀长度不同教材对next[0]的定义还不一样有的是 0 有的是 -1。代码里最容易错的是回溯时下标写错把j next[j]写成j next[i]。解决先固定一套约定并手推验证。我用的约定是next[0] -1/* 求模式串 T 的 next 数组 */ void GetNext(const char *T, int next[]) { int i 0, j -1; int len (int)strlen(T); next[0] -1; while (i len - 1) { if (j -1 || T[i] T[j]) { i; j; next[i] j; /* 匹配成功next 就是当前前缀长度 */ } else { j next[j]; /* 不匹配回溯到前缀的前缀 */ } } }写完后拿个字符串手动验证T abaabcac推出来的 next 数组应该是{-1, 0, 0, 1, 1, 2, 0, 1}。如果对不上就一行行对照循环过程检查九成是j next[j]的回溯路径没走对。5.5 二叉树非递归遍历进入死循环现象中序非递归遍历跑起来不结束一直在压栈弹栈top越来越大或者反复不变。原因进入右子树的代码丢了。弹栈访问完节点后没写p p-rchild;p 保持为刚弹出的旧节点内层 while 又会把它压回去形成死循环或者内层 while 里没写p p-lchild;同一个节点被反复压栈。解决回到第 4.2 节的模板确认两行都在内层循环必须写p p-lchild;弹栈后必须写p p-rchild;。如果还不放心就画一棵三个节点的树把每一步栈里的内容写出来对照。这类问题纸上走一遍比盯着代码看十遍都管用。6. 怎么验证算法设计题答案测试用例、内存检查与 408 考法光能把代码编译通过只说明语法对不说明逻辑对。严蔚敏课后题的答案资料满天飞但你真正要信的是自己验证过的代码。我一般会对每道算法设计题做三件事。第一件事补全边界测试用例。链表逆置至少要跑四组输入空链表、单节点、双节点、五个以上节点的普通链表。括号匹配要跑四类串纯嵌套的({[]})、交叉错配的([)]、左括号多、右括号多。很多资料里的答案是网上流传的经常只在一种输入下成立边界一测就暴露。数据结构期末复习时我也只用这一招快速筛查答案质量。第二件事用工具查内存问题。编译和运行不报错不代表没有越界或泄漏我习惯用 valgrindgcc -g -o test_linkedlist test_linkedlist.c common.h valgrind --leak-checkfull ./test_linkedlist看输出只要关注三类信息Invalid read/write说明内存越界definitely lost说明申请了没释放Conditional jump depends on uninitialised value说明用了未初始化变量。链表逆置、树的递归遍历这类指针密集的代码跑一遍 valgrind 能发现大量隐蔽问题。如果你用的是 Windows也可以先开编译器自带的 AddressSanitizer效果类似。第三件事对照 408 和王道数据结构的真题风格。408 统考里的代码大题难度恰好落在严蔚敏课后题的中低档链表逆置、二叉树遍历、排序、查找都是常客。数据结构排序算法里最简单的冒泡排序c语言 必须在 10 分钟内手写无 bug/* 冒泡排序加 flag 提前结束 */ void BubbleSort(int a[], int n) { int i, j, tmp, swapped; for (i 0; i n - 1; i) { swapped 0; /* 每轮开始重置标记 */ for (j 0; j n - 1 - i; j) if (a[j] a[j 1]) { tmp a[j]; a[j] a[j 1]; a[j 1] tmp; swapped 1; } if (!swapped) break; /* 整轮无交换说明已经有序 */ } }最后说说考场习惯。我做课后题时每题先在纸上写完整代码再敲进编译器验证最后把验证通过的版本标上注释归档。这样到了考场上即使没有编译器笔头也形成肌肉记忆。写代码题的得分点往往不是复杂逻辑而是边界处理和返回值设计这两点只有靠日常一组组测试用例磨出来。希望这篇笔记能帮你把手头的严蔚敏《数据结构》从「读过」变成「跑过」也希望能帮你在数据结构这条路上少踩几个我当年踩过的坑。本文还有配套的精品资源点击获取