简介数据结构各章节算法实现C语言版是一份以严蔚敏《数据结构》教材为配套的Word文档面向计算机专业学生、ACM参赛者、考研复试机试与校招笔试人群。文档按顺序表、栈和队列、查找排序、字符串匹配、树、图等章节组织提供字符统计、一元多项式相加、行编辑器、后缀表达式求值、二分查找、各类排序、KMP匹配、二叉树遍历、哈夫曼树、最小生成树等可独立运行的完整C语言实现便于对照原理自行验证和扩展。包体共1个docx文件大小162KB排版清晰、目录完整方便在Word中注释补充。目前已有1391人浏览学习适合作为期末复习、考研机试和面试算法训练的随手查资料。虽然内容以经典算法代码为主但正好补足了教材示例零散、难以直接运行的痛点可帮助读者将数据结构理论与上机实践快速打通。1. 一份“数据结构各章节算法实现C语言版”为什么值得自己重写一遍数据结构这门课跟高数不一样它的考点几乎都能落在“能不能把算法写出来”上。一份“数据结构各章节算法实现C语言版”说白了就是把教材里顺序表、链表、栈、队列、树、图、排序、查找这些章节的抽象描述一行一行翻译成能编译、能跑、能测的 C 代码。对期末复习、考研数据结构 408、补数据结构实验报告、以及面试前临时手撕算法的人来说这份东西比 PPT 管用得多——它解决的是最现实的问题书上说“循环队列判空条件是 front rear”可你真要写队列时头指针尾指针谁先动、什么时候取模全是坑。这类文档的常见形态是一个 Word 文档每章放几段核心算法代码。但我建议你把它当素材而不是答案真正值钱的部分不是里面的最终代码而是“对照章节自己重写一遍”的过程。我下面要讲的就是怎么把这本笔记做成你自己的并且让每一章都能在考试、实验和面试里派上用场。2. 先定框架把《数据结构》拆成能动手的章节清单拿到这类笔记我第一件事不是翻代码而是先把章节目录和代码模块对应起来。C 语言版的《数据结构》一般按教材章节走常见组织方式是线性表、栈和队列、串、树、图、排序、查找。如果后期要靠它复习我会把每章对应成一个独立目录每个模块配一组 .h/.c 文件。我的习惯是建这样的结构data_struct_c/ ├── 01_linear_list/ │ ├── seq_list.h │ ├── seq_list.c │ └── test_seq_list.c ├── 02_stack_queue/ │ ├── stack_array.c │ └── queue_circular.c ├── 03_string/ │ └── kmp.c ├── 04_tree/ │ ├── binary_tree.c │ └── traversal.c ├── 05_graph/ │ ├── adjacency_matrix.c │ └── adjacency_list.c ├── 06_sort/ │ ├── quick_sort.c │ └── heap_sort.c └── 07_search/ ├── binary_search.c └── bst.c这样组织最大的好处是依赖关系清楚后边章节的代码会反复用到前面章节的数据结构比如图的最短路径要用队列KMP 要用字符串如果所有代码混在一个文件里最后根本没法维护。目录本身就是数据类型的分层也符合模块化的思路。文件命名上我统一用“数据结构_操作方式.c”这种格式比如 seq_list 表示顺序表、queue_circular 表示循环队列测试文件一律以 test_ 开头这样做实验报告截图时也好抓重点。2.1 线性表章节顺序表与单链表的 C 语言骨架线性表是所有后续章节的地基。顺序表的实现核心是结构体定义和扩容逻辑很多人写到一半发现数组不够用就是因为一开始把容量写死。我一般用动态数组结构体里同时记录长度和容量容量不够时再扩容typedef struct { int *data; // 动态数组配合 malloc 使用 int length; // 当前元素个数 int capacity; // 当前容量 } SeqList; void init_seq_list(SeqList *list, int cap) { list-data (int *)malloc(sizeof(int) * cap); if (list-data NULL) { printf(malloc failed\n); exit(1); } list-length 0; list-capacity cap; }说明这里传进去的是一个“初始容量”不是最大长度。后续插入元素时要先判断 length 是否等于 capacity等于就先扩容扩容一般每次扩大为原来的两倍。参数 cap 建议至少给 8 或 16太小会频繁触发 realloc反而影响效率。动态数组的好处是后期做排序、查找时直接对 data 这个连续内存操作不用担心指针碎片。单链表部分最容易翻车的是头插法和尾插法的区别。头插法每次把新节点插到链表头部最后得到的是一个逆序的链表尾插法需要额外维护一个尾指针。这里给个头插法实现typedef struct Node { int data; struct Node *next; } ListNode; void insert_at_head(ListNode **head, int val) { ListNode *new_node (ListNode *)malloc(sizeof(ListNode)); if (new_node NULL) return; new_node-data val; new_node-next *head; *head new_node; }说明这里形参必须用二级指针 ListNode **head。如果只传 ListNode *head函数里修改 head 变量本身不会传导到外部调用者链表就永远是空的这个坑在 C 语言数据结构代码里出现频率极高。参数说明新节点的 next 指向原来的头再把头指针更新为新节点顺序反了会丢链表。头插法配合“逆序建表”很常用比如读入一串数据要求逆序输出时可以直接边读边头插。2.2 栈与队列章节数组实现与链表实现的取舍栈的特点“后进先出”落在代码上就是 top 指针只在一端移动。队列“先进先出”需要队头和队尾两个位置如果用数组实现普通队列会出现假溢出——前面出队腾出的空间用不上所以实际都要写循环队列。循环队列唯一难理解的地方是取模运算我给一份能直接跑的基础版本typedef struct { int *data; int front; // 队头下标出队时移动 int rear; // 队尾下标入队时先放再移 int capacity; } CircularQueue; int enqueue(CircularQueue *q, int val) { if ((q-rear 1) % q-capacity q-front) { return 0; // 队满 } q-data[q-rear] val; q-rear (q-rear 1) % q-capacity; return 1; } int dequeue(CircularQueue *q, int *val) { if (q-front q-rear) { return 0; // 队空 } *val q-data[q-front]; q-front (q-front 1) % q-capacity; return 1; }说明判满条件是 (rear 1) % capacity front这个写法会浪费一个存储单元但能简单区分空和满。如果你不想浪费空间可以加一个 size 计数器代价是每次入队出队都要同步维护 size。参数说明capacity 必须是大于 1 的正整数front 和 rear 初始化都指向 0。这个队列在图的广度优先遍历里会原样复用到是典型的高频模块。2.3 树与图章节先写遍历再写建树建图树的实现重点是递归。二叉树的前序、中序、后序遍历代码上只是 printf 的位置不同很多算法题就是在遍历过程中剪枝或统计。先给结构体和前序遍历typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; void preorder(TreeNode *root) { if (root NULL) return; printf(%d , root-val); preorder(root-left); preorder(root-right); }说明中序遍历把 printf 放到两个递归调用之间后序放到最后一行都不用改。这个递归思路必须烂熟因为考研真题里经常考“已知前序和中序还原二叉树”本质就是递归划分左右子树。参数说明root 为空时直接返回是递归终止条件漏掉会导致无限递归直到栈溢出。图的部分邻接矩阵适合稠密图邻接表适合稀疏图。考研数据结构 408 里图和数组经常结合出题算法题常考 DFS 和 BFS。BFS 需要队列做辅助如果前面循环队列已经写过这里只用数组下标模拟队列也够用void bfs_graph(int matrix[MAXV][MAXV], int n, int start) { int visited[MAXV] {0}; int queue[MAXV], head 0, tail 0; queue[tail] start; visited[start] 1; while (head tail) { int cur queue[head]; printf(%d , cur); for (int i 0; i n; i) { if (matrix[cur][i] !visited[i]) { visited[i] 1; queue[tail] i; } } } }说明数组 queue 的前端 head 出队、尾端 tail 入队和循环队列思路一致。MAXV 建议定义成足够大的常量比如 100但如果你处理的图顶点数超过这个值数组就越界了实战里更稳妥的做法是动态分配。参数说明n 是顶点总数start 是起点visited 数组防止重复访问——这是 BFS 和 DFS 的公共骨架漏掉 visited 会死循环。3. 排序、查找、串三个最容易写崩的算法章节这章是文档里最容易被抄错的部分。排序和查找的代码明明很短但短代码里藏的全是边界条件串的 KMP 算法更是考研数据结构里的老大难。复习到中后期你会发现真正拉分的不是“会不会写”而是“边界条件处理得对不对”。3.1 排序章节快排和堆排的边界为什么总翻车快速排序有很多写法笔试里最常见的是“挖坑法”。我复习时会把一种写法练熟而不是背多个版本否则考试时容易记混void quick_sort(int *arr, int left, int right) { if (left right) return; int i left, j right, pivot arr[left]; while (i j) { while (i j arr[j] pivot) j--; arr[i] arr[j]; while (i j arr[i] pivot) i; arr[j] arr[i]; } arr[i] pivot; quick_sort(arr, left, i - 1); quick_sort(arr, i 1, right); }说明这个版本每次循环从右边找一个比 pivot 小的值填到左边挖出的坑再从左边找一个比 pivot 大的值填回右边的坑最后把 pivot 放回 i 的位置。两个内层 while 必须带 i j 条件否则会越界。比较时用的是 和 带等号是为了处理重复元素如果全相等元素都换成不带等号的写法可能出现左右指针互相交叉导致栈溢出。参数说明初次调用是 quick_sort(arr, 0, n-1)不是 n 也不是 n-2。堆排序则要分清数组下标从 0 开始还是从 1 开始。教材里很多伪代码下标从 1 开始但 C 语言的数组天然从 0 开始写堆维护函数时 child parent * 2 和 child parent * 2 1 的差异就在这。如果你做题时发现堆排结果第一遍基本正确、后面几步乱了十有八九是下标定义混用了。我一般会在代码文件头部注释里写明“本文件统一使用下标 0”防止自己临时改错。3.2 查找章节折半查找的细节与二叉排序树的构造折半查找的代码长度不到十行但考研真题反复考 mid 的取值和失败时指针的位置。这是我常用的版本int binary_search(int *arr, int n, int target) { int left 0, right n - 1; while (left right) { int mid left (right - left) / 2; if (arr[mid] target) return mid; else if (arr[mid] target) left mid 1; else right mid - 1; } return -1; }说明循环条件写成 left right 对应的是闭区间这样当 left 和 right 指向同一个元素时也能进入循环再判断一次。mid 的写法刻意避开了 (left right) / 2当 left 和 right 都很大时加法可能溢出 int这在真题和面试里都考过这一点。参数说明前提是数组已按升序排序返回 -1 表示查找失败。查找失败时left 恰好是 target 应该插入的位置下标这个性质在做“插入位置”类题目时可以直接用。二叉排序树的插入适合用“递归返回根节点”的写法比二级指针更容易理解也不容易错TreeNode *bst_insert(TreeNode *root, int val) { if (root NULL) { TreeNode *node (TreeNode *)malloc(sizeof(TreeNode)); node-val val; node-left node-right NULL; return node; } if (val root-val) { root-left bst_insert(root-left, val); } else if (val root-val) { root-right bst_insert(root-right, val); } return root; }说明每个递归调用返回的是“处理完之后的子树根节点”这样父节点只需要把返回值接到 left 或 right 上。参数说明插入值等于当前节点值时不做处理这样可以避免重复键导致树不平衡。这种递归写法的特点是代码短、不容易出现链表的断链问题但递归深度等于树高对极端退化的树要小心栈溢出。3.3 串与 KMP 算法把暴力枚举换成 O(nm) 的完整写法字符串匹配的朴素做法是暴力枚举每次从主串某个位置开始和模式串逐个比较失败就右移一位时间复杂度 O(n*m)。KMP 的核心是把“已经匹配的部分”信息存进 next 数组让模式串不回退。我在《数据结构》复习笔记里保留的是这种写法void build_next(const char *pattern, int *next) { int i 0, j -1; next[0] -1; int len strlen(pattern); while (i len - 1) { if (j -1 || pattern[i] pattern[j]) { i; j; next[i] j; } else { j next[j]; } } } int kmp_match(const char *text, const char *pattern) { int n strlen(text), m strlen(pattern); if (m 0) return 0; int next[m]; build_next(pattern, next); int i 0, j 0; while (i n j m) { if (j -1 || text[i] pattern[j]) { i; j; } else { j next[j]; } } if (j m) return i - j; return -1; }说明这里 next[0] 固定为 -1 是这套写法的关键。j 为 -1 时说明连第一个字符都没匹配上此时 i 和 j 都要前进让主串移动一位、模式串从头开始。build_next 里循环只做到 len - 2因为 next 数组长度是 m下标从 0 到 m-1最后一个下标在循环外不需要再特殊处理。参数说明text 是主串pattern 是模式串返回值是模式串第一次出现的位置下标匹配失败返回 -1。时间复杂度 O(nm)比暴力枚举在重复字符多的场景下快得多这也是 KMP 在考研里反复出现的原因。数组 next 长度是 m这种变长数组写法在 C99 下可用如果用的是 VS 系列编译器可能报错改成 malloc 动态分配即可。4. 避坑清单这份 C 语言笔记常见的四个翻车点代码背得再熟编译不过或者跑出野值考试和实验一样拿不到分。我在整理数据结构实验报告时反复踩过几个坑每条都是先用几分钟查不出原因、最后发现是小问题的类型这里直接按现象到解决写清楚。4.1 顺序表插入越界位置校验丢了一行现象在顺序表的末尾插入元素程序不报错但下一次插入时数据全乱更严重时直接段错误。原因插入函数里没有校验 pos 的范围把数据写到了 length 后面甚至写到了 capacity 之外。解决任何插入前先判断 pos 0 || pos length非法位置直接返回失败码不要在越界之后指望编译器帮你发现。4.2 malloc 忘记加 1字符串的结束符没地方放现象用 strlen 计算长度后 malloc(len)再用 strcpy 拷贝程序运行时报 “stack smashing detected” 或者堆损坏。原因strlen 返回的长度不含末尾的 \0但如果只申请 len 个字节结束符就写到了越界位置。解决字符串相关的内存分配统一写成 malloc(strlen(s) 1)。这个 1 是字符串操作的万能记忆点不管是 strcpy、strcat 还是自己写字符串逆序都要先确认末尾有地方放 \0。4.3 scanf 读字符时吃到换行符现象循环里用 scanf(%c, ch) 连续读字符第二次调用不等待输入直接跳过用 printf 打印发现读进来的是换行。原因%c 不会跳过空白字符上一次输入结束时留在缓冲区里的 \n 被当成了有效字符。解决把格式串改成 %c前面加一个空格让 scanf 先跳过空白字符或者每次读完后手动 getchar() 把换行消费掉。这个坑在写链表的菜单交互式实验程序时几乎必现。4.4 树和图的下标基准混用现象递归遍历二叉树的数组存储时明明按教材公式写的 2i 和 2i1结果总有一个子树访问不到或者访问到错误节点。原因教材里树和图的数组下标经常从 1 开始而 C 数组从 0 开始左孩子下标是 2i1右孩子是 2i2和教材公式差一个偏移。解决在文档每章开头用注释写明“本章数组下标从 0 开始”写代码前先画一个小例子确认孩子下标不要凭记忆直接套公式。这是数据结构复习里最隐蔽的偏移问题默写代码时尤其容易翻车。5. 从“看得懂”到“写得出来”复习路径与验证方法能看懂别人写的算法和自己能写出来中间隔着一个“动手量”。很多同学把这份文档从头到尾读了一遍合上之后发现自己连单链表反转都写不利索原因就是输入太少、输出太多。这一章讲的是我怎么把这份笔记变成真正可复用的复习工具。5.1 三种抄代码的方式第一种是照着书改拿文档里的代码自己新建一个 .c 文件逐行敲进去边敲边想每一行在做什么。这个阶段要求不高能编译通过就算成功目的是把代码从“眼睛看过”变成“手打过”。第二种是合上手写每学完一章把关键算法单独写在一张 A4 纸上不参考任何资料。写不出来就空着最后再对照文档用红笔补。这种方式能快速暴露你的记忆断点——很多人以为自己记住了快排的挖坑法合上书写才发现中间几步的循环顺序全乱了。第三种是改参数把代码里的输入换成边界数据比如链表只有一个节点、数组元素全相同、模式串为空观察结果是否符合预期。这一步不仅巩固算法理解还能直接为实验报告积累测试用例一举两得。5.2 边界输入与测试用例我在整理文档时专门在每章代码末尾追加一个 test 函数把常见的边界情况设计成一组测试输入。以下这几个场景基本覆盖了大多数章节的隐藏问题场景输入示例期望行为空表遍历初始化后直接打印不崩溃length 为 0单元素排序数组 {1}输出 1不进入多余分支全相同元素的快排{5,5,5,5,5}不栈溢出结果仍为五个 5KMP 模式串为空pattern 约定返回 0 或明确报错字符串长度为 0str strlen 返回 0不访问非法内存说明这些用例的价值不在于“测出错误”而在于帮你确认代码在极端情况下的行为。比如全相同元素的快排如果不带等号的比较会频繁交换且递归无法收敛提前测一次考试时心里就有底。表格里的每个用例都可以写进数据结构实验报告的功能测试部分老师看到的是完整测试意识。5.3 把 docx 里的代码整理成能编译的工程Word 文档可以作为实验报告的最终交付格式但复习时不能只盯着 docx 看。我的常见做法是以文档为素材库把每章代码抽取成独立的工程文件统一用 gcc 编译验证。编译命令保持简单gcc -Wall -g -o test_seq_list seq_list.c test_seq_list.c说明-Wall 打开全部编译警告很多潜在问题比如未使用的变量、类型不匹配会在编译时提示-g 是生成调试信息配合 gdb 可以单步跟踪看到底是哪个指针悬空了。参数说明如果代码里用到了数学库函数需要加 -lm但数据结构基础代码一般用不上。每个测试文件都要有自己的 main 函数否则链接会报重复定义如果多个模块需要一起编译就把所有 .c 文件按依赖顺序列在命令末尾。6. 让代码自己会说话给每个核心算法写一段“讲课稿式注释”代码能不能被复习时快速捡起来关键看注释。我见过太多笔记里的代码只写“插入排序”“快排”这种标题式注释三个月后回来看还得重新推一遍逻辑。我的习惯是给核心算法写一段“讲课稿式注释”想象你正在给同桌讲这段代码把嘴里说的话落到注释里。链表反转是最适合示范这个写法的算法因为它指针操作多、逻辑链条长写清楚注释和写不清楚注释效率差一倍// 输入head 指向原链表第一个节点 // 输出反转后链表的新头节点 // 思路三个指针 prev/cur/next每次把 cur 的 next 改指 prev // 然后整体右移。关键在 right 移之前先存 next避免断链。 ListNode *reverse_list(ListNode *head) { ListNode *prev NULL; ListNode *cur head; while (cur ! NULL) { ListNode *next cur-next; // 先存后继 cur-next prev; // 当前节点回头指向前驱 prev cur; // 前驱右移 cur next; // 当前节点右移到原后继 } return prev; // 循环结束时 prev 就是新头 }说明注释里把“先存后继”和“回头指向前驱”的动作写清楚比单纯写 “反转链表” 有用得多。参数说明next 指针是局部变量每轮循环重新定义它的作用只是暂存 cur 的原后继防止改完 cur-next 之后找不到剩余链表。这个实现迭代版的空间复杂度是 O(1)不依赖递归栈对很长的链表不会爆栈。把这个注释习惯扩展到其他章节顺序表扩容时注释写明“新容量为旧容量两倍使用 realloc”循环队列注释写明“浪费一个位置是为了区分空和满”KMP 的 next 数组注释写明“j 为 -1 表示模式串需要整体后移”。三个月后再打开这份笔记你不需要从头推逻辑照着注释就能回忆起来。我自己的教训是以前整理数据结构复习资料只追求代码正确注释能省则省。结果期末考前一周翻自己写的笔记发现快排那段代码根本看不懂当时为什么这么循环只能重新推演一遍白白浪费了复习时间。从那以后我要求自己每份数据结构算法实现文档里核心算法的注释必须像讲课稿一样完整。希望这些方法能帮你也把这份 C 语言版笔记整理成真正能背书、能应付考试和面试的实战手册。本文还有配套的精品资源点击获取