简介C语言数据结构与算法学习资料包面向计算机专业初学者及希望巩固基础的开发者系统覆盖数据结构核心概念与典型算法实现。压缩包内共558个文件以C源码、Dev-C工程文件、可执行程序及编译输出为主配套说明文档内容涉及图与树的存储结构、查找表、线性表、字符串、栈和队列、数组与广义表以及插入、交换、选择等多类内部排序和外部排序算法。包体约12.92MB文件组织清晰便于按专题查阅和动手实验。目前已有1977人学习下载。通过阅读源码、运行示例并观察输出可直观理解各类数据结构的存储机制与算法执行流程掌握从理论到C语言编码的转换方法从顺序存储到链式存储从递归思想到迭代优化均可在源码中找到对应实现对课程学习、考研复习或项目实践均有较高参考价值。1. 用C语言啃数据结构与算法看似过气实则是把内存和指针练成直觉的唯一路径很多人看到《C语言数据结构与算法》这类资料的第一反应是“都什么时代了还在用C刷题”。但当你真的去排查线上崩溃、去读开源基础组件的源码、去做嵌入式或通信类项目时会发现最底层的东西全在用指针操作内存。C语言版的线性表、树、图并不高深它逼着你自己处理节点分配、释放和边界判断走完这一遍之后再回去看其他语言里的“语法糖”你会清楚地知道那个糖底下包的是什么。它能解决的问题很具体笔试里的链表反转只是最表层真正的收获是建立“从地址和生命周期去推演程序行为”的习惯。适合准备机试、刚入行想补底层能力、以及上了一阵网课却还没完整写过关键代码的人。这篇笔记不贴大段理论直接把我做过的实现思路、参数选择和踩过的坑按章节摆出来。2. 从数组到链表C语言数据结构里的两种物理布局连CPU缓存都在替选择投票2.1 数组随机访问O(1)的代价是连续空间的维护成本在C语言里“数据结构”在底层总是一段地址和长度的推算。数组是最朴素的一种一段连续内存通过下标就能算地址。语言层面int a[10]定义后a[i]等价于a i所以随机访问的时间复杂度是 O(1)。这个 O(1) 不只是数学上的常数它意味着 CPU 可以直接用基址加偏移的方式取数据对缓存也很友好这次读入的相邻数据下次可能还在高速缓存里。但连续空间是有代价的。数组中间插入一个元素必须把它后面的元素依次往右挪动删除一个元素又得整体往左挪。我在做顺序表习题时最常见的翻车点是在函数里memmove一整片数据却忘了处理扩容或者外面继续用旧指针访问。下面是动态数组插入的常用写法关键在于调用方要同步更新长度和容量#include stdio.h #include stdlib.h // 在动态数组 arr 的 pos 位置插入 val // len/cap 都传指针函数里改动外部能感知 int insert_arr(int **arr, int *len, int *cap, int pos, int val) { if (pos 0 || pos *len) return -1; // 非法位置拦截 if (*len *cap) { // 已满则扩容 int new_cap (*cap 0) ? 4 : (*cap * 2); // 空表从4起步之后翻倍 int *tmp (int *)realloc(*arr, new_cap * sizeof(int)); if (tmp NULL) return -1; // 失败时原内存仍有效 *arr tmp; *cap new_cap; } for (int i *len; i pos; i--) { (*arr)[i] (*arr)[i - 1]; // 从尾部开始挪避免覆盖 } (*arr)[pos] val; (*len); return 0; }逻辑说明这个函数把扩容和插入放在一起调用方只需要关心数组指针、当前长度和容量。arr使用二级指针是因为realloc可能让堆内存搬家原来的首地址失效如果不把新地址传出去下一次操作就是对已释放地址的写操作。pos *len的边界允许尾插但拒绝在中间留下空洞。参数说明len是已使用的元素个数cap是已分配的元素容量两者语义容易混淆。扩容策略用倍数而不是固定加长是因为每次扩容需要 O(n) 的拷贝翻倍以后均摊成本降到 O(1)。如果你在嵌入式环境里不能接受这种突发的内存搬运可以考虑提前分配一个足够大的cap或者改用手写环形缓冲。数组删除的边界条件同样值得注意删除位置必须在[0, len)之间然后从前往后覆盖最后len--。容量不会立即缩水这一点是有意为之避免反复插入删除时频繁触发分配。调试时多用printf(%p\n, *arr)看首地址扩容前后地址变化会非常直观如果某个指针还是旧地址那它已经悬空了。2.2 链表头插法、反转与“先保存next”的铁律链表针对数组的连续内存短板而生。每个节点单独分配通过next指针串在一起。从逻辑上说在链表中插入和删除只要改相邻指针像 O(1)但实际要先遍历到目标位置且节点在堆里的地址离散CPU 缓存预取基本失效。所以在工程代码里大量随机访问场景数组几乎总赢链表更常见于“不知道总量、头尾反复增删”的地方。在 C 里写链表第一节课就是头插法。下面这两个函数是我每次练习都要默写一遍的typedef struct Node { int val; struct Node *next; } Node; // 头插法返回新头返回值必须接住 Node *list_push(Node *head, int val) { Node *n (Node *)malloc(sizeof(Node)); if (n NULL) return head; n-val val; n-next head; return n; } // 反转链表三个指针轮转 Node *list_reverse(Node *head) { Node *pre NULL; Node *cur head; while (cur) { Node *nxt cur-next; // 先保存后驱 cur-next pre; pre cur; cur nxt; } return pre; }逻辑说明list_push返回新节点作为新头如果调用方只写list_push(head, 1)而不接返回值新节点就变成孤儿。反转函数里nxt是绝对关键先保存cur-next再修改cur-next指向pre很多初学实现把这一步顺序写反导致链表断成两截。参数说明pre初始化为NULL它最终会成为新链表的尾结点反转完成后也是新头。cur是当前要处理的节点nxt是它在原链表里的下一站。循环结束条件是cur NULL此时pre正好指向原链表的最后一个节点也就是反转后的头。练习时我建议每次push后打印节点地址会看到堆地址毫无规律和数组的连续地址形成强烈对比。链表和数组的选择在实际中要看访问模式特性数组单链表随机访问O(1)O(n)头部插入需要移动全部元素O(1)中间插入需要移动后续元素需要先遍历到前驱空间连续性一块连续区域碎片化缓存命中率高低这张表不是劝你放弃链表而是提醒你算法题里的链表操作练的是指针逻辑但在生产环境里连续内存和缓存友好常常比理论复杂度更重要。理解了这一点再回头看“数组和链表哪个好”这个问题就有了自己的答案。3. 排序与查找把C语言算法的复杂度从理论变成可观测的差距3.1 手写快速排序三个参数决定递归边界与最坏表现排序是最容易体现“同一份代码不同写法差几倍时间”的内容。快速排序的平均复杂度是 O(n log n)但它不是银弹当分区极端不平衡时复杂度退化为 O(n²)。C语言版快排的教科书实现很多我常用下面这种写法它把所有边界条件统一成“左闭右闭区间”。static void swap_ints(int *a, int *b) { int t *a; *a *b; *b t; } void quick_sort(int a[], int left, int right) { if (left right) return; int i left, j right; int pivot a[left (right - left) / 2]; // 中间值避开溢出 while (i j) { while (a[i] pivot) i; while (a[j] pivot) j--; if (i j) { swap_ints(a[i], a[j]); i; j--; } } // 此时 left j i right quick_sort(a, left, j); quick_sort(a, i, right); }逻辑说明循环结束后j 会在 i 的左边数组被分成[left, j]和[i, right]两个互不重叠的区间然后递归排序。pivot 本身不单独保留在某个固定位置它可能随着交换被放到左侧或右侧所以递归时不需要跳过某个“pivot下标”。这种写法的交换次数比另一种经典的 Lomuto 分区更少但边界不好理解我习惯把区间语义直接写在注释里。参数说明mid left (right - left) / 2而不是(left right) / 2是为了防止两个大整数相加溢出。在 32 位 int 下标场景下这是真实存在的风险。while (a[i] pivot)使用严格小于跳过等于 pivot 的元素避免两个相等元素无限交换加上外层while (i j)等于 pivot 的元素会被渐渐分到两侧递归区间仍然有效。快速排序最怕每次选到区间最小或最大元素作 pivot那样递归深度变成 O(n)在十万级随机数据上就可能栈溢出。应对办法有随机选 pivot、三数取中以及小分区转用插入排序。我在练习里通常先用固定种子生成一万个随机数排序再故意用已排序数组测试观察它是否会退化成“慢得离谱”。如果测试机开了调试内存检查这种退化往往会先表现为栈溢出而不是结果错误因为递归压栈先消耗完栈空间。3.2 二分查找左闭右开约定为何能少写一堆offset二分查找代码很短但越短越容易把边界写错。大多数人翻车在区间开闭约定不统一导致死循环或漏解。我推荐一种约定左闭右开下标right是查找范围的后边界不包含在当前范围内。int binary_search(int a[], int n, int target) { int left 0, right n; // 搜索区间为 [left, right) while (left right) { int mid left (right - left) / 2; if (a[mid] target) return mid; else if (a[mid] target) left mid 1; else right mid; } return -1; }逻辑说明左闭右开最大的好处是让right永远指向“不是目标”或“待检查边界”的位置不会取到最后一个元素的下一位。当a[mid] target说明左侧一半全部小于目标左边界可以安全推进到mid 1当a[mid] target右边界收缩到mid仍保持“右开”。这样循环区间始终合法不会出现left right后的死循环。这个约定还能直接扩展成查找第一个不小于目标的“下界”函数。只要把返回-1的地方改成返回left并调整比较分支就能得到类似标准库lower_bound的行为。我经常在一个程序里同时写两种查找共用同一个区间语义避免记忆混乱。如果你不适应左闭右开也可以坚持左闭右闭[left, right]但更新必须写成left mid 1和right mid - 1。两种风格都能工作最怕的是这种代码里混用左边用闭区间、右边用开区间最后必然出现哨兵位置偏移。我的习惯是把“左闭右开”写进注释然后所有相关函数都照这个语义写。3.3 哈希查找从装载因子里读出冲突链的退化边界哈希表在C语言里不是库函数而是一个需要自己维护的“数组 链表”复合结构。它的理想复杂度是 O(1)但冲突会让单次查找退化成链表的 O(n)。工程上决定退化程度的核心参数是装载因子也就是表中已有元素数量与环境容量的比值。#define TABLE_SIZE 128 typedef struct HashNode { int key; int val; struct HashNode *next; } HashNode; HashNode *hash_table[TABLE_SIZE]; // 取模哈希把负数先转成无符号再计算 static unsigned hash_idx(int key) { return ((unsigned)key) % TABLE_SIZE; } // 查找先定位桶再沿冲突链遍历 HashNode *hash_find(int key) { unsigned idx hash_idx(key); for (HashNode *p hash_table[idx]; p ! NULL; p p-next) { if (p-key key) return p; } return NULL; }逻辑说明hash_idx用取模映射TABLE_SIZE是固定环境容量。这里把key转换成unsigned再取模避免负数产生负下标。hash_find先计算桶号再从桶头开始遍历冲突链逐个比较 key。查找成功时返回节点指针失败返回NULL调用方需要自行区分。参数说明装载因子 元素总数 /TABLE_SIZE。当元素数接近容量时冲突链变长查找时间不再是常数级。常见的做法是设置一个阈值比如 0.7超过后重新申请更大的表并全部重新哈希。扩容不是简单的复制因为每个元素的桶号会随容量变化必须重算一次。插入时同样先查链中是否已有同 key有则更新没有则头插到桶链表。头插比尾插快但对链表的顺序不敏感哈希表也不需要稳定顺序。我刚开始写哈希时总是默认取模就够了。后来拿真实键值跑一遍发现如果TABLE_SIZE是合数比如 128某些连续偶数 key 会全部挤在一半桶里装载因子虽然只有 0.5但冲突链已经很长。把容量换成素数或采用更分散的混合哈希这个问题会明显缓解。所以哈希表不只是写一个查找函数容量选值和阈值控制同样决定最终效果。4. 树与图用递归指针模拟关系型结构的最小模板4.1 二叉搜索树的插入、查找与“递归返回新根”写法树在C语言里就是“一堆指针互相引用”。二叉搜索树要求左子树所有 key 小于根右子树所有 key 大于根。每次查找都从根出发根据比较结果选择左或右理想情况下能把搜索范围折半。它的递归操作特别适合作为C语言指针训练的第二课。typedef struct BSTNode { int key; struct BSTNode *left; struct BSTNode *right; } BSTNode; // 插入key递归返回新根 BSTNode *bst_insert(BSTNode *root, int key) { if (root NULL) { BSTNode *n (BSTNode *)malloc(sizeof(BSTNode)); if (n NULL) return NULL; n-key key; n-left n-right NULL; return n; } if (key root-key) { root-left bst_insert(root-left, key); } else if (key root-key) { root-right bst_insert(root-right, key); } return root; } // 查找key写成迭代省递归栈 BSTNode *bst_find(BSTNode *root, int key) { while (root) { if (key root-key) return root; else if (key root-key) root root-left; else root root-right; } return NULL; }逻辑说明bst_insert的核心是“递归返回新根”。当递归到空位置时创建节点并返回上层调用会把它赋值到root-left或root-right。如果不接收返回值新节点就挂在半空整棵树丢失。查找没有修改结构所以用迭代循环更省栈。两段代码都遵循同一个方向规则小走左大走右。参数说明root在插入函数里传递的是局部指针值真正的树节点地址靠返回值一层层传回。对 NULL 的检查放在最前面作为递归出口。如果malloc失败返回 NULL 会让上层把它当成新节点这是练习代码里的隐患工程级代码应该使用独立的错误码或全局错误标记而不只是返回 NULL。遍历是树结构最直观的验证方式。中序遍历可以按 key 顺序输出全部节点代码很简短递归左子树、打印当前节点、递归右子树。前序和后序只是调整打印位置。学习二叉树最容易替换的一个经验是用gdb或printf打印root地址和key观察递归调用时地址如何层层深入又回溯比单纯看抽象演示更能建立递归记忆。删除是二叉搜索树中最难的部分。删除单分支节点只需把孩子挂上去删除双分支节点时需要用右子树中的最小值节点替换当前节点再递归删除那个最小节点。每次做这道题我都会提醒自己替换不是搬地址而是交换或者覆盖 key 值否则会留下悬空指针。4.2 图的邻接表从初始化到BFS的最小模板图在 C 语言里通常有两种表示邻接矩阵和邻接表。邻接矩阵代码简单适合稠密图但空间 O(n²) 在顶点较多时扛不住邻接表适合稀疏图本质是“每个顶点拉一条链表”。工程里大量场景是稀疏关系所以邻接表更常用。typedef struct AdjNode { int v; struct AdjNode *next; } AdjNode; typedef struct Graph { int n; AdjNode **adj; } Graph; Graph *graph_create(int n) { Graph *g (Graph *)malloc(sizeof(Graph)); g-n n; // calloc 会清空指针数组避免野指针头节点 g-adj (AdjNode **)calloc(n, sizeof(AdjNode *)); return g; } // 在 u 的邻接表头部插入 v有向图的单向边 void graph_add_edge(Graph *g, int u, int v) { AdjNode *node (AdjNode *)malloc(sizeof(AdjNode)); node-v v; node-next g-adj[u]; g-adj[u] node; }逻辑说明adj是一个指针数组数组下标对应顶点编号数组元素是链表的头指针。calloc会把所有头指针初始化为NULL这一步不能省。graph_add_edge使用头插法不需要遍历链表尾部因此插入是 O(1)。如果要表示无向图就对u和v各调用一次。参数说明n是顶点数量adj数组长度固定为n所以初始化时必须把顶点数传进来。头插法的缺点是遍历边的顺序和输入顺序相反如果需要按序输出可以在函数里改成尾插。由于每个邻接表的节点都是独立malloc的销毁图时需要遍历每个链表并逐个释放这比数组要麻烦得多也更容易泄漏。BFS 需要队列。C 标准库没有现成队列一个简单的办法是开一个n大小的数组当循环队列因为 BFS 中每个顶点最多入队一次队列长度不会超过顶点数void bfs(Graph *g, int start) { if (start 0 || start g-n) return; int *visited (int *)calloc(g-n, sizeof(int)); int *queue (int *)malloc(g-n * sizeof(int)); int head 0, tail 0; queue[tail] start; visited[start] 1; while (head tail) { int u queue[head]; for (AdjNode *p g-adj[u]; p ! NULL; p p-next) { int v p-v; if (!visited[v]) { visited[v] 1; queue[tail] v; } } } free(visited); free(queue); }逻辑说明visited数组防止环导致无限循环。每个节点入队前先标记即使它已经在队里也不会重复入队。队列采用线性数组模拟tail往增长head往前消费BFS 结束条件是队列为空。参数说明start是起点顶点编号必须小于g-n否则越界。打印节点时我习惯在弹出u后加一条printf而不是在入队时打印这样输出顺序才符合“层序”的概念。需要路径信息时还要加一个parent数组记录每个节点是从哪个节点过来的最后从终点回溯路径。5. C语言数据结构避坑实录释放、边界和递归里的翻车现场5.1 内存释放、浅拷贝和删节点的高频事故第一块free 之后立刻读指针。 现象释放一个链表节点后过一会儿读它的 val 还是原值但程序在某次 malloc 后会崩溃。原因free 只把内存归还给分配器不会清除内容也没有让指针失效这成了悬空指针。解决释放后立即把指针置为 NULL并在结构体设计中让每个节点归单一 owner 管理避免多个地方同时持有释放权。第二块结构体“”赋值埋双重释放。 现象写代码时图省事用struct Node b *a;复制节点之后分别释放 a 和 b程序第二次 free 时直接 abort。原因默认赋值是逐位拷贝指针被简单复制两个结构体指向同一个内存块。解决需要复制节点时先malloc新节点再逐一复制字段或者显式交出所有权不让同一个内存地址有两位主顾。第三块删除链表节点时先 free 再取 next。 现象在循环里删除符合条件的所有节点结果遍历到一半段错误。原因先执行free(cur)再访问cur-next此时 cur 已经是悬空指针。解决正确的删除姿势是Node *nxt cur-next; free(cur); cur nxt;先把后驱节点地址保存下来再释放当前节点。这个顺序熟练之后应该像手背纹路一样自然。5.2 递归栈和边界条件都是考验细心的地方第四块快速排序递归爆栈。 现象给已经有序的十万个整数排几次进程直接 stack overflow。原因每次选取的都恰好是最小或最大元素递归区间重叠成一条直线递归深度退化为 n。解决pivot 改成随机选择或三数取中小规模分区转插入排序也可以显著降低递归深度。更保险的做法是手动维护一个栈把递归改成迭代式快速排序只是代码会变长。第五块二分查找死循环。 现象target 不在数组中时程序卡在某一对 mid 值来回跳或者最后返回一个错误位置。原因更新边界的公式和区间语义不匹配例如左闭右开却写了right mid - 1让某个元素永远留在查找区里形成死循环。解决固定一种区间语义把[left, right)或[left, right]写在注释里每次循环都保证区间严格缩小比如left mid 1需要推进至少一格right mid同样要把右边界向左收。写完代码后用三个用例验证目标在中间、目标在左边界、目标不存在。第六块也是通常最隐蔽的数组下标越界改写了相邻变量。 现象程序本身不崩溃但某个指针变量莫名变成非空导致后面 if 分支走了完全错误的路。原因C 不会自动检查数组越界越界写入可能砸到栈上相邻变量的内存。解决调试时用地址和print把越界位置附近的内存画出来开发阶段开启编译器的地址消毒选项比如-fsanitizeaddress能直接告诉你越界发生在哪一行代码。这是最值得提前掌握的排查手段比一上来盯代码逻辑高效得多。6. 用断言、地址观察和回归测试把数据结构练成高置信度实现6.1 给每个结构设计一个最小回归脚本数据结构最怕“看着对跑起来错”。我给自己定的习惯是每实现一个结构立刻配套一个test_xxx.c把插入、删除、遍历、释放全部串起来用断言验证不变量。比如链表反转后从前往后遍历应该从 0 到 9#include assert.h void test_list_reverse(void) { Node *head NULL; for (int i 0; i 10; i) { head list_push(head, i); } head list_reverse(head); int expect 0; while (head) { assert(head-val expect); Node *tmp head; head head-next; free(tmp); } assert(expect 10); }逻辑说明assert在发布版本里会被 NDEBUG 宏关闭所以这份测试文件要单独编译运行不能拿-DNDEBUG去砍掉它。编译时用gcc -Wall -g test_list.c -o test_list再打开地址消毒选项就能同时检查逻辑和内存问题。参数说明测试函数的粒度尽量小一次只测一种行为比如“插入后数量对不对”“反转后顺序对不对”“删除后链表长度对不对”。我在每个测试文件最后放一个main函数按顺序调用各个测试块任何一条断言失败都能精确定位到子函数里对应的测试用例。6.2 观察地址与 watchpoint 来自问“指针去哪里了”另一件做过就回不去的事用调试器观察指针变化。malloc一个节点后打印它的地址free 之后再打印同一个地址并尝试读取它的内存内容。你会发现 free 后内存里的数据可能还在但下一次 malloc 会可能立刻复用这块地址原本的值被覆盖。把地址当作追踪线索很多 bug 会在你看清“指针谁持有、内存归谁管”之后自动暴露。我最初的坏习惯是每次写完链表就凭直觉以为自己懂了实际上翻了车才回头查地址。后来改成每读一个教程章节就把它配套的代码手动敲一遍编译、运行、看地址变化再做一次这个最小回归测试。这套流程走下来数据结构知识点不再是名词而是可验证的工程行为。希望这篇文章能在你动手练习时少一点方向上的摇摆真正把C语言的指针和内存掌控感练成自己的底气。本文还有配套的精品资源点击获取
简介C语言数据结构与算法学习资料包面向计算机专业初学者及希望巩固基础的开发者系统覆盖数据结构核心概念与典型算法实现。压缩包内共558个文件以C源码、Dev-C工程文件、可执行程序及编译输出为主配套说明文档内容涉及图与树的存储结构、查找表、线性表、字符串、栈和队列、数组与广义表以及插入、交换、选择等多类内部排序和外部排序算法。包体约12.92MB文件组织清晰便于按专题查阅和动手实验。目前已有1977人学习下载。通过阅读源码、运行示例并观察输出可直观理解各类数据结构的存储机制与算法执行流程掌握从理论到C语言编码的转换方法从顺序存储到链式存储从递归思想到迭代优化均可在源码中找到对应实现对课程学习、考研复习或项目实践均有较高参考价值。1. 用C语言啃数据结构与算法看似过气实则是把内存和指针练成直觉的唯一路径很多人看到《C语言数据结构与算法》这类资料的第一反应是“都什么时代了还在用C刷题”。但当你真的去排查线上崩溃、去读开源基础组件的源码、去做嵌入式或通信类项目时会发现最底层的东西全在用指针操作内存。C语言版的线性表、树、图并不高深它逼着你自己处理节点分配、释放和边界判断走完这一遍之后再回去看其他语言里的“语法糖”你会清楚地知道那个糖底下包的是什么。它能解决的问题很具体笔试里的链表反转只是最表层真正的收获是建立“从地址和生命周期去推演程序行为”的习惯。适合准备机试、刚入行想补底层能力、以及上了一阵网课却还没完整写过关键代码的人。这篇笔记不贴大段理论直接把我做过的实现思路、参数选择和踩过的坑按章节摆出来。2. 从数组到链表C语言数据结构里的两种物理布局连CPU缓存都在替选择投票2.1 数组随机访问O(1)的代价是连续空间的维护成本在C语言里“数据结构”在底层总是一段地址和长度的推算。数组是最朴素的一种一段连续内存通过下标就能算地址。语言层面int a[10]定义后a[i]等价于a i所以随机访问的时间复杂度是 O(1)。这个 O(1) 不只是数学上的常数它意味着 CPU 可以直接用基址加偏移的方式取数据对缓存也很友好这次读入的相邻数据下次可能还在高速缓存里。但连续空间是有代价的。数组中间插入一个元素必须把它后面的元素依次往右挪动删除一个元素又得整体往左挪。我在做顺序表习题时最常见的翻车点是在函数里memmove一整片数据却忘了处理扩容或者外面继续用旧指针访问。下面是动态数组插入的常用写法关键在于调用方要同步更新长度和容量#include stdio.h #include stdlib.h // 在动态数组 arr 的 pos 位置插入 val // len/cap 都传指针函数里改动外部能感知 int insert_arr(int **arr, int *len, int *cap, int pos, int val) { if (pos 0 || pos *len) return -1; // 非法位置拦截 if (*len *cap) { // 已满则扩容 int new_cap (*cap 0) ? 4 : (*cap * 2); // 空表从4起步之后翻倍 int *tmp (int *)realloc(*arr, new_cap * sizeof(int)); if (tmp NULL) return -1; // 失败时原内存仍有效 *arr tmp; *cap new_cap; } for (int i *len; i pos; i--) { (*arr)[i] (*arr)[i - 1]; // 从尾部开始挪避免覆盖 } (*arr)[pos] val; (*len); return 0; }逻辑说明这个函数把扩容和插入放在一起调用方只需要关心数组指针、当前长度和容量。arr使用二级指针是因为realloc可能让堆内存搬家原来的首地址失效如果不把新地址传出去下一次操作就是对已释放地址的写操作。pos *len的边界允许尾插但拒绝在中间留下空洞。参数说明len是已使用的元素个数cap是已分配的元素容量两者语义容易混淆。扩容策略用倍数而不是固定加长是因为每次扩容需要 O(n) 的拷贝翻倍以后均摊成本降到 O(1)。如果你在嵌入式环境里不能接受这种突发的内存搬运可以考虑提前分配一个足够大的cap或者改用手写环形缓冲。数组删除的边界条件同样值得注意删除位置必须在[0, len)之间然后从前往后覆盖最后len--。容量不会立即缩水这一点是有意为之避免反复插入删除时频繁触发分配。调试时多用printf(%p\n, *arr)看首地址扩容前后地址变化会非常直观如果某个指针还是旧地址那它已经悬空了。2.2 链表头插法、反转与“先保存next”的铁律链表针对数组的连续内存短板而生。每个节点单独分配通过next指针串在一起。从逻辑上说在链表中插入和删除只要改相邻指针像 O(1)但实际要先遍历到目标位置且节点在堆里的地址离散CPU 缓存预取基本失效。所以在工程代码里大量随机访问场景数组几乎总赢链表更常见于“不知道总量、头尾反复增删”的地方。在 C 里写链表第一节课就是头插法。下面这两个函数是我每次练习都要默写一遍的typedef struct Node { int val; struct Node *next; } Node; // 头插法返回新头返回值必须接住 Node *list_push(Node *head, int val) { Node *n (Node *)malloc(sizeof(Node)); if (n NULL) return head; n-val val; n-next head; return n; } // 反转链表三个指针轮转 Node *list_reverse(Node *head) { Node *pre NULL; Node *cur head; while (cur) { Node *nxt cur-next; // 先保存后驱 cur-next pre; pre cur; cur nxt; } return pre; }逻辑说明list_push返回新节点作为新头如果调用方只写list_push(head, 1)而不接返回值新节点就变成孤儿。反转函数里nxt是绝对关键先保存cur-next再修改cur-next指向pre很多初学实现把这一步顺序写反导致链表断成两截。参数说明pre初始化为NULL它最终会成为新链表的尾结点反转完成后也是新头。cur是当前要处理的节点nxt是它在原链表里的下一站。循环结束条件是cur NULL此时pre正好指向原链表的最后一个节点也就是反转后的头。练习时我建议每次push后打印节点地址会看到堆地址毫无规律和数组的连续地址形成强烈对比。链表和数组的选择在实际中要看访问模式特性数组单链表随机访问O(1)O(n)头部插入需要移动全部元素O(1)中间插入需要移动后续元素需要先遍历到前驱空间连续性一块连续区域碎片化缓存命中率高低这张表不是劝你放弃链表而是提醒你算法题里的链表操作练的是指针逻辑但在生产环境里连续内存和缓存友好常常比理论复杂度更重要。理解了这一点再回头看“数组和链表哪个好”这个问题就有了自己的答案。3. 排序与查找把C语言算法的复杂度从理论变成可观测的差距3.1 手写快速排序三个参数决定递归边界与最坏表现排序是最容易体现“同一份代码不同写法差几倍时间”的内容。快速排序的平均复杂度是 O(n log n)但它不是银弹当分区极端不平衡时复杂度退化为 O(n²)。C语言版快排的教科书实现很多我常用下面这种写法它把所有边界条件统一成“左闭右闭区间”。static void swap_ints(int *a, int *b) { int t *a; *a *b; *b t; } void quick_sort(int a[], int left, int right) { if (left right) return; int i left, j right; int pivot a[left (right - left) / 2]; // 中间值避开溢出 while (i j) { while (a[i] pivot) i; while (a[j] pivot) j--; if (i j) { swap_ints(a[i], a[j]); i; j--; } } // 此时 left j i right quick_sort(a, left, j); quick_sort(a, i, right); }逻辑说明循环结束后j 会在 i 的左边数组被分成[left, j]和[i, right]两个互不重叠的区间然后递归排序。pivot 本身不单独保留在某个固定位置它可能随着交换被放到左侧或右侧所以递归时不需要跳过某个“pivot下标”。这种写法的交换次数比另一种经典的 Lomuto 分区更少但边界不好理解我习惯把区间语义直接写在注释里。参数说明mid left (right - left) / 2而不是(left right) / 2是为了防止两个大整数相加溢出。在 32 位 int 下标场景下这是真实存在的风险。while (a[i] pivot)使用严格小于跳过等于 pivot 的元素避免两个相等元素无限交换加上外层while (i j)等于 pivot 的元素会被渐渐分到两侧递归区间仍然有效。快速排序最怕每次选到区间最小或最大元素作 pivot那样递归深度变成 O(n)在十万级随机数据上就可能栈溢出。应对办法有随机选 pivot、三数取中以及小分区转用插入排序。我在练习里通常先用固定种子生成一万个随机数排序再故意用已排序数组测试观察它是否会退化成“慢得离谱”。如果测试机开了调试内存检查这种退化往往会先表现为栈溢出而不是结果错误因为递归压栈先消耗完栈空间。3.2 二分查找左闭右开约定为何能少写一堆offset二分查找代码很短但越短越容易把边界写错。大多数人翻车在区间开闭约定不统一导致死循环或漏解。我推荐一种约定左闭右开下标right是查找范围的后边界不包含在当前范围内。int binary_search(int a[], int n, int target) { int left 0, right n; // 搜索区间为 [left, right) while (left right) { int mid left (right - left) / 2; if (a[mid] target) return mid; else if (a[mid] target) left mid 1; else right mid; } return -1; }逻辑说明左闭右开最大的好处是让right永远指向“不是目标”或“待检查边界”的位置不会取到最后一个元素的下一位。当a[mid] target说明左侧一半全部小于目标左边界可以安全推进到mid 1当a[mid] target右边界收缩到mid仍保持“右开”。这样循环区间始终合法不会出现left right后的死循环。这个约定还能直接扩展成查找第一个不小于目标的“下界”函数。只要把返回-1的地方改成返回left并调整比较分支就能得到类似标准库lower_bound的行为。我经常在一个程序里同时写两种查找共用同一个区间语义避免记忆混乱。如果你不适应左闭右开也可以坚持左闭右闭[left, right]但更新必须写成left mid 1和right mid - 1。两种风格都能工作最怕的是这种代码里混用左边用闭区间、右边用开区间最后必然出现哨兵位置偏移。我的习惯是把“左闭右开”写进注释然后所有相关函数都照这个语义写。3.3 哈希查找从装载因子里读出冲突链的退化边界哈希表在C语言里不是库函数而是一个需要自己维护的“数组 链表”复合结构。它的理想复杂度是 O(1)但冲突会让单次查找退化成链表的 O(n)。工程上决定退化程度的核心参数是装载因子也就是表中已有元素数量与环境容量的比值。#define TABLE_SIZE 128 typedef struct HashNode { int key; int val; struct HashNode *next; } HashNode; HashNode *hash_table[TABLE_SIZE]; // 取模哈希把负数先转成无符号再计算 static unsigned hash_idx(int key) { return ((unsigned)key) % TABLE_SIZE; } // 查找先定位桶再沿冲突链遍历 HashNode *hash_find(int key) { unsigned idx hash_idx(key); for (HashNode *p hash_table[idx]; p ! NULL; p p-next) { if (p-key key) return p; } return NULL; }逻辑说明hash_idx用取模映射TABLE_SIZE是固定环境容量。这里把key转换成unsigned再取模避免负数产生负下标。hash_find先计算桶号再从桶头开始遍历冲突链逐个比较 key。查找成功时返回节点指针失败返回NULL调用方需要自行区分。参数说明装载因子 元素总数 /TABLE_SIZE。当元素数接近容量时冲突链变长查找时间不再是常数级。常见的做法是设置一个阈值比如 0.7超过后重新申请更大的表并全部重新哈希。扩容不是简单的复制因为每个元素的桶号会随容量变化必须重算一次。插入时同样先查链中是否已有同 key有则更新没有则头插到桶链表。头插比尾插快但对链表的顺序不敏感哈希表也不需要稳定顺序。我刚开始写哈希时总是默认取模就够了。后来拿真实键值跑一遍发现如果TABLE_SIZE是合数比如 128某些连续偶数 key 会全部挤在一半桶里装载因子虽然只有 0.5但冲突链已经很长。把容量换成素数或采用更分散的混合哈希这个问题会明显缓解。所以哈希表不只是写一个查找函数容量选值和阈值控制同样决定最终效果。4. 树与图用递归指针模拟关系型结构的最小模板4.1 二叉搜索树的插入、查找与“递归返回新根”写法树在C语言里就是“一堆指针互相引用”。二叉搜索树要求左子树所有 key 小于根右子树所有 key 大于根。每次查找都从根出发根据比较结果选择左或右理想情况下能把搜索范围折半。它的递归操作特别适合作为C语言指针训练的第二课。typedef struct BSTNode { int key; struct BSTNode *left; struct BSTNode *right; } BSTNode; // 插入key递归返回新根 BSTNode *bst_insert(BSTNode *root, int key) { if (root NULL) { BSTNode *n (BSTNode *)malloc(sizeof(BSTNode)); if (n NULL) return NULL; n-key key; n-left n-right NULL; return n; } if (key root-key) { root-left bst_insert(root-left, key); } else if (key root-key) { root-right bst_insert(root-right, key); } return root; } // 查找key写成迭代省递归栈 BSTNode *bst_find(BSTNode *root, int key) { while (root) { if (key root-key) return root; else if (key root-key) root root-left; else root root-right; } return NULL; }逻辑说明bst_insert的核心是“递归返回新根”。当递归到空位置时创建节点并返回上层调用会把它赋值到root-left或root-right。如果不接收返回值新节点就挂在半空整棵树丢失。查找没有修改结构所以用迭代循环更省栈。两段代码都遵循同一个方向规则小走左大走右。参数说明root在插入函数里传递的是局部指针值真正的树节点地址靠返回值一层层传回。对 NULL 的检查放在最前面作为递归出口。如果malloc失败返回 NULL 会让上层把它当成新节点这是练习代码里的隐患工程级代码应该使用独立的错误码或全局错误标记而不只是返回 NULL。遍历是树结构最直观的验证方式。中序遍历可以按 key 顺序输出全部节点代码很简短递归左子树、打印当前节点、递归右子树。前序和后序只是调整打印位置。学习二叉树最容易替换的一个经验是用gdb或printf打印root地址和key观察递归调用时地址如何层层深入又回溯比单纯看抽象演示更能建立递归记忆。删除是二叉搜索树中最难的部分。删除单分支节点只需把孩子挂上去删除双分支节点时需要用右子树中的最小值节点替换当前节点再递归删除那个最小节点。每次做这道题我都会提醒自己替换不是搬地址而是交换或者覆盖 key 值否则会留下悬空指针。4.2 图的邻接表从初始化到BFS的最小模板图在 C 语言里通常有两种表示邻接矩阵和邻接表。邻接矩阵代码简单适合稠密图但空间 O(n²) 在顶点较多时扛不住邻接表适合稀疏图本质是“每个顶点拉一条链表”。工程里大量场景是稀疏关系所以邻接表更常用。typedef struct AdjNode { int v; struct AdjNode *next; } AdjNode; typedef struct Graph { int n; AdjNode **adj; } Graph; Graph *graph_create(int n) { Graph *g (Graph *)malloc(sizeof(Graph)); g-n n; // calloc 会清空指针数组避免野指针头节点 g-adj (AdjNode **)calloc(n, sizeof(AdjNode *)); return g; } // 在 u 的邻接表头部插入 v有向图的单向边 void graph_add_edge(Graph *g, int u, int v) { AdjNode *node (AdjNode *)malloc(sizeof(AdjNode)); node-v v; node-next g-adj[u]; g-adj[u] node; }逻辑说明adj是一个指针数组数组下标对应顶点编号数组元素是链表的头指针。calloc会把所有头指针初始化为NULL这一步不能省。graph_add_edge使用头插法不需要遍历链表尾部因此插入是 O(1)。如果要表示无向图就对u和v各调用一次。参数说明n是顶点数量adj数组长度固定为n所以初始化时必须把顶点数传进来。头插法的缺点是遍历边的顺序和输入顺序相反如果需要按序输出可以在函数里改成尾插。由于每个邻接表的节点都是独立malloc的销毁图时需要遍历每个链表并逐个释放这比数组要麻烦得多也更容易泄漏。BFS 需要队列。C 标准库没有现成队列一个简单的办法是开一个n大小的数组当循环队列因为 BFS 中每个顶点最多入队一次队列长度不会超过顶点数void bfs(Graph *g, int start) { if (start 0 || start g-n) return; int *visited (int *)calloc(g-n, sizeof(int)); int *queue (int *)malloc(g-n * sizeof(int)); int head 0, tail 0; queue[tail] start; visited[start] 1; while (head tail) { int u queue[head]; for (AdjNode *p g-adj[u]; p ! NULL; p p-next) { int v p-v; if (!visited[v]) { visited[v] 1; queue[tail] v; } } } free(visited); free(queue); }逻辑说明visited数组防止环导致无限循环。每个节点入队前先标记即使它已经在队里也不会重复入队。队列采用线性数组模拟tail往增长head往前消费BFS 结束条件是队列为空。参数说明start是起点顶点编号必须小于g-n否则越界。打印节点时我习惯在弹出u后加一条printf而不是在入队时打印这样输出顺序才符合“层序”的概念。需要路径信息时还要加一个parent数组记录每个节点是从哪个节点过来的最后从终点回溯路径。5. C语言数据结构避坑实录释放、边界和递归里的翻车现场5.1 内存释放、浅拷贝和删节点的高频事故第一块free 之后立刻读指针。 现象释放一个链表节点后过一会儿读它的 val 还是原值但程序在某次 malloc 后会崩溃。原因free 只把内存归还给分配器不会清除内容也没有让指针失效这成了悬空指针。解决释放后立即把指针置为 NULL并在结构体设计中让每个节点归单一 owner 管理避免多个地方同时持有释放权。第二块结构体“”赋值埋双重释放。 现象写代码时图省事用struct Node b *a;复制节点之后分别释放 a 和 b程序第二次 free 时直接 abort。原因默认赋值是逐位拷贝指针被简单复制两个结构体指向同一个内存块。解决需要复制节点时先malloc新节点再逐一复制字段或者显式交出所有权不让同一个内存地址有两位主顾。第三块删除链表节点时先 free 再取 next。 现象在循环里删除符合条件的所有节点结果遍历到一半段错误。原因先执行free(cur)再访问cur-next此时 cur 已经是悬空指针。解决正确的删除姿势是Node *nxt cur-next; free(cur); cur nxt;先把后驱节点地址保存下来再释放当前节点。这个顺序熟练之后应该像手背纹路一样自然。5.2 递归栈和边界条件都是考验细心的地方第四块快速排序递归爆栈。 现象给已经有序的十万个整数排几次进程直接 stack overflow。原因每次选取的都恰好是最小或最大元素递归区间重叠成一条直线递归深度退化为 n。解决pivot 改成随机选择或三数取中小规模分区转插入排序也可以显著降低递归深度。更保险的做法是手动维护一个栈把递归改成迭代式快速排序只是代码会变长。第五块二分查找死循环。 现象target 不在数组中时程序卡在某一对 mid 值来回跳或者最后返回一个错误位置。原因更新边界的公式和区间语义不匹配例如左闭右开却写了right mid - 1让某个元素永远留在查找区里形成死循环。解决固定一种区间语义把[left, right)或[left, right]写在注释里每次循环都保证区间严格缩小比如left mid 1需要推进至少一格right mid同样要把右边界向左收。写完代码后用三个用例验证目标在中间、目标在左边界、目标不存在。第六块也是通常最隐蔽的数组下标越界改写了相邻变量。 现象程序本身不崩溃但某个指针变量莫名变成非空导致后面 if 分支走了完全错误的路。原因C 不会自动检查数组越界越界写入可能砸到栈上相邻变量的内存。解决调试时用地址和print把越界位置附近的内存画出来开发阶段开启编译器的地址消毒选项比如-fsanitizeaddress能直接告诉你越界发生在哪一行代码。这是最值得提前掌握的排查手段比一上来盯代码逻辑高效得多。6. 用断言、地址观察和回归测试把数据结构练成高置信度实现6.1 给每个结构设计一个最小回归脚本数据结构最怕“看着对跑起来错”。我给自己定的习惯是每实现一个结构立刻配套一个test_xxx.c把插入、删除、遍历、释放全部串起来用断言验证不变量。比如链表反转后从前往后遍历应该从 0 到 9#include assert.h void test_list_reverse(void) { Node *head NULL; for (int i 0; i 10; i) { head list_push(head, i); } head list_reverse(head); int expect 0; while (head) { assert(head-val expect); Node *tmp head; head head-next; free(tmp); } assert(expect 10); }逻辑说明assert在发布版本里会被 NDEBUG 宏关闭所以这份测试文件要单独编译运行不能拿-DNDEBUG去砍掉它。编译时用gcc -Wall -g test_list.c -o test_list再打开地址消毒选项就能同时检查逻辑和内存问题。参数说明测试函数的粒度尽量小一次只测一种行为比如“插入后数量对不对”“反转后顺序对不对”“删除后链表长度对不对”。我在每个测试文件最后放一个main函数按顺序调用各个测试块任何一条断言失败都能精确定位到子函数里对应的测试用例。6.2 观察地址与 watchpoint 来自问“指针去哪里了”另一件做过就回不去的事用调试器观察指针变化。malloc一个节点后打印它的地址free 之后再打印同一个地址并尝试读取它的内存内容。你会发现 free 后内存里的数据可能还在但下一次 malloc 会可能立刻复用这块地址原本的值被覆盖。把地址当作追踪线索很多 bug 会在你看清“指针谁持有、内存归谁管”之后自动暴露。我最初的坏习惯是每次写完链表就凭直觉以为自己懂了实际上翻了车才回头查地址。后来改成每读一个教程章节就把它配套的代码手动敲一遍编译、运行、看地址变化再做一次这个最小回归测试。这套流程走下来数据结构知识点不再是名词而是可验证的工程行为。希望这篇文章能在你动手练习时少一点方向上的摇摆真正把C语言的指针和内存掌控感练成自己的底气。本文还有配套的精品资源点击获取
