简介面向考研学生的C编程训练源码包以日常题目演练为线索集中覆盖数据合并、求和、质数检测、指针操作、结构体封装等基础与进阶编程练习帮助考生通过读代码、改代码、运行程序来理解语法细节、提升解题熟练度。压缩包共23个文件其中11个cpp源码分别对应11个exe可执行程序另有1个readme说明整体仅545KB轻量易用每一道练习都配有可运行结果便于即时对照输出并排查逻辑问题。目前已有118人学习使用。除基础算法训练外还包含测试逻辑、指针与动态内存操作、结构体应用、函数与数组组合等模块能够帮助读者系统梳理C常见考点若干补充题可作为额外练习适合计算机专业及所有需要强化编程能力的考研备考生反复演练、查漏补缺。1. C考研题目日常训练源码这套代码设计到底解决什么问题考研计算机统考和自命题的机试、笔试里C的代码设计能力是硬门槛。很多人从《算法笔记》或者王道单科书出发刷题但代码写完不知道对不对或者看了解析合上书就忘核心原因是缺少一套「题目、测试数据、参考实现」三件套齐备的训练集。这套源码包做的正是这件事按专题组织日常训练题目每个题目配套可运行的C参考代码和样例数据覆盖顺序表、链表、二叉树、图遍历、排序、动态规划、字符串处理这些高频考点拿来就能直接编译运行对照输入输出验证自己的实现。适合正在准备计算机考研的在校生、跨考但有一定编程基础的同学以及想系统过一遍数据结构与算法笔试代码题的从业者。它不教语法而是把「题目长什么样、代码怎么写、边界怎么卡」一次性给到你。2. 代码设计的组织逻辑专题切片、标准输入输出与可验证性2.1 为什么按专题切片而不是按难度排序日常训练最怕的是每天随便抓一道题做做完不知道覆盖了哪些考点。这套源码包的做法是把题目按数据结构与算法专题分组每一组内部再按从易到难的顺序排列。比如线性表这一组先做顺序表的基本操作再做链表的反转和合并最后做循环链表的约瑟夫问题这种梯度设计的好处是你做题时有明确的「最近发展区」写完一题回头看前一题能明显感觉到复杂度在提升。我一般会建议训练时按「线性表 → 栈和队列 → 二叉树 → 图 → 排序 → 动态规划」的顺序推进不要跳着刷。因为很多图的代码需要栈和队列做铺垫而动态规划的题目又经常要配合排序预处理。每组题目在源码包里是一个独立目录目录内是题目描述、输入输出样例和参考代码三个文件。题目描述部分会写明数据范围这个信息很关键直接决定了你要用什么复杂度的算法——比如数据量到 10^5 时 O(n^2) 的冒泡排序基本就没戏了必须换 O(n log n) 的归并或快排。2.2 输入输出约定的重要性为什么全部采用标准输入输出很多考研机试是黑盒评测程序从标准输入读数据把结果打印到标准输出评测系统比对输出文件。这套源码包的所有题目都严格按这个约定设计参考代码里不使用文件读写不用全局变量传递数据不依赖任何第三方库。这样做的原因是让你从一开始就养成「面向评测」的编码习惯——你在本地跑的代码提交到任何 OJ 平台上都不需要改。举个例子一个二叉树层序遍历的题目输入格式是间隔符分隔的节点序列输出是按层打印。如果参考代码里用了 Windows 特有的system(pause)或者conio.h在 Linux 评测机上就编译不过。这套源码包里全部用纯标准库写法iostream、vector、queue、algorithm、cstring这些头文件覆盖所有题目你在 Visual Studio、Dev-C、VSCode 配的 GCC 环境下都能直接编译。2.3 本地运行的三个关键命令编译、重定向、对比输出拿到源码包后第一步是在本地把参考代码跑起来。我以 VSCode 配 GCC 为例进入某个题目目录后先编译g -stdc11 -Wall -O2 -o solution solution.cpp这里-stdc11指定 C11 标准考研机试环境里 C11 是最保险的版本C14 和 C17 的特性不一定被所有评测机支持-Wall显示所有警告能在训练阶段帮你抓出未初始化变量这类隐患-O2开优化题目里的 O(n log n) 算法在不优化的条件下可能跑出 O(n^2) 的效果会误导你对算法效率的判断。编译成功后用重定向方式喂测试数据./solution input.txt output.txt把input.txt的内容作为标准输入流送入程序把程序的标准输出写入output.txt这样你不用手动敲输入也能批量验证。验证完当前测试点后对比输出和预期结果diff -w output.txt expected.txt-w参数忽略所有空白字符差异因为 OJ 比对输出时通常忽略行尾空格和空行但不会忽略中间的多余空格。训练时如果能过 diff说明这组样例没问题过不了就要对照着定位是算法逻辑错了还是格式输出错了——这两个错误处理方式完全不同。2.4 题目与代码的配套粒度每题独立、状态共享这套源码包里每个题目都带一个main.cpp不会出现一个文件同时包含多道题的情况。我拆过不少网上流传的代码包最常见的问题是一个cpp文件里堆了十几道题的函数注释混乱想跑第二题还得把第一题的 main 函数注释掉。这套包每题独立目录结构是topic-name/input.txt、topic-name/expected.txt、topic-name/solution.cpp你复制任何一个目录到本地都能单独编译运行。训练时我建议你不要直接打开参考代码而是先看题目描述自己写写不出来或者样例跑不过的时候再去看源码。看完源码之后把文件关掉自己重新写一遍这个过程比量变刷题重要得多。源码包里所有代码都写了核心注释但不是逐行注释——逐行注释会让人产生「看懂了」的错觉实际上只是读懂了英文单词。关键步骤注释就够了比如「此处必须用双指针否则 O(n^2) 超时」「边界条件链表为空时直接返回 head」。3. 核心题型的C实现套路从线性表到动态规划的参数与边界3.1 顺序表删除重复元素的原地算法与参数陷阱顺序表题目里出镜率最高的是删除有序数组中的重复元素要求原地修改数组返回新长度。这道题是考研 408 的常客很多人在笔试时写得出思路上机就翻车在返回值和新长度的关系上。参考代码用的是快慢双指针慢指针指向新数组的末尾位置快指针遍历整个数组int removeDuplicates(vectorint nums) { if (nums.size() 2) return nums.size(); // 空数组或单元素直接返回 int slow 1; // 慢指针新数组下一个可写入位置 for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow - 1]) { // 只有遇到新元素才进位 nums[slow] nums[fast]; } } return slow; // slow 就是去重后的长度 }这段代码有两个参数位置值得注意。第一个是if (nums.size() 2)很多人写成 1也能跑对但逻辑不直观——size()返回的是size_t无符号类型和字面量 1 比较没问题但如果写nums.size() - 1 1就有隐患无符号整数减法会向上溢出变成超大值。第二个是slow和fast都从 1 开始而不是从 0 开始因为数组有序第 0 个元素一定保留从第 1 个位置开始比较可以少一次没必要的判断。做完这道题你可以顺手验证一下边界数组全是相同元素时fast每次比较都不相等slow始终是 1最后返回 1数组被压缩成只有一个元素——这个结果符合预期。数组本身没有重复元素时fast每步都在写入slow最后等于原长度代码不会越界因为slow - 1最大不超过fast - 1而fast到不了nums.size()。3.2 单链表递归反转与迭代反转的取舍链表反转题在机试里出现频率极高主要原因是代码量短但指针操作容易晕。理解迭代反转的核心是维护三个指针prev指向前一个节点cur指向当前节点next临时保存下一个节点。每次循环把cur-next指向prev然后三个指针整体后移。参考代码实现如下ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; // 前驱指针初始为空 ListNode* cur head; while (cur) { ListNode* next cur-next; // 先保存后继否则断链后无法前进 cur-next prev; // 反转当前节点的指向 prev cur; // 前驱前进 cur next; // 当前节点前进 } return prev; // 循环结束后 prev 指向原链表的尾节点即新链表头 }这里的核心坑是ListNode* next cur-next;必须先执行。如果先改cur-next再取next取到的就是已经反转后的prev节点链表当场断掉。我训练时见过不少人在这个顺序上翻车调试半天找不到原因最后发现是取了被覆盖的指针。递归版代码更短但性能和可读性都有代价。递归栈深度等于链表长度链表长度到 10^5 时可能栈溢出而机试题目数据范围写到 10^5 很常见所以建议以迭代版为主。如果题目明确要求递归实现那另说——考试时看清题面再决定。3.3 二叉树层序遍历的队列参数与空节点处理层序遍历要求按层输出节点值核心工具是队列。参考代码里有一个容易被忽略的参数——空节点nullptr是否入队。如果题目要求输出完整二叉树的层序结构空节点也要入队来占位如果只要求输出非空节点值序列空节点就不入队。这两者代码不同vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; queueTreeNode* q; if (root) q.push(root); // 空树直接返回空结果 while (!q.empty()) { int levelSize q.size(); // 关键参数当前层的节点数 vectorint level; for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); // 空节点不入队 if (node-right) q.push(node-right); } result.push_back(level); } return result; }int levelSize q.size();这行必须在循环外先取到在循环内q.size()的值会随push和pop动态变化直接写i q.size()会让循环多跑甚至跑成死循环。队列里可能同时存在两层节点拿到当前层的初始大小才能保证这一层只弹出levelSize个节点。考研机试里的层序题基本都要按层输出二维数组所以levelSize这个参数是必写的。3.4 动态规划最长递增子序列的两个版本怎么选动态规划题里最长递增子序列LIS是很好的分水岭题目能看出你是在背模板还是真的理解状态转移。O(n^2) 版本是基础定义dp[i]表示以第 i 个元素结尾的最长递增子序列长度转移方程是从所有j i且nums[j] nums[i]的位置取最大值加一int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint dp(n, 1); // 每个元素自身构成长度为 1 的子序列 int ans 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) dp[i] max(dp[i], dp[j] 1); } ans max(ans, dp[i]); // 最终答案是所有 dp[i] 的最大值 } return ans; }这个版本能过数据范围 n 1000 的题目但 n 到 10^5 就会超时。机试里数据范围常常写到 10^5所以要同时掌握二分优化的贪心版本维护一个tails数组tails[i]表示长度为 i1 的递增子序列的末尾元素最小值对每个数字用二分查找定位它能接在哪个位置的尾部后面。两个版本本质上是同一种问题的不同复杂度维度训练时应该都写一遍——只背 O(n^2) 版本遇到大数据就会原地卡死。另一个容易错的地方是初始化。dp数组初始化为 1 是对的因为任意一个元素单独都能构成长度为 1 的递增子序列。但有人会把长度 0 的子序列也纳入考虑认为dp[i]初始为 0这在本题里会导致答案少 1。区分标准是题目定义「空序列」算不算子序列考研题目里通常不把空序列计入所以初始化为 1 才是正确答案。4. 训练中的常见问题排查编译、性能和边界条件4.1 头文件包含的玄学为什么代码在你的机器上编译不过现象参考代码在源码包里能编译复制到自己电脑上用 Dev-C 5.11 打开就报vector does not name a type。原因Dev-C 5.11 自带的 GCC 版本太低默认没有启用 C11 语法而源码包里的代码大量使用vectorint、auto和范围 for 循环这些都是 C11 才有的特性。解决编译命令里显式加上-stdc11或者在 Dev-C 的「工具 → 编译选项 → 编译器」里加入-stdc11到编译命令中。如果你用 VSCode在tasks.json的args数组里加上-stdc11。我默认所有训练代码都按 C11 标准写不会用 C14 的make_unique或 C17 的if constexpr就是怕你本地环境不支持。4.2 运行超时的真正原因不是循环太慢而是循环做多了无用功现象一个看起来只有一层 for 循环的题目数据量 10^5本地跑样例秒出提交到 OJ 却超时。原因一层 for 循环内部如果调用了vector::eraseerase的时间复杂度是 O(n)因为后续元素要前移整体就变成了 O(n^2)。很多人在分析复杂度时只看循环层数不看循环内操作的实际代价。解决训练时遇到超时先用小数据量测正确性再用大数据量测时间。如果确定是erase导致的问题改成双指针原地覆盖或者用remove_if先标记后统一删除。这套源码包的参考代码里凡是有erase的地方都做了说明就是为了避免你抄到这种隐性 O(n^2) 写法。4.3 输出格式的边角问题多一个空格和少一个换行都判错现象diff 对比时-w参数忽略空白后一致但 OJ 上就是 Presentation Error。原因OJ 的判题分两种严格模式对输出逐字符比对宽松模式忽略行尾空格。考研机试的出题方通常用严格模式要求每个数字间隔一个空格行尾无多余空格最后一行有换行符也行、没有也行但行内不能多空格。解决写输出逻辑时统一用「第一个元素之前不输出空格后续元素先输出空格再输出值」的套路for (int i 0; i n; i) { if (i 0) cout ; cout arr[i]; } cout \n;不要写成cout arr[i] 加最后单独处理回退空格那样代码逻辑分散容易漏。这套源码包里所有输出代码都按「先判断再输出」的写法统一处理你照着这个风格写基本不会在输出格式上扣分。4.4 动态规划数组越界dp[i-1]在 i 为 0 时读到了垃圾值现象程序运行时不报错但答案在小数据时正确大数据时偶尔出错肉眼检查逻辑看不出问题。原因数组访问越界是未定义行为在小数据时可能恰好读到了dp[-1]地址对应的未知内存结果碰巧等于 0掩盖了错误数据变大后内存布局变化读到非零值结果就崩了。解决一个万能的调试技巧是在每次读取dp[i-1]之前先检查i 0。更系统的做法是训练时开启 Address Sanitizer 编译选项g -stdc11 -fsanitizeaddress -g solution.cpp -o solution_asan这个工具会在数组越界时立即报错并指出越界的行号比肉眼排查快得多。我每写完一个动态规划的解法都会用-fsanitizeaddress跑一遍样例确认没有越界后再交到 OJ。4.5 递归栈溢出二叉树深度为 10^4 时程序直接崩溃现象二叉树的递归遍历代码逻辑正确样例全过但一提交就段错误Segmentation Fault。原因递归深度等于树的高度如果题目给的是链状二叉树深度可能到 10^4 甚至 10^5默认栈空间不够函数调用直接爆栈。解决两类方案。第一类是改写成非递归版本用显式栈模拟递归过程这是推荐做法第二类是调整编译链接选项在编译命令里加-Wl,--stack,268435456把栈空间扩到 256MB但 OJ 上不能改链接选项所以这个方案只适合本地调试。考研机试不要赌递归深度默认所有树相关题目都写成非递归或显式栈版本养成这个习惯你就不会在这种问题上吃亏。5. 训练效果验证与进阶用数据生成器和复杂度估算做自我检查训练到一定量级后单纯做题已经不足以判断水平你需要一套可操作的验证方法来确认自己的代码真的能在机试环境下通过。这里分享我常用的三个步骤。第一步是批量回归测试。不要把样例数据手动敲进去写一个简单的 shell 脚本或批处理文件自动遍历题目目录下的所有测试点for f in input_*.txt; do ./solution $f ${f/input/output} done循环里把每个输入文件重定向到程序输出文件保存为output_对应编号.txt之后用diff -w和预期文件对比。这套流程的价值在于改完 bug 后可以一键跑完全部测试点而不是改一次测一组。源码包里每个题目只带一组样例数据和一组边界数据边界数据专门覆盖空输入、单元素、全相同元素这些极端情况批量回归能把大多数隐性 bug 逼出来。第二步是时间复杂度估算。写完一题代码后先用小数据跑通再构造一个题目允许的最大数据量输入本地测运行时间。如果 10^5 数据量跑出了 1 秒以上说明算法大概率有优化空间。我一般会先看循环层数乘以内层操作复杂度两层循环且每层到 n就是 O(n^2)一层循环内做二分查找就是 O(n log n)。机试的时间限制通常给 1 到 2 秒把一个 O(n^2) 算法交给数据范围 10^5 的题目等于是拿鸡蛋碰石头——不是评测机不行是思路还没到位。第三步是刻意练习参数化重构。把同一道题延长数据范围问自己如果 n 翻十倍当前代码还成立吗如果不成立瓶颈在哪一步比如顺序表删除重复元素的双指针版本是 O(n) 空间 O(1) 的换成普通写法每次删除后erase是 O(n) 的整体就变成 O(n^2)。这种追问是训练从「能跑」到「能过」的核心分水岭。最后分享一个习惯我每次训练完一组题目都会花十分钟把每个题的数据范围、算法复杂度、易错点写在一个文本文件里放在和源码包同级的笔记目录。之后再刷第二轮时只打开笔记不看源码尝试用自己的话复现代码写不出来就回去翻原版。这个过程循环三轮之后那些边界条件和输出格式的细节才算真正进入肌肉记忆。从那以后我每次准备机试都没有临时抱佛脚的慌张感因为训练时就按数据生成器、批量回归、复杂度自查这套流程走了一遍。希望这套源码包和这篇文章的训练思路能帮你少走一段我当年走过的弯路。本文还有配套的精品资源点击获取
C++考研机试训练源码：数据结构与算法实战
简介面向考研学生的C编程训练源码包以日常题目演练为线索集中覆盖数据合并、求和、质数检测、指针操作、结构体封装等基础与进阶编程练习帮助考生通过读代码、改代码、运行程序来理解语法细节、提升解题熟练度。压缩包共23个文件其中11个cpp源码分别对应11个exe可执行程序另有1个readme说明整体仅545KB轻量易用每一道练习都配有可运行结果便于即时对照输出并排查逻辑问题。目前已有118人学习使用。除基础算法训练外还包含测试逻辑、指针与动态内存操作、结构体应用、函数与数组组合等模块能够帮助读者系统梳理C常见考点若干补充题可作为额外练习适合计算机专业及所有需要强化编程能力的考研备考生反复演练、查漏补缺。1. C考研题目日常训练源码这套代码设计到底解决什么问题考研计算机统考和自命题的机试、笔试里C的代码设计能力是硬门槛。很多人从《算法笔记》或者王道单科书出发刷题但代码写完不知道对不对或者看了解析合上书就忘核心原因是缺少一套「题目、测试数据、参考实现」三件套齐备的训练集。这套源码包做的正是这件事按专题组织日常训练题目每个题目配套可运行的C参考代码和样例数据覆盖顺序表、链表、二叉树、图遍历、排序、动态规划、字符串处理这些高频考点拿来就能直接编译运行对照输入输出验证自己的实现。适合正在准备计算机考研的在校生、跨考但有一定编程基础的同学以及想系统过一遍数据结构与算法笔试代码题的从业者。它不教语法而是把「题目长什么样、代码怎么写、边界怎么卡」一次性给到你。2. 代码设计的组织逻辑专题切片、标准输入输出与可验证性2.1 为什么按专题切片而不是按难度排序日常训练最怕的是每天随便抓一道题做做完不知道覆盖了哪些考点。这套源码包的做法是把题目按数据结构与算法专题分组每一组内部再按从易到难的顺序排列。比如线性表这一组先做顺序表的基本操作再做链表的反转和合并最后做循环链表的约瑟夫问题这种梯度设计的好处是你做题时有明确的「最近发展区」写完一题回头看前一题能明显感觉到复杂度在提升。我一般会建议训练时按「线性表 → 栈和队列 → 二叉树 → 图 → 排序 → 动态规划」的顺序推进不要跳着刷。因为很多图的代码需要栈和队列做铺垫而动态规划的题目又经常要配合排序预处理。每组题目在源码包里是一个独立目录目录内是题目描述、输入输出样例和参考代码三个文件。题目描述部分会写明数据范围这个信息很关键直接决定了你要用什么复杂度的算法——比如数据量到 10^5 时 O(n^2) 的冒泡排序基本就没戏了必须换 O(n log n) 的归并或快排。2.2 输入输出约定的重要性为什么全部采用标准输入输出很多考研机试是黑盒评测程序从标准输入读数据把结果打印到标准输出评测系统比对输出文件。这套源码包的所有题目都严格按这个约定设计参考代码里不使用文件读写不用全局变量传递数据不依赖任何第三方库。这样做的原因是让你从一开始就养成「面向评测」的编码习惯——你在本地跑的代码提交到任何 OJ 平台上都不需要改。举个例子一个二叉树层序遍历的题目输入格式是间隔符分隔的节点序列输出是按层打印。如果参考代码里用了 Windows 特有的system(pause)或者conio.h在 Linux 评测机上就编译不过。这套源码包里全部用纯标准库写法iostream、vector、queue、algorithm、cstring这些头文件覆盖所有题目你在 Visual Studio、Dev-C、VSCode 配的 GCC 环境下都能直接编译。2.3 本地运行的三个关键命令编译、重定向、对比输出拿到源码包后第一步是在本地把参考代码跑起来。我以 VSCode 配 GCC 为例进入某个题目目录后先编译g -stdc11 -Wall -O2 -o solution solution.cpp这里-stdc11指定 C11 标准考研机试环境里 C11 是最保险的版本C14 和 C17 的特性不一定被所有评测机支持-Wall显示所有警告能在训练阶段帮你抓出未初始化变量这类隐患-O2开优化题目里的 O(n log n) 算法在不优化的条件下可能跑出 O(n^2) 的效果会误导你对算法效率的判断。编译成功后用重定向方式喂测试数据./solution input.txt output.txt把input.txt的内容作为标准输入流送入程序把程序的标准输出写入output.txt这样你不用手动敲输入也能批量验证。验证完当前测试点后对比输出和预期结果diff -w output.txt expected.txt-w参数忽略所有空白字符差异因为 OJ 比对输出时通常忽略行尾空格和空行但不会忽略中间的多余空格。训练时如果能过 diff说明这组样例没问题过不了就要对照着定位是算法逻辑错了还是格式输出错了——这两个错误处理方式完全不同。2.4 题目与代码的配套粒度每题独立、状态共享这套源码包里每个题目都带一个main.cpp不会出现一个文件同时包含多道题的情况。我拆过不少网上流传的代码包最常见的问题是一个cpp文件里堆了十几道题的函数注释混乱想跑第二题还得把第一题的 main 函数注释掉。这套包每题独立目录结构是topic-name/input.txt、topic-name/expected.txt、topic-name/solution.cpp你复制任何一个目录到本地都能单独编译运行。训练时我建议你不要直接打开参考代码而是先看题目描述自己写写不出来或者样例跑不过的时候再去看源码。看完源码之后把文件关掉自己重新写一遍这个过程比量变刷题重要得多。源码包里所有代码都写了核心注释但不是逐行注释——逐行注释会让人产生「看懂了」的错觉实际上只是读懂了英文单词。关键步骤注释就够了比如「此处必须用双指针否则 O(n^2) 超时」「边界条件链表为空时直接返回 head」。3. 核心题型的C实现套路从线性表到动态规划的参数与边界3.1 顺序表删除重复元素的原地算法与参数陷阱顺序表题目里出镜率最高的是删除有序数组中的重复元素要求原地修改数组返回新长度。这道题是考研 408 的常客很多人在笔试时写得出思路上机就翻车在返回值和新长度的关系上。参考代码用的是快慢双指针慢指针指向新数组的末尾位置快指针遍历整个数组int removeDuplicates(vectorint nums) { if (nums.size() 2) return nums.size(); // 空数组或单元素直接返回 int slow 1; // 慢指针新数组下一个可写入位置 for (int fast 1; fast nums.size(); fast) { if (nums[fast] ! nums[slow - 1]) { // 只有遇到新元素才进位 nums[slow] nums[fast]; } } return slow; // slow 就是去重后的长度 }这段代码有两个参数位置值得注意。第一个是if (nums.size() 2)很多人写成 1也能跑对但逻辑不直观——size()返回的是size_t无符号类型和字面量 1 比较没问题但如果写nums.size() - 1 1就有隐患无符号整数减法会向上溢出变成超大值。第二个是slow和fast都从 1 开始而不是从 0 开始因为数组有序第 0 个元素一定保留从第 1 个位置开始比较可以少一次没必要的判断。做完这道题你可以顺手验证一下边界数组全是相同元素时fast每次比较都不相等slow始终是 1最后返回 1数组被压缩成只有一个元素——这个结果符合预期。数组本身没有重复元素时fast每步都在写入slow最后等于原长度代码不会越界因为slow - 1最大不超过fast - 1而fast到不了nums.size()。3.2 单链表递归反转与迭代反转的取舍链表反转题在机试里出现频率极高主要原因是代码量短但指针操作容易晕。理解迭代反转的核心是维护三个指针prev指向前一个节点cur指向当前节点next临时保存下一个节点。每次循环把cur-next指向prev然后三个指针整体后移。参考代码实现如下ListNode* reverseList(ListNode* head) { ListNode* prev nullptr; // 前驱指针初始为空 ListNode* cur head; while (cur) { ListNode* next cur-next; // 先保存后继否则断链后无法前进 cur-next prev; // 反转当前节点的指向 prev cur; // 前驱前进 cur next; // 当前节点前进 } return prev; // 循环结束后 prev 指向原链表的尾节点即新链表头 }这里的核心坑是ListNode* next cur-next;必须先执行。如果先改cur-next再取next取到的就是已经反转后的prev节点链表当场断掉。我训练时见过不少人在这个顺序上翻车调试半天找不到原因最后发现是取了被覆盖的指针。递归版代码更短但性能和可读性都有代价。递归栈深度等于链表长度链表长度到 10^5 时可能栈溢出而机试题目数据范围写到 10^5 很常见所以建议以迭代版为主。如果题目明确要求递归实现那另说——考试时看清题面再决定。3.3 二叉树层序遍历的队列参数与空节点处理层序遍历要求按层输出节点值核心工具是队列。参考代码里有一个容易被忽略的参数——空节点nullptr是否入队。如果题目要求输出完整二叉树的层序结构空节点也要入队来占位如果只要求输出非空节点值序列空节点就不入队。这两者代码不同vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; queueTreeNode* q; if (root) q.push(root); // 空树直接返回空结果 while (!q.empty()) { int levelSize q.size(); // 关键参数当前层的节点数 vectorint level; for (int i 0; i levelSize; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); // 空节点不入队 if (node-right) q.push(node-right); } result.push_back(level); } return result; }int levelSize q.size();这行必须在循环外先取到在循环内q.size()的值会随push和pop动态变化直接写i q.size()会让循环多跑甚至跑成死循环。队列里可能同时存在两层节点拿到当前层的初始大小才能保证这一层只弹出levelSize个节点。考研机试里的层序题基本都要按层输出二维数组所以levelSize这个参数是必写的。3.4 动态规划最长递增子序列的两个版本怎么选动态规划题里最长递增子序列LIS是很好的分水岭题目能看出你是在背模板还是真的理解状态转移。O(n^2) 版本是基础定义dp[i]表示以第 i 个元素结尾的最长递增子序列长度转移方程是从所有j i且nums[j] nums[i]的位置取最大值加一int lengthOfLIS(vectorint nums) { int n nums.size(); if (n 0) return 0; vectorint dp(n, 1); // 每个元素自身构成长度为 1 的子序列 int ans 1; for (int i 1; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) dp[i] max(dp[i], dp[j] 1); } ans max(ans, dp[i]); // 最终答案是所有 dp[i] 的最大值 } return ans; }这个版本能过数据范围 n 1000 的题目但 n 到 10^5 就会超时。机试里数据范围常常写到 10^5所以要同时掌握二分优化的贪心版本维护一个tails数组tails[i]表示长度为 i1 的递增子序列的末尾元素最小值对每个数字用二分查找定位它能接在哪个位置的尾部后面。两个版本本质上是同一种问题的不同复杂度维度训练时应该都写一遍——只背 O(n^2) 版本遇到大数据就会原地卡死。另一个容易错的地方是初始化。dp数组初始化为 1 是对的因为任意一个元素单独都能构成长度为 1 的递增子序列。但有人会把长度 0 的子序列也纳入考虑认为dp[i]初始为 0这在本题里会导致答案少 1。区分标准是题目定义「空序列」算不算子序列考研题目里通常不把空序列计入所以初始化为 1 才是正确答案。4. 训练中的常见问题排查编译、性能和边界条件4.1 头文件包含的玄学为什么代码在你的机器上编译不过现象参考代码在源码包里能编译复制到自己电脑上用 Dev-C 5.11 打开就报vector does not name a type。原因Dev-C 5.11 自带的 GCC 版本太低默认没有启用 C11 语法而源码包里的代码大量使用vectorint、auto和范围 for 循环这些都是 C11 才有的特性。解决编译命令里显式加上-stdc11或者在 Dev-C 的「工具 → 编译选项 → 编译器」里加入-stdc11到编译命令中。如果你用 VSCode在tasks.json的args数组里加上-stdc11。我默认所有训练代码都按 C11 标准写不会用 C14 的make_unique或 C17 的if constexpr就是怕你本地环境不支持。4.2 运行超时的真正原因不是循环太慢而是循环做多了无用功现象一个看起来只有一层 for 循环的题目数据量 10^5本地跑样例秒出提交到 OJ 却超时。原因一层 for 循环内部如果调用了vector::eraseerase的时间复杂度是 O(n)因为后续元素要前移整体就变成了 O(n^2)。很多人在分析复杂度时只看循环层数不看循环内操作的实际代价。解决训练时遇到超时先用小数据量测正确性再用大数据量测时间。如果确定是erase导致的问题改成双指针原地覆盖或者用remove_if先标记后统一删除。这套源码包的参考代码里凡是有erase的地方都做了说明就是为了避免你抄到这种隐性 O(n^2) 写法。4.3 输出格式的边角问题多一个空格和少一个换行都判错现象diff 对比时-w参数忽略空白后一致但 OJ 上就是 Presentation Error。原因OJ 的判题分两种严格模式对输出逐字符比对宽松模式忽略行尾空格。考研机试的出题方通常用严格模式要求每个数字间隔一个空格行尾无多余空格最后一行有换行符也行、没有也行但行内不能多空格。解决写输出逻辑时统一用「第一个元素之前不输出空格后续元素先输出空格再输出值」的套路for (int i 0; i n; i) { if (i 0) cout ; cout arr[i]; } cout \n;不要写成cout arr[i] 加最后单独处理回退空格那样代码逻辑分散容易漏。这套源码包里所有输出代码都按「先判断再输出」的写法统一处理你照着这个风格写基本不会在输出格式上扣分。4.4 动态规划数组越界dp[i-1]在 i 为 0 时读到了垃圾值现象程序运行时不报错但答案在小数据时正确大数据时偶尔出错肉眼检查逻辑看不出问题。原因数组访问越界是未定义行为在小数据时可能恰好读到了dp[-1]地址对应的未知内存结果碰巧等于 0掩盖了错误数据变大后内存布局变化读到非零值结果就崩了。解决一个万能的调试技巧是在每次读取dp[i-1]之前先检查i 0。更系统的做法是训练时开启 Address Sanitizer 编译选项g -stdc11 -fsanitizeaddress -g solution.cpp -o solution_asan这个工具会在数组越界时立即报错并指出越界的行号比肉眼排查快得多。我每写完一个动态规划的解法都会用-fsanitizeaddress跑一遍样例确认没有越界后再交到 OJ。4.5 递归栈溢出二叉树深度为 10^4 时程序直接崩溃现象二叉树的递归遍历代码逻辑正确样例全过但一提交就段错误Segmentation Fault。原因递归深度等于树的高度如果题目给的是链状二叉树深度可能到 10^4 甚至 10^5默认栈空间不够函数调用直接爆栈。解决两类方案。第一类是改写成非递归版本用显式栈模拟递归过程这是推荐做法第二类是调整编译链接选项在编译命令里加-Wl,--stack,268435456把栈空间扩到 256MB但 OJ 上不能改链接选项所以这个方案只适合本地调试。考研机试不要赌递归深度默认所有树相关题目都写成非递归或显式栈版本养成这个习惯你就不会在这种问题上吃亏。5. 训练效果验证与进阶用数据生成器和复杂度估算做自我检查训练到一定量级后单纯做题已经不足以判断水平你需要一套可操作的验证方法来确认自己的代码真的能在机试环境下通过。这里分享我常用的三个步骤。第一步是批量回归测试。不要把样例数据手动敲进去写一个简单的 shell 脚本或批处理文件自动遍历题目目录下的所有测试点for f in input_*.txt; do ./solution $f ${f/input/output} done循环里把每个输入文件重定向到程序输出文件保存为output_对应编号.txt之后用diff -w和预期文件对比。这套流程的价值在于改完 bug 后可以一键跑完全部测试点而不是改一次测一组。源码包里每个题目只带一组样例数据和一组边界数据边界数据专门覆盖空输入、单元素、全相同元素这些极端情况批量回归能把大多数隐性 bug 逼出来。第二步是时间复杂度估算。写完一题代码后先用小数据跑通再构造一个题目允许的最大数据量输入本地测运行时间。如果 10^5 数据量跑出了 1 秒以上说明算法大概率有优化空间。我一般会先看循环层数乘以内层操作复杂度两层循环且每层到 n就是 O(n^2)一层循环内做二分查找就是 O(n log n)。机试的时间限制通常给 1 到 2 秒把一个 O(n^2) 算法交给数据范围 10^5 的题目等于是拿鸡蛋碰石头——不是评测机不行是思路还没到位。第三步是刻意练习参数化重构。把同一道题延长数据范围问自己如果 n 翻十倍当前代码还成立吗如果不成立瓶颈在哪一步比如顺序表删除重复元素的双指针版本是 O(n) 空间 O(1) 的换成普通写法每次删除后erase是 O(n) 的整体就变成 O(n^2)。这种追问是训练从「能跑」到「能过」的核心分水岭。最后分享一个习惯我每次训练完一组题目都会花十分钟把每个题的数据范围、算法复杂度、易错点写在一个文本文件里放在和源码包同级的笔记目录。之后再刷第二轮时只打开笔记不看源码尝试用自己的话复现代码写不出来就回去翻原版。这个过程循环三轮之后那些边界条件和输出格式的细节才算真正进入肌肉记忆。从那以后我每次准备机试都没有临时抱佛脚的慌张感因为训练时就按数据生成器、批量回归、复杂度自查这套流程走了一遍。希望这套源码包和这篇文章的训练思路能帮你少走一段我当年走过的弯路。本文还有配套的精品资源点击获取
