严蔚敏《数据结构》C语言代码实现与调试实战指南

简介一份与严蔚敏《数据结构与算法C语言版》配套的代码实现资源面向正在学习数据结构课程的高校学生、备考与自学者以及希望巩固算法基础的C语言程序员。资源以教材核心知识点为主线覆盖线性表、栈与队列、树与二叉树、图、排序与查找、递归与分治、动态规划等经典算法包含顺序表与链表的增删改查、二叉树遍历、图的深度与广度优先搜索、最小生成树、常见排序与查找等C语言实现可作为理论学习的对照代码与实验参考。压缩包共416个文件以.c与.cpp源程序、.h头文件为主包含154个c、154个cpp和89个h文件另有少量txt说明、dat数据及可执行文件等整体仅494KB便于下载与本地编译运行。目前已有1606人学习使用适合按章节查阅或结合教材逐段调试帮助加深对数据结构和算法设计思路的理解提升编程实现与排错能力。1. 教材代码实现前的认知准备1.1 这本书的代码是什么性质严蔚敏的《数据结构C语言版》在计算机专业学生心中的地位约等于《新华字典》在识字阶段的地位——不一定天天翻但需要的时候必须得有。很多人买了这本书或者从图书馆借来之后第一反应是翻到附录或者某个章节找一段能直接跑起来的完整代码。但翻来覆去会发现书里的代码大量使用“类C”写法比如Status、ElemType、SqList L这类抽象类型配上InitList(L)、ListInsert(L, i, e)这种操作函数声明整体更像一套严谨的算法描述框架而不是编译就能跑的工程代码。这种设计其实是刻意的。严蔚敏这本书的目标是讲清楚“数据对象、数据关系、基本操作”这三个层次把逻辑结构、存储结构和算法的关系掰开揉碎。教材代码的重点在于表达清楚思路而不是直接生产可交付的程序。所以很多结构体定义里会用ElemType代替具体的int或char用引用参数表示传址甚至有些地方用到了C的引用语法——这在纯C编译器里根本过不了。对初学者来说第一道坎就是能不能把书里的抽象描述改写成手写可运行代码。1.2 为什么要自己动手补全实现我见过很多同学把课本代码抄了一遍又一遍考试照样过但一到上机实验或者刷题就懵。原因很简单看代码和写代码是两种完全不同的认知活动。看书时你的大脑会自动忽略很多细节比如malloc返回值要不要判空、数组下标从0还是1开始、free之后要不要置NULL、循环边界能不能取等号。这些细节恰恰是运行结果正确与否的分水岭。自己动手实现一遍本质上是在做一次“降维翻译”把抽象的ADT抽象数据类型翻译成具体结构体把逻辑操作翻译成指针操作或内存操作把复杂度分析翻译成实际性能感知。比如你光看“顺序表插入平均移动n/2个元素”可能没感觉但当你真的用代码插入10万个元素、程序卡了半秒时就明白为什么链表在某些场景下更合适。这就是代码实现带来的附加价值。另外当下许多网课和实验平台比如王卓老师的数据结构PPT课件、洛谷题单、PTA习题集都以严蔚敏教材为核心参考。你要是能在教材代码的基础上写出自己的版本做课后题、写实验报告、应付机试都会顺手很多。接下来的内容我会按我实际学习和教学过程中总结的路线带你从零搭建一套可以运行的严蔚敏风格C语言代码库。2. 搭建一套通用的C语言实现模板2.1 编译环境与工具链选择这里先说明一下我下面的所有示例都基于纯C语言C99标准不涉及C特性。环境方面有几种选择Windows下推荐Dev-C或者Code::Blocks它们内置MinGW的gcc编译器新建一个Console项目就能直接编译运行。不推荐拿Visual Studio去直接编译严蔚敏风格的代码因为VS对C的支持默认走C模式malloc返回void*的隐式转换、bool类型这些地方容易报错。Linux/macOS下直接用gcc加文本编辑器Vim、VS Code都行编译命令简单明了gcc -stdc99 -g -Wall main.c sqlist.c -o demo。我实际用下来加-g -Wall这两个参数非常重要-g是生成调试信息-Wall会把可疑的写法都警告出来排错效率翻倍。还有一类选择是在线IDE比如OnlineGDB、菜鸟工具、IDEONE等。如果你只是临时验证一小段逻辑用在线IDE很方便不需要配置环境。但注意在线IDE大多不支持多文件项目操作对练习严蔚敏这种按“一个结构对应一个模块”的教材代码来说本地多文件编译才是更接近真实工程的做法。2.2 头文件、宏定义与Status类型设计严蔚敏教材里大量使用Status、ElemType、TRUE/FALSE、OK/ERROR等类型和宏。在纯C里手工实现这套基础设施只需要一个头文件我建议建一个common.h统一管理#ifndef COMMON_H #define COMMON_H #include stdio.h #include stdlib.h #include string.h #include stdbool.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; // 默认元素类型为int #endif这样写有几个好处。第一所有源文件只要#include common.h就能直接使用Status作为函数返回类型语义清晰。第二ElemType可以随时换成char、double甚至结构体测试时只需要改一处。第三stdbool.h提供了真正的bool类型配合TRUE/FALSE宏让逻辑判断更直观。我当年踩过一个坑如果不用#ifndef头文件保护多文件互相包含时会出现重复定义错误。所以无论你的头文件多简单保护宏一定不能省。2.3 从抽象操作到可运行代码的转化思路教材里每个ADT都给出了基本操作函数的声明比如InitList、DestroyList、ListEmpty、ListLength、GetElem、LocateElem、ListInsert、ListDelete。实现的时候我建议按下面的顺序推进画存储结构图。顺序表的连续内存、链表的不连续节点、二叉树的递归结构先在纸上画清楚。定义结构体。把图变成C语言的结构体注意指针字段存放的到底是地址还是逻辑关系。实现基本操作。先写最底层的Init和Destroy再写Length、Empty这种查状态的操作最后写增删改。写测试主函数。每实现一个函数立即测试不要等全部写完再统一跑。实测下来这种“边写边测”的方式能省掉大量调试时间。这套思路看起来简单但很多人会跳过第二步直接写操作函数结果结构体的字段没设计好写到一半推倒重来。数据结构代码的根基就是结构体定义这一步稳了后面就顺了。3. 五个经典数据结构的代码实现拆解3.1 顺序表最容易被低估的动态数组顺序表就是动态数组底层是一段连续内存。严蔚敏书里的定义是typedef struct { ElemType *elem; // 存储空间基址 int length; // 当前长度 int listsize; // 当前分配的存储容量 } SqList;关键操作是插入和删除。插入第i个位置逻辑位置从1开始时需要把第i个到第n个元素全部后移一格删除时则全部前移一格。这个“整体搬家”的过程就是顺序表的本质特征。我在实现时特别注意两点插入前要判断i是否在1 i length1范围内。容量不足时要使用realloc扩容。书里说“增加LISTINCREMENT个位置”实际上新增大小怎么定有讲究。我一般按oldsize * 2扩展这样摊还复杂度是O(1)频繁插入时性能更稳。如果每次只扩一个元素连续插入的代价会退化到O(n^2)。扩展函数长这样Status ListInsert(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; } ElemType *q (L-elem[i - 1]); for (ElemType *p (L-elem[L-length - 1]); p q; --p) *(p 1) *p; *q e; L-length; return OK; }这里注意realloc的返回值必须用新指针暂存防止扩容失败时把原来的指针覆盖掉。我看到很多新手直接L-elem realloc(...)一旦内存不足返回NULL原数据就丢了还泄漏内存。3.2 单链表指针操作的入门必修课链表在严蔚敏书里有两种形式带头节点和不带头节点。教材代码默认带头节点因为这个额外的“哨兵”能让插入、删除的代码统一处理第一个位置和中间位置不需要单独写if分支。这个设计我强烈建议保留。节点定义typedef struct LNode { ElemType data; struct LNode *next; } LNode, *LinkList;链表实现里最容易出错的三个点头插法、尾插法、删除节点。头插法做逆序很好用代码只有两行核心p-next L-next; // 新节点指向原来的第一个节点 L-next p; // 头节点指向新节点这两行的顺序完全不能反。先执行第二行会丢掉原来的第一个节点的地址形成悬空内存泄漏。尾插法则要维护一个尾指针tail每次在尾部连接新节点不要每次从头遍历到尾否则建链表的复杂度会变成O(n^2)。删除节点q的前驱是p时标准操作是p-next q-next; free(q);。这里有两个坑第一free(q)之后一定要手动q NULL否则变成野指针第二如果你还要用q-next里的数据比如要返回值必须先保存再free。我写删除函数时习惯先记下被删节点的值再改链、再释放Status ListDelete(LinkList L, int i, ElemType *e) { LinkList p L; int j 0; while (p-next j i - 1) { p p-next; j; } if (!p-next || j i - 1) return ERROR; LinkList q p-next; *e q-data; p-next q-next; free(q); q NULL; return OK; }调试链表代码我自己的经验是每次操作后打印一遍整个链表写个PrintList函数肉眼检查指针关系是否正确。这种“可视化输出”比单步调试更直观尤其当链表长度变长以后。3.3 栈与队列两种“受限”的线性结构栈和队列本质上还是线性结构但操作受限。栈是先进后出队列是先进先出。严蔚敏教材分别用顺序栈和链队列两种方式实现。我建议栈用顺序存储队列用链式存储这样能和教材保持一致也方便理解两种典型场景。栈的结构体typedef struct { ElemType *base; ElemType *top; int stacksize; } SqStack;顺序栈的核心是一个容易忽略的细节top指针指向栈顶元素的下一个位置还是栈顶元素本身严蔚敏教材是空栈时base top入栈先赋值再top出栈先--top再取元素。也就是说top指向栈顶元素的上一个空位。搞清这一点后栈的所有操作都不会写错。队列如果用链式注意队尾指针rear指向最后一个节点而队头指针front指向头节点不是第一个数据节点。入队操作时要判别队列是否为空空队列需要同时修改front和rear。每次写完都建议验证三个状态空队列、只有一个元素、多个元素。栈的经典应用场景是括号匹配、逆波兰表达式、递归转非递归。我练手时常做的一个小项目是用栈把中缀表达式转后缀表达式再计算后缀表达式的值。这个题目初看很绕但只要把栈的两个性质优先级比较、暂存操作符用熟代码就顺理成章。强烈建议你拿这个题目检验一下自己对栈的掌握程度。3.4 二叉树递归遍历的代码含量与坑二叉树这一章是数据结构教材里递归浓度最高的一章。教材代码给出二叉树节点的结构、前序中序后序递归遍历、层序遍历、求深度、叶子节点数等操作。其中递归遍历的代码简洁得让人怀疑是不是漏了什么东西typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void PreOrderTraverse(BiTree T) { if (T NULL) return; printf(%d , T-data); PreOrderTraverse(T-lchild); PreOrderTraverse(T-rchild); }就这么几行。但初学者最容易栽倒的地方是“递归建树”特别是怎么用先序序列构建一棵树。书上给出的例子通常是输入一个扩展二叉树的前序序列比如AB#C##D##其中#代表空指针。建树函数void CreateBiTree(BiTree *T) { ElemType ch; scanf(%c, ch); if (ch #) { *T NULL; } else { *T (BiTNode *)malloc(sizeof(BiTNode)); if (!*T) exit(OVERFLOW); (*T)-data ch; CreateBiTree((*T)-lchild); CreateBiTree((*T)-rchild); } }这里有个典型的C指针陷阱函数参数是BiTree *T也就是指向指针的指针。为什么要这样因为函数内部要修改指针本身的值让它指向新建节点或NULL。如果你直接用BiTree T做参数函数内部改了T外头的指针完全感知不到。这一点我在教学里反复强调过无数次但仍然有很多人在这里卡住。说个笨办法遇到“函数需要修改主调函数中的指针变量本身”时一律用二级指针或者返回指针的方式保准不会错。层序遍历需要借助队列。思路是根节点入队循环中出队一个节点、访问它再把非空左右孩子入队。这恰好和3.3里链队列的实现衔接上建议把队列代码和二叉树代码放在一起编译测试。3.5 排序与查找从冒泡到快速排序严蔚敏教材的排序部分给出了直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、归并排序等。如果只能挑一个“必须能手写”的我会选快速排序。教材里的Partition函数用一个“哨兵”记录枢轴元素实现时“挖坑填数”的思路非常典型int Partition(SqList *L, int low, int high) { L-elem[0] L-elem[low]; // 哨兵暂存枢轴 ElemType pivotkey L-elem[low]; while (low high) { while (low high L-elem[high] pivotkey) --high; L-elem[low] L-elem[high]; while (low high L-elem[low] pivotkey) low; L-elem[high] L-elem[low]; } L-elem[low] L-elem[0]; return low; }我第一次手写快排时的惨痛教训是两个内部循环里忘了写low high条件结果数组有序时直接访问越界程序崩溃。原因是当high一路减到low之前时elem[high]已经变成非法的负数下标。所以这个边界条件必须卡死。另外一个排序相关的常考问题是稳定性。直接插入排序和冒泡排序稳定快速排序、简单选择排序、堆排序不稳定希尔排序和归并排序视实现而定。我在写实验报告时会把每个排序的稳定性、时间复杂度、是否原地排序整理成表格方便最后复习。这样从代码实现到理论总结都过一遍才算真正把这一章吃透。4. 刷题场景下的代码实践与调试技巧4.1 从教材代码到OJ提交的差异很多同学把教材代码在本地跑通之后兴冲冲地去洛谷或者PTA刷题发现第一道题就过不了。根本原因不在算法而在输入输出和边界处理上。教材代码是面向“一组输入”设计的而OJ题目通常是“多组测试数据”或者“以特定条件结束”。例如PTA很多题目要求读到EOF结束这就要用while (scanf(%d, n) ! EOF)这种循环结构。我建议做一次“翻译练习”把教材里的单次运行代码改成支持多组输入的版本。比如顺序表插入删除的例子改成“每行一个操作指令类型遇到0退出”输出对应的结果。这个练习能帮你把scanf、printf、EOF、getchar这些基础操作彻底练熟也能让你理解教材代码和工程/竞赛代码之间的差别。此外OJ题目的数据范围往往比教材示例大得多。教材里的数组开到100已经够用OJ上可能要求10^5甚至10^6规模的数据。这时候就要考虑内存布局和算法复杂度。我遇到过不少同学在主函数里声明int a[1000000]结果栈溢出崩溃改成全局变量或malloc堆内存后就好了。这是一个极其常见但很少有人主动讲的坑。4.2 高频错误与排查速查表我整理了近几年带学生过程中最常出现的错误做成一个速查表排错时可以先对照一遍错误现象常见原因排查方法程序崩溃报Segmentation fault指针未初始化、数组越界、访问已释放内存用gdb调试bt查看调用栈检查最近一次使用的指针输出全是乱码或负数未初始化的局部变量声明时赋初值或memset清零scanf后程序卡住输入缓冲区残留换行符使用scanf( %c, ch)加空格跳过空白字符malloc后内存泄漏只malloc没free用valgrind检测或者养成“谁申请谁释放”的习惯链表打印出现死循环链表成环尾节点指向了前面的节点打印最多N个节点检查尾节点next是否为NULL二叉树叶节点统计不对递归边界条件错误用只有根节点/空树两种最简树测试快排有序数据时超时枢轴选择是第一个元素导致递归树严重不平衡改成三者取中或者随机选择枢轴这里特别说一下scanf的换行问题。教材示例里多用scanf(%d, n)比如输入3 1 2 3它不会读入空格和换行所以没问题。但如果你用%c读字符比如建二叉树时输入AB#C##D##回车符会残留在缓冲区导致第一个字符读成\n。解决办法是scanf( %c, ch)注意%c前面加一个空格。这个空格的含义是“跳过所有空白字符”是C语言里非常实用的小技巧。4.3 实验报告与代码注释的小建议严蔚敏教材配套的实验课通常要求写实验报告包括问题描述、需求分析、概要设计、详细设计、调试分析、用户使用说明、测试结果等模块。我写这部分时有几条个人经验第一报告中一定要给出“测试数据与结果截图”哪怕只有一组输入输出。很多老师会重点看这一步因为能证明代码真的跑起来了。第二核心算法的流程图用流程图工具绘制即可或者用文字描述清楚“输入、处理、输出”三个阶段。第三代码注释不必满篇都是但关键函数和关键语句必须注释。我的习惯是每个函数头部用两三行说明“功能、参数、返回值”函数内部的注释集中在算法难点处比如快排的枢轴调整、链表的指针修改顺序。另外如果你在刷洛谷、PTA这类在线判题平台注意提交语言的选项要选“C (gcc)”而不是“C”。虽然gcc可以编译C代码但纯C代码用了C编译器可能会出现一些类型转换上的兼容问题。像malloc返回void*隐式转换在C中是允许的在C中是报错的。所以提交前确认语言选项非常关键。4.4 从教材代码到可复用代码库当你能把顺序表、链表、栈、队列、二叉树、排序这六大块都实现一遍以后我建议做一件事把它们整理成一个自己的代码库。这不仅是作业复用的便利更是对“ADT”思想的一次真正实践。我的做法是每个结构单独一个文件夹里面放.h头文件和.c源文件。头文件对外暴露数据结构定义和操作函数声明源文件只实现具体的逻辑。这样未来刷题时需要顺序表就直接#include sqlist.h需要二叉树就引入二叉树模块不用从头写起。多个文件用Makefile或CMake组织Windows下也可以用Dev-C新建一个多文件工程。这一步“整库”的过程你会被迫思考模块之间的接口设计为什么ListInsert的参数是SqList *而不是SqList为什么GetElem要返回Status并通过指针带出元素值这些不再是书上的教条而是你在组织自己代码时真实遇到的取舍。到这一步严蔚敏教材的价值才算真正内化成你自己的能力。5. 常见问题与排查技巧实录5.1 我踩过的三个经典坑第一个坑是“结构体声明写在源文件里头文件里只有操作函数声明”。听起来没什么但当你第二个源文件想使用这个结构体的字段时编译器直接报“invalid use of undefined type”。正确做法是结构体定义必须放在头文件里源文件只负责实现。实验课上有同学把SqList定义写死在main.c里其他文件无法共用最后只能复制粘贴。教训就是数据结构的定义是接口的一部分应该公开给所有使用方。第二个坑是“所有函数都用一个return -1处理异常”。教材里的Status类型包含OK、ERROR、OVERFLOW、INFEASIBLE不同错误值有不同语义。如果你不区分排查问题时根本不知道错误发生在哪个环节。我刚写代码时也爱偷懒但后来发现加上区分不仅不影响效率还让调试体验显著改善。比如LocateElem找不到元素时返回ERROR而内存不足时返回OVERFLOW这两个错误性质完全不同处理方式也完全不同。第三个坑是“忽视编译器警告”。gcc的-Wall选项会把很多潜在问题列出来比如“implicit declaration of function”说明你忘了包含头文件“unused variable”说明有变量没用到。这些警告不是小题大做而是编译器在免费帮你排查低级问题。我到现在依然坚持“零警告编译”的习惯宁可多花几分钟修掉所有警告也不要带着警告提交作业或代码。5.2 调试效率提升的几条心得在数据结构代码的实现过程中掌握简单的调试手段能节省大量时间。我自己的工具链排序是printf输出 gdb单步 valgrind内存检测。为什么不是上来就gdb因为很多错误其实是逻辑错误用几个printf把关键位置的值打印出来比点来点去的调试器更直接。比如链表插入后打印一次链表、二叉树层序遍历后打印每一层的节点一眼就能看出哪里不对劲。一旦确认程序崩溃gdb是最好用的工具。用gdb ./demo启动后输入run复现崩溃然后bt查看调用栈基本就能定位到是哪一行代码出了问题。配合print命令查看当时的变量值排查指针问题效率极高。valgrind则是内存问题的照妖镜。valgrind --leak-checkfull ./demo运行后它会列出所有内存泄漏的位置精确到行号。我当年提交实验报告前都会跑一遍这个工具确保没有内存泄漏这样即使用例再多也不会因为内存问题翻车。5.3 如何从“看懂”走向“手写”很多读者应该已经能看懂书上的所有代码了但合上书写不出来。这不是智力问题是训练量不够。我给一个“手写训练”的路线按顺序来第一天合上书写顺序表的初始化、插入、删除、遍历输出。第二天写单链表的头插法建表、尾插法建表、删除指定位置节点。第三天写栈的入栈、出栈并用栈实现括号匹配。第四天写队列的入队、出队再写二叉树的前序递归建树和中序遍历。第五天写快速排序的Partition和递归主函数。每天只练一个模块每个模块反复写三遍每一遍都静默计时。第一遍通常要20分钟第三遍如果能在5分钟内写完说明你真的掌握了。这个训练量看起来不大但对于考试和机试来说绰绰有余。我见过太多人在刷题网站上刷了上百道题遇到“手写排序”还是卡壳原因就是没有做过这种“合上书默写”的训练。我自己第一次带学生时也走过弯路总想把所有知识点都讲一遍结果学生记住了名词却没记住代码。后来改成“每个结构都必须手写一遍再讲下一章”效果反而好了很多。写代码这件事本质上是在训练手和脑的配合光知道“为什么”还不够还得把手速练出来。本文还有配套的精品资源点击获取