简介《数据结构各章节算法实现C语言版》是一份面向计算机专业学生、ACM竞赛爱好者、考研复试及求职笔试人群的算法整合文档。内容覆盖顺序表、栈和队列、查找排序、字符串匹配、树与图等章节每个程序均可独立编译运行并非零散函数与严蔚敏《数据结构(C语言版)》教材章节对齐适合边学边练。文档包含顺序表字符统计、一元多项式相加、行编辑器、后缀表达式求值、索引顺序表与哈希表查找、二分查找、八种排序算法直接插入、希尔、冒泡、快排、归并、基数等、KMP字符串匹配、二叉树建立遍历与深度计数、哈夫曼编码、基于邻接矩阵和邻接表的广度优先搜索、最小生成树等完整实现可直接用于期末复习、机试刷题和面试笔试准备。资源采用Word格式含1个docx文件压缩包仅162KB排版清爽、留白充足便于读者注释、扩展并整理成个性化题库。目前已有1391人学习下载是快速打通数据结构代码关卡的实用配套资料。1. 这份数据结构 C 语言算法实现文档从复试机试到期末复习都能用的代码手册如果你正在准备计算机专业考研复试或者期末前突击《数据结构(C语言版)》这门课大概率会陷入一种状态教材里的算法都看得懂真到上机写代码就卡在指针、边界条件和递归上。《数据结构各章节算法实现C语言版》这份文档把严蔚敏教材里的主要算法拆成了可以独立编译运行的 C 语言程序——顺序表、栈和队列、八大排序、查找、字符串匹配、二叉树、哈夫曼、图的最短路径和最小生成树按章节组织Word 排版复制到编译器里就能跑。它不是讲概念的精美讲义而是能直接抄、能改、能对着练的算法实现手册。适合三类人准备计算机复试机试的考研党、期末前需要代码参考的数据结构学生、以及刷 ACM 或校招笔试时想快速查模板的人。文档是 Word 格式方便加注释、删改和扩展这也是我认为它比网上零散代码更有价值的地方。2. 顺序表与链表字符统计、多项式相加和链表操作怎么写不翻车顺序表和链表这章看着基础但文档里的几个例子刚好覆盖了机试最容易出现的四类操作桶计数、链表合并、区间删除和去重。每个题单独拎出来都不难难的是把指针操作和边界条件写对。下面按文档顺序拆顺带标注哪些地方容易翻车。2.1 字符统计数组桶计数的两个要点文档 1.1 的字符统计是典型的桶计数逻辑不复杂但有两个细节直接影响能不能过样例。先看代码#includestdio.h #includestring.h #includestdlib.h int main() { char c; int a[1000], i, n; scanf(%d, n); getchar(); // 吃掉 scanf 后留在缓冲区的换行 while (n--) { memset(a, 0, sizeof(a)); while (scanf(%c, c) ! EOF c ! \n) a[c]; // 字符的 ASCII 值直接当数组下标 int cnt 3; while (cnt--) { int leag -1, temp A; for (i A; i z; i) { if (leag a[i]) { leag a[i]; temp i; } } if (a[temp] ! 0) printf((%c,%d), temp, leag); a[temp] 0; // 取完后清零找下一个次多的 } printf(\n); } return 0; }这里第一个要点是getchar()的位置。scanf(%d)只读取数字换行符还留在缓冲区里如果不用getchar()吃掉下面第一次while (scanf(%c)...)会直接读到\n导致第一组数据统计为空。这个坑非常隐蔽样例数据少的时候根本看不出来等输入变多才会发现漏统计一组。第二个要点是找前三个出现次数最多的字符时遍历区间是从A到z。这个范围在 ASCII 表里正好覆盖大写字母和小写字母中间夹着的[ \ ] ^ _ 等符号一般不会出现在统计场景里所以不受影响。如果要扩展到任意可见字符把循环改成i 0; i 128; i 即可数组大小同步调整。提示int a[1000]其实开大了ASCII 可打印字符最多到 126开int a[128]就够。但机试时不缺这点内存按文档的 1000 也没有问题重点是memset别忘了。2.2 一元多项式相加合并时毁不毁原链表是考点文档里给了两个多项式相加版本目录名写得很清楚——一个直接相加、一个保留原链表信息。两种解法的差别不只在代码量还在链表节点是复用还是新建。先看第一版核心比较逻辑p head1-next; q head2-next; head3 (LINK *)malloc(sizeof(LINK)); tail3 head3; while (q ! NULL p ! NULL) { if (p-y q-y) { tail3-next p; // 直接把节点挂到结果链表 tail3 p; p p-next; continue; } else if (p-y q-y) { tail3-next q; tail3 q; q q-next; continue; } else { // 指数相等合并系数 if (p-x q-x 0) { p p-next; q q-next; // 系数抵消两个节点都不要 } else { p-x p-x q-x; tail3-next p; tail3 p; q q-next; p p-next; } } } tail3-next NULL;这段代码按指数从小到大的顺序归并两条链表。当指数相等时如果系数相加为 0两个节点都跳过否则把结果写回p节点再挂到结果链表尾部。注意一个容易看漏的细节在else分支里q先前进、p再前进这个顺序不能换。如果先p p-next再q q-next从逻辑上也说得通但代码里tail3已经指向 p一旦p提前移动后面就找不到正确节点了。我自己在这里改错过一次结果是链表直接断了一半。第二版createLink函数里每次循环都malloc一个新节点把系数和指数复制过去再挂到结果链表的尾部。代价是多了一轮内存分配换来的是原链表完整保留。机试时如果题目明确说“不改变原链表”必须用第二种没要求时用第一种效率更高代码也短一些。2.3 链表的建立、删除区间元素和去重1.6 的链表建立代码用的是头插法p (LINK *)malloc(sizeof(LINK)); scanf(%d, p-data); p-next head-next; // 新节点指向原来的第一个节点 head-next p; // 头节点指向新节点头插法最终得到的是逆序链表。如果题目要求按输入顺序输出这里就是翻车点。改成尾插法只需要换三行p (LINK *)malloc(sizeof(LINK)); scanf(%d, p-data); p-next NULL; tail-next p; tail p; // tail 始终指向最后一个节点1.5 的删除指定区间节点文档做法是先标记再输出。每个节点结构体里加一个num字段第一遍遍历把区间内的节点num置 0第二遍只输出num 1的节点p head-next; for (i 1; i n; i) { if (p-data a p-data b) p-num 0; p p-next; }这种做法不真的释放内存也不修改指针连接所以不会出现指针断链。机试里如果题目只要求输出删除后的结果标记法是最稳的选择。但如果面试官要求手撕“真正的删除”就得用双指针LINK *prev head, *cur head-next; while (cur) { if (cur-data a cur-data b) { prev-next cur-next; free(cur); cur prev-next; } else { prev cur; cur cur-next; } }1.7 的单链表去重也是类似思路外层节点固定内层指针扫描后面所有节点遇到相同数据就把内层节点的num标记为 0。时间复杂度 O(n²)数据量 10^4 以内完全能跑。这种写法依赖结构体里有num字段如果题目限制不能修改结构体定义那就换成哈希表记录出现过的值空间换时间代码也不复杂。3. 栈与队列行编辑器、后缀表达式求值和双向队列的实现栈和队列这章是机试高频区尤其是用数组手写栈和队列。文档里的行编辑器和后缀表达式求值都是栈的典型应用代码不长但操作数顺序和栈顶指针的含义是必考的细节。3.1 行编辑器# 退格和 清行的模拟这个题用数组模拟栈文档 2.1 的做法是struct node { char a[300]; int top; // 栈顶指针指向下一个写入位置 } p; char s[1000]; while (gets(s) ! NULL) { p.top 0; n strlen(s); for (i 0; i n; i) { if (s[i] ! # s[i] ! ) p.a[p.top] s[i]; // 普通字符入栈 else if (s[i] #) { if (p.top ! 0) p.top--; // 退格逻辑弹出 } else if (s[i] ) p.top 0; // 清行栈置空 } for (i 0; i p.top; i) printf(%c, p.a[i]); printf(\n); }核心就一条top始终指向“下一个待写入的位置”。写入用p.a[p.top]退格用p.top--清行直接把top归零。要注意的是#的处理必须判断top ! 0空栈时如果有#top会变成负数后续写入就数组越界了。这在机试里一踩一个准轻则答案错误重则运行时崩溃。注意gets在 C11 标准里已经被移除新版 VS 编译器会直接报错建议改成fgets(s, sizeof(s), stdin)读入后手动去掉末尾的换行符。机试环境如果用 GCC 一般没问题但养成fgets的习惯更稳。3.2 后缀表达式求值操作数顺序是最大的坑文档 2.2 的后缀表达式求值核心逻辑如下for (i 0; ch[i] ! #; i) { if (ch[i] 0 ch[i] 9) p.a[p.top] ch[i] - 0; else if (ch[i] *) { p.a[p.top - 2] p.a[p.top - 1] * p.a[p.top - 2]; p.top p.top - 1; } else if (ch[i] /) { p.a[p.top - 2] p.a[p.top - 2] / p.a[p.top - 1]; p.top p.top - 1; } else if (ch[i] ) { p.a[p.top - 2] p.a[p.top - 1] p.a[p.top - 2]; p.top p.top - 1; } else if (ch[i] -) { p.a[p.top - 2] p.a[p.top - 2] - p.a[p.top - 1]; p.top p.top - 1; } }这个程序用数组模拟栈遇到数字字符就ch[i] - 0入栈遇到运算符就弹出栈顶两个元素计算结果写回次栈顶位置。最坑的是减法和除法。栈里后进的是右操作数先进的是左操作数所以a[top-1]是右操作数、a[top-2]是左操作数。减法必须写a[top-2] - a[top-1]除法必须写a[top-2] / a[top-1]。为什么这是坑因为像8 2 -和5 2 /这种数据谁减谁、谁除以谁结果都一样抄代码时写反了下标也测不出来。换2 8 -或者5 2 /正确结果分别是 -6 和 2写反就是 6 和 2。我见过不止一个人在这里翻车查了半天才发现是除法和减法的操作数顺序反了。另外文档的代码只支持单个数字字符的操作数。如果题目里出现多位数读取时要做数字累积if (ch[i] 0 ch[i] 9) { int num 0; while (ch[i] 0 ch[i] 9) { num num * 10 (ch[i] - 0); i; } p.a[p.top] num; }3.3 双向队列数组模拟的边界处理文档 2.3 的双向队列用结构体加数组实现up和down分别记录两端。这类题在机试里常见形式是“支持两端插入删除的序列”。用数组模拟时最稳妥的做法是开一个足够大的数组初始队头和队尾都指向中间位置int q[200000]; int head 100000, tail 100000; // 头部插入 q[--head] x; // 尾部插入 q[tail] x; // 头部删除 head; // 尾部删除 tail--;这样两边都有足够的空间不会出现单向耗尽的问题。如果开的是局部数组记得head和tail的初始值要留够余量否则头插几十次就负数越界了。文档里的a[20000]是针对 n 在 10^4 量级设计的实际用的时候按题目给的 n 调整数组大小。4. 查找与排序二分、八大排序、哈希表和 KMP 的模板选择文档第三章和第四章合起来是内容最多的一块从二分的边界条件到基数排序的桶分配再到字符串匹配的 KMP。这章代码质量参差不齐有的能直接跑有的只是核心片段需要自己补齐。建议不要整段复制而是按机试习惯改写成自己的模板。4.1 二分查找和快排组合边界条件写清楚二分查找是手写频率最高的算法文档 3.1 的标准写法int binary_search(int a[], int n, int key) { int low 0, high n - 1; while (low high) { int mid low (high - low) / 2; // 防溢出 if (a[mid] key) return mid; else if (a[mid] key) low mid 1; else high mid - 1; } return -1; }三个易错点循环条件是low high写成会漏查最后一个元素mid建议用low (high - low) / 2避免low high溢出指针更新必须带1或-1写成low mid或high mid在找不到目标时会死循环。文档 3.2 的“二分快排”思路很简单先快排让数组有序再二分查询。快速排序建议用下面的模板pivot 取中间元素能避开大部分最坏情况void quick_sort(int a[], int left, int right) { if (left right) return; int i left, j right; int pivot a[(left right) / 2]; while (i j) { while (a[i] pivot) i; while (a[j] pivot) j--; if (i j) { int temp a[i]; a[i] a[j]; a[j] temp; i; j--; } } quick_sort(a, left, j); quick_sort(a, i, right); }4.2 八大排序复杂度、稳定性和代码量对照文档从 3.7 到 3.14 覆盖了直接插入、希尔、直接选择、堆、冒泡、快排、归并、基数八种排序。对机试来说核心判断是“这道题该用哪种排序”。参数对照如下算法平均时间复杂度最坏时间复杂度空间复杂度稳定性代码量直接插入O(n²)O(n²)O(1)稳定少希尔排序O(n^1.3)O(n²)O(1)不稳定少直接选择O(n²)O(n²)O(1)不稳定少堆排序O(n log n)O(n log n)O(1)不稳定多冒泡排序O(n²)O(n²)O(1)稳定少快速排序O(n log n)O(n²)O(log n)不稳定中归并排序O(n log n)O(n log n)O(n)稳定多基数排序O(d(nr))O(d(nr))O(nr)稳定多机试现场我一般只写两种快排和归并。快排代码短、常数小绝大多数情况够用如果题目明确要求稳定排序或者操作对象是链表就写归并。堆排序虽然也是 O(n log n)但sift下沉函数的边界条件特别容易写错现场手撕性价比不高。希尔排序和基数排序在机试里出现概率低期末笔试倒是常考理解思想就行。4.3 哈希表什么时候直接开数组就够了文档 3.4 的哈希表是直接定址法数组下标即键值没有处理冲突。这在机试里其实是最常用的“哈希”。判断一个值是否出现过、统计出现次数直接开一个大数组int hash[1000001] {0}; for (i 0; i n; i) { scanf(%d, x); hash[x]; }这种做法的前提是数据范围已知且连续。如果数据是字符串、或者范围很大的整数才需要真正设计哈希函数和冲突处理。机试里很少让你手写链地址法考研笔试才是重点。文档 3.4 的代码当教材看就好别在机试现场折腾复杂哈希。4.4 字符串匹配KMP 的 next 数组推导第四章的 BF 算法是朴素匹配代码简单但复杂度 O(n*m)。KMP 才是考点核心是 next 数组。void get_next(char *p, int *next) { int i 0, j -1; next[0] -1; int len strlen(p); while (i len - 1) { if (j -1 || p[i] p[j]) { i; j; next[i] j; } else { j next[j]; } } } int kmp(char *t, char *p) { int i 0, j 0; int n strlen(t), m strlen(p); int next[100]; get_next(p, next); while (i n j m) { if (j -1 || t[i] p[j]) { i; j; } else { j next[j]; } } if (j m) return i - j; return -1; }next[0]约定为-1这是 KMP 处理第一个字符就失配的关键。理解 next 数组不能死记它的本质是“当前位置失配后模式串应该回退到哪个位置”。比如p ababc到第四个字符a失配时模式串前缀和后缀的重叠部分是ab所以回退到下标 2。我建议考前把 KMP 独立默写三遍以上机试现场很少有时间临场推 next 数组。5. 树与图的算法模板与常见问题排查树和图是文档里代码量最大的部分也是复试机试区分度最高的部分。二叉树遍历、哈夫曼编码、图的 BFS/DFS、最短路径和最小生成树几乎每个都是考点。这章先给模板再集中梳理高频踩坑点。5.1 二叉树的建立与遍历递归边界和访问时机文档 5.1 的二叉树建立通常用输入标记表示空节点比如 0 或 -1typedef struct node { int data; struct node *lchild, *rchild; } BTNode; BTNode *create() { int x; scanf(%d, x); if (x 0) // 0 表示空节点 return NULL; BTNode *p (BTNode *)malloc(sizeof(BTNode)); p-data x; p-lchild create(); p-rchild create(); return p; }前序、中序、后序遍历的差别只在printf的位置前序在递归左子树前打印中序在两者之间后序在最后。递归边界是p NULL时直接返回这条漏了就是段错误。树叶计数和求深度是另外两个高频操作int leaf_count(BTNode *p) { if (p NULL) return 0; if (p-lchild NULL p-rchild NULL) return 1; return leaf_count(p-lchild) leaf_count(p-rchild); } int tree_depth(BTNode *p) { if (p NULL) return 0; int left tree_depth(p-lchild); int right tree_depth(p-rchild); return (left right ? left : right) 1; }深度的1是把根节点那一层算进去。如果题目定义“深度从 0 开始”返回值要去掉这个1考试前看清题目描述。5.2 哈夫曼树和最小体力值贪心合并的实现文档 5.8 到 5.10 的哈夫曼编码、构造哈夫曼树、求最小体力值本质是同一个贪心过程每次取权重最小的两个节点合并直到只剩一个根节点。求最小体力值就是累加每次合并的代价。用数组排序模拟小根堆是最容易理解的写法int cmp(const void *a, const void *b) { return *(int *)a - *(int *)b; } int main() { int n, i, a[1000]; scanf(%d, n); for (i 0; i n; i) scanf(%d, a[i]); long long ans 0; int len n; while (len 1) { qsort(a, len, sizeof(int), cmp); ans a[0] a[1]; // 合并最小的两个 a[1] a[0] a[1]; // 合并结果放到 a[1] a[0] a[len - 1]; // 用最后一个元素补位 len--; // 有效长度减一 } printf(%lld\n, ans); return 0; }注意ans要用long long。哈夫曼合并的累计代价可能超过 int 范围尤其数据量大时。机试里如果只要求输出带权路径长度 WPL用这个方法就够了不需要真的建树。5.3 图的 BFS/DFS、最小生成树和最短路模板邻接矩阵的 BFS 写法最简单适合 n 在 10^3 量级的稠密图void bfs(int start, int n) { int queue[1000], front 0, rear 0; int visited[1000] {0}; queue[rear] start; visited[start] 1; while (front rear) { int cur queue[front]; printf(%d , cur); for (int i 0; i n; i) { if (graph[cur][i] !visited[i]) { visited[i] 1; queue[rear] i; } } } }DFS 递归版本更短但递归深度是隐患。如果图退化成链式结构递归深度可能等于节点数系统栈直接溢出。迭代版用显式栈void dfs_iterative(int start, int n) { int stack[1000], top 0; int visited[1000] {0}; stack[top] start; while (top 0) { int cur stack[--top]; if (visited[cur]) continue; visited[cur] 1; printf(%d , cur); // 邻接点逆序入栈保证访问顺序和递归一致 for (int i n - 1; i 0; i--) { if (graph[cur][i] !visited[i]) stack[top] i; } } }最短路径是图这章的重头戏。Dijkstra 处理单源非负权核心是每次找未访问顶点中 dist 最小的那个然后松弛它的邻接点Floyd 处理多源三层循环里中间顶点 k 必须放最外层void floyd(int n) { for (int k 0; k n; k) // 枚举中间顶点 for (int i 0; i n; i) for (int j 0; j n; j) if (dist[i][k] dist[k][j] dist[i][j]) dist[i][j] dist[i][k] dist[k][j]; }最小生成树的 Prim 适合稠密图Kruskal 适合稀疏图但需要并查集。文档 7.3 有并查集的简单实现机试时两个都要备着。5.4 常见问题排查指针、递归、负权边和测试数据以下五条是机试里反复出现的翻车记录按“现象 → 原因 → 解决”整理现象一程序跑着跑着 segmentation fault。原因链表或树的新节点用malloc分配后next或lchild/rchild没置空。malloc不会自动清零只有calloc才清零。解决所有新建节点的指针字段在赋值后立即补p-next NULL;或p-lchild p-rchild NULL;。抄文档代码时要特别注意有些地方靠tail负责置空有些地方完全没处理。现象二二叉树递归遍历在大输入下崩溃。原因二叉树退化成单链表递归深度等于节点数系统栈不够用。解决节点数在 10^4 量级以上改用显式栈的迭代遍历如果 n 在几百以内递归更省事。现象三后缀表达式求值在减法或除法用例上答案不对。原因操作数出栈顺序写反。先出栈的是右操作数后出栈的是左操作数a[top-2] - a[top-1]不能写成a[top-1] - a[top-2]。解决每次写完后缀表达式求值先跑一组带减法和除法的用例比如5 2 - 3 *预期是 9用这类用例自测。现象四Dijkstra 在有负权边的图上输出错误结果。原因Dijkstra 的贪心性质要求边权非负存在负权边时它找到的不是全局最短路径。解决题目保证“边权非负”才用 Dijkstra可能出现负权时改用 Bellman-Ford 或 SPFA。考研笔试里这题常以判断形式出现需要记牢前提条件。现象五稀疏矩阵转置输出一堆重复元素。原因文档 1.4 的main函数里测试数据把m.data[1]重复赋值了九次数组的其他下标都是未初始化的内存。转置函数本身没问题测试数据写错了。解决拿到文档后先逐个编译运行发现测试数据有问题的自己补。文档的价值在算法函数测试数据本来就是留给读者自己构造的。6. 机试前把文档变成自己的模板库整理方法和验证技巧文档里的算法是按教材章节组织的但机试做题是按题型来的。我的用法是把文档拆成一个个独立的模板函数按题型重新归档而不是按章节背。整理方式很简单建一个“机试模板”文件夹每个文件只放一个算法的完整可运行版本包含必要的头文件、结构体定义和注释。比如linklist.c只放链表建立、删除、去重的完整代码graph_bfs_dfs.c只放两种遍历的邻接矩阵和邻接表实现。这样一个题来了直接翻对应文件复制主逻辑改输入输出。整理模板最值得花时间的是输入输出部分。机试默认可能有多组输入很多题用while (scanf(%d, n) ! EOF)包住主逻辑就能过但有的题要处理字符串、要跳过空白符这些细节比算法本身更容易挂。每整理完一个模板我都强制自己按三个用例验证一遍最小输入比如 n1 或空树确认边界不崩最大规模按题目上限构造数据确认时间和内存够用特殊形态比如递增序列、递减序列、全是重复值的序列确认排序和查找不会退化到死循环。很多算法在普通用例上是对的只有在“全部相等”这种极端用例上才暴露问题——快排的划分边界、冒泡的优化标志位都是在这里翻车的。机试最后十分钟我会把所有涉及指针的程序重跑一遍检查每个新建节点的指针字段是否置空。这份文档帮我把常见模板都整理齐了从那以后我每次写链表、二叉树和邻接表都强制自己先手写一遍完整结构体定义再写操作函数这两个顺序不能反。希望这份真实可跑的 C 语言算法实现也能帮你少踩几个我踩过的坑。本文还有配套的精品资源点击获取