进阶阶段 — Unit 2: C Essentials（数据结构与算法核心训练）
"Programs = Data Structures + Algorithms." — Niklaus Wirth（Pascal 之父，图灵奖得主）
课程总览
| 课号 | 模块 | 题目 | 难度 | 核心知识点 |
|---|---|---|---|---|
| 25 | 字符串 | 实现 my_strstr | 易 | 滑动窗口双重循环、i<=n-m 边界、O(n·m) 最坏退化、NUL 终止符、KMP 思想简介 |
| 26 | 内存 | 实现 my_memcpy | 易-中 | void*→char* 转换、逐字节拷贝、const 语义、size_t 类型、浅拷贝 vs 深拷贝 |
| 27 | 内存 | 实现 my_memmove | 中 | 三重叠情形、正向级联污染、反向拷贝证明、三分支方向判断、memcpy vs memmove |
| 28 | 回溯 | 全排列问题 | 中 | 回溯三步(swap→递归→swap back)、排列树 n! 叶、去重剪枝、O(n·n!) 下界 |
| 29 | 回溯 | 八皇后问题 | 难 | 一维棋盘约简、对角线公式 |
| 30 | 链表 | 单链表插入 | 易-中 | 头插 O(1) 反序 vs 尾插 O(n) 保序、空表边界、C 值传递返回 head、哨兵节点 |
| 31 | 链表 | 单链表查找与删除 | 中 | prev 滞后一步、删除五情形(头/中/尾/独/未找到)、free 顺序、双向链表 O(1) |
| 32 | 链表 | 链表反转与环检测 | 中-难 【面试高频】 | 三指针反转、Floyd 快慢指针、环入口定位证明、快慢针延伸(中点/倒数第 k/回文) |
| 33 | 链表 | 循环链表与约瑟夫 | 中-难 | 自环最小合法态、do-while 遍历、数据结构选型对比、约瑟夫 O(N) 递推 |
| 34 | 栈 | 括号匹配 | 易-中 | LIFO=最近配对、三种失败模式、数组栈 top=-1、HTML/XML 推广、O(n) 分析 |
| 35 | 队列 | 环形队列基础 | 易-中 | FIFO 语义、假溢出→取模回绕、"先放后推"顺序、牺牲一槽区分空满、Linux kfifo |
| 36 | 树 | 二叉树 DFS 遍历 | 易-中 | 三种遍历仅 printf 位置不同、前+中唯一重构、非递归栈遍历、Morris O(1)、序列化 |
| 37 | 树 | 二叉树层序 BFS | 中 | BFS=队列 vs DFS=栈、队列泛化 int→node*、按层分组 rear-front、完全二叉树检测 |
| 38 | 树 | BST 增删查 | 难 | 左≤根≤右、递归插入/搜索 O(h)、删除三情形、双子右子树最小值替换、退化→AVL |
| 39 | 堆 | 堆与 Top-K | 难 | 完全二叉树↔数组映射、heapify 下滤、build_heap O(n) Σ 证明、小顶堆 Top-K 陷阱 |
| 40 | 查找 | 二分查找 | 中 | O(log n)每步减半、mid 防溢出(JDK-5045582)、lo<=hi 等号、lower_bound 变体 |
| 41 | 排序 | 快速排序 | 中-难 | Lomuto 划分、pivot 落最终位、O(n²) 最坏→随机化修复、Lomuto vs Hoare、introsort |
| 42 | 标准库 | snprintf 安全 | 易-中 | sprintf 溢出灾难谱系、ret=企图长度(核心考点)、ret>=size 截断判定、pre-sizing |
| 43 | 标准库 | strtok_r 切分 | 易-中 | 原地修改 \0 替换、delim 字符集、saveptr=线程安全、字面量段错误、CSV 局限 |
| 44 | 标准库 | qsort 泛型排序 | 中 | void*+size+cmp=C 泛型、(const char**)a 两级解引用陷阱、指针级数表 |
| 45 | 标准库 | realloc 扩容 | 中 | 致命 arr=realloc(arr,size)、安全 tmp 模式、倍增摊还 O(1)、1.5× vs 2× |
| 46 | 标准库 | sscanf 解析 | 易-中 | %[^X] 扫描集、返回值=金标准、%s vs %[^:] 差异、宽度限制防溢出、赋值抑制 |
| 47 | 机制 | setjmp/longjmp | 中 | 返回两次机制、恢复 SP/PC 空投锚点、jmp_buf 必须 global、C++ try/catch 起源 |
| 48 | I/O | I/O 缓冲性能 | 中 | syscall 量化(fgetc 20M vs fread 5K)、三种缓冲模式、setvbuf 黄金规则、fgetc int |
24 道题 × 7 大模块，从零实现数据结构到重写 C 标准库。每题采用 stdout 评测模式，平均编写约 25 行 C 代码。
一、阶段定位与目标
本阶段是 C 语言训练营的第三站，承接 Unit 1（C Fundamentals）建立的 C 语言核心语法与状态机思维，正式进入数据结构与算法的系统学习。如果说 Unit 1 是"掌握 C 语言全貌"，那么 Unit 2 就是"用 C 语言组织数据、驾驭算法"——从零实现工业级数据结构，亲手重写 C 标准库关键函数。
根据训练营总体规划，本阶段旨在解决"学员会写 C 代码但不懂数据组织与算法设计"这一核心问题。设计思路为：结构为纲，算法为目——每引入一个数据结构，立刻用经典算法将其激活。
主要目标
- 掌握经典数据结构的从零实现：单向链表、循环链表、栈、环形队列、二叉树、二叉搜索树（BST）、堆。不只是"会用"，而是"会造"——每个结构都用纯 C 语言的
struct与指针从零搭建，理解每一行代码背后的内存布局。 - 掌握经典算法的设计思想：回溯（全排列、八皇后）、分治（快速排序）、剪枝、二分查找、广度优先搜索（BFS 层序遍历）、深度优先搜索（DFS 递归遍历）、Top-K 堆筛选。理解"同一问题多种解法"的工程取舍。
- 深入 C 标准库的底层机制：从
memcpy/memmove的内存重叠处理，到snprintf的截断检测、strtok_r的线程安全、qsort的泛型比较器、realloc的安全扩容、sscanf的高级格式、setjmp/longjmp的非局部跳转、标准 I/O 缓冲性能——七个练习带你读懂 glibc 的实现哲学。 - 为后续阶段铺路：本阶段的 24 个 Lesson 覆盖了 Unit 3（CS 经典问题）所需的全部数据结构基础（堆、散列、树、图遍历），并为 Unit 4（编译器实现）中的 AST 树结构、符号表（散列表）、递归下降解析等核心技术打下根基。
授课形式
与 Unit 1（C Fundamentals，两节直播）类似，本阶段采用腾讯会议直播授课，共四节：
| 节次 | 时间 | 内容 |
|---|---|---|
| 第一节 | 2026 年 07 月 03 日 20:00 | Lesson 25-30：字符串与内存操作、递归回溯、链表入门 |
| 第二节 | 2026 年 07 月 06 日 20:00 | Lesson 31-36：链表进阶、栈与队列、二叉树遍历 |
| 第三节 | 2026 年 07 月 08 日 20:00 | Lesson 37-42：树进阶与堆、查找与排序、标准库入门 |
| 第四节 | 2026 年 07 月 10 日 20:00 | Lesson 43-48：标准库深入与工程实践 |
每节直播约 2 小时，包含数据结构图解、算法推导、代码实战、现场答疑。直播录像会回传至训练营知识库供回看。
学习依托
- 训练营维护的 clings 练习仓库（24 个 Lesson，共 24 道题）
- 每个 Lesson 配套的 README 讲义（含算法图解、内存布局分析、课堂讨论与课后练习）
- CNB 云原生开发环境（一键开箱）或本地 GCC 环境
二、主要内容与学习路径
本阶段通过 24 个递进式 Lesson，覆盖以下知识模块：
字符串与内存操作（Lesson 25-27）
Lesson 25 — 实现 my_strstr（1 道题）
- 实现暴力字符串匹配：双重循环滑动窗口。
- 掌握外层循环终止条件
i <= n - m（等号不可丢）、内层逐字符比较。 - 理解时间复杂度 (O(n \times m)) 与最坏情况（
"AAAA...A"匹配"AAB"）。
Lesson 26 — 实现 my_memcpy（1 道题）
- 实现 C 标准库
memcpy：void*转换为char*逐字节拷贝。 - 理解
void*不能做算术运算的原因、const修饰符的语义、size_t类型。 - 返回
dest而非临时指针，保持与标准库一致的接口契约。
Lesson 27 — 实现 my_memmove【重点】（1 道题）
- 实现 C 标准库
memmove：处理源与目的内存区域重叠的情况。 - 核心判断：
dest < src正向拷贝，dest > src反向拷贝，避免覆盖未读数据。 - 理解
memcpy与memmove的本质区别——这是面试高频考点。
递归与回溯（Lesson 28-29）
Lesson 28 — 全排列问题（1 道题）
- 回溯算法入门：选择 → 递归 → 撤销（swap back 恢复现场）。
- 理解"回溯三步曲"与暴力枚举的区别：回溯保证进入下一层和回到当前层时状态都正确。
- 掌握排列树的递归结构，为 Lesson 29 八皇后打基础。
Lesson 29 — 八皇后问题【标杆题】（1 道题）
- 回溯 + 剪枝的经典应用：逐行放置皇后，冲突检测提前剪枝。
- 冲突检测：同列
col[i] == c，同对角线|row - i| == |c - col[i]|。 - 理解剪枝的威力：暴力 (8^8 = 16{,}777{,}216) 种可能，回溯剪枝仅探索约 15,000 个节点，剪枝率 > 99.9%。
链表（Lesson 30-33）
Lesson 30 — 单链表插入（1 道题）
- 头插法（O(1)，结果逆序）与尾插法（O(n)，结果顺序）的实现与对比。
- 理解
malloc动态分配节点、指针链接的内存操作。
Lesson 31 — 单链表查找与删除（1 道题）
- 按值查找、按索引查找、节点删除（维护前驱指针）。
- 掌握三种删除边界：删头节点（
prev == NULL）、删尾节点（prev->next = NULL）、删唯一节点（head = NULL）。 - 理解
free与指针修改的顺序——先改指针再释放内存。
Lesson 32 — 单链表反转与环检测【高频题】（1 道题）
- 三指针反转法：
prev/curr/next逐节点翻转指向。 - 快慢指针（Floyd 龟兔赛跑）环检测：快指针走 2 步、慢指针走 1 步，有环必相遇。
- 这是面试最高频的链表题之一。
Lesson 33 — 循环链表与约瑟夫环（1 道题）
- 循环链表的插入（自环初始化）与删除（找前驱遍历）。
- 约瑟夫环算法：每轮走 K-1 步到达被淘汰者，打印并删除，直到链表为空。
- 理解循环结构"尾节点指向头"的特殊性。
栈与队列（Lesson 34-35）
Lesson 34 — 栈实现括号匹配（1 道题）
- 栈的经典应用：左括号入栈，右括号弹栈匹配。
- 掌握栈的基本操作（
push/pop/is_empty）与三种匹配失败情况。 - 理解"栈是 LIFO 后进先出"的本质——这是编译器括号检查、表达式求值的基础。
Lesson 35 — 环形队列基础（1 道题）
- 数组实现的环形队列：
front/rear双指针 + 取模运算实现环绕。 - 入队
rear = (rear + 1) % MAX，出队front = (front + 1) % MAX，队空front == rear。 - 理解取模的意义：循环复用数组空间，避免线性队列"假溢出"问题。
树与堆（Lesson 36-39）
Lesson 36 — 二叉树前中后序遍历（1 道题）
- 递归实现三种 DFS 遍历：前序（根左右）、中序（左根右）、后序（左右根）。
- 理解三种遍历只是"访问根节点"的时机不同——只差一行代码的顺序。
- 这是理解递归与树结构的入门关。
Lesson 37 — 二叉树层序遍历（1 道题）
- BFS 广度优先遍历：用队列辅助，逐层访问。
- 队列存储
struct node*（指针），出队打印后左右孩子入队。 - 对比 Lesson 36 的 DFS（递归/隐式栈）与 BFS（显式队列），理解两种搜索策略的本质差异。
Lesson 38 — 二叉搜索树操作（1 道题）
- BST 的插入、查找、删除（难点）。
- 删除三种情况：叶子节点直接删、单子树返回子树、双子树用右子树最小值替换。
- 理解 BST 的有序性：中序遍历得到有序序列。
Lesson 39 — 堆与 Top-K 问题（1 道题）
- 小顶堆的
heapify（向下调整）与build_heap（自底向上建堆）。 - Top-K 算法：用大小为 K 的小顶堆维护 K 个最大值，堆顶即门槛。
- 理解"为什么用小顶堆而非大顶堆"——堆顶是 K 个中最小的，作为筛选门槛。
查找与排序（Lesson 40-41）
Lesson 40 — 二分查找（1 道题）
- 迭代二分查找：每次将搜索范围缩小一半。
- 三个关键陷阱：
mid = lo + (hi - lo) / 2防溢出、循环条件lo <= hi带等号、更新用mid ± 1防死循环。 - 理解为什么大厂面试必考二分——边界条件是 Bug 重灾区。
Lesson 41 — 快速排序（1 道题）
- Lomuto 分区方案 + 递归快排。
partition：选arr[hi]为 pivot，i维护"小于等于区"右边界，扫描交换。- 时间复杂度：平均 (O(n \log n))，最坏 (O(n^2))，空间 (O(\log n)) 递归栈。
标准库深入（Lesson 42-48）
Lesson 42 — snprintf 格式化安全（1 道题）
snprintf的安全用法与返回值语义：返回"企图写入的字符数"。- 通过
ret >= size判断是否截断，理解为什么大厂严禁sprintf。 - 缓冲区溢出是 C 语言最常见的安全漏洞——
snprintf是防御的第一道防线。
Lesson 43 — strtok_r 线程安全切分（1 道题）
strtok_r的使用：saveptr保存切分位置上下文，首次传字符串、后续传NULL。- 理解
strtok为什么不是线程安全的（内部static变量），strtok_r如何解决。 - 掌握命令行解析的核心技术——为 shell 实现铺路。
Lesson 44 — qsort 泛型排序（1 道题）
qsort的比较器函数（comparator）：int数组与char*字符串数组。- 重点理解
char*数组排序时*(const char **)a的双重解引用——这是指针理解的试金石。 - 常见错误：写成
(const char *)a会拿到半个指针导致段错误。
Lesson 45 — realloc 动态扩容（1 道题）
realloc的安全用法：用临时变量接收返回值，成功才赋值。- 致命错误
arr = realloc(arr, new_size)：失败时返回NULL导致内存泄漏。 - 理解原地扩容
[in-place]与异地搬迁[moved]的区别，以及加倍扩容策略的均摊 (O(1))。
Lesson 46 — sscanf 高级解析（1 道题）
sscanf的高级格式%[^:]：匹配除冒号外的所有字符。- 一行解析
host:port，返回值代表成功匹配的字段数。 - 理解为什么不用正则——
sscanf零依赖，简单场景完全够用。
Lesson 47 — setjmp/longjmp 非局部跳转（1 道题）
setjmp设锚点（首次返回 0），longjmp跨函数跳回（让setjmp返回指定值）。- 理解被跳过的栈帧不会执行，C++ 的
try/catch底层就基于此机制。 - 掌握异常处理的底层原理——这是从 C 走向 C++ 的桥梁。
Lesson 48 — 标准 I/O 缓冲性能（1 道题）
- 对比逐字节拷贝（
fgetc/fputc）与缓冲拷贝（fread/fwrite）的性能差异。 - 10MB 文件：
fgetc约 1000 万次系统调用，fread(4KB)约 2500 次——快 100-1000 倍。 - 理解标准库三种缓冲模式（全缓冲、行缓冲、无缓冲）与系统调用的代价。
练习工具 — clings
- 使用训练营基于 CNB 云原生开发环境的 clings 练习仓库进行交互式练习。
- 通过 Rustlings 风格的"读报错、修代码、保存即验证"的方式逐题过关。
- 训练营会自动统计您的完成情况并记入阶段成绩。
三、推荐学习资料
以下资料可作为本阶段的主要参考：
核心教材
- 《数据结构与算法分析：C 语言描述》(Mark Allen Weiss)：本阶段最契合的教材，用 C 语言从零实现链表、栈、队列、树、堆、散列表，覆盖排序与查找算法。强烈推荐边读边做练习。
- 《算法》(Robert Sedgewick)：普林斯顿大学经典教材，算法图解清晰，C 语言实现简洁。排序、查找、图算法章节尤其出色。
- 《C 程序设计语言》(The C Programming Language, K&R)：第 5-6 章深入讲解指针与结构体，第 7 章覆盖标准 I/O 与系统接口——是 Lesson 25-27、42-48 的最佳参考。
在线教程
- Learn-C.org — Data Structures：含链表、二叉树等交互式章节。
- GeeksforGeeks — Data Structures in C：覆盖链表、栈、队列、树、堆的 C 语言实现。
- VisuAlgo：数据结构与算法可视化工具，帮助理解遍历、排序过程。
- 一站式学习 C 编程 — 宋劲杉：C 语言系统编程参考。
参考资料（进阶）
- memcpy vs memmove — StackOverflow：Lesson 27 内存重叠的经典讨论。
- Function Pointers & qsort — GeeksforGeeks：Lesson 44 比较器的深入解析。
- setjmp/longjmp — GNU C Library：Lesson 47 非局部跳转的官方文档。
- Backtracking — 八皇后问题：Lesson 29 回溯算法的经典案例。
- Floyd's Cycle Detection：Lesson 32 快慢指针环检测算法。
开发环境搭建
- 推荐使用 CNB 云原生开发环境（Fork 仓库后一键启动，无需本地配置）。
- 本地开发推荐 Linux 环境（WSL2 + Ubuntu 或虚拟机），安装 GCC 和 Python 3.11+。
- 安装 clings 练习工具：推荐使用
uvx clings@latest命令（无需全局安装，隔离运行）。
四、学习方式与建议
先读讲义，再做练习：每个 Lesson 目录下的 README.md 包含算法推导、内存布局图解、状态转移分析和课堂讨论题。建议先通读讲义，理解数据结构的内存模型后再动手修改 .c 文件。
善用 clings 工具：进入 clings 的 watch 模式后，每次保存文件会自动编译和验证。遇到卡壳时按
h查看提示，按l浏览题目列表，按t查看测试用例（TDD 开发）。动手画内存图：本阶段是指针与内存的"进阶关"。链表的指针链接、树的孩子指针、堆的数组表示——每学一个结构，务必在纸上画出节点与箭头。Lesson 27（内存重叠）、Lesson 32（链表反转）、Lesson 38（BST 删除）尤其需要画图辅助理解。
理解递归思维：Lesson 28（全排列）、Lesson 29（八皇后）、Lesson 36（树遍历）、Lesson 38（BST 操作）、Lesson 41（快排）五个练习构成了"递归五连击"。学会用"基准条件 + 递归步骤"分解问题，是后续编译器递归下降解析的核心技能。
对照标准库源码：Lesson 25-27（字符串/内存）和 Lesson 42-48（标准库）共 10 个练习都是重写 C 标准库函数。完成后建议对照 glibc 或 musl 的真实实现，体会工业级代码的边界处理与性能优化。
按时参加直播：本阶段有四节腾讯会议直播课（07/03、07/06、07/08、07/10），建议按时参加以获得最佳学习效果。直播中会现场演示数据结构的构建过程和算法的逐步推导，并解答疑问。如无法参加，请务必在课后观看回放。
五、关于晋级与要求
晋级方式
- Fork 训练营的 Unit-2-C-Essentials 仓库，在云原生开发环境或本地环境中完成 24 道练习题。
- 提交代码到 main 分支并创建合并请求（PR），CI 系统会自动评分。
- 可多次提交，以最高分为准。通过后即可在 OpenCamp 晋级榜单上查看成绩。
评分标准
- 共 24 个 Lesson、24 道题，每题通过 clings 自动评测。
- 评测模式以标准输出比对（stdout）为主，部分题目检查返回值与编译验证。
重要提示
本阶段是 C 语言训练营的进阶关，题目从 19 行代码（Lesson 26 memcpy）到 118 行代码（Lesson 31 链表操作）逐步递进。24 道题覆盖了数据结构与算法的核心骨架——链表、栈、队列、树、堆、排序、查找，外加 7 个 C 标准库函数的从零实现。每题平均编写约 25 行 C 代码，关键不是代码量，而是理解每个数据结构的内存布局与每个算法的设计思想。认真完成本阶段后，您将具备独立设计和实现中等规模数据结构的能力，为 Unit 3（CS 经典问题）和 Unit 4（编译器实现）打下坚实的算法与工程基础。
六、训练营完整学习路线
本 C 语言训练营采用 "四阶段 + 双项目" 的成长路径，从零基础入门到亲手实现编译器与操作系统内核，共 6 个 Unit，共计 120 课。最终目标：学员同时具备用 C 语言实现编译器和从裸机搭建操作系统内核的系统级编程能力，形成"语言 → 算法 → 系统 → 编译器 → 内核"的完整知识闭环。
导学阶段
| Unit | 名称 | 课程数 | 核心内容 |
|---|---|---|---|
| Unit 0 | C Primer | 5 课 / 9 题 | 最简程序、printf、循环、条件分支、累加求和 |
从"编辑 — 编译 — 运行"的全流程入手，通过 5 个最小可运行程序建立 C 语言的基本心智模型。使用 clings 工具交互式练习。
基础阶段
| Unit | 名称 | 课程数 | 核心内容 |
|---|---|---|---|
| Unit 1 | C Fundamentals | 19 课 / 40 题 | 嵌套循环、函数、数组、指针、结构体、联合体、位运算、可变参数、预处理器、状态机 |
从九九乘法表到词法分析器，涵盖 C 语言核心语法特性。通过实现 printf、命令解释器、预处理器、词法分析器等项目，将语法知识转化为工程能力。两节腾讯会议直播授课（2026/06/29 和 2026/07/01）。
进阶阶段
| Unit | 名称 | 课程数 | 核心内容 |
|---|---|---|---|
| Unit 2 | C Essentials | 24 课 / 24 题 | 链表、栈、队列、树、堆、排序、查找、回溯、C 标准库深入实现 |
系统学习经典数据结构与算法，从字符串内存操作（strstr/memcpy/memmove）到链表/栈/队列/树/堆的从零实现，再到快速排序、二分查找、Top-K 堆筛选，最终深入 snprintf/strtok_r/qsort/realloc/sscanf/setjmp/I/O 缓冲七个标准库函数的底层机制。四节腾讯会议直播授课（2026/07/03、07/06、07/08、07/10）。
专业阶段
| Unit | 名称 | 课程数 | 核心内容 |
|---|---|---|---|
| Unit 3 | C Classicals | 24 课 | 哲学家就餐、停等协议、LL(1) 解析器、B+ 树、光线追踪、A*寻路、RSA、向量时钟、缓存模拟、Aho-Corasick、NFA→DFA、测试框架、缓冲区溢出、感知机、LU 分解、无锁环形缓冲、标记清除 GC、图灵机、FFT、Sobel 边缘检测、TF-IDF、量子比特、PoW 区块链、终端计算器 |
覆盖计算机科学 17 个子领域的经典问题，每题平均编写约 96 行 C 代码，为编译器项目建立广阔的 CS 视野。
项目阶段
完成前三个阶段后，进入双线并行的项目实践：
| Unit | 名称 | 课程数 | 核心内容 |
|---|---|---|---|
| Unit 4 | C Compiler | 24 课 | 从零实现 C 编译器 nccl-cc：一棵 AST，四个后端，五个运行环境 |
| Unit 5 | C Kernel | 24 课 | 从零实现操作系统内核 Avatar OS：裸机引导到多核调度 |
Unit 4 — C Compiler 用约 4000 行 C 代码完整走通"预处理 → 词法 → 语法 → 类型标注 → 代码生成"全流程，支持 RISC-V / ARM / AArch64 / x86-64 四个后端和 Linux 用户态 + 裸机共五种运行环境。最终验证：用自己写的编译器编译约瑟夫环程序，在四个架构上得到相同结果。
Unit 5 — C Kernel 基于 Avatar OS 真实内核代码，分五个子阶段递进：裸机基础 → 内存与同步 → 中断与定时器 → 多任务 → 用户态与多核。代码取自 Avatar OS 仓库，支持 AArch64 / RISC-V 64 / x86_64 三架构在 QEMU 上验证。最终目标：一个能运行 busybox shell、在多核处理器上并行调度的完整操作系统。