简介这套资料精心整理了C语言数据结构与算法中的核心内容从图、树等复杂存储结构如邻接矩阵、邻接表、二叉树到查找表、线性表、字符串处理再到排序算法冒泡、选择、插入、快速排序等、外部排序、栈与队列以及数组和广义表覆盖了课程教学与实践应用的常见主题。无论是初学者建立概念框架还是程序员巩固算法功底、优化代码实现都可从中获得扎实的参考价值。整个压缩包共含558个文件体积约12.92MB主要文件类型包括C语言源代码、Dev-C工程文件、编译生成的可执行程序以及配套说明文档便于直接阅读、运行和二次修改。目前已有1977人学习下载特别适合作为教材配套资料或自学实战素材帮助读者从原理到实现系统掌握数据结构与算法。1. 数据结构与算法C语言从严蔚敏教材到一行可运行代码之间的距离《数据结构C语言版》常年挂在各大高校参考书单和考研408的考纲里但很多人把它当理论书读完就放下真正上机手撕代码时才露馅链表反转写不顺、快排的 partition 边界每次都要试错、KMP 的 next 数组算出来总差一位。这份资源就是把严蔚敏那本教材里的伪代码和典型课后题落成一套能直接编译运行的 C 语言工程配套实验报告、习题解析和考点代码。它适合考研408和期末机试的备考者也适合数据结构知识点背得熟、代码却写不利索的在职开发。数据结构与算法这门课用 C 语言表达到今天依然是笔试和手撕代码的主流先把代码落地后面省的才是真时间。2. 顺序表与链表C语言数据结构的两个基础存储结构顺序存储和链式存储是 C 语言数据结构的第一层分水岭。顺序表靠连续内存链表靠指针把碎片节点串起来。考试里常问“顺序表插入平均移动多少元素”“链表能不能随机访问”这些概念背一背就有但真正动笔写代码时顺序表扩容、单链表头插尾插、双向链表四指针操作才是拉开差距的地方。下面逐段拆开这三块。2.1 顺序表的动态扩容realloc 的返回值必须拿新变量接顺序表核心是三个字段data 指针、length 和 capacity。容量不够时最直接的做法是 realloc但网上不少示例代码写成了这种危险姿势list-data (int*)realloc(list-data, newCap * sizeof(int));这个写法在 realloc 失败时会返回 NULL直接把原来的指针覆盖掉之前的数据全部丢失。我一般用临时变量接住返回值#include stdio.h #include stdlib.h typedef struct { int *data; int length; int capacity; } SeqList; void initSeqList(SeqList *L, int cap) { L-data (int*)malloc(cap * sizeof(int)); if (L-data NULL) { exit(1); } L-length 0; L-capacity cap; } void expandSeqList(SeqList *L) { int newCap L-capacity * 2; int *tmp (int*)realloc(L-data, newCap * sizeof(int)); if (tmp NULL) { printf(扩容失败保持原容量\n); return; } L-data tmp; L-capacity newCap; }逻辑说明先把 realloc 的返回值存进 tmp判断非空后再赋给 L-data。realloc 成功时旧内存由运行时自动回收不需要手动 free失败时旧内存块原封不动只是扩容没有生效。capacity 翻倍而不是加固定值是为了把插入操作的平均时间复杂度摊到 O(1)这是动态数组的通用设计。参数说明initSeqList 的 cap 是初始容量我习惯开 4 或 8。扩容因子取 2 是时间换空间工程里取 1.5 的也不少主要是减少内存碎片。如果目标是嵌入式或内存受限环境翻倍会导致分配失败概率上升改成固定增量更合适。2.2 单链表头插与尾插反转和顺序构建的差别单链表节点就是 data 加 next。头插法新节点永远插在头节点后面尾插法需要维护一个尾指针。两者应用场景完全不同。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node* createNode(int val) { Node* n (Node*)malloc(sizeof(Node)); n-data val; n-next NULL; return n; } // 头插法每步 O(1)最终链表是输入序列的逆序 Node* insertHead(Node* head, int val) { Node* n createNode(val); n-next head; return n; } // 尾插法需要 tail 指针最终链表保持输入顺序 Node* insertTail(Node* head, Node** tail, int val) { Node* n createNode(val); if (head NULL) { head n; } else { (*tail)-next n; } *tail n; return head; }逻辑说明头插法每次把新节点的 next 指向当前 head再把 head 移到新节点所以遍历结果的顺序和输入完全相反。单链表原地逆置就是按头插法的思路一遍遍历加插入不需要额外开数组。尾插法必须记录 tail否则每次都要从头遍历到尾插入退化成 O(n)。参数说明insertTail 的 tail 是二级指针因为函数内部要修改 tail 指向的节点。很多人在这一步栽跟头传一级指针进函数跑完 tail 还是老值根源是 C 语言的值传递后面第 5 章单独展开。2.3 双向链表插入删除四个指针的先后顺序双向链表每个节点有 prior 和 next。在 a 和 b 之间插入 p需要操作四根指针顺序错了就断链。#include stdio.h #include stdlib.h typedef struct DNode { int data; struct DNode *prior; struct DNode *next; } DNode; // 在节点 a 后面插入节点 p void insertAfter(DNode* a, DNode* p) { p-next a-next; // 第 1 步p 先指向原后继 if (a-next ! NULL) { a-next-prior p; // 第 2 步原后继的 prior 指回 p } a-next p; // 第 3 步a 的 next 指向 p p-prior a; // 第 4 步p 的 prior 指向 a }逻辑说明第 1 步和第 2 步必须在 a-next 被改写前完成。如果先执行 a-next p原来那个后继节点就找不到了第 2 步操作的就不是原后继链表直接断掉。删除节点同理先让前驱的 next 指向后继、后继的 prior 指向前驱再考虑 free 当前节点。参数说明insertAfter 默认 p 已经初始化且 p 当前不在任何链表中。如果 p 之前挂在另一个链表里需要先把它摘除否则会出现两个链表共享一个节点free 时造成重复释放。3. 栈、队列与二叉树递归和指针操作的结合部栈和队列是限制存取位置的线性表树是第一个非线性结构。C 语言里它们共同的难点在于判空条件、循环下标和递归调用栈的消耗。这三块在考试题里的出场率非常高代码量不大但边界陷阱密集。3.1 链式栈的 push 和 pop中缀转后缀的骨架栈分顺序栈和链式栈。顺序栈数组大小要提前定链式栈节点动态分配适合深度不确定的场景。#include stdio.h #include stdlib.h typedef struct StackNode { char data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; } LinkedStack; void push(LinkedStack *s, char c) { StackNode *n (StackNode*)malloc(sizeof(StackNode)); n-data c; n-next s-top; s-top n; } int pop(LinkedStack *s, char *out) { if (s-top NULL) { return 0; // 栈空 } StackNode *tmp s-top; *out tmp-data; s-top tmp-next; free(tmp); return 1; }逻辑说明push 是把新节点的 next 指向当前栈顶然后 top 走到新节点pop 先把栈顶值取出来top 下移再 free 原栈顶。pop 用 int 返回成功与否避免栈空时拿到无效的 out。中缀转后缀、括号匹配的题核心就是用栈暂存运算符遇到优先级低的运算符时把栈里优先级高的先弹出去。参数说明s 是指向链栈结构的指针。判空只看 top NULL不需要 base 指针。如果你在单片机这类 RAM 很小的环境里大量 push每个 malloc 都会消耗堆空间并产生碎片这就是“单片机c语言没有堆栈吗”这种问题背后的现实来源——MCU 的栈区本来就小递归一深就溢出了。3.2 循环队列front 和 rear 的边界判断顺序队列的致命问题是假溢出rear 到数组末尾时前面还有空位但数组“感觉”满了。解决方式是取模。#include stdio.h #include stdlib.h #define MAXSIZE 10 typedef struct { int data[MAXSIZE]; int front; int rear; } CircularQueue; int isFull(CircularQueue *q) { return (q-rear 1) % MAXSIZE q-front; } int isEmpty(CircularQueue *q) { return q-front q-rear; } int enqueue(CircularQueue *q, int val) { if (isFull(q)) { return 0; } q-data[q-rear] val; q-rear (q-rear 1) % MAXSIZE; return 1; } int dequeue(CircularQueue *q, int *out) { if (isEmpty(q)) { return 0; } *out q-data[q-front]; q-front (q-front 1) % MAXSIZE; return 1; }逻辑说明循环队列通过 (rear1) % MAXSIZE 把 rear 从数组末尾绕回开头。判断队满用的是“牺牲一个存储单元”的方案即 (rear1)%MAXSIZE front 就认为满实际最多存 MAXSIZE-1 个元素。队空直接用 front rear。这两条边界条件就是循环队列考试题的全部考点。参数说明MAXSIZE 是数组物理长度。如果你想让队列真正用满 MAXSIZE必须加一个 size 字段记录当前元素个数否则空和满都会表现为 front rear这是最常见的困惑点。BFS 遍历二叉树或图时用队列也是这套结构只是 data 换成节点指针。3.3 二叉树的递归遍历与非递归调用栈是底层逻辑二叉树节点定义和遍历代码很简短但很多人看得懂递归自己写就懵。核心是抓住“空树就是递归基”。#include stdio.h #include stdlib.h typedef struct BTNode { int data; struct BTNode *left; struct BTNode *right; } BTNode; void preOrder(BTNode *root) { if (root NULL) { return; } printf(%d , root-data); // 先访问根 preOrder(root-left); // 再遍历左子树 preOrder(root-right); // 最后遍历右子树 } void inOrder(BTNode *root) { if (root NULL) { return; } inOrder(root-left); printf(%d , root-data); inOrder(root-right); } void postOrder(BTNode *root) { if (root NULL) { return; } postOrder(root-left); postOrder(root-right); printf(%d , root-data); }逻辑说明三种遍历的差别只有一条 printf 的位置。先序在递归左子树之前打印中序在左子树递归完之后打印后序在两个子树都处理完才打印。非递归版本本质上是用显式栈模拟这些递归调用返回的位置。考研常考“用栈实现中序遍历”原理是先把根和整条左链入栈左到底就出栈访问再转向右子树。参数说明root NULL 时的 return 就是递归基缺少它函数会无限递归直到栈溢出。前面说的 MCU“没有堆栈”疑问本质就是递归深度耗尽栈空间。工程上你可以用队列和循环代替递归或者把递归改成非递归遍历来规避。3.4 哈夫曼树与编码每次选两个最小权值哈夫曼树每次从集合里取两个最小权值节点合并重复 n-1 次最后带权路径长度最小。C 实现里最简单的选择方式就是两轮比较。#include stdio.h #include stdlib.h #define INF 10000 // 在 weights 中选两个最小下标跳过 used 标记的节点 void selectTwo(int *weights, int *used, int n, int *min1, int *min2) { int m1 INF, m2 INF; *min1 *min2 -1; for (int i 0; i n; i) { if (used[i]) continue; if (weights[i] m1) { m2 m1; *min2 *min1; m1 weights[i]; *min1 i; } else if (weights[i] m2) { m2 weights[i]; *min2 i; } } }逻辑说明selectTwo 维护一个最小值和一个次小值。每轮选完以后把两个旧节点标记为 used把合并后的新权值写回数组继续下一轮。整个过程执行 n-1 次。这里 INF 是兜底哨兵值保证空位不会参选。参数说明n 是叶子节点数量哈夫曼树总节点数固定是 2n-1。这个性质考试常考题目告诉你叶子有 100 个树的总节点一定是 199。用数组实现哈夫曼树比指针省事节点间关系用数组下标表达即可王道数据结构教材里也是这套思路。4. 图与排序与查找邻接表、快速排序和 KMP 的三个硬骨头图的遍历、快速排序、KMP 三块内容是数据结构里最容易“觉得会了但一写就出错”的部分。问题都集中在边界条件图的 visited 标记时机、快排 partition 的左右指针、KMP 的 next 数组回退语义。4.1 图的邻接表存储BFS 用队列DFS 用递归邻接表是“顶点数组 每条边一个链表节点”。BFS 需要队列记录待访问顶点DFS 可以借助递归访问未访问的相邻顶点。#include stdio.h #include stdlib.h #define MAXV 100 typedef struct EdgeNode { int adjvex; // 邻接点的下标 struct EdgeNode *next; } EdgeNode; typedef struct { int data; // 顶点数据 EdgeNode *firstEdge; // 第一条边 } VertexNode; typedef struct { VertexNode vertices[MAXV]; int numVertices, numEdges; } Graph; void DFS(Graph *g, int v, int *visited) { visited[v] 1; printf(%d , v); for (EdgeNode *e g-vertices[v].firstEdge; e ! NULL; e e-next) { if (!visited[e-adjvex]) { DFS(g, e-adjvex, visited); } } }逻辑说明visited 数组在进入节点时立刻置 1防止在环上绕圈。DFS 沿一条边递归到底再返回BFS 则用队列把当前顶点的所有邻居先访问完再往下一层推进。BFS 实现就是把 DFS 的递归换成“入队、出队、邻居入队”三步。参数说明邻接表适合稀疏图邻接矩阵适合稠密图。稀疏图用矩阵会浪费大量空间但判断两点是否直接相连只要查一个下标。时间复杂度和空间复杂度的分析题里邻接表和邻接矩阵的差别主要就是这一条。4.2 快速排序partition 的边界条件决定生死快速排序是面试手撕代码出场率最高的排序算法。C 语言实现里最典型的是 Hoare 分区两个指针从两端往中间移动。#include stdio.h void swap(int *a, int *b) { int t *a; *a *b; *b t; } int partition(int *arr, int low, int high) { int pivot arr[low]; int i low, j high; while (i j) { while (i j arr[j] pivot) j--; if (i j) { arr[i] arr[j]; i; } while (i j arr[i] pivot) i; if (i j) { arr[j] arr[i]; j--; } } arr[i] pivot; return i; } void quickSort(int *arr, int low, int high) { if (low high) { int pi partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); } }逻辑说明partition 固定取 low 位置的值为基准 pivot。j 从右往左找比 pivot 小的值填到左边空位i 从左往右找比 pivot 大的值填到右边空位最后 i 和 j 相遇的位置就是 pivot 的最终位置。quickSort 递归处理左右两段。注意两个内层 while 都带 i j 条件少了它 j 会一路越过 i数组被覆盖出界这是快排最常见的段错误来源。参数说明这个写法把 pivot 存到临时变量用“挖坑填数”避免每步都 swap。如果 pivot 选在中间位置需要先和 low 交换再开始移动。尾递归优化版本会把短边递归、长边循环那是工程优化考试手撕用基础版就够。和冒泡排序比快排每轮不是简单把最大值沉底而是同时确定一个元素的最终位置平均复杂度降到 O(n log n)。数据结构排序算法这块快排是最值得先写熟的一个。4.3 KMP 算法next 数组的计算一个字母都不能错KMP 是那种看懂了觉得很简单、自己写就翻车的算法。核心是 next 数组表示匹配失败时模式串要回退到的位置。#include stdio.h #include string.h void getNext(const char *p, int *next) { int m strlen(p); int j 0, k -1; next[0] -1; while (j m - 1) { if (k -1 || p[j] p[k]) { j; k; next[j] k; } else { k next[k]; } } } int kmpSearch(const char *s, const char *p) { int i 0, j 0; int n strlen(s), m strlen(p); int next[100]; getNext(p, next); while (i n j m) { if (j -1 || s[i] p[j]) { i; j; } else { j next[j]; } } if (j m) { return i - j; // 匹配起始位置 } return -1; }逻辑说明getNext 里初始 k -1、next[0] -1。k -1 表示没有公共前后缀此时模式串直接移到开头。匹配时失配就令 j next[j]主串下标 i 不回退这是 KMP 相比朴素匹配省时间的原因。当 j -1 时也走 i; j代表模式串开头和主串当前字符都匹配不上主串前进一个字符。参数说明next 数组有不同语义版本。这里用的是“失配时模式串从位置 next[j] 重新比较”next[0] -1。王道408教材和不少考试用的是 next[0] 0 那一版两种只差一位。换版本时必须保证 getNext 和 kmpSearch 用同一套语义否则结果一定错。5. C语言数据结构避坑指南指针传参、内存泄漏和输入缓冲的实测记录这一章是我实际调试数据结构和算法代码时踩过、翻车过的记录每一条都按“现象 → 原因 → 解决”写清楚可以直接对照排查。5.1 指针参数传不进去值传递陷阱现象在函数里给链表头节点赋值、malloc 之后函数返回调用方打印 head 还是 NULL。 原因C 语言参数是值传递。head 指针本身也只是个变量传进函数的是它的拷贝函数里修改 head 修改的是拷贝调用方的 head 变量没有变化。 解决需要修改指针变量本身时传二级指针。典型场景是头插法的头节点更新以及“让栈顶变化”的函数。// 错误传一级指针函数内修改 head 无效 void initList(Node *head, int val) { head (Node*)malloc(sizeof(Node)); head-data val; head-next NULL; } // 正确传二级指针 void initListCorrect(Node **head, int val) { *head (Node*)malloc(sizeof(Node)); (*head)-data val; (*head)-next NULL; }逻辑说明正确版本里 *head malloc 修改的是调用方那个指针变量本身函数返回后 head 地址有效。如果只是修改指针指向的内容比如 p-data 100一级指针就够了因为 p 指向的对象是同一个。判断标准很简单函数内是否要改变指针变量本身的值要改就上二级指针。5.2 malloc 与 free 不配对内存泄漏的客观存在现象程序跑起来没问题连续运行多次后内存占用只涨不降用 valgrind 一查整堆“definitely lost”。 原因分配了节点但忘了释放或者 free 链表头节点时把其余节点链搞断剩下节点成了孤儿。最常见的写法是循环里每次 malloc 新对象跳出循环时没有把所有节点逐个 free。 解决养成习惯写完 insert 马上写配套的销毁函数。释放单向链表时必须先把 next 存下来再 free 当前节点否则 free 之后 next 字段已不可访问。void freeList(Node *head) { Node *cur head; while (cur ! NULL) { Node *tmp cur-next; free(cur); cur tmp; } }逻辑说明tmp 先保存下一跳free 之后再移动 cur。如果先 free(cur) 再 cur cur-next访问的是已释放内存属于未定义行为大多数情况下程序会跑飞或崩溃。双链表释放还要注意先摘除前驱后继关系避免重复释放同一块内存。5.3 scanf 和 getchar回车符是隐藏的坑现象用 scanf(%c, c) 读字符预期输入 a 然后 b结果读到的是换行符程序总少读一个字符。 原因scanf 的 %c 不跳过空白字符前面输入数字后回车会残留在输入缓冲里被 %c 直接读走。 解决在 %c 前加一个空格或者用 getchar() 把缓冲里的回车吃掉。字符串逆序、字符统计这类题经常被它卡住。char a, b; scanf(%c %c, a, b); // %c 前面留空格跳过空白字符逻辑说明scanf 的 %c 前加空格会让它跳过包括换行在内的所有空白字符这样 b 拿到的才是真正的字符。用 getchar() 清缓冲要小心它会阻塞等待输入有些程序卡死就是因为在等一个永远不来的回车。5.4 递归深度过大导致栈溢出现象二叉树退化成链表之后递归遍历直接段错误甚至程序没反应就退出。 原因递归每次调用都在调用栈上压一帧深度达到几百上千层时栈空间耗尽。前面说的“单片机c语言没有堆栈吗”这类疑问本质就是栈区太小递归深度一高就爆。 解决改用显式栈或队列做非递归遍历。考试里不让用递归时这套写法必须手熟。void preOrderNoRec(BTNode *root) { BTNode *stack[100]; int top -1; if (root ! NULL) { stack[top] root; } while (top 0) { BTNode *node stack[top--]; printf(%d , node-data); if (node-right ! NULL) { stack[top] node-right; } if (node-left ! NULL) { stack[top] node-left; } } }逻辑说明栈里先压右子树再压左子树出栈时左子树先被访问正好模拟先序递归的顺序。这样把函数递归调用变成了循环里的显式压栈深度不再受系统调用栈限制。如果树特别深stack 数组大小也要跟着调大或者改成链式栈。6. 把数据结构代码跑起来gdb、valgrind 和随机化验证写数据结构的最大错觉是“代码看起来对”。真正跑起来段错误、输出多一个空格、排序结果不对各种问题全冒出来。我的习惯是每写完一个数据结构立刻用三件套验证。6.1 gdb打断点看链表节点和指针编译时加 -g 保留调试符号然后进 gdb 打断点直接 print 指针指向的结构体。gcc -g -o list list.c gdb ./list break printList run print head-data print head-next-datagdb 的 print 能直接看到链表节点里的字段值。链表断链问题用 print head-next 就能看出哪一跳断了。比瞎改代码加日志快得多。6.2 valgrind 和随机化用例让内存问题和边界问题现形内存问题用 valgrind 跑一遍valgrind --leak-checkfull --show-leak-kindsall ./listmalloc 出来的节点没释放、free 之后又访问valgrind 会逐行报出 “definitely lost” 和 “Invalid read”。排序算法多用随机数据验证顺序数组、逆序数组、大量重复元素各跑一遍。快速排序碰到全等数组会反复递归原地打转直到栈溢出这是隐藏最深的边界问题。排序和查找这类算法用随机输入验证正确性比对着答案看代码可靠得多。有一回我调链表头插法纸上推演完全没问题一跑就段错误。最后是 gdb 打印每次循环后的 head 和节点地址发现少了一次 p p-next 的更新。从那以后我每次写完链表、树、图都强制自己用 gdb 加 valgrind 走一遍已经成了条件反射。希望帮到你。本文还有配套的精品资源点击获取