数据结构C语言实现：八类核心算法手撕代码避坑指南-北京尧图网络

简介文档为数据结构各章节算法的 C 语言版本配套严蔚敏《数据结构(C语言版)》使用覆盖顺序表、栈和队列、查找排序、字符串匹配、树与图等核心内容适合期末复习、ACM 训练、考研机试与复试刷题、校招笔试面试准备。文档不是零散函数而是将字符统计、多项式相加、后缀表达式求值、二分查找、哈希表、KMP 匹配、八种经典排序、哈夫曼树、图的广度优先搜索和最小生成树等经典算法组织为可独立运行的完整代码每个示例都可单独编译执行便于在理解原理的同时动手验证。资源为单个 Word 文档docx包体约 162KB目录按章节标注清晰排版良好可直接在文档中补注释或扩展新题目已有 1391 人学习。配合教材和机试题单使用能显著提升手写代码与调试能力是准备机试、复试和面试前查漏补缺的实用备查资料。课后自学或考前冲刺时也可作为代码模板快速定位提高复习效率。1. 为什么这份文档值得一页一页过而不是当作答案合集数据结构各章节算法实现C语言版这份文档每到期末、考研冲刺和面试前一周就会被翻出来。它把线性表、栈、队列、串、树、图、查找、排序八类经典算法收在了一起看起来像一份“标准答案”于是一批人复制粘贴跑通就觉得完事了。真正的分水岭不在跑通而在你能不能把这份 C 语言实现默写出来能不能说清每一行的作用能不能在边界条件上不被面试官问倒。这篇笔记就顺着文档的章节顺序过一遍每个算法给你最小可运行版本把参数和边界讲透再标出那些容易翻车的细节。适合三类人准备考研数据结构 408 的面试要手写链表反转和二叉树遍历的以及课程设计要交实验报告、不想只靠抄代码的同学。先从线性表开始。2. 线性表、栈与队列顺序存储还是链式存储先做对选型这一章是所有后续内容的地基树的兄弟表示法、图的邻接表、BFS 用的队列全是这章数据结构的复合应用。我一般建议先把线性表和栈队列的代码调到能盲写再去碰树和图。2.1 顺序表与单链表结构体定义和插入删除的差异顺序表和链表的核心差异只有一句内存连续还是指针串联。顺序表随机访问是 O(1)插入删除要挪动后续元素链表插入删除只需要改指针但前提是你已经找到前驱结点而查找本身要 O(n)。选择题经常在这里挖坑比如“频繁按位置访问元素用哪个”答案永远是顺序表。顺序表最简定义#define MAXN 100 typedef struct { int data[MAXN]; int len; } SeqList;这里的len表示当前元素个数不是最大容量。插入前检查len MAXN是表满删除前检查len 0是表空这两个条件写反或者漏写后续所有操作都会带病运行。很多教材里顺序表的下标从 0 开始第 i 个元素存在data[i-1]手撕时先明确这一点再写循环。单链表结点的结构体几乎人人都能写出来但反转链表这道题能挂掉一半人核心问题在于“先存后继再改指针”typedef struct LNode { int data; struct LNode *next; } LNode; LNode *reverse(LNode *head) { LNode *pre NULL, *cur head; while (cur) { LNode *next cur-next; // 先存后继否则 cur-next 被覆盖后链表就断了 cur-next pre; pre cur; cur next; } return pre; // 原链表尾结点变成新头 }这段代码的注释就是血泪经验如果不先用next保存后继执行cur-next pre之后原来的下一个结点地址就丢了而且丢了没有后悔药只能重新遍历。参数上要注意head本身可能是空指针反转前判空一次返回的是新的头指针调用处要记得接收返回值否则原来的head指向的是反转后的尾结点。对比项顺序表单链表随机访问O(1)O(n)插入/删除O(n)需移动元素O(1)已知前驱时额外内存少每个结点多一个指针域适用场景下标访问频繁、元素规模稳定频繁头插头删、长度不确定2.2 顺序栈压栈、弹栈与括号匹配栈在文档里通常只讲一个数组加一个栈顶指针但top的语义有两种写法指向栈顶元素或者指向下一个空位。这两种写法影响所有相关代码我的习惯是统一用“top指向当前栈顶元素”初始化top -1压栈先top再赋值。考试手撕时保持这个口径能少一个麻烦。括号匹配是栈的经典验证题很多同学卡在“弹栈前忘了判空”int match(char *s) { char stack[MAXN]; int top -1; for (int i 0; s[i]; i) { if (s[i] ( || s[i] [) stack[top] s[i]; else if (s[i] )) { if (top 0 || stack[top] ! () return 0; top--; } else if (s[i] ]) { if (top 0 || stack[top] ! [) return 0; top--; } } return top -1; }注意if (top 0 || ...)的顺序不能反过来一旦栈空stack[top]就越界访问了C 语言里这是未定义行为可能当场段错误也可能玄学地跑很久。这里先判断栈空再取值属于最基础的防御性写法。括号类型多了之后建议把左右括号映射成整型再比较代码会清爽很多。2.3 环形队列判空判满的两种实现线性队列最大的问题是“假溢出”rear到数组末尾后即使前面空着也没法入队。环形队列把数组首尾接起来但判满的条件必须取模。牺牲一个存储单元是最常见做法也最好理解#define MAXN 5 typedef struct { int data[MAXN]; int front, rear; } Queue; void initQueue(Queue *q) { q-front q-rear 0; } int isFull(Queue *q) { return (q-rear 1) % MAXN q-front; // 牺牲一个格子区分空和满 } int isEmpty(Queue *q) { return q-front q-rear; } int enQueue(Queue *q, int x) { if (isFull(q)) return 0; q-data[q-rear] x; q-rear (q-rear 1) % MAXN; return 1; } int deQueue(Queue *q, int *x) { if (isEmpty(q)) return 0; *x q-data[q-front]; q-front (q-front 1) % MAXN; return 1; }这里最大的坑是把isFull写成q-rear 1 q-front少了取模。当rear走到数组末尾再回绕时这个判断就会失效队列永远判不满入队时直接越界写坏内存。另一个容易错的地方是队列实际容量牺牲一个存储单元后容量是MAXN - 1不是MAXN。元素个数用(rear - front MAXN) % MAXN计算公式里加MAXN是为了处理负数。后面树的层序遍历和图的 BFS 都要用这版队列现在把它调通相当于给后面买保险。3. 串与二叉树KMP 的 next 数组递归与非递归一体两面串这一章教材一般只要求一个 KMP树这一章核心是遍历。把这两章放在一起复习是因为它们都跟“状态回退”有关KMP 里模式串指针要回退到 next 数组指定的位置二叉树非递归遍历要把已经访问过的结点状态压进栈里。搞懂一个另一个也顺了。3.1 KMPnext 数组计算与匹配主循环朴素串匹配就是暴力枚举主串和模式串每个位置都试一遍复杂度 O(n*m)当模式串是“aaaaab”这种重复串时极其难受。KMP 的思路是主串指针不回退模式串回退到该回退的位置这个位置由next数组预先算好。#include stdio.h #include string.h #define MAXN 100 void getNext(const char *p, int *next) { int m strlen(p); next[0] -1; int i 0, j -1; while (i m) { if (j -1 || p[i] p[j]) next[i] j; else j next[j]; } } int kmp(const char *s, const char *p) { int n strlen(s), m strlen(p); int next[MAXN]; getNext(p, next); int i 0, j 0; while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; // 主串不回退只回退模式串 } } return j m ? i - j : -1; }两个细节容易翻车。第一next[0]初始化为-1和初始化为0的版本相比匹配主循环里必须处理j -1否则下一轮s[i] p[j]会访问p[-1]直接越界。第二getNext里next[i] j计算的是失配后跳转的位置不是最长公共前后缀的长度很多人手算能算出前缀表却不知道代码里要整体右移一位并减一。写匹配主循环时先if (j -1 || s[i] p[j])把j -1放在前面顺序错了照样越界。KMP 的复杂度是 O(nm)主串指针不回退是它和暴力枚举最直观的区别。如果题目考的是nextval那是在next基础上再做一次优化考试前把两种版本的分工记清楚。3.2 二叉树遍历递归三行与非递归用栈二叉树的递归遍历简单到令人怀疑先序三行一个空指针判断加两个递归调用完事。typedef struct BTNode { int data; struct BTNode *left, *right; } BTNode; void preOrder(BTNode *root) { if (!root) return; printf(%d , root-data); preOrder(root-left); preOrder(root-right); }面试不会只考递归一定会追一句“不用递归怎么写”。递归本质是系统在维护一个调用栈函数一层层压栈返回时再弹栈。非递归就是把这个黑匣子打开自己用数组模拟栈。其中中序非递归最容易写错因为它要先一路压左孩子直到空然后出栈访问再转向右子树void inorderNonRec(BTNode *root) { BTNode *stack[MAXN]; int top -1; BTNode *cur root; while (cur || top ! -1) { while (cur) { stack[top] cur; cur cur-left; // 先把所有左孩子压栈 } cur stack[top--]; printf(%d , cur-data); cur cur-right; // 转向右子树下一轮继续左压 } }循环条件cur || top ! -1不能省略前半句第一次进入时栈为空但cur是根结点省略了循环直接结束。压栈时cur可能为 NULL出栈后cur cur-right也可能为 NULL但外层循环靠top ! -1兜住不会越界。先序非递归稍微简单遍历到一个结点先访问再压栈后序非递归最麻烦要标记右子树是否已经访问过考试时如果时间紧后序建议直接写递归。3.3 层序遍历与 BST 插入队列和二叉树的交叉点层序遍历是二叉树的“广度优先”必须用队列。把 2.3 的环形队列改一下类型或者直接用数组模拟逻辑完全一样void levelOrder(BTNode *root) { Queue q; initQueue(q); if (root) enQueue(q, root); while (!isEmpty(q)) { BTNode *cur; deQueue(q, cur); printf(%d , cur-data); if (cur-left) enQueue(q, cur-left); if (cur-right) enQueue(q, cur-right); } }入队时判断孩子是否为空为空就不入队。这样出队时拿到的每个结点都一定非空层序代码里不需要再判空。二叉搜索树的插入是另一个高频代码核心是“小的往左走大的往右走遇空就挂上”BTNode *bstInsert(BTNode *root, int val) { if (!root) { BTNode *p (BTNode *)malloc(sizeof(BTNode)); p-data val; p-left p-right NULL; return p; } if (val root-data) root-left bstInsert(root-left, val); else if (val root-data) root-right bstInsert(root-right, val); return root; }这段代码看起来简单坑在内存分配后必须把left和right置空否则后续遍历会遍历到野指针。如果插入的是重复值很多实现直接返回也有实现在左子树或右子树里放重复值先和队友确认口径再写。4. 图的 C 语言落地邻接表建图、DFS/BFS 与并查集图论代码是考研数据结构里“图和数组”这一考点的重头戏面试里也总爱让你手写“图的深度优先遍历”。这一章我建议把存储结构和遍历算法绑定记忆你选邻接矩阵还是邻接表直接影响建图代码和遍历复杂度。4.1 邻接矩阵 vs 邻接表先选存储结构再写代码邻接矩阵适合稠密图判断两个顶点是否相邻只要 O(1)但初始化就要 O(n^2)邻接表适合稀疏图空间是 O(VE)遍历一个顶点的所有邻接点时间等于它的度。408 选择题喜欢给一个图让你算两种存储的空间复杂度记住一句边数接近 n^2 用矩阵边数远小于 n^2 用邻接表。邻接表建图是最常见的代码用“头插法”把每条边挂到链头#define MAXV 100 typedef struct EdgeNode { int adjvex; // 边的另一端顶点编号 struct EdgeNode *next; } EdgeNode; typedef struct { int data; // 顶点信息 EdgeNode *firstedge; // 边链表头 } VertexNode; VertexNode adjlist[MAXV]; void addEdge(int u, int v) { EdgeNode *p (EdgeNode *)malloc(sizeof(EdgeNode)); p-adjvex v; p-next adjlist[u].firstedge; adjlist[u].firstedge p; // 头插法 }如果是无向图一条边要插两次addEdge(u, v); addEdge(v, u);。漏掉第二次边数就会减半遍历时只能从其中一个方向走到另一个方向这就是常见“图遍历少顶点”的根源。MAXV是固定数组的上限实际顶点数n应小于等于它建图前把adjlist[0..n-1].firstedge全部置 NULL。4.2 DFS 与 BFSvisited 数组是灵魂深度优先遍历的递归版和二叉树先序几乎一模一样但图有环所以必须加一个visited数组标记已访问int visited[MAXV]; void dfs(int u) { visited[u] 1; printf(%d , u); for (EdgeNode *p adjlist[u].firstedge; p; p p-next) { int v p-adjvex; if (!visited[v]) dfs(v); } }递归 DFS 在深度很大的图上可能爆系统栈所以面试也考非递归版手动用一个栈入栈时标记出栈后把未访问的邻接点全部压栈。这个写法有个细节标记时机选“入栈时”还是“出栈时”会导致同一个点被多次入栈建议统一入栈即标记配合if (!visited[v])判断才能避免重复。BFS 用队列配合 visited 数组代码比 DFS 还短void bfs(int s) { int q[MAXV], head 0, tail 0; visited[s] 1; q[tail] s; while (head tail) { int u q[head]; printf(%d , u); for (EdgeNode *p adjlist[u].firstedge; p; p p-next) { int v p-adjvex; if (!visited[v]) { visited[v] 1; // 入队前标记防止重复入队 q[tail] v; } } } }BFS 这个“入队前标记”和 DFS 的“递归前判断”是同一个原则访问一个顶点之前先确认它没被访问过。很多同学把visited[v] 1丢到出队时再写同一个顶点就会在队列里出现多份结果还能跑通但输出顺序和去重逻辑都变味了。剪枝算法里的“剪枝”思想就是 DFS 的延伸在递归入口加限制条件提前终止明显不可能的分支比如迷宫问题里越界就 return。4.3 并查集与最小生成树判断加边会不会成环并查集是图论里出现频率极高的小算法Kruskal 求最小生成树之前要先按边权排序然后从小到大选边每选一条就判断“这条边两端是否已经连通”。如果连通加进去就成环必须跳过。这个判断用并查集 O(1) 就能完成int parent[MAXV], rnk[MAXV]; int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); // 路径压缩 return parent[x]; } void unite(int a, int b) { a find(a); b find(b); if (a b) return; if (rnk[a] rnk[b]) { int t a; a b; b t; } parent[b] a; if (rnk[a] rnk[b]) rnk[a]; }find里“路径压缩”把查找路径上的所有结点直接挂到根上让后续查找接近 O(1)。unite里的按秩合并目的是把矮树挂到高树上防止并查集退化成一条链。初始化时parent[i] irnk[i] 0别漏。Kruskal 整体流程是所有边按权值升序排序遍历每条边只要两端不连通就选入生成树选够 n-1 条就停。Prim 适合稠密图Kruskal 适合稀疏图408 简答题喜欢给一个小图让你手推最小生成树代码题更倾向考并查集本身。5. 查找、排序与 KMP 的常见问题排查五个反复出现的坑前面几章的代码照着文档抄完一般能跑。但查找和排序这几节不一样代码能编译不代表结果对很多隐藏问题只在特定输入下暴露。这里列几个我见过的典型翻车现场按“现象 → 原因 → 解决”写遇到同样问题直接对照处理。5.1 二分查找死循环和漏判现象 1在有序数组里找一个确定存在的数程序却返回 -1。原因循环条件写成while (low high)同时high的更新方式是high mid。当区间只剩一个元素时循环退出正好漏掉最后一个元素。解决保留“闭区间”写法循环用low high找到就返回否则low mid 1、high mid - 1。这是最不容易出错的模板int binarySearch(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; }现象 2mid (low high) / 2在数组很大时计算出负数或异常值。原因low high溢出 int这是经典问题和算法本身无关。解决统一写成low (high - low) / 2这也是面试官常考的一句话。注意如果你用“左闭右开区间”[low, high)循环条件要换成low highhigh midlow mid 1两种模板混着用最容易出问题。5.2 快速排序与堆排序算法实现的两个高发翻车点现象 1快排对有序数组反而慢到离谱甚至递归太深导致栈溢出。原因基准值固定取a[low]或a[high]当数组已经有序时每次划分极度不平衡复杂度退化到 O(n^2)。这也解释了为什么有些文档里的快排能过随机数据遇到考试专用的“升序数组”就挂。解决三数取中取a[low]、a[mid]、a[high]的中位数作为基准或者干脆用随机下标。三数取中的代码也不复杂关键是让基准值尽可能接近中位数。现象 2堆排序输出不是升序或者出现数组越界。原因堆排序的下标处理错位。0 基数组中最后一个非叶子结点的下标是n/2 - 1不是n/2siftDown的循环条件写成2 * i 1 n括号里漏了-1访问了a[n]。解决先把数组画成完全二叉树下标从 0 开始数一遍再写循环就不会错。void siftDown(int a[], int n, int i) { while (2 * i 1 n) { // 有左孩子才继续 int j 2 * i 1; if (j 1 n a[j 1] a[j]) // 选出左右孩子中的较大者 j; if (a[i] a[j]) break; int t a[i]; a[i] a[j]; a[j] t; i j; // 交换后继续向下调整 } } void heapSort(int a[], int n) { for (int i n / 2 - 1; i 0; i--) siftDown(a, n, i); for (int i n - 1; i 0; i--) { int t a[0]; a[0] a[i]; a[i] t; siftDown(a, i, 0); // 堆规模减一从根再调整 } }堆排序算法是各类文档排序章节的必收代码也是最容易“背下来了但写不对”的。siftDown里交换后必须执行i j继续下沉漏掉这一步小元素就沉不下去。5.3 KMP 的 next 数组匹配位置错乱现象KMP 匹配结果比实际位置靠前或靠后有时直接段错误。原因next数组是“前缀表右移一位并减一”的产物把它当成朴素前缀表直接用匹配就会错位。还有一种情况是混用了两种版本next[0] -1和next[0] 0的代码交叉粘贴。解决确定一个版本并保持全篇统一。我在 3.1 里给的是next[0] -1版本对应的匹配主循环里必须有j -1这个分支。getNext计算时next[i] j里的j从-1开始第一次循环算出next[1] 0第二次才能正常推进。如果你手算出来的next数组第一位是 0那匹配循环里就不该出现j -1把这个统一就能避开一大半问题。KMP 的主串指针不回退是它和暴力枚举的复杂度差异来源也是面试时最能体现你理解深度的细节。6. 把文档代码变成自己的武器验证与改造文档里的代码再多也是别人的照着敲一遍只能练手。我会再做一步把每章代码改造成自己的“算法笔记本”每条代码都经过一道在线评测题的验证。比如单链表反转就去找一条链表反转题跑一遍二叉树层序遍历就去找层序遍历题跑一遍堆排序就去找排序题KMP 就去找“找出模式串在主串中首次出现的下标”。让代码在真实输入输出上跑通比在纸上默写十遍都管用。我一般习惯给每个算法配一道题代码留一个统一风格的文件头包含结构体定义、辅助函数和测试用例命名用list.h、tree.h、graph.h分门别类。验证之外还要做两件小事加断言和加释放函数。在环形队列的deQueue里加一句assert(!isEmpty(q))调试时就能定位是调用方的问题还是队列本身的问题树结点、图边结点都是 malloc 出来的写一个freeTree、freeGraph把内存还回去。C 语言的内存管理不主动做长时间运行的内存泄漏会积累到措手不及。遇到段错误别靠猜用 gdb 断在出错行看调用栈十次里有九次能直接看出指针问题。我当年调环形队列判满写成了rear 1 front少了取模队列永远判不满数据一路往数组外写最后角落里堆了一堆垃圾数据还浑然不知。后来把整个队列画在草稿纸上转了几圈才猛然发现是取模的问题。算法实现这东西跑通只是开始边界值、空间释放、异常输入都处理干净才叫真正掌握。希望帮到你。本文还有配套的精品资源点击获取

数据结构C语言实现：八类核心算法手撕代码避坑指南

相关推荐

工业自动化FAT检验表：87项硬核测试与四层验证逻辑

电商社群KPI失效真相：从静态考核表到动态作战地图

纠删码CPU开销实测：RustFS对比三副本，成本与性能权衡

更多资讯

26年程序员转AI指南：收藏这份学习路线，轻松拥抱大模型时代！

PHP登录安全实战：TOTP多因素认证、风控拦截与Redis会话一致性

数组：算法竞赛的地基，从内存模型到高级数据结构的底层逻辑

逆变器母线电容选型实战：耐压与纹波电流计算指南

Zynq双千兆以太网硬件设计：RGMII时序收敛与PHY选型实战

ST语言BYTE数组解析：Modbus字节序问题的本质与UDT解决方案

今日更新

Multisim仿真NE555 PWM控制器：从搭电路到调占空比全流程

S32K312 AUTOSAR BSW开发实战：从配置踩坑到烧录交付

双目视觉三维人脸重建：从视差图到点云粗配准全流程解析

本周精选

CMOS设计三大物理效应：体效应、沟道长度调制与亚阈值导电

微信小程序在线阅读毕设全解析：Java后端+MySQL+避坑实战

Android音频问题五层分析法：从App到Codec的系统化诊断

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？