严蔚敏《数据结构》C语言代码复现：从教学伪代码到可编译工程

简介这份资源是严蔚敏《数据结构与算法C语言》教材的配套代码实现合集面向计算机专业学生、考研备考者以及希望夯实算法基础的程序员用于对照教材动手实践各类数据结构与经典算法。压缩包共416个文件以154个cpp与154个c源文件为主辅以89个头文件另有少量txt说明、dat测试数据及工程配置文件整体约494KB体量轻便便于逐章查阅与编译调试。内容覆盖线性表、栈与队列、二叉树与平衡树、图及其遍历、排序查找、动态规划、贪心、回溯、分治以及最小生成树、最短路径、网络流等经典算法代码与书中章节对应可直接运行验证。目前已有1607人学习下载适合作为课程实验、考研复习与算法刷题的参考实现帮助读者在动手编码中理解数据结构的设计思路与算法的时间空间特性。1. 严蔚敏《数据结构与算法》C 语言代码实现为什么“照着抄”反而跑不通很多人第一次翻开严蔚敏那本《数据结构C 语言版》都会产生一个错觉书上的代码看起来清清楚楚伪代码加 C 语言混排逻辑也不复杂抄下来编译一下不就完事了结果一上手就翻车——Status是什么类型ElemType在哪定义InitList返回的OK和ERROR编译器根本不认识。这不是你水平不行而是这本书的代码本质上是“教学伪代码”它省略了大量工程实现细节需要读者自己补全一套可编译的骨架。这个标题真正要解决的问题就是把这套教学代码变成能在本地跑起来的 C 语言工程。适合两类人一是正在跟着教材学数据结构、想动手验证每个算法行为的学生二是准备考研或面试、需要把线性表、栈、队列、树、图这些结构亲手实现一遍的开发者。核心思路只有一条先搭一套统一的类型定义和状态码约定再按章节逐个把算法落成可编译、可测试的.c文件。下面我按自己实际复现的顺序把选型理由、目录组织、关键代码和踩过的坑讲清楚。2. 先搭骨架再写算法类型定义与工程目录怎么定2.1 为什么必须先统一 Status 和 ElemType严蔚敏书里所有函数几乎都返回Status所有数据元素都叫ElemType。如果你在每个.c文件里各定义一遍链接时必然重定义冲突如果完全不定义编译器直接报未知类型。常见做法是抽一个公共头文件把这两个类型和OK/ERROR/OVERFLOW三个状态码固定下来。这样做的好处是后续所有章节的代码都能复用同一套约定函数签名和书上保持一致对照阅读时不会产生认知负担。/* common.h —— 全工程公共类型与状态码 */ #ifndef COMMON_H #define COMMON_H #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define TRUE 1 #define FALSE 0 typedef int Status; /* 函数返回状态对应书中的 Status */ typedef int ElemType; /* 数据元素类型先默认 int可改 */ #endif这段代码的关键点在于ElemType用typedef而不是宏定义。用宏的话调试时看不到真实类型名用typedef可以在需要时改成float、char甚至结构体只要改一处。Status同理书中有时把它当布尔用有时当错误码用统一成int最省事。参数说明OK为 1、ERROR为 0 是书里的约定不要改成 0/1 反过来否则所有if (InitList(L) OK)的判断都会静默出错。2.2 目录结构按“线性结构 → 树 → 图 → 查找排序”分层我一般不会把所有.c堆在一个文件夹里而是按教材章节分目录每个目录一个Makefile或统一用顶层Makefile管理。这样做的理由是线性表、栈、队列之间有大量相似操作放一起方便对比树和图相对独立单独隔离避免命名冲突。下面是我实际用的目录布局。ds-c-implementation/ ├── common.h # 公共类型与状态码 ├── linear_list/ │ ├── sqlist.h │ ├── sqlist.c # 顺序表 │ ├── linklist.h │ └── linklist.c # 单链表 ├── stack_queue/ │ ├── sqstack.c # 顺序栈 │ ├── linkqueue.c # 链队列 │ └── ... ├── tree/ │ ├── bitree.c # 二叉树链表实现 │ └── ... ├── graph/ │ ├── mgraph.c # 邻接矩阵 │ └── algraph.c # 邻接表 ├── search_sort/ │ ├── bsearch.c │ └── ... └── Makefile每个.h只放结构体定义和函数声明.c放实现测试代码单独写在test_xxx.c里。这样编译时用gcc -c分别编译再链接能快速定位是哪个模块出错。注意书里很多结构体定义直接写在函数前面复现时要把它提到头文件里否则别的文件没法引用。2.3 最小可编译验证以顺序表为例跑通第一条链路骨架搭好后第一件事不是急着写树和图而是用顺序表验证整条编译链路是否通畅。顺序表的SqList结构体在书里是{ ElemType *elem; int length; int listsize; }动态分配版本比静态数组版本更贴近书中描述。下面给出头文件和初始化函数。/* sqlist.h */ #ifndef SQLIST_H #define SQLIST_H #include common.h #define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef struct { ElemType *elem; /* 基地址指针 */ int length; /* 当前长度 */ int listsize; /* 当前分配的容量 */ } SqList; Status InitList_Sq(SqList *L); Status ListInsert_Sq(SqList *L, int i, ElemType e); void PrintList_Sq(SqList *L); #endif/* sqlist.c */ #include stdio.h #include stdlib.h #include sqlist.h Status InitList_Sq(SqList *L) { L-elem (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType)); if (!L-elem) exit(OVERFLOW); /* 分配失败直接退出书中写法 */ L-length 0; L-listsize LIST_INIT_SIZE; return OK; } Status ListInsert_Sq(SqList *L, int i, ElemType e) { if (i 1 || i L-length 1) return ERROR; /* 位置非法 */ if (L-length L-listsize) { /* 容量满扩容 */ ElemType *newbase (ElemType *)realloc( L-elem, (L-listsize LISTINCREMENT) * sizeof(ElemType)); if (!newbase) exit(OVERFLOW); L-elem newbase; L-listsize LISTINCREMENT; } for (int j L-length; j i; j--) /* 后移 */ L-elem[j] L-elem[j - 1]; L-elem[i - 1] e; L-length; return OK; }逻辑说明InitList_Sq用malloc分配初始容量listsize记录的是“能放多少个元素”而不是字节数这一点书里写得很清楚但很容易抄错。ListInsert_Sq里位置判断用的是i L-length 1因为插入位置可以紧跟在最后一个元素之后。扩容用realloc而不是重新malloc加拷贝是因为realloc在可能的情况下会原地扩展效率更高。参数说明LIST_INIT_SIZE和LISTINCREMENT是书里的宏实际工程中可以调大但复现阶段建议保持原值方便和书上的复杂度分析对应。编译命令用gcc -I. linear_list/sqlist.c test_sqlist.c -o test_sqlist-I.表示在当前目录找common.h。如果报undefined reference to InitList_Sq八成是忘了把sqlist.c加进编译命令而不是代码写错了。3. 线性表、栈、队列指针操作最容易翻车的三个地方3.1 单链表插入为什么你的指针顺序一改就断链单链表是全书第一个真正考验指针理解的结构。书上的ListInsert_L核心就两行s-next p-next; p-next s;。但很多人自己写的时候会写成p-next s; s-next p-next;结果s-next指向了自己链表从s开始形成一个环遍历时死循环。血泪经验是先接后断顺序不能反。下面给出带头结点的单链表插入实现。/* linklist.c 片段 */ #include stdlib.h #include common.h typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList; Status ListInsert_L(LinkList L, int i, ElemType e) { LNode *p L; int j 0; while (p j i - 1) { /* 找到第 i-1 个结点 */ p p-next; j; } if (!p || j i - 1) return ERROR; LNode *s (LNode *)malloc(sizeof(LNode)); if (!s) exit(OVERFLOW); s-data e; s-next p-next; /* 第一步新结点指向原后继 */ p-next s; /* 第二步前驱指向新结点 */ return OK; }逻辑说明while循环的条件j i - 1是为了让p停在插入位置的前一个结点。如果i 1循环一次都不执行p就是头结点插入在第一个位置这是带头结点链表的标准做法。参数说明L是头指针不是头结点本身调用时传L而不是L因为头指针本身不需要修改。如果报段错误先检查malloc后有没有判空再检查while里p是否可能变成NULL后还访问p-next。3.2 顺序栈top 指针到底指向栈顶还是栈顶的下一个顺序栈的top语义是初学者最容易混淆的点。严蔚敏书里的约定是top指向栈顶元素的下一个位置即S.top S.base表示空栈入栈时先*S.top e出栈时先--S.top再取*S.top。如果你按“top 指向栈顶元素”来写所有边界判断都会差一位。下面按书中约定实现。/* sqstack.c 片段 */ #include stdlib.h #include common.h #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 typedef struct { ElemType *base; ElemType *top; int stacksize; } SqStack; Status InitStack(SqStack *S) { S-base (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType)); if (!S-base) exit(OVERFLOW); S-top S-base; /* 空栈top base */ S-stacksize STACK_INIT_SIZE; return OK; } Status Push(SqStack *S, ElemType e) { if (S-top - S-base S-stacksize) { /* 栈满扩容 */ S-base (ElemType *)realloc( S-base, (S-stacksize STACKINCREMENT) * sizeof(ElemType)); if (!S-base) exit(OVERFLOW); S-top S-base S-stacksize; /* 重设 top */ S-stacksize STACKINCREMENT; } *S-top e; /* 先赋值再后移 */ return OK; } Status Pop(SqStack *S, ElemType *e) { if (S-top S-base) return ERROR; /* 空栈 */ *e *--S-top; /* 先前移再取值 */ return OK; }逻辑说明扩容后必须重设S-top因为realloc可能把内存块搬到新地址原来的top指针就悬空了。这是顺序栈最隐蔽的坑很多人扩容后不重设top程序在小数据量下正常一超过初始容量就崩溃。参数说明S-top - S-base得到的是当前元素个数因为指针相减得到的是元素个数而不是字节数。Push和Pop都传SqStack *S因为要修改结构体内部的指针。3.3 链队列出队时什么时候需要修改队尾指针链队列的难点在于当队列中只有一个元素时出队后队列变空此时rear指针必须重新指向头结点否则rear变成野指针下一次入队就会写到非法内存。书上的DeQueue用了一个判断if (Q.front Q.rear) Q.rear Q.front;来处理这种情况。下面给出完整实现。/* linkqueue.c 片段 */ #include stdlib.h #include common.h typedef struct QNode { ElemType data; struct QNode *next; } QNode, *QueuePtr; typedef struct { QueuePtr front; /* 头指针指向头结点 */ QueuePtr rear; /* 尾指针指向最后一个结点 */ } LinkQueue; Status InitQueue(LinkQueue *Q) { Q-front Q-rear (QueuePtr)malloc(sizeof(QNode)); if (!Q-front) exit(OVERFLOW); Q-front-next NULL; return OK; } Status EnQueue(LinkQueue *Q, ElemType e) { QueuePtr p (QueuePtr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p-data e; p-next NULL; Q-rear-next p; /* 挂到队尾 */ Q-rear p; /* 更新队尾 */ return OK; } Status DeQueue(LinkQueue *Q, ElemType *e) { if (Q-front Q-rear) return ERROR; /* 空队列 */ QueuePtr p Q-front-next; /* 第一个数据结点 */ *e p-data; Q-front-next p-next; if (Q-rear p) Q-rear Q-front; /* 只剩一个元素时 */ free(p); return OK; }逻辑说明DeQueue里if (Q-rear p)判断的是“出队的恰好是最后一个结点”此时把rear拉回头结点队列回到初始空状态。如果不加这一句rear指向已被free的内存下次EnQueue时Q-rear-next p就是写野指针。参数说明Q-front始终指向头结点头结点不存数据这样空队列和非空队列的判断统一为front rear。4. 树与图递归写法和邻接结构里的边界条件4.1 二叉树遍历递归三行代码背后的空指针判断二叉树的先序、中序、后序遍历在书上各只有三行但直接抄下来如果漏了空指针判断遇到叶子结点的左右孩子就会崩溃。标准写法是if (T)开头先判断当前结点是否存在再递归。下面给出二叉链表定义和中序非递归遍历因为非递归版本更能暴露栈操作的细节。/* bitree.c 片段 */ #include stdlib.h #include common.h #include sqstack.h /* 复用第 3 章的栈 */ typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; /* 中序非递归遍历用栈模拟递归 */ void InOrderTraverse_NonRec(BiTree T) { SqStack S; InitStack(S); BiTree p T; while (p || S.top ! S.base) { /* p 非空或栈非空 */ if (p) { Push(S, (ElemType)(size_t)p); /* 指针转 int 存栈仅演示 */ p p-lchild; } else { ElemType e; Pop(S, e); p (BiTree)(size_t)e; printf(%d , p-data); p p-rchild; } } }逻辑说明非递归中序遍历的核心是“一路向左压栈弹栈时访问并转向右子树”。while条件是p || 栈非空两者缺一不可p非空表示还有左子树没走完栈非空表示还有祖先结点没访问。参数说明这里为了复用ElemType为int的栈把指针强制转成size_t再转int在 64 位系统上会截断指针仅用于演示逻辑。实际工程中应该单独定义一个存BiTree的栈或者把ElemType改成void *。这是一个典型的“教学代码能跑但工程上不能这么干”的例子。4.2 邻接矩阵与邻接表什么时候选哪个图的存储结构选择直接影响后续算法DFS、BFS、最小生成树、最短路径的写法。下面这张表是我在实际复现时总结的选型依据不是书上的原话但和书里的复杂度分析一致。对比项邻接矩阵邻接表空间复杂度O(n²)与边数无关O(ne)稀疏图省空间判断边 (i,j) 是否存在O(1)直接查arcs[i][j]O(度)需遍历链表遍历某顶点所有邻接点O(n)扫描整行O(度)效率高适合场景稠密图、频繁判断两点是否相邻稀疏图、频繁遍历邻接点书中对应结构MGraphALGraph选型理由如果图的边数接近 n²邻接矩阵的 O(1) 边判断优势明显如果边数远小于 n²邻接表不会浪费大量零元素空间。复现时建议两种都实现一遍因为后续 Prim 算法用邻接矩阵写更直观而拓扑排序用邻接表写更自然。4.3 图的深度优先遍历visited 数组为什么必须传引用DFS 的递归写法里visited数组用来标记已访问顶点防止重复访问和死循环。常见错误是把visited定义在函数内部每次递归都重新初始化导致同一个顶点被反复访问。正确做法是把visited作为参数传递或者定义为全局数组。下面给出邻接矩阵版本的 DFS。/* mgraph.c 片段 */ #include stdio.h #include common.h #define MAX_VERTEX_NUM 20 typedef struct { int vexs[MAX_VERTEX_NUM]; /* 顶点表 */ int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; /* 邻接矩阵 */ int vexnum, arcnum; } MGraph; int visited[MAX_VERTEX_NUM]; /* 全局访问标记初始全 0 */ void DFS(MGraph G, int v) { visited[v] 1; printf(%d , G.vexs[v]); for (int w 0; w G.vexnum; w) { if (G.arcs[v][w] ! 0 !visited[w]) /* 有边且未访问 */ DFS(G, w); } } void DFSTraverse(MGraph G) { for (int i 0; i G.vexnum; i) visited[i] 0; /* 只初始化一次 */ for (int v 0; v G.vexnum; v) if (!visited[v]) DFS(G, v); /* 处理非连通图 */ }逻辑说明DFSTraverse里的初始化循环只执行一次然后对每个未访问顶点调用DFS这样即使图不连通也能遍历所有分量。DFS内部先标记再打印再递归顺序不能反如果先递归再标记遇到环就会无限递归。参数说明G.arcs[v][w] ! 0表示有边如果边权可能为 0需要额外用一个hasEdge数组或把无边表示为INF。5. 避坑与排查复现严蔚敏代码时最常见的 5 个翻车现场5.1 编译报unknown type name Status现象每个.c文件单独编译时都报Status、ElemType未定义。原因没有包含common.h或者包含路径不对。解决在编译命令里加-I.并确保每个.c文件开头都有#include common.h。如果用了子目录-I要指向common.h所在目录。5.2 链表遍历进入死循环现象程序卡在while (p)里出不来。原因插入时指针顺序写反形成了环或者删除结点后没有把前驱的next指向后继。解决用纸笔画一遍指针变化确认s-next p-next在p-next s之前执行。调试时可以在while里加一个计数器超过length就break并打印错误。5.3realloc之后程序崩溃现象顺序表或顺序栈元素超过初始容量后程序在后续操作中段错误。原因realloc可能返回新地址但原来的top或elem指针没有更新。解决realloc的返回值必须先赋给临时指针判空后再赋回原指针顺序栈还要重设top base stacksize。5.4 图的 DFS 只访问了第一个连通分量现象非连通图遍历时只输出了一部分顶点。原因DFSTraverse里只调了一次DFS(G, 0)没有循环检查所有顶点。解决外层加for循环对每个!visited[v]的顶点调用DFS。这是书上明确写了但容易被忽略的细节。5.5 把ElemType改成char后输出乱码现象把typedef int ElemType改成char后printf(%d, e)输出的是 ASCII 码而不是字符。原因格式化字符串没有跟着改。解决ElemType为char时用%c为float时用%f。更稳妥的做法是写一个PrintElem(ElemType e)函数把格式化集中在一处改类型时只改这个函数。6. 进阶技巧用统一测试框架验证每个数据结构6.1 为什么需要一个最小测试框架复现教材代码最大的问题是“看起来对了”但边界条件没验证。我一般会写一个极简的测试宏每个数据结构对应一个test_xxx.c用断言检查返回值。这样每次改完代码跑一遍比手工输入数据可靠得多。下面是一个不依赖任何第三方库的测试宏。/* test_common.h */ #ifndef TEST_COMMON_H #define TEST_COMMON_H #include stdio.h #include stdlib.h static int test_pass 0; static int test_fail 0; #define ASSERT_EQ(expect, actual, msg) do { \ if ((expect) (actual)) { \ test_pass; \ } else { \ test_fail; \ printf(FAIL: %s, expect%d, actual%d\n, \ msg, (int)(expect), (int)(actual)); \ } \ } while (0) #define TEST_REPORT() \ printf(pass%d, fail%d\n, test_pass, test_fail) #endif逻辑说明ASSERT_EQ用do { ... } while (0)包裹保证在if语句中作为单条语句使用不会出错。test_pass和test_fail用static修饰每个测试文件独立计数。参数说明expect和actual都转成int比较适合Status和ElemType为int的场景如果ElemType改成浮点需要另写一个带误差的宏。6.2 以顺序表为例写一个完整测试/* test_sqlist.c */ #include stdio.h #include test_common.h #include sqlist.h int main(void) { SqList L; ASSERT_EQ(OK, InitList_Sq(L), init); ASSERT_EQ(0, L.length, init length); ASSERT_EQ(OK, ListInsert_Sq(L, 1, 10), insert 1st); ASSERT_EQ(OK, ListInsert_Sq(L, 2, 20), insert 2nd); ASSERT_EQ(OK, ListInsert_Sq(L, 2, 15), insert middle); ASSERT_EQ(3, L.length, length after 3 inserts); ASSERT_EQ(10, L.elem[0], elem[0]); ASSERT_EQ(15, L.elem[1], elem[1]); ASSERT_EQ(20, L.elem[2], elem[2]); ASSERT_EQ(ERROR, ListInsert_Sq(L, 5, 99), insert invalid pos); TEST_REPORT(); return test_fail 0 ? 1 : 0; }逻辑说明测试覆盖了初始化、尾部插入、中间插入、非法位置插入四种情况。ASSERT_EQ(ERROR, ListInsert_Sq(L, 5, 99), ...)验证的是位置判断逻辑因为当前长度为 3合法插入位置是 1 到 45 应该返回ERROR。参数说明return test_fail 0 ? 1 : 0让make test能根据退出码判断成功与否方便接入自动化脚本。6.3 把测试接入 MakefileCC gcc CFLAGS -I. -Wall -g TEST_SRCS $(wildcard test_*.c) TEST_BINS $(TEST_SRCS:.c) all: $(TEST_BINS) %: %.c $(CC) $(CFLAGS) $ linear_list/sqlist.c -o $ test: all for t in $(TEST_BINS); do ./$$t; done clean: rm -f $(TEST_BINS)逻辑说明%: %.c是模式规则把每个test_xxx.c编译成同名可执行文件。test目标依赖all然后逐个运行。参数说明-Wall打开所有警告-g保留调试信息。如果某个测试链接失败先检查对应的.c实现文件有没有加进编译命令。这套框架跑通后每学一个新结构就加一个test_xxx.c长期积累下来就是一套可回归验证的代码库。我自己的习惯是每复现完一个章节先不急着往下翻而是把这一章的测试全部跑绿再对比书上的复杂度分析确认行为一致。遇到指针操作宁可在纸上画三遍也不靠编译器报错来定位——因为指针错误往往不报错直接段错误后悔药都没得吃。希望帮到你。本文还有配套的精品资源点击获取