简介这份资源面向C语言初学者与进阶程序员系统梳理数据结构与算法的核心知识帮助读者建立从线性表到图、树的完整认知框架并掌握典型算法的C语言实现思路。压缩包共558个文件约12.92MB以c源码、win工程文件、out与o编译产物、layout与dev配置、exe可执行程序为主另含少量bak备份与txt说明覆盖顺序栈、线性表、字符串、数组与广义表、栈和队列、查找表、排序及外部排序、图与树存储结构等模块工程文件可直接编译运行便于对照调试。目前已有1977人学习下载适合作为课程配套练习、教材参考或面试复习素材读者可借此理解邻接矩阵、邻接表、二叉树、B树、二分查找、快速排序等具体实现并通过可运行工程加深对内存布局与算法效率的体会。1. 从一道 5×5 鞍点题说起C 语言数据结构与算法到底在练什么很多人第一次被「数据结构与算法」这四个字劝退是在一道看起来人畜无害的题上用stdio.h和limits.h求 5×5 矩阵的鞍点。鞍点的定义是——该元素在所在行最大、在所在列最小。写两层循环找一遍逻辑三分钟就能想明白可真正敲进编辑器边界、初始化、多解、无解、INT_MIN和INT_MAX的取值全都能让人翻车。这道题恰好把 C 语言数据结构与算法的核心矛盾摊开了算法思路是抽象的但落到 C 里你得亲手管内存、管边界、管类型。C 语言数据结构与算法这门方向练的不是背下多少种排序而是三件事第一把抽象的数据关系线性、树、图用指针和数组真实地搭出来第二把算法的时间与空间代价算清楚知道什么时候该用暴力枚举、什么时候该上 KMP 或剪枝第三在 C 这种没有垃圾回收、没有泛型容器的语言里把内存和边界处理干净。它适合正在啃 C 语言基础、准备数据结构期末复习或 408 考研的人也适合已经会写业务代码、但一遇到性能问题就只会加机器的人。下面按「先立住原理、再动手复现、最后避坑」的顺序把这条路径讲透。2. 线性结构先打底顺序表、链表与双端队列的 C 实现线性结构是所有数据结构的起点也是 C 语言里最能暴露指针功底的地方。顺序表和链表看起来简单但真正写一个能用的版本涉及扩容策略、哨兵节点、内存释放顺序这些细节决定了你后面写树和图时会不会一路踩坑。2.1 顺序表与链表为什么不能只会一种顺序表用一段连续内存存元素随机访问是 O(1)但中间插入删除要搬移数据均摊 O(n)。链表用节点加指针串起来插入删除 O(1)但访问第 k 个元素要 O(n)。选型的分水岭在于你的操作是「读多写少且要随机访问」还是「频繁在中间增删」。常见做法是如果数据量可预估且以查询为主用顺序表如果元素大小不一、增删频繁用链表。C 里写顺序表核心是维护data、size、capacity三个字段扩容时按 1.5 或 2 倍增长避免每次插入都realloc。写链表核心是搞清楚「改指针的顺序」——先接后断否则会丢节点。下面给一个带头结点的单链表插入实现。#include stdio.h #include stdlib.h typedef struct Node { int val; struct Node *next; } Node; /* 在 pos 位置插入pos 从 0 开始头结点不计入 */ int list_insert(Node *head, int pos, int val) { Node *p head; int i 0; while (p ! NULL i pos) { /* 找到 pos-1 位置 */ p p-next; i; } if (p NULL) return -1; /* pos 越界 */ Node *node (Node *)malloc(sizeof(Node)); if (node NULL) return -1; /* 内存分配失败 */ node-val val; node-next p-next; /* 先接后断 */ p-next node; return 0; }逻辑说明while循环把指针推到插入位置的前一个节点i pos保证头结点不参与计数。参数pos是逻辑下标val是待插入值。关键点是node-next p-next必须在p-next node之前顺序反了就会把后面的链表整段丢掉这是链表最经典的血泪经验。返回值用 0 表示成功、-1 表示失败方便调用方判断。2.2 双端队列用数组模拟比链表更稳双端队列deque允许两端插入删除是滑动窗口、单调队列等算法的底座。C 标准库没有现成的 deque常见做法是用环形数组模拟维护front、rear、capacity用取模运算让下标循环。相比双向链表环形数组缓存友好、没有频繁malloc在算法题里更稳。#define MAXN 100005 int dq[MAXN]; int front 0, rear 0; /* [front, rear) 区间 */ /* 尾部入队 */ int push_back(int x) { if ((rear 1) % MAXN front) return -1; /* 满 */ dq[rear] x; rear (rear 1) % MAXN; return 0; } /* 头部出队 */ int pop_front(int *out) { if (front rear) return -1; /* 空 */ *out dq[front]; front (front 1) % MAXN; return 0; }逻辑说明用(rear 1) % MAXN front判满会浪费一个槽位这是环形数组的经典取舍——换来的是判空判满不用额外计数器。参数MAXN要按题目数据范围开开小了会假溢出开大了浪费内存。pop_front用指针把出队值带出去避免返回值同时承担「状态」和「数据」两种语义。单调队列求滑动窗口最大值时就是在这个结构上维护一个递减序列。3. 排序与查找从冒泡到堆排序参数和边界怎么定排序是数据结构与算法里最容易被低估的部分。很多人觉得会写冒泡、快排就够了但真正在 C 里手写堆排序、归并排序才会发现下标、递归边界、临时数组的分配全是坑。这一章把常见排序的适用场景和实现要点讲清楚。3.1 冒泡、插入、快排什么时候用哪个冒泡排序 O(n²)稳定几乎只用于教学。插入排序 O(n²)但在数据基本有序时接近 O(n)是小数组的实用选择。快速排序平均 O(n log n)最坏 O(n²)不稳定但常数小、缓存友好是通用排序的首选。C 标准库的qsort就是快排的工程化版本带三数取中和小区间优化。选型上我一般这样判断数据量小于 16 用插入排序数据量大且对稳定性没要求用快排要求稳定就用归并。快排的坑在于基准值选取——如果每次都取第一个元素遇到已排序数组会退化成 O(n²)。常见做法是三数取中或随机化基准。#include stdlib.h /* 三数取中返回基准下标 */ int median3(int *a, int left, int right) { int mid left (right - left) / 2; if (a[left] a[mid]) { int t a[left]; a[left] a[mid]; a[mid] t; } if (a[left] a[right]) { int t a[left]; a[left] a[right]; a[right] t; } if (a[mid] a[right]) { int t a[mid]; a[mid] a[right]; a[right] t; } /* 此时 a[left] a[mid] a[right]把中位数换到 right-1 */ int t a[mid]; a[mid] a[right - 1]; a[right - 1] t; return a[right - 1]; }逻辑说明三次比较把left、mid、right三个位置排好序中位数放到right-1作为基准这样左右两侧都至少有一个元素不用再比较。参数left、right是闭区间下标。注意mid用left (right - left) / 2而不是(left right) / 2避免大数组时整型溢出这是很多人忽略的细节。3.2 堆排序手写 sift_down 的三个参数堆排序 O(n log n)原地、不稳定适合对空间敏感的场景。核心是sift_down下沉操作它有三个关键参数数组、当前节点下标、堆的有效长度。很多人写错就错在把「有效长度」写成数组总长度导致已排好的尾部元素又被卷进来。/* 大顶堆下沉n 是堆的有效长度 */ void sift_down(int *a, int i, int n) { int child; while ((child 2 * i 1) n) { /* 左孩子存在 */ if (child 1 n a[child 1] a[child]) child; /* 选较大的孩子 */ if (a[i] a[child]) break; /* 已满足堆性质 */ int t a[i]; a[i] a[child]; a[child] t; i child; /* 继续下沉 */ } } void heap_sort(int *a, int n) { for (int i n / 2 - 1; i 0; i--) /* 建堆从最后一个非叶节点开始 */ sift_down(a, i, n); for (int i n - 1; i 0; i--) { /* 逐个把堆顶换到末尾 */ int t a[0]; a[0] a[i]; a[i] t; sift_down(a, 0, i); /* 注意这里是 i不是 n */ } }逻辑说明建堆从n/2 - 1开始因为下标大于它的都是叶子节点天然满足堆性质。排序阶段每次把堆顶最大值换到当前末尾然后对前i个元素重新下沉。参数n在sift_down里表示堆的有效长度排序循环里传i而不是n这是堆排序最容易写错的地方。写错的表现是排序结果局部有序但整体乱调试时可以用小数组打印每轮状态。4. 树与图指针、递归和遍历顺序的硬功夫树和图是数据结构与算法的分水岭。线性结构还能靠数组糊弄到了树和图指针操作、递归边界、访问标记一个都不能少。这一章讲二叉树和图的 C 实现要点。4.1 二叉树的三种遍历与递归边界二叉树遍历分前序、中序、后序递归写法简洁但容易在空指针上翻车。核心是递归函数的终止条件必须写在最前面且要处理root NULL的情况。非递归写法用栈模拟适合深度大、怕爆栈的场景。typedef struct TreeNode { int val; struct TreeNode *left, *right; } TreeNode; /* 中序遍历左 - 根 - 右 */ void inorder(TreeNode *root) { if (root NULL) return; /* 终止条件必须最先判断 */ inorder(root-left); printf(%d , root-val); inorder(root-right); }逻辑说明中序遍历对二叉搜索树会输出有序序列这是判断 BST 是否合法的常用手段。参数root是当前子树根节点。递归深度等于树高如果树退化成链表深度到 n可能爆栈这时要改用显式栈。前序和后序只需调整printf的位置但后序在释放树内存时特别有用——先释放左右子树再释放根。4.2 图的存储邻接矩阵还是邻接表图有两种主流存储邻接矩阵用二维数组空间 O(V²)判断两点是否相邻 O(1)适合稠密图邻接表用数组加链表或vector风格的动态数组空间 O(VE)遍历邻居高效适合稀疏图。C 里没有vector邻接表常用「头插法链表」或「边数组 head数组」实现。存储方式空间判相邻遍历邻居适用场景邻接矩阵O(V²)O(1)O(V)稠密图、需频繁判边邻接表O(VE)O(度)O(度)稀疏图、遍历为主DFS 和 BFS 是图的两大基础遍历。DFS 用递归或栈适合找路径、判连通BFS 用队列适合求最短路径无权图。两者都必须维护visited数组否则有环图会死循环。常见做法是visited在入队/入栈时标记而不是出队时标记否则同一节点可能被重复入队。#include string.h #define MAXV 1005 int adj[MAXV][MAXV]; /* 邻接矩阵 */ int visited[MAXV]; int queue[MAXV]; void bfs(int start, int n) { int head 0, tail 0; memset(visited, 0, sizeof(visited)); queue[tail] start; visited[start] 1; /* 入队即标记 */ while (head tail) { int u queue[head]; printf(%d , u); for (int v 1; v n; v) { if (adj[u][v] !visited[v]) { visited[v] 1; /* 入队即标记防止重复入队 */ queue[tail] v; } } } }逻辑说明visited[start] 1在入队时设置保证每个节点只入队一次。参数n是节点总数节点编号从 1 开始。memset把visited清零注意它按字节赋值只对 0 和 -1 安全。如果图不连通需要在外面再套一层循环对每个未访问节点调用一次 BFS。5. 避坑与排查C 语言数据结构最容易翻车的 5 个点这一章是我自己踩过、也看别人踩过的坑按「现象 → 原因 → 解决」写。每一条都能在调试器里复现建议对照自己的代码检查。5.1 段错误链表释放顺序反了现象程序在释放链表时崩溃报 Segmentation fault。原因先free(head)再访问head-next此时head已是野指针。解决先用临时指针保存next再释放当前节点。void free_list(Node *head) { while (head ! NULL) { Node *tmp head-next; /* 先保存下一个 */ free(head); /* 再释放当前 */ head tmp; } }5.2 结果错误环形队列判满条件写错现象队列明明没满push_back却返回失败。原因判满写成rear front和判空条件冲突。解决牺牲一个槽位用(rear 1) % MAXN front判满或者额外维护size计数器。5.3 死循环图遍历忘记标记 visited现象BFS/DFS 在有环图上无限循环。原因visited只在出队时标记同一节点被多次入队。解决入队/入栈时立即标记保证每个节点只进一次。这个坑在 408 图论题里非常常见。5.4 整型溢出二分查找的 mid 计算现象大数组二分查找结果错误或死循环。原因mid (left right) / 2在left和right都接近INT_MAX时溢出。解决写成mid left (right - left) / 2。这个坑在limits.h相关的题目里尤其要注意。5.5 内存泄漏malloc 后异常分支没释放现象程序长时间运行内存持续增长。原因malloc成功后在某个return -1分支直接返回没释放已分配内存。解决统一出口用goto或把释放逻辑集中到函数末尾。C 里没有 RAII只能靠纪律。提示调试这类问题时gdb的btbacktrace能快速定位崩溃点valgrind能查出内存泄漏和越界。养成写完链表、树、图就过一遍valgrind的习惯比事后救火省事得多。6. 用 KMP 和剪枝把暴力枚举优化到位前面几章把基础结构讲完了这一章落到一个具体技巧怎么把「暴力枚举」这种最朴素但最容易超时的思路用 KMP 和剪枝优化到能过题。这也是从「会写」到「写得好」的关键一步。字符串匹配是暴力枚举的典型场景。朴素匹配每次失配都回退主串指针最坏 O(nm)。KMP 的核心是next数组它记录模式串自身的「最长相等前后缀」失配时模式串指针回退到next[j]而不是 0主串指针永不回退整体 O(nm)。#include string.h /* 求 next 数组next[i] 表示 pattern[0..i-1] 的最长相等前后缀长度 */ void get_next(const char *pat, int *next, int m) { next[0] -1; int i 0, j -1; while (i m) { if (j -1 || pat[i] pat[j]) { i; j; next[i] j; } else { j next[j]; /* 回退到上一个可能匹配的位置 */ } } } /* 返回 pattern 在 text 中首次出现的下标未找到返回 -1 */ int kmp(const char *text, const char *pat) { int n strlen(text), m strlen(pat); int next[m 1]; get_next(pat, next, m); int i 0, j 0; while (i n j m) { if (j -1 || text[i] pat[j]) { i; j; } else { j next[j]; /* 主串指针 i 不回退 */ } } return j m ? i - m : -1; }逻辑说明get_next里j从 -1 开始next[0] -1是哨兵表示无法再回退。参数m是模式串长度next数组要开m1。kmp主循环里i只增不减这是 KMP 线性复杂度的来源。注意next数组的语义有两种常见写法前缀长度或回退下标混用会导致结果错位选定一种就统一到底。剪枝则是搜索类问题的优化手段。以「5×5 鞍点」为例朴素做法是每个元素都扫一遍所在行和列O(n³)。优化思路先预处理每行的最大值和每列的最小值再遍历一次比对降到 O(n²)。这就是剪枝的朴素形态——把重复计算提前算好。#include stdio.h #include limits.h #define N 5 void find_saddle(int a[N][N]) { int row_max[N], col_min[N]; for (int i 0; i N; i) { row_max[i] INT_MIN; for (int j 0; j N; j) if (a[i][j] row_max[i]) row_max[i] a[i][j]; } for (int j 0; j N; j) { col_min[j] INT_MAX; for (int i 0; i N; i) if (a[i][j] col_min[j]) col_min[j] a[i][j]; } int found 0; for (int i 0; i N; i) for (int j 0; j N; j) if (a[i][j] row_max[i] a[i][j] col_min[j]) { printf(鞍点: a[%d][%d] %d\n, i, j, a[i][j]); found 1; } if (!found) printf(无鞍点\n); }逻辑说明row_max和col_min分别预处理每行最大值和每列最小值用INT_MIN、INT_MAX初始化这正是limits.h的用途。参数N是矩阵阶数改成 5 就是题目要求的 5×5。注意鞍点可能不唯一所以用found标记而不是找到就返回。这个优化把 O(n³) 降到 O(n²)在更大矩阵上差距明显。我自己的习惯是拿到任何一道「暴力能过但慢」的题先问三个问题——有没有重复计算可以预处理有没有单调性可以用双指针或单调队列有没有失配信息可以复用KMP 的 next、AC 自动机的 fail这三个问题问下来大部分超时都能救回来。数据结构与算法这门功夫说到底就是把这些套路练到条件反射然后在 C 里把它们一行行敲对。希望帮到你。本文还有配套的精品资源点击获取