严蔚敏数据结构C语言代码包全解析：核心算法与避坑指南

简介数据结构与算法是计算机科学的核心基础课程代码实践是将原理落到实处的关键。严蔚敏《数据结构与算法C语言版》教材的配套代码实现包面向计算机专业学生及需要巩固算法基础的C/C开发者。资源以教材章节为线索覆盖线性表、栈与队列、二叉树、二叉搜索树与平衡树、堆、图论与网络流、排序查找、动态规划、贪心算法、回溯与分治策略等经典专题并提供对应C语言可运行源码读者可对照教材逐章验证每种数据结构的存储设计与操作实现也能直接学习函数封装和边界处理。压缩包共416个文件以154个C、154个C源文件和89个头文件为主体辅以数据文件、文本说明和工程配置文件命名与教材示例编号对应便于直接编译调试整体仅494KB。已有1607人学习代码适合作为课程设计参考与面试算法复习手册无论是课程实验、期末复习还是准备算法面试都能提供直观范例与快速调试环境帮助把抽象概念转化为可上机运行的实现尤其适合严蔚敏教材自学者边读边练。1. 严蔚敏数据结构C语言代码包为什么我拿到手先翻了三遍某同学从网盘下了一份号称“严蔚敏《数据结构C语言版》代码实现”的压缩包解压之后对着十来个文件夹发呆——里面既有顺序表又有图算法却不知道从哪个文件开始看更别说能不能编译通过。这套资源对应的正是教材里从线性表到查找排序的整套可运行C代码直接服务于数据结构实验报告、数据结构期末复习和考研数据结构刷题场景。多数打包者会把头文件、源文件按章节分开拿到手正确的打开方式不是挨个点开而是先看目录结构、确认编译环境再挑一个最简单的顺序表程序验证工具链。适合三类人正在抄实验报告但不想全抄的学生、准备考研笔试想动手跑算法的考生、以及从C转过来想补C指针功底的开发者。2. 线性表与串的实现从顺序表初始化到KMP匹配的几个关键动作2.1 顺序表结构体定义、初始化与插入的代码拆解线性表是所有后续算法的基础而顺序表又是线性表里最容易在传参上踩坑的部分。严蔚敏版教材里顺序表用结构体封装数组和长度定义一般长这样#define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int length; } SeqList;配套的初始化函数并不复杂但经常有人写成传值导致 length 永远改不回去// 注意形参是指针不是 SeqList L void InitList(SeqList *L) { L-length 0; // 写成 L.length 0 的话main里不会有任何变化 }初始化本身的逻辑很简单真正的分水岭在插入操作。插入的核心是“从最后一个元素开始依次后移”代码长这样int ListInsert(SeqList *L, int i, int e) { int k; if (i 1 || i L-length 1) return 0; // 插入位置越界 if (L-length MAXSIZE) return 0; // 表已满 for (k L-length; k i; k--) { L-data[k] L-data[k - 1]; // 从后往前挪 } L-data[i - 1] e; L-length; return 1; }这段代码有两个容易忽略的设计。一是越界判断必须同时看下限和上限i 小于 1 不行i 大于 length1 也不行等于 length1 其实是允许的因为那等于在末尾追加。二是后移必须从后往前循环如果写成for (k i - 1; k L-length; k) data[k1] data[k]前面元素会把后面还没挪的位置覆盖掉结果全表变成同一个值。参数 i 是逻辑序号和数组下标差 1这也是初学阶段最容易绕晕的地方。2.2 链表带头结点创建和删除时的指针误用链表比顺序表多一层指针间接资源包里最常见的翻车点是“修改节点内容后 main 函数没反应”。链表节点定义一般直接沿用教材的结构体typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;头结点的价值在于让“删除第一个元素”和“删除其他元素”的代码逻辑统一不需要单独写 if 分支。尾插法创建单链表的常用实现是LinkList CreateList(int n) { LinkList head (LinkList)malloc(sizeof(LNode)); LNode *tail head; int i; head-next NULL; for (i 0; i n; i) { LNode *p (LNode*)malloc(sizeof(LNode)); scanf(%d, p-data); p-next NULL; tail-next p; // 新节点接在尾部 tail p; // tail 后移 } return head; }理解这段代码的关键在 tail 指针它始终指向当前链表的最后一个节点每插入一个节点就移动一次。head 从头到尾没有变过始终指向头结点。如果你在循环里让 head 也往后移动函数返回时链表头就丢了遍历会从错误位置开始。删除第 i 个节点时要先找到第 i-1 个节点再动指针直接删第 i 个节点会因为拿不到前驱而无法维护链表关系int ListDelete(LinkList L, int i, int *e) { LNode *p L; int j 0; while (p-next j i - 1) { // 找到第 i-1 个节点 p p-next; j; } if (!p-next) return 0; // 第 i 个节点不存在 LNode *q p-next; p-next q-next; // 绕过 q *e q-data; free(q); // 释放后务必不再使用 q return 1; }有人删完节点之后继续打印 q-data 去验证这是未定义行为释放过的指针应该立刻置 NULL。还有一个细节删除接口用int *e把被删元素带出来这是 C 语言里“函数需要多个返回值”的标准解法。如果你直接返回节点数据碰到删除失败比如位置越界就不知道该返回什么了。2.3 KMP 匹配next 数组构造与主串 i 不回退串这一章预处理数组和 KMP 匹配常常让新手怀疑人生。严蔚敏教材里字符串是用S[0]存长度、字符从S[1]开始存的设计数组长度比字符个数多一个。KMP 的 next 数组构造函数用 C 写出来是void GetNext(char *T, int *next) { int i 1, j 0; next[1] 0; while (i T[0]) { if (j 0 || T[i] T[j]) { i; j; next[i] j; // 当前匹配长度 1 } else { j next[j]; // 失配则回退到上一个可用位置 } } }匹配主函数则利用 next 让 i 一直往前走不回退int Index_KMP(char *S, char *T, int pos) { int i pos, j 1; int next[255]; GetNext(T, next); while (i S[0] j T[0]) { if (j 0 || S[i] T[j]) { i; j; } else { j next[j]; // 只有 j 回退i 不动 } } if (j T[0]) { return i - T[0]; // 返回模式串在主串中的起始位置 } return 0; }KMP 的核心价值在于主串下标 i 绝不回溯失配时只移动模式串指针 j。普通 BF 算法每次失配都要i i - j 2; j 1;一旦主串很长重复比较的开销非常大。next[j]的含义很难用一句话说全我自己的理解是“模式串第 j 个位置失配后下一步用第几个位置的字符继续比较”。配套代码包里如果把字符串逆序或 c语言字符串数组 相关的练习一起看更容易理解下标设计字符数组长度必须开成 N1T[0]才能安全保存长度。pos参数表示从主串的哪个位置开始匹配默认传 1如果传 0 会在循环条件里直接退出这个细节很多人第一次跑通代码才发现。3. 树与图把递归遍历和最短路径的代码跑起来3.1 二叉树先序、中序、后序递归栈里的访问时机树这章最值得花时间的是三种遍历的递归关系。先序、中序、后序的区别只有一行访问根节点的那句话放在递归调用的前面、中间还是后面。以先序为例typedef struct BiTNode { char data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; void CreateBiTree(BiTree *T) { char ch; scanf(%c, ch); if (ch #) { *T NULL; } else { *T (BiTree)malloc(sizeof(BiTNode)); (*T)-data ch; CreateBiTree((*T)-lchild); // 先递归建左子树 CreateBiTree((*T)-rchild); // 再递归建右子树 } } void PreOrder(BiTree T) { if (T NULL) return; printf(%c , T-data); // 访问根节点 PreOrder(T-lchild); // 遍历左子树 PreOrder(T-rchild); // 遍历右子树 }这段代码里CreateBiTree的参数用了二级指针原因和顺序表传指针一样建树过程中要修改*T本身指向的地址只传一级指针的话malloc分配的内存地址在函数返回后丢失。输入序列用#表示空子树例如输入AB#D##C##会构建一棵先序序列为 ABDC 的二叉树。PreOrder的递归理解不要纠缠在“栈怎么压”而是记住每个节点都会经历“访问根-进左子树-出左子树-进右子树-出右子树”这条路径printf 写在第一步就是先序写在中间是后序。做数据结构期末复习的时候把三种遍历的打印序列在纸面上推演三遍比盲目刷十道题更有用。3.2 图的邻接矩阵初始化、DFS 与 visited 数组的作用图论代码在本资源里通常占两个文件一个存邻接矩阵结构一个存遍历和路径算法。邻接矩阵的定义和初始化不长但容易漏掉对角线#define N 100 typedef struct { int edges[N][N]; // 邻接矩阵 int n, e; // 顶点数和边数 } MGraph; void CreateMGraph(MGraph *G) { int i, j, k, w; scanf(%d %d, G-n, G-e); for (i 0; i G-n; i) { for (j 0; j G-n; j) { G-edges[i][j] 0; // 初始化为无边 } } for (k 0; k G-e; k) { scanf(%d %d %d, i, j, w); G-edges[i][j] w; G-edges[j][i] w; // 无向图对称赋值 } }深度优先遍历的骨架也是递归但多了一个关键辅助数组 visitedint visited[N]; void DFS(MGraph *G, int v) { int j; visited[v] 1; printf(%d , v); for (j 0; j G-n; j) { if (G-edges[v][j] ! 0 !visited[j]) { DFS(G, j); } } }visited 数组的作用是防止回头路图不像树那样天然有方向A 访问邻居 B 之后B 的邻接表里又会有 A没有 visited 标记就会在两个节点之间反复横跳直到栈溢出。注意 visited 是全局数组默认值为 0但如果你在一次程序里对多个连通分量分别调用 DFS必须在每次调用前把 visited 清零否则第二个分量会被跳过。这一点在避坑章节还会细说。至于广度优先遍历把递归换成队列出队时访问并把未访问邻居入队逻辑类似这两段代码建议对比着看。3.3 Prim 与 Dijkstra两个贪心算法的数组更新对比Prim 最小生成树和 Dijkstra 最短路径在很多教材里挨着讲是因为它们共享同一套贪心框架。Prim 维护 lowcost 数组表示“已选集合”到每个未选顶点的最小边权Dijkstra 维护 dist 数组表示源点到每个顶点的最短路径长度。核心循环都是“找最小值-固定-更新数组”但更新条件不同void Prim(MGraph *G, int start) { int lowcost[N], mst[N]; int i, j, min, minid; for (i 0; i G-n; i) { lowcost[i] G-edges[start][i]; mst[i] start; } for (i 1; i G-n; i) { min 9999; minid -1; for (j 0; j G-n; j) { if (lowcost[j] ! 0 lowcost[j] min) { // 0 表示已在集合内 min lowcost[j]; minid j; } } printf((%d,%d) weight%d\n, mst[minid], minid, min); lowcost[minid] 0; // 加入已选集合 for (j 0; j G-n; j) { if (lowcost[j] ! 0 G-edges[minid][j] lowcost[j]) { lowcost[j] G-edges[minid][j]; // 只更新边权 mst[j] minid; } } } }两者的核心区别在于更新阶段Prim 只看新选中节点到其他节点的“直接边权”是否比现在的 lowcost 更小Dijkstra 则要看“从源点到新选中节点的已知最短路径 新节点到其他节点的边权”是否小于现有 dist。表格对比更直观对比项PrimDijkstra目标连接所有顶点的最小总边权源点到各顶点的最短距离数组含义lowcost集合边权dist源点路径权更新条件edges[minid][j] 与 lowcost[j] 比较dist[minid] edges[minid][j] 与 dist[j] 比较是否处理负权边不适用不适用出现负权需换算法我自己早年常犯的错是把 Dijkstra 的更新写成if (G-edges[minid][j] dist[j])忘记了最短路径的累加属性。如果你同样在做图算法的实验报告建议在纸上把两个数组各画一张表跑一轮 5 顶点的小图再对照代码比直接改 bug 更有效率。这一段看完图的基本代码就够用了。4. 查找与排序折半边界和快排分区的实现细节4.1 折半查找left right 与取中值方式共同决定会不会死循环折半查找是查找章节的入门题也是数据结构折半查找例题里最容易写错的边界题。标准实现int BinarySearch(int a[], int n, int key) { int left 0; int right n - 1; int mid; while (left right) { mid left (right - left) / 2; // 防止 left right 溢出 if (a[mid] key) { return mid; } else if (a[mid] key) { left mid 1; // 目标在右半区 } else { right mid - 1; // 目标在左半区 } } return -1; }循环条件left right是必须的写成left right会让查找范围收窄到单元素时直接退出导致最后一个元素永远找不到。mid left (right - left) / 2这个写法不只是防溢出还能保证 mid 始终落在区间中点的左侧配合left mid 1、right mid - 1就不会出现区间无法缩小而死循环。查找失败时返回 -1 而不是 0因为下标 0 是合法位置用 0 表示失败会掩盖“第一个元素命中”的情况。4.2 快速排序一次划分里的空位移动与枢轴选择数据结构排序算法这一章快排的代码最具戏剧性。一次划分写成独立函数以数组的第一个元素为枢轴双指针交替填坑int Partition(int a[], int low, int high) { int pivot a[low]; // 选第一个元素为枢轴 while (low high) { while (low high a[high] pivot) high--; // 从右往左扫 a[low] a[high]; // 右边比枢轴小的移到左边空位 while (low high a[low] pivot) low; // 从左往右扫 a[high] a[low]; // 左边比枢轴大的移到右边空位 } a[low] pivot; // 枢轴归位 return low; } void QuickSort(int a[], int low, int high) { int pivotPos; if (low high) { pivotPos Partition(a, low, high); QuickSort(a, low, pivotPos - 1); QuickSort(a, pivotPos 1, high); } }两个内层 while 的等号处理是很多翻车现场的来源如果写成a[high] pivot而不是遇到与枢轴相等的重复元素时两个指针可能互相卡住因为外层 while(low high) 永远不退出。枢轴选第一个元素有个缺点——如果数组本身有序每次划分只能消掉一个元素递归深度变成 n栈压力很大。我一般会把第一个和中间元素比较后换个位置再选枢轴这是改动最小且能大幅度降低退化概率的做法。外层递归的终止条件也要写对if (low high)而不是if (low ! high)否则分区返回的位置和 high 相等时会多递归一层在小数组上就爆栈。4.3 堆排序从 n/2-1 开始的向下调整堆排序算法是所有 O(n log n) 排序里最难凭直觉写对的一个因为它的下标映射关系藏在完全二叉树的性质里。用数组存堆时第 i 个节点的左孩子是 2i1右孩子是 2i2父亲是 (i-1)/2。建堆要从最后一个非叶子节点开始往前调整最后一个非叶子节点的下标是 n/2-1void HeapAdjust(int a[], int root, int n) { int temp a[root]; int child; while (2 * root 1 n) { child 2 * root 1; if (child 1 n a[child] a[child 1]) { child; // child 指向较大的孩子 } if (temp a[child]) { a[root] a[child]; // 孩子上移 root child; // 继续向下检查 } else { break; // 找到合适位置 } } a[root] temp; } void HeapSort(int a[], int n) { int i, temp; for (i n / 2 - 1; i 0; i--) { HeapAdjust(a, i, n); // 自底向上建大顶堆 } for (i n - 1; i 0; i--) { temp a[0]; a[0] a[i]; a[i] temp; HeapAdjust(a, 0, i); // 堆顶换到最后缩小堆范围 } }这段代码里最容易犯的错误是把 HeapAdjust 里的循环写成只调整一层就返回。堆调整要求节点一直下沉到子树中合适的位置所以root child这一步不能少。第二个容易错的地方是第二次 HeapAdjust 传入的堆长度 i每轮排序后堆的有效范围减一之前换到数组末尾的元素已经有序不能再参与调整。建堆从 n/2-1 开始而不是从 n-1 开始是因为叶子节点没有孩子不需要调整从最后一个有孩子的节点开始可以保证每一层都已经满足堆性质。想验证理解程度可以把比较符号从改成试试建小顶堆再想想排序结果是升序还是降序。5. 避坑排查这套代码里常见的五个翻车现场5.1 修改函数不生效结构体传参只传了副本现象在 main 里调用InitList(L)后打印L.length仍然是随机值链表创建函数拿到 head 之后 main 里 head 还是 NULL。原因C 语言函数参数是值传递直接把结构体变量传进去函数内部修改的是栈上的一个临时拷贝。结构体数组退化成指针所以看起来正常但SeqList这种整体变量不会自动传址。解决所有需要回写数据的函数形参改成指针。InitList(SeqList *L)、CreateMGraph(MGraph *G)调用时传L。检查函数签名凡是函数内部出现L-xxx和(*G).xxx的都是指针版本不要混用。5.2 scanf 吃换行导致二叉树建树错乱现象运行CreateBiTree(T)时输入AB#D##C##结果第一次 scanf 读到的是换行符根节点内容变成空白整棵树结构全乱。原因scanf 的%c会读取任意字符包括换行前一次输入结束时按下的回车停留在输入缓冲区被下一个%c消费。解决建树前加一句getchar();吃掉残留换行或者用scanf( %c, ch)在格式串前面留一个空格跳过空白字符。这属于玄学问题里最经典的一个很多人排查半小时最后发现是缓冲区问题从此学会在调试树形代码之前先清理输入状态。5.3 visited 数组没重置第二次遍历结果不对现象图里有两个连通分量第一次 DFS 输出正常第二次调用 DFS 只输出一个节点就停了。原因visited 是全局数组第一次 DFS 已经把第一个分量的节点标记为 1第二次遍历时这些节点不再满足!visited[j]条件整个程序直接跳过。解决每次调用 DFS 之前写一个循环清零 visited或者把 visited 放进一个 InitVisited 函数统一管理。这个方法同样适用于 BFS我在实际写实验代码时习惯把 visited 的定义和清理写在同一对函数里避免漏调。5.4 KMP 下标从 1 开始导致数组越界现象把模式串正常按 C 习惯存成abc后调用Index_KMP匹配结果不对或者运行时报段错误。原因严蔚敏版字符串约定是下标 0 存长度字符从下标 1 开始。T[0]原本存的是串长如果直接存字符aASCII 值是 97循环次数完全错乱。解决给字符串数组分配长度 1 的空间把串长写进T[0]字符从T[1]开始赋值。例如char T[4]; T[0] 3; T[1]a; T[2]b; T[3]c;。这在资源包配套代码里是通用约定不是某一处函数的特殊写法。5.5 快排在有序数组上递归过深现象对已经升序的数组执行 QuickSort程序在 n 接近一万时栈溢出崩溃换成无序随机数组就没事。原因枢轴永远选第一个元素而有序数组的划分结果每次都是枢轴在最边上递归深度从期望的 log n 退化到 n运行时栈被压穿。解决选枢轴前把a[low]与a[mid]、a[high]三者比较取中位数放到 low 位置再 Partition。这个改动不会破坏排序正确性但能显著降低最坏情况出现概率。对于数据量特别大且可能有序的场景还可以在递归深度超过一定阈值时切换堆排序这就是优化版 introsort 的思路。6. 一个进阶技巧把调试开关和随机测试数据固化到工程里6.1 用 DEBUG 宏统一控制调试输出从这套代码包里复现算法时最烦的是每改一处都要手动找 printf 删掉。我后来的习惯是开头统一加一个调试宏所有带诊断信息的输出都走它#ifdef DEBUG #define LOG(fmt, ...) printf([DEBUG] fmt \n, ##__VA_ARGS__) #else #define LOG(fmt, ...) do {} while (0) #endif编译时加-DDEBUG就开启日志去掉就静默。代码里用LOG(插入后 length%d, L-length)代替裸 printf保留关键中间状态但不用反复注释。##__VA_ARGS__是 GNU 扩展在 Windows 上用 MSVC 编译需要改成__VA_ARGS__。这个宏在验证排序划分是否正确、检查 KMP 的 next 数组是否按预期更新时作用很大尤其是数据规模一大肉眼根本看不清过程值加两行 LOG 立刻定位问题。6.2 每次改完算法先跑“小数据、边界、随机”三步验证学这套代码最容易陷入的误区是跑通一个用例就宣告完成。我的验证顺序固定是先拿 5 个元素的小数组手动推演一遍再构造边界数据——空表、单元素、全相同元素、升序有序数组最后用随机数据生成器跑大量测试与暴力算法对拍。void GenRandom(int a[], int n, int maxVal) { int i; for (i 0; i n; i) { a[i] rand() % (maxVal 1); } }对拍的意思是同一个输入分别跑自己写的算法和一个确定正确但效率低的版本比较输出是否一致。排序可以对比冒泡匹配可以对比 BF 暴力函数查找可以对比循环遍历。这一步能验证大部分隐藏缺陷特别是快排的等号问题、堆排序的边界问题都是随机大量数据才能暴露出来的。我从那以后每次拿到新的算法代码都强制走一遍这个流程先确认编译器和代码的字符串下标约定再用 DEBUG 宏跑小数据接着用边界值折磨函数最后随机数据对拍。这个习惯救了我很多次希望帮到你。本文还有配套的精品资源点击获取