简介这份资源面向C语言初学者与进阶程序员系统梳理数据结构与算法的核心知识帮助读者建立从线性表到图、树的完整认知框架并掌握典型算法的C语言实现方法。压缩包共558个文件以c源码、win工程文件、out与o编译产物、layout与dev配置及exe可执行文件为主另含少量bak备份与txt说明整体约12.92MB目录按知识点分模块组织便于对照源码逐项调试运行。内容覆盖线性表、栈与队列、字符串、数组与广义表、查找表结构、图与树的存储结构以及排序算法和外部排序算法等主题既有基础概念的讲解也有邻接矩阵、邻接表、二叉树、B树、二分查找、快速排序等具体实现细节。已有1977人学习适合作为课程实验参考、期末复习提纲或工程实践中的算法查阅手册帮助读者在动手编码中深化理解、提升问题解决能力。1. 从一道 5×5 鞍点题说起C 语言数据结构与算法到底在练什么很多人第一次被「数据结构与算法」这四个字劝退是在一道看起来人畜无害的题上用stdio.h和limits.h在 C 语言里求 5×5 矩阵的鞍点。所谓鞍点是某一行里最大、同时又是某一列里最小的那个元素。写出来不到三十行但真动手就会发现边界、初始化、找不到鞍点时怎么输出全是坑。这道题恰好把 C 语言数据结构与算法的核心矛盾摆到台面上语言本身只给你数组、指针和一块裸内存剩下的结构怎么组织、算法怎么收敛全靠你自己想清楚。这篇笔记面向的是正在啃 C 语言基础、准备考研数据结构 408、或者要交数据结构实验报告的人。我不打算复述教科书而是把「数组、链表、栈队列、树、图、排序查找」这条主线按能跑通、能调试、能应付课程设计和考试的顺序讲一遍。你会看到每个结构为什么存在、C 里怎么落地、参数怎么设、翻车点在哪。读完你应该能自己判断这个方向值不值得投入以及从哪一步开始动手。2. 线性结构数组、链表与双端队列在 C 里的落地方式线性结构是数据结构学习的第一站也是 C 语言最能体现「手动管理内存」优势的地方。数组和链表不是二选一的对错题而是两种内存布局的取舍数组连续、随机访问快、但插入删除要搬数据链表离散、插入删除 O(1)、但访问要遍历。理解这一点后面栈、队列、树、图的存储选型都是同一套逻辑的延伸。2.1 数组与动态数组从定长到可扩容C 的数组是定长的int a[5]一旦声明长度就锁死。课程设计里经常需要「长度未知」的容器常见做法是手写一个动态数组用malloc/realloc管理容量。下面是一个最小可用的动态数组支持追加和按索引读取。#include stdio.h #include stdlib.h typedef struct { int *data; // 指向堆上的连续内存 int size; // 当前元素个数 int capacity; // 当前已分配的容量 } DynArray; // 初始化先给一个初始容量避免频繁扩容 void init(DynArray *arr, int initCap) { arr-data (int *)malloc(sizeof(int) * initCap); if (arr-data NULL) { // 分配失败必须检查否则后面全是野指针 fprintf(stderr, malloc failed\n); exit(1); } arr-size 0; arr-capacity initCap; } // 追加容量不够时按 2 倍扩容 void push_back(DynArray *arr, int value) { if (arr-size arr-capacity) { int newCap arr-capacity * 2; int *tmp (int *)realloc(arr-data, sizeof(int) * newCap); if (tmp NULL) { fprintf(stderr, realloc failed\n); exit(1); } arr-data tmp; arr-capacity newCap; } arr-data[arr-size] value; } int get(DynArray *arr, int index) { if (index 0 || index arr-size) { // 越界检查是 C 里最容易被忽略的一步 fprintf(stderr, index out of range\n); exit(1); } return arr-data[index]; } void destroy(DynArray *arr) { free(arr-data); arr-data NULL; arr-size arr-capacity 0; } int main(void) { DynArray arr; init(arr, 4); for (int i 0; i 10; i) push_back(arr, i * i); printf(size%d capacity%d arr[7]%d\n, arr.size, arr.capacity, get(arr, 7)); destroy(arr); return 0; }逻辑上size是逻辑长度capacity是物理容量两者分离是动态数组的关键。扩容策略选 2 倍而不是每次加 1是为了让追加操作的均摊复杂度降到 O(1)。参数上initCap给太小会频繁realloc给太大会浪费内存课程设计里给 4 或 8 都合理。realloc之后一定要用临时指针接返回值直接arr-data realloc(...)在失败时会丢掉原指针造成内存泄漏这是血泪经验。2.2 单链表头插、尾插与释放的三个必调点链表的核心是节点和指针。C 里没有引用所有修改头指针的操作都要传Node **否则函数内改的只是副本。下面这段覆盖了头插、尾插、遍历和释放。#include stdio.h #include stdlib.h typedef struct Node { int val; struct Node *next; } Node; // 头插O(1)但顺序会反过来 void push_front(Node **head, int val) { Node *n (Node *)malloc(sizeof(Node)); n-val val; n-next *head; *head n; } // 尾插O(n)需要先走到末尾 void push_back(Node **head, int val) { Node *n (Node *)malloc(sizeof(Node)); n-val val; n-next NULL; if (*head NULL) { *head n; return; } Node *cur *head; while (cur-next ! NULL) cur cur-next; cur-next n; } void print_list(Node *head) { for (Node *cur head; cur ! NULL; cur cur-next) printf(%d - , cur-val); printf(NULL\n); } // 释放必须逐个 free不能只 free 头节点 void free_list(Node *head) { while (head ! NULL) { Node *tmp head; head head-next; free(tmp); } } int main(void) { Node *head NULL; push_back(head, 1); push_back(head, 2); push_front(head, 0); print_list(head); // 0 - 1 - 2 - NULL free_list(head); return 0; }三个必调点第一头插和尾插都要传Node **因为可能修改头指针本身第二尾插在空链表时要单独处理否则cur-next会解引用空指针第三释放时先保存next再free当前节点顺序反了就是 use-after-free。链表题在 LeetCode 和考研 408 里高频出现反转链表、找中点、判环都是这套指针操作的组合。2.3 双端队列用循环数组实现 O(1) 两端操作双端队列deque允许两端插入删除是栈和队列的推广。用循环数组实现最省内存关键是front和rear的取模运算。#include stdio.h #include stdlib.h typedef struct { int *data; int front; // 指向队首元素 int rear; // 指向队尾元素的下一个位置 int capacity; int size; } Deque; void init(Deque *dq, int cap) { dq-data (int *)malloc(sizeof(int) * cap); dq-front 0; dq-rear 0; dq-capacity cap; dq-size 0; } int is_empty(Deque *dq) { return dq-size 0; } int is_full(Deque *dq) { return dq-size dq-capacity; } // 前端插入front 往前挪一格注意负数取模 void push_front(Deque *dq, int val) { if (is_full(dq)) { fprintf(stderr, deque full\n); return; } dq-front (dq-front - 1 dq-capacity) % dq-capacity; dq-data[dq-front] val; dq-size; } // 后端插入先写再挪 rear void push_back(Deque *dq, int val) { if (is_full(dq)) { fprintf(stderr, deque full\n); return; } dq-data[dq-rear] val; dq-rear (dq-rear 1) % dq-capacity; dq-size; } int pop_front(Deque *dq) { if (is_empty(dq)) { fprintf(stderr, deque empty\n); return -1; } int v dq-data[dq-front]; dq-front (dq-front 1) % dq-capacity; dq-size--; return v; } int main(void) { Deque dq; init(dq, 5); push_back(dq, 1); push_back(dq, 2); push_front(dq, 0); printf(%d %d\n, pop_front(dq), pop_front(dq)); // 0 1 free(dq.data); return 0; }参数上capacity决定队列上限size用来区分队空和队满——如果只用front rear判断空和满无法区分这是循环队列最经典的坑。push_front里(front - 1 capacity) % capacity的 capacity是为了避免负数取模C 的%对负数结果依赖实现不加这一项在某些编译器上会翻车。3. 树与图从二叉树遍历到 408 高频存储结构树和图是数据结构里分值最重的部分也是考研 408 和课程设计的主战场。二叉树是树的特例图是树的推广两者在 C 里的落地都绕不开「节点 指针/数组」这套组合。这一章把遍历、存储、以及图的最短路径讲清楚。3.1 二叉树三种遍历递归与非递归的取舍二叉树遍历分前序、中序、后序递归写法三行搞定但面试和考试常要求非递归因为递归深度受栈限制链式二叉树退化成链表时会爆栈。#include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left, *right; } TreeNode; TreeNode *new_node(int val) { TreeNode *n (TreeNode *)malloc(sizeof(TreeNode)); n-val val; n-left n-right NULL; return n; } // 递归中序左 - 根 - 右 void inorder(TreeNode *root) { if (root NULL) return; inorder(root-left); printf(%d , root-val); inorder(root-right); } // 非递归中序用显式栈模拟递归调用栈 void inorder_iter(TreeNode *root) { TreeNode *stack[100]; // 简单场景用定长数组当栈 int top -1; TreeNode *cur root; while (cur ! NULL || top 0) { while (cur ! NULL) { // 一路向左沿途压栈 stack[top] cur; cur cur-left; } cur stack[top--]; // 弹出栈顶访问 printf(%d , cur-val); cur cur-right; // 转向右子树 } } int main(void) { TreeNode *root new_node(1); root-left new_node(2); root-right new_node(3); root-left-left new_node(4); inorder(root); printf(\n); // 4 2 1 3 inorder_iter(root); printf(\n); // 4 2 1 3 return 0; }递归和非递归结果一致区别在空间递归用系统调用栈非递归用自己开的数组栈。参数上stack[100]是硬编码上限实际项目里应该按树高动态分配。非递归中序的核心是「一路向左压栈弹栈访问转向右子树」这三步循环理解了就不会忘。前序和后序只是访问时机不同前序在压栈前打印后序需要额外记录右子树是否已访问。3.2 图的邻接矩阵与邻接表选哪个看稠密程度图有两种主流存储邻接矩阵和邻接表。邻接矩阵是V×V的二维数组判断两点是否相邻 O(1)但空间 O(V²)邻接表是每个顶点挂一条链表空间 O(VE)但判断相邻要遍历链表。稠密图用矩阵稀疏图用表这是 408 选择题的常客。对比项邻接矩阵邻接表空间复杂度O(V²)O(VE)判断边存在O(1)O(度)遍历某点所有邻居O(V)O(度)适合场景稠密图、需频繁查边稀疏图、需频繁遍历邻居有向图入度统计遍历列 O(V)需逆邻接表或额外数组邻接表的 C 实现每个顶点一个头节点边用链表串起来#include stdio.h #include stdlib.h typedef struct EdgeNode { int to; // 边的终点 int weight; // 权值无权图可忽略 struct EdgeNode *next; } EdgeNode; typedef struct { EdgeNode **heads; // 每个顶点的边链表头 int vertexCount; } Graph; Graph *create_graph(int vCount) { Graph *g (Graph *)malloc(sizeof(Graph)); g-vertexCount vCount; g-heads (EdgeNode **)calloc(vCount, sizeof(EdgeNode *)); // calloc 自动置 NULL return g; } // 添加有向边 from - to void add_edge(Graph *g, int from, int to, int weight) { EdgeNode *e (EdgeNode *)malloc(sizeof(EdgeNode)); e-to to; e-weight weight; e-next g-heads[from]; // 头插O(1) g-heads[from] e; } void print_graph(Graph *g) { for (int i 0; i g-vertexCount; i) { printf(%d:, i); for (EdgeNode *e g-heads[i]; e ! NULL; e e-next) printf( - %d(w%d), e-to, e-weight); printf(\n); } } int main(void) { Graph *g create_graph(4); add_edge(g, 0, 1, 5); add_edge(g, 0, 2, 3); add_edge(g, 1, 3, 2); print_graph(g); return 0; }calloc比malloc多一步清零头指针数组必须初始化为 NULL否则遍历时会访问野指针。头插让加边变成 O(1)代价是边的顺序和输入相反需要顺序时改成尾插。无向图加边要调用两次add_edge两个方向都加。3.3 最短路径Dijkstra 的 C 实现与参数设置Dijkstra 解决单源最短路径要求边权非负。核心是每次从未确定的顶点里选距离最小的然后松弛它的邻居。朴素实现 O(V²)用优先队列可降到 O(E log V)。#include stdio.h #include limits.h #define V 5 #define INF INT_MAX // 返回未访问顶点中距离最小的下标 int min_distance(int dist[], int visited[]) { int min INF, min_idx -1; for (int i 0; i V; i) if (!visited[i] dist[i] min) { min dist[i]; min_idx i; } return min_idx; } void dijkstra(int graph[V][V], int src) { int dist[V]; int visited[V] {0}; for (int i 0; i V; i) dist[i] INF; dist[src] 0; for (int count 0; count V - 1; count) { int u min_distance(dist, visited); if (u -1) break; // 剩余顶点不可达提前退出 visited[u] 1; for (int v 0; v V; v) { // 松弛条件u 可达 v且经过 u 更短 if (!visited[v] graph[u][v] ! 0 dist[u] ! INF dist[u] graph[u][v] dist[v]) dist[v] dist[u] graph[u][v]; } } for (int i 0; i V; i) printf(到 %d 的最短距离: %s%d\n, i, dist[i] INF ? INF : , dist[i] INF ? 0 : dist[i]); } int main(void) { int graph[V][V] { {0, 10, 0, 5, 0}, {0, 0, 1, 2, 0}, {0, 0, 0, 0, 4}, {0, 3, 9, 0, 2}, {7, 0, 6, 0, 0} }; dijkstra(graph, 0); return 0; }参数上graph[u][v] 0表示无边这是邻接矩阵的约定如果边权可能为 0 就要换用INF表示无边。dist[u] ! INF的判断不能省否则INF weight会整数溢出变成负数导致错误松弛这是用limits.h时最容易踩的坑。min_distance返回 -1 表示剩余顶点都不可达提前退出能省时间。4. 排序与查找冒泡、堆排序、KMP 的 C 落地与性能边界排序和查找是算法部分的半壁江山也是「暴力枚举算法」和「剪枝算法」这些热词背后的基础。这一章挑三个有代表性的冒泡作为入门、堆排序作为 O(n log n) 代表、KMP 作为字符串匹配的经典。4.1 冒泡排序为什么它还在教材里冒泡排序 O(n²)实际项目几乎不用但它是理解「交换」和「稳定性」的最好例子。加一个swapped标志最好情况能降到 O(n)。#include stdio.h void bubble_sort(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; // 本轮无交换已有序提前结束 } } int main(void) { int arr[] {5, 2, 9, 1, 5, 6}; int n sizeof(arr) / sizeof(arr[0]); bubble_sort(arr, n); for (int i 0; i n; i) printf(%d , arr[i]); return 0; }swapped标志是唯一值得加的优化能把已有序数组降到 O(n)。冒泡是稳定排序相等元素不会交换位置这一点在需要保持原始顺序的场景有用。内层循环上界n - 1 - i是因为每轮结束最大的元素已经沉到末尾不用再比。4.2 堆排序建堆与下沉的两个关键操作堆排序 O(n log n)原地排序空间 O(1)是排序算法里综合性能最好的之一。核心是「建堆」和「下沉」两个操作。#include stdio.h // 下沉把 i 位置的元素调整到合适位置n 是堆的有效大小 void heapify(int arr[], int n, int i) { int largest i; int left 2 * i 1; int right 2 * i 2; if (left n arr[left] arr[largest]) largest left; if (right n arr[right] arr[largest]) largest right; if (largest ! i) { int tmp arr[i]; arr[i] arr[largest]; arr[largest] tmp; heapify(arr, n, largest); // 递归下沉被换下去的元素 } } void heap_sort(int arr[], int n) { // 建堆从最后一个非叶子节点开始下沉 for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i); // 逐个把堆顶最大值换到末尾再对剩余部分重新下沉 for (int i n - 1; i 0; i--) { int tmp arr[0]; arr[0] arr[i]; arr[i] tmp; heapify(arr, i, 0); } } int main(void) { int arr[] {12, 11, 13, 5, 6, 7}; int n sizeof(arr) / sizeof(arr[0]); heap_sort(arr, n); for (int i 0; i n; i) printf(%d , arr[i]); return 0; }建堆从n/2 - 1开始因为下标大于等于n/2的节点都是叶子叶子本身满足堆性质。下沉用递归写最直观但递归深度是树高 O(log n)数据量大时可以改成循环。堆排序不稳定相等元素的相对顺序可能改变需要稳定排序时不能用它。堆这个结构本身还能做优先队列Dijkstra 的优化版本就用它。4.3 KMPnext 数组的求法与匹配过程KMP 解决字符串匹配把朴素匹配的 O(mn) 降到 O(mn)。核心是next数组记录模式串每个位置失配后应该跳到哪里。#include stdio.h #include string.h // 求 next 数组next[i] 表示 pattern[0..i-1] 的最长相等前后缀长度 void build_next(const char *pattern, int *next, int m) { next[0] 0; int len 0; // 当前最长相等前后缀长度 int i 1; while (i m) { if (pattern[i] pattern[len]) { len; next[i] len; i; } else { if (len ! 0) { len next[len - 1]; // 回退到上一个可能的前缀 } else { next[i] 0; i; } } } } // 返回 pattern 在 text 中首次出现的下标找不到返回 -1 int kmp_search(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, m); int i 0, j 0; // i 走 textj 走 pattern while (i n) { if (text[i] pattern[j]) { i; j; if (j m) return i - j; // 匹配完成 } else { if (j ! 0) j next[j - 1]; // 失配j 回退 else i; // j 已在开头i 前进 } } return -1; } int main(void) { const char *text ababcabcacbab; const char *pattern abcac; printf(匹配位置: %d\n, kmp_search(text, pattern)); // 5 return 0; }next[i]的定义是pattern[0..i-1]的最长相等前后缀长度注意是i-1不是i这个下标差是 KMP 最容易写错的地方。失配时j next[j-1]而不是next[j]因为next[j]描述的是j之前的信息。KMP 在 PTA、LeetCode 和考研题里都高频字符串逆序、找子串这类题用它能过掉暴力枚举的超时。5. 避坑与排查C 语言数据结构实验里最常见的 5 个翻车点这一章是我带课程设计和批实验报告时总结的高频问题每条按「现象 → 原因 → 解决」写新手照着排查能省大量时间。5.1 段错误Segmentation fault指针没初始化或越界现象程序编译通过一运行就崩gdb 显示SIGSEGV。原因通常是三种指针声明后没赋值就解引用、数组下标越界、malloc返回 NULL 没检查。解决用 gdb 跑gdb ./a.out然后run崩了之后bt看调用栈定位到具体行。声明指针时习惯性初始化为 NULLmalloc后立刻检查返回值数组访问前确认下标范围。虚拟机 Ubuntu 里配好 gdb 是必修课gcc -g编译带上调试信息。5.2 内存泄漏free 漏了或释放顺序错现象程序跑久了内存占用越来越高或者 Valgrind 报definitely lost。原因链表、树、图释放时只 free 了头节点或者释放顺序反了导致 use-after-free。解决用valgrind --leak-checkfull ./a.out检查释放链表时先保存next再free当前节点释放树用后序遍历释放图先释放所有边再释放顶点数组。动态数组的data和结构体本身要分别 free。5.3 循环队列队空队满判断错误现象队列明明空了却报满或者满了还在插入覆盖数据。原因只用front rear判断无法区分空和满。解决加一个size字段或者牺牲一个存储单元容量为 n 的数组最多存 n-1 个元素。用size最直观is_empty看size 0is_full看size capacity取模运算统一用(x capacity) % capacity避免负数。5.4 排序结果不稳定导致业务逻辑出错现象按分数排序后同分学生的原始顺序被打乱。原因用了堆排序或快速排序这类不稳定排序。解决需要稳定时改用归并排序或冒泡/插入排序或者在比较函数里加一个「原始下标」作为第二关键字。C 的qsort本身不稳定要稳定得自己控制比较逻辑。5.5 KMP 的 next 数组下标差一现象KMP 匹配结果比预期少一位或多一位或者死循环。原因next[i]的定义搞混了有的教材定义next[0] -1有的定义next[0] 0两种写法回退逻辑不同。解决选定一种定义后全程统一本文用的是next[0] 0的版本失配时j next[j-1]。调试时把next数组打印出来手动验证几个位置的前后缀长度比盯着代码看快得多。6. 从能跑到能过用 gdb 和 Valgrind 把实验报告打磨到 408 水准写完能跑只是第一步课程设计要拿高分、考研 408 要稳过还得会调试和验证。我一般用两个工具gdb 定位逻辑错误Valgrind 查内存问题。下面是一套我常用的调试流程配合前面的代码直接能用。先编译带调试信息gcc -g -Wall -Wextra -o ds_test ds_test.c-g生成调试符号-Wall -Wextra打开所有警告很多指针和类型问题编译器会提前告诉你。然后 gdb 里几个必会命令命令作用使用场景run启动程序复现崩溃bt打印调用栈段错误定位break 行号设断点单步跟踪print 变量查看变量值确认指针和下标next/step单步执行区分是否进入函数watch 变量监视变量变化追踪被意外修改的值内存检查用 Valgrindvalgrind --leak-checkfull --show-leak-kindsall ./ds_test输出里definitely lost是确定泄漏invalid read/write是越界访问use of uninitialised value是用了未初始化内存。每次改完链表或树的释放逻辑我都会跑一遍 Valgrind确认All heap blocks were freed才算完。一个具体技巧调试递归函数时gdb 的bt会打印完整调用栈能直接看到递归深度和每层的参数。如果递归太深爆栈bt会显示几千层这时候就该考虑改非递归了。堆排序的heapify、二叉树遍历、Dijkstra 的松弛都可以用这个方法验证。最后说个习惯每写一个数据结构我都会配一个最小的main测试覆盖空结构、单元素、边界下标三种情况再跑 Valgrind。这个习惯让我在课程设计答辩时从没被问倒过因为每个边界我都亲手验过。C 语言数据结构与算法这门课真正的门槛不在算法本身而在对内存和边界的敬畏。希望帮到你。本文还有配套的精品资源点击获取