简介面向C语言学习者的数据结构与算法完整资料包覆盖图与树存储结构、查找表、线性表、字符串、数组与广义表、栈与队列、排序算法等核心模块包含冒泡、选择、插入、快速等内部排序及外部排序实现既有基础概念讲解也提供各算法在C语言中的具体代码与运行验证方式适合初学者系统入门亦有助于进阶者巩固编程思维。压缩包共558个文件以c源码、dev工程、exe可执行程序、out输出、layout界面等类型为主配套readme说明文档整体约12.92MB目录结构清晰便于按主题查阅。已有1977人学习使用这份资料能帮助读者理解邻接矩阵、二叉树、顺序查找、二分查找等关键知识点也可作为课程设计或期末复习的实用参考。1. C语言数据结构与算法先别急着刷题把结构和算法在内存里跑起来很多人一提到“C语言数据结构与算法”第一反应是严蔚敏那本绿皮书或者是王道408的复习题。但现实场景是你用Python写一个链表几分钟搞定换成C语言却卡在“二级指针到底要不要用”“free之后指针为什么还在”这些细节上。C语言的数据结构与算法本质上不是教你背概念而是逼你回答一个问题——这段数据究竟在内存里怎么放、怎么访问、怎么释放。理解了这一点不管是考研408、笔试手撕代码还是嵌入式开发里需要自己维护缓冲区和链表都不会再觉得数据结构是“黑匣子”。这篇文章面向的读者是学过C语言基础但数据结构一直停留在“看得懂、写不出”阶段的从业者和学生。我会按“理论先立住代码能复现坑提前踩掉”的顺序把线性表、树、图、排序、字符串匹配这些经典内容用C语言逐一落地并给出一套可以直接复用的练习环境。目标只有一个让数据结构不再是“玄学”而是你手底下能跑、能调、能验证的代码。2. 从严蔚敏到王道408C语言数据结构到底在学什么理论怎么落到代码2.1 数据结构五大件线性表、树、图、查找、排序的掌握边界数据结构这门课说到底是围绕“数据怎么组织、怎么操作”展开的。用C语言学习时我习惯把内容拆成五大块每一块都有明确的“C语言落地标准”。线性表是基础包含顺序表和链表。顺序表就是动态数组要掌握扩容策略链表要掌握单链表、双链表和循环链表。判断标准能在纸上画出插入、删除时指针的指向变化然后用C语言写出来并且不出现内存泄漏。树这一块重点是二叉树。掌握前中后序遍历、层序遍历、二叉搜索树、堆。对于C语言来说还要能写出用递归和栈两种方式实现遍历——后者才是面试常考的点。图的部分相对抽象重点掌握邻接矩阵和邻接表两种存储结构以及深度优先搜索DFS和广度优先搜索BFS的代码实现。查找和排序是重头戏从顺序查找、二分查找到哈希表从冒泡排序、插入排序到归并排序、堆排序、快速排序每一类都要能手写并且说清楚时间复杂度和稳定性。至于王道408里要求的“掌握程度”我的经验是概念题考的是你能否用一句话说清“什么是栈”之外的深层理解比如“为什么DFS用栈而BFS用队列”。代码题考的是你在白板上写出的C语言能否直接运行。所以不要只背定义把严蔚敏教材里的每一个ADT抽象数据类型用C语言实现一遍比看十遍“知识点归纳”都有用。2.2 为什么用C语言实现数据结构三个理由和“伪代码害死人”的真相很多教程喜欢用伪代码糊弄比如“将p节点插入链表”。看起来很好懂但一动手写C语言就崩。原因在于C语言没有自动垃圾回收你必须自己管理节点的创建和释放。用C语言实现数据结构的第一个理由就是它能暴露“内存生命周期”这个关键问题——节点是malloc出来的什么时候freefree之后指针值不变但指向的内存已无效这就是use-after-free的直接来源。第二个理由是C语言的结构体和指针能让你一眼看清数据对象在内存里的布局。结构体成员有偏移量数组是连续内存链表节点通过指针串起来这些在高级语言里被封装掉了但理解它们才能理解算法为什么“快”或“慢”。第三个理由是面试和竞赛环境的主流仍是C/C。手撕代码时C语言不会给你语法糖写不出来就是写不出来反而逼你练真功夫。至于“伪代码害死人”我见过太多同学把“if p-next NULL return false”背得滚瓜烂熟但问“p为什么不空”“free之后要不要把p置空”就卡住。伪代码省略了指针处理和内存管理而这两个恰恰是C语言的核心。所以我的做法是每个数据结构都写一份最小可运行的程序包含创建、销毁、插入、删除、遍历五个基本操作跑起来后才算“过”。2.3 最小练习闭环用C语言把数组栈和链表栈各写一遍栈是入门第一个数据结构同时也是检验你C语言基础是否扎实的好工具。我建议用两种方式实现顺序栈数组和链式栈链表。先看顺序栈#include stdio.h #include stdlib.h #include stdbool.h // 顺序栈结构数组 栈顶下标 容量 typedef struct { int *data; int top; // 栈顶指针指向下一个可写入位置 int capacity; // 当前容量 } ArrayStack; // 初始化申请初始容量为4的数组 void initStack(ArrayStack *s) { s-capacity 4; s-data (int *)malloc(sizeof(int) * s-capacity); if (s-data NULL) exit(1); s-top 0; // 空栈时top0 } // 入栈先检查容量再写入数据 void push(ArrayStack *s, int value) { if (s-top s-capacity) { s-capacity * 2; s-data (int *)realloc(s-data, sizeof(int) * s-capacity); if (s-data NULL) exit(1); } s-data[s-top] value; } // 出栈top先减一再取数据 int pop(ArrayStack *s) { if (s-top 0) { fprintf(stderr, stack underflow\n); exit(1); } return s-data[--s-top]; } // 销毁释放数组内存 void destroyStack(ArrayStack *s) { free(s-data); s-data NULL; s-top s-capacity 0; }这里最容易踩的坑是realloc失败导致原指针丢失所以先检查返回值再赋值。另一个坑是出栈时--s-top的顺序很多初学者写成s-top--然后取data[s-top]虽然结果一样但可读性差。我的习惯是data[--s-top]这样语义清晰先下移top再读取。再看链式栈核心是节点结构和入栈出栈时指针的更新typedef struct Node { int data; struct Node *next; } Node; // 链式栈只需要一个top指针指向栈顶节点 typedef struct { Node *top; } LinkedStack; // 入栈新建节点前插到top前面 void pushLinked(LinkedStack *s, int value) { Node *newNode (Node *)malloc(sizeof(Node)); if (newNode NULL) exit(1); newNode-data value; newNode-next s-top; // 新节点指向原来的栈顶 s-top newNode; // 更新栈顶 } // 出栈保存旧栈顶top后移free旧节点 int popLinked(LinkedStack *s) { if (s-top NULL) { fprintf(stderr, stack underflow\n); exit(1); } Node *old s-top; int value old-data; s-top old-next; free(old); // 只释放old节点不影响新栈顶 return value; }链式栈不用考虑容量但每个节点都要单独malloc和free。我建议把两个栈都写一遍然后对比数组栈的入栈在扩容时可能触发拷贝链式栈的每个节点都有指针开销。这个对比过程能帮你真正理解“空间换时间”的含义。写完后用一组随机数压栈再弹栈检查输出是否逆序这就是第一个可复现的练习闭环。3. 经典算法落地冒泡排序、归并排序、KMP匹配的C语言实现与测试3.1 排序算法从冒泡到归并参数和边界条件怎么调排序是数据结构的“试金石”。我要求自己至少能手写四种冒泡、插入、归并和堆排序。冒泡排序虽然效率低但用来理解“相邻元素交换”最直观。一个容易忽略的优化是如果某轮没有发生交换说明已经有序可以提前退出。void bubbleSort(int arr[], int n) { for (int i 0; i n - 1; i) { int swapped 0; // 本轮是否发生交换 for (int j 0; j n - 1 - i; j) { if (arr[j] arr[j 1]) { int tmp arr[j]; arr[j] arr[j 1]; arr[j 1] tmp; swapped 1; } } if (!swapped) break; // 无交换则提前结束 } }注意内层循环的范围是n - 1 - i因为每轮结束后最后i个元素已经是排好序的不需要再比较。归并排序的难点则在于合并操作必须用临时数组并且要把剩余元素拷贝回去// 合并两个有序区间 [l, mid] 和 [mid1, r] void merge(int arr[], int l, int mid, int r) { int leftSize mid - l 1; int rightSize r - mid; int left[leftSize], right[rightSize]; for (int i 0; i leftSize; i) left[i] arr[l i]; for (int i 0; i rightSize; i) right[i] arr[mid 1 i]; int i 0, j 0, k l; while (i leftSize j rightSize) { if (left[i] right[j]) arr[k] left[i]; else arr[k] right[j]; } // 处理剩余元素 while (i leftSize) arr[k] left[i]; while (j rightSize) arr[k] right[j]; } void mergeSort(int arr[], int l, int r) { if (l r) return; int mid l (r - l) / 2; // 防止整数溢出 mergeSort(arr, l, mid); mergeSort(arr, mid 1, r); merge(arr, l, mid, r); }mid用l (r - l) / 2而不是(l r) / 2是因为当l和r接近INT_MAX时后者的加法会溢出。这个细节在笔试中不一定考但在真实内存溢出排查中很可能遇到。归并排序是稳定的代价是额外O(n)空间这也是面试官喜欢追问的点为什么快排不稳定而归并稳定。3.2 KMP的next数组到底怎么求一段C代码说清字符串匹配字符串匹配是C语言数据结构里的“魔王”。KMP算法的核心不是匹配过程而是求next数组。很多教程用“最长公共前后缀”来解释但一写代码就乱。我的记忆方法是next[j] 表示“在模式串的第j位置发生失配时下一次比较应该从模式串的哪个下标开始”。求next数组本质上是在模式串自身身上做前缀匹配。#include string.h // 计算模式串pat的next数组数组长度与pat相同 void getNext(const char *pat, int *next) { int len strlen(pat); next[0] -1; // 哨兵表示首字符失配时主串指针也要前进 int i 0, j -1; while (i len - 1) { if (j -1 || pat[i] pat[j]) { i; j; next[i] j; } else { j next[j]; // 回溯这是KMP的精髓 } } } // KMP匹配返回pat在text中首次出现的下标没有则返回-1 int kmpSearch(const char *text, const char *pat, const int *next) { int i 0, j 0; int tLen strlen(text), pLen strlen(pat); while (i tLen j pLen) { if (j -1 || text[i] pat[j]) { i; j; } else { j next[j]; } } if (j pLen) return i - j; return -1; }next[0] -1是C语言实现里的常见做法它让回溯逻辑统一为j next[j]而不用单独处理j0的情况。我见过很多人求next时把i和j的移动顺序写错导致死循环。建议在纸上手动演算一遍“ABCDABD”的next数组-1,0,0,0,0,1,2再对照代码你会发现i是模式串的后缀指针j是前缀指针j -1时就说明前缀已经到头必须同时前进并重置。这道坎跨过去KMP就算真正掌握了。3.3 可复现的测试框架用随机数据对比不同算法耗时算法写对了没有不能靠眼睛看。我习惯用一个最简单的测试框架生成随机数组分别调用排序函数对比结果和耗时。这样既验证正确性也能直观看到O(n^2)和O(n log n)的差距。#include time.h #include stdlib.h #include stdio.h // 生成一个长度为n的随机数组范围[0, maxVal) void genRandomArray(int arr[], int n, int maxVal) { srand(time(NULL)); // 用当前时间做种子 for (int i 0; i n; i) { arr[i] rand() % maxVal; } } // 检查数组是否非递减 int isSorted(int arr[], int n) { for (int i 1; i n; i) { if (arr[i - 1] arr[i]) return 0; } return 1; } // 计时并返回排序函数执行时间毫秒 long timeSort(void (*sortFunc)(int *, int), int arr[], int n) { clock_t start clock(); sortFunc(arr, n); clock_t end clock(); return (end - start) * 1000 / CLOCKS_PER_SEC; }这里有个坑clock()测量的是CPU时间不是墙钟时间在多线程下可能不准但单线程练习足够。另外如果你要对比多个排序算法必须复制一份相同的数组否则第一个排序已经把它排好了第二个算法测出来是0毫秒。这其实就是“控制变量”的思想也是算法对比测试里最容易翻车的地方。KMP的测试一般是构造一个长文本和一个模式串用朴素匹配和KMP各跑一遍统计比较次数比看耗时更有说服力——因为字符串匹配的耗时受缓存影响太大。4. C语言数据结构避坑指南指针悬挂、越界、递归溢出的5个血泪教训4.1 删除链表节点后“忘了置空”use-after-free崩溃现象链表删除函数执行后遍历链表时偶发段错误有时还能打印出已经“被删除”节点的值。原因free(p)只是释放了p指向的内存但p指针本身的值没变仍然指向那块已回收的内存。如果后续代码继续通过p访问或者另一个节点还残留指向p的next指针就成了悬挂指针。解决删除节点时必须先把前驱节点的next指向p-next再释放p。释放后把p置为NULL避免误用。我一般会在free后加一行p NULL;。更高要求的做法是如果链表可能被多处引用删除后返回新的头指针并让调用方更新。这个习惯能规避大部分use-after-free问题。4.2 数组下标差1排序里最隐蔽的越界现象冒泡排序里内层循环写成j n - i归并排序的临时数组大小算错一位结果要么越界写坏数据要么排序结果里有一个元素始终不对。原因C语言数组下标从0开始长度为n的数组合法下标是0到n-1。排序循环里“最多需要比较n-1次”和“第i轮需要比较n-1-i次”很容易差1。越界写内存不会立刻崩溃但会悄悄篡改相邻变量导致数据错乱。解决写完排序后用断言检查边界。比如在冒泡内层循环里加一句if (j 1 n) break;运行时立刻暴露问题。我还会用AddressSanitizer编译gcc -fsanitizeaddress -g sort.c这样越界访问会直接报错并给出调用栈省去大量排查时间。4.3 递归深度过大二叉树深度优先遍历的栈溢出现象对一棵深度接近10000的二叉树做递归前序遍历程序直接段错误连报错都没有。原因递归调用依赖系统调用栈Linux默认栈大小通常为8MB每层递归函数只要分配几十字节上下文10000层就可能溢出。数据结构教材里的递归遍历在理论上没问题但真实生产环境的树可能非常深。解决把递归改成显式栈或者用Morris遍历利用空指针线索。需要保留递归写法时可以做两件事一是让递归函数尽量少用局部变量二是用ulimit -s查看并增大栈空间。但我的建议是二叉树的非递归遍历是高频面试题不如趁着这个机会把“用栈模拟递归”练熟一劳永逸。4.4 结构体按值传参大数据结构体为什么慢现象把一个包含几万个节点的二叉树结构体直接传入函数编译不开优化时每次调用都要拷贝几十KB数据明显感觉程序卡顿。原因C语言里结构体按值传参时实参会完整复制到新栈帧。如果结构体很大复制开销远大于传指针。解决传递指针并在函数内只修改需要修改的部分。如果函数不需要修改原结构体传const Node *node既安全又能让编译器优化。这个教训在实现图和树的时候尤其重要因为节点结构体往往包含多个数组或子节点指针按值传参等于把整棵子树复制一遍纯属浪费。4.5 测试数据一锅端有序、乱序、重复数据下的排序性能假象现象用一组几乎有序的数据测试快速排序发现它跑得比冒泡还慢又或者用全相同数据测试有些排序直接段错误。原因快排在最坏情况下时间复杂度为O(n^2)当数据已经有序且选取中间元素作为基准时递归深度可能接近n导致栈溢出。而冒泡排序对有序数据反而能提前退出。解决测试排序算法时至少要准备三种输入随机乱序、升序、降序、全相同。针对快排可以改为“三数取中”选取基准或者随机选取基准避免固定边界导致的最坏情况。我一般会在测试框架里生成这四组数据分别跑一遍并打印耗时这样才能真实评估一个算法的适用场景。5. 工程化练习环境VSCode GCC Makefile valgrind 的最小配置5.1 为什么我不用IDE直接写三行Makefile带来的确定性很多同学用Visual Studio或Clion点一下运行就能看到输出。但数据结构练习需要“可复现、可检查、可调试”IDE把这些细节藏起来了。我用VSCode配GCC和Makefile理由是编译命令是可见的调试参数是显式的内存检查是随手写的。当你亲手敲出gcc -g -Wall这几行你会开始关注编译警告而不是等程序崩了再去猜。VSCode里只需要安装C/C扩展然后用终端命令编译运行。这样你在面试白板上写代码时也不会依赖智能提示。我建议不要用一键运行按钮而是养成在终端里执行make ./main的习惯。5.2 最小Makefile模板支持调试与内存检查下面这个Makefile我用了很久足够覆盖数据结构练习的绝大多数需求CC gcc CFLAGS -Wall -Wextra -g -stdc11 LDFLAGS # 需要根据实际文件调整这里假设最终目标是main SRCS main.c stack.c linkedlist.c OBJS $(SRCS:.c.o) main: $(OBJS) $(CC) $(LDFLAGS) -o $ $^ %.o: %.c $(CC) $(CFLAGS) -c $ -o $ clean: rm -f main $(OBJS) # 内存检查编译后运行valgrind memcheck: main valgrind --leak-checkfull --error-exitcode1 ./main参数说明-Wall -Wextra开启严格警告能提示未使用变量、符号比较等问题-g生成调试信息供gdb和valgrind使用-stdc11避免一些旧标准下的隐晦行为。%.o: %.c是通用规则每次新增源文件只需要在SRCS里加一行。运行make memcheck时就会自动编译并调用valgrind检查内存泄漏。我第一次跑通这个模板时发现自己冒泡排序里有个数组越界是valgrind先报出来的这感觉比事后查半天舒服多了。5.3 gdb断点调试与valgrind内存泄漏检测的常用命令用gdb调试链表时我最常用的三条命令是break、next、print。例如在删除节点的函数开头设断点gdb ./main break deleteNode # 在deleteNode函数入口处暂停 run # 启动程序停在断点 print p-data # 查看当前节点数据 next # 单步执行一行 print p-next # 看next指针指向哪里 continue # 继续运行这里的print对指针结构体也能直接展开显示成员省去手动查内存地址。而valgrind的命令更简单valgrind --leak-checkfull --show-leak-kindsall ./main如果输出里有definitely lost: N bytes说明内存泄漏了。定位到具体行号后回头检查malloc和free是否成对。我见过有些同学总说“我的链表没内存泄漏”直到valgrind报出一大堆才发现销毁函数只free了头节点后面的节点都丢了。这个教训让我养成习惯每写一个涉及malloc的接口就立刻写对应的free接口并把两者在注释里对应起来。6. 让算法真正长在身上每学一个结构先画图再写码最后用随机数据验证数据结构与算法这门课最怕的就是“眼睛会了手不会”。我自己的方法是固定三步走坚持三个月后手写常见数据结构的代码基本不会卡壳。第一步是画图。学链表时画两个方框代表节点用箭头表示指针学二叉树时画一棵树然后标出前序、中序、后序遍历的路径。画图能让你把“抽象结构”变成“记忆中的画面”写代码时脑子里就有一个指针怎么移动的动画。我甚至会在草稿纸上模拟空指针、头节点、双向链表prev和next的对称性。这一步省不掉尤其是KMP的next数组不画图根本理解不了“回溯”。第二步是写代码但不能贴抄。我的习惯是早上看完原理晚上合上书从空白文件开始写。写的过程中不许查教材只许查C语言语法比如realloc的用法。写完编译运行如果报错就用gdb定位。这样折腾出来的代码比看十遍例题都印象深刻。关键点要画“记忆锚点”比如KMP的next[0] -1链表删除时free(p); p NULL;这些是你未来面试手撕时的条件反射。第三步是用随机数据验证。这是最容易被新手忽略的。我写的每个排序、查找、树操作都会配一个测试函数构造随机数据、执行操作、检查结果是否符合预期。比如测试二叉搜索树插入后中序遍历应该是有序序列测试栈后弹出序列应该等于压栈逆序。这套验证方法还能帮你发现隐藏的性能问题——当数据规模从100变成100000时O(n^2)和O(n log n)的耗时差距会变得触目惊心。最后说一个我最近的教训写堆排序时我自认为理解了“下沉”操作结果构建堆时把条件写反导致排序结果完全错误。原因就是我没画图只靠代码推理。后来我在纸上画出数组在完全二叉树中的对应位置立刻发现下标计算差了一个偏移量。这件事让我更坚定数据结构不是背出来的是画出来、写出来、测出来的。如果你也正在被“看着都会一写就废”困扰不妨试试我这个三步法先从今天学的一个栈或一个排序开始。希望帮到你。本文还有配套的精品资源点击获取