C++训练Day73：指针、快速幂与字符串处理的实战复盘

写训练记录写到第73天这个阶段其实挺有意思。刚起步那会每天被指针、引用、内存分配折腾得晕头转向一道链表反转能写一晚上到了现在再回头看这些基础题会有一种“原来当时卡住是因为没理解底层”的顿悟感。Day73是个很微妙的节点语法层面的新鲜感基本消退算法和数据结构的题目开始成为主力同时还会不断回头补基础漏洞。这篇记录不打算写成流水账主要分享三件事一是这个阶段我到底在练什么、为什么这么练二是几个绕不开的知识点指针、const/static、运算符优先级、随机数在训练里是怎么被反复锤打的三是三道经典题目的完整复盘和踩坑记录。如果你也正处在C学习的中期爬坡阶段或者刷题刷到怀疑人生这篇应该能给你一点参考。1. 今日训练内容与选题思路1.1 为什么“Day73”开始混合刷题Day1到Day30那会儿我基本是照着语法书一个知识点一个知识点地过int、float、循环、数组、函数、结构体每个都单独练。到了Day40左右开始接触链表、栈、队列这些线性结构才发现语法会写和能用是两码事。Day60以后我开始把算法题和语法复习混在一起练每天不只看“这题怎么做”还要问“这个写法在底层到底发生了什么”。Day73的训练内容就是这种思路的延续。我没有专门去开新章节而是选了三个看起来不相关的点串在一起链表反转复习指针操作和递归、快速幂复习位运算和分治思想、字符串数组初始化复习C风格字符串和C标准库的取舍。这三个点正好覆盖了C训练中最容易出问题的几个区域指针的指向关系、运算的边界条件、内存的分配方式。如果你也处在类似阶段我的建议是不要只刷单一类型的题每天在“语法补漏 数据结构 一个数学/位运算题”之间做组合这样训练效果会比单刷一类题好很多。1.2 从热搜词看大家C训练的真实痛点最近在社区里看到不少C相关的高频搜索词比如“指针用法”“const/static详解”“结构体链表基本语法”“运算符优先级顺序表”“快速幂算法”“按位与”这些。说实话这些词暴露了绝大部分C初学者的真实状态不是不知道语法怎么念而是不知道语法怎么用。比如“指针用法”这个词搜的人很多但真正的问题往往不是“指针是什么”而是“指针到底该在什么场景下用、怎么避免把指针用崩”。再比如“结构体链表基本语法”实际卡住的地方通常是“创建节点、连接节点、遍历节点”这三步循环而不是struct关键字本身。今天训练里我特意把这些痛点对应的题目都安排了一遍。1.3 训练环境的预处理开始做题前我先花十分钟把环境梳理了一遍。我用的是VS Code MinGW-w64g 11.2.0编译参数是-stdc17 -Wall -Wextra -g调试用GDB。之所以不用IDE的一键运行是因为命令行编译能让你看清每一个中间文件的生成过程对理解编译原理有好处。如果你的环境还没配好建议优先搞定这三点编译器能正常处理C17标准、调试器能命中断点、编译时报错信息能定位到具体行号。这三件事不解决后面所有的训练都会很痛苦你会在“环境问题”和“代码问题”之间来回折腾根本分不清到底是谁的错。2. 核心知识点拆解训练里反复踩的四个点2.1 指针从“会写”到“不会崩”指针是C训练里绕不过去的大山Day73再看指针我的理解已经和Day10完全不同了。很多初学者以为指针就是“存地址的变量”这句话没错但真正写代码时会发现指针的问题从来不在“存地址”这一步而在“解引用”这一步。你定义一个int* p;却不初始化然后直接*p 10;程序在绝大多数情况下不会立刻崩而是悄悄踩踏了未知内存这就导致问题特别难排查。今天做链表反转时我专门写了个错误版本故意让头节点的指针悬空然后在GDB里观察野指针的地址值看到那个乱七八糟的十六进制数才真正理解了为什么“初始化指针”是铁律。另一个容易踩的坑是“指针的指针”和“指针引用”。写树形结构时经常要把Node*作为参数传递用来修改调用者手里的指针本身。如果这里用成Node*看起来只差一个实际效果是函数内部改了指针的指向但调用者手里的指针纹丝不动。今天我专门用一个insertNode函数验证了这俩的区别这种基础细节只要是训练C就不可能绕开。2.2 const 与 static它们到底在约束谁很多人对const的理解就是“变量不可改”但训练到中后期你会发现const的真实作用是“约定”。const int* p和int* const p有什么区别前者是“p指向的东西不能通过p改”后者是“p本身不能改”。写链表类时const还经常出现在成员函数后面比如int getVal() const;意思是这个成员函数不会修改对象的状态。如果不写这个const那么一个const Node对象就没法调用这个函数。static的坑稍微简单一点但也很隐蔽。类里的 static 成员变量是所有对象共享的它必须在类外单独定义否则链接时会报“undefined reference”。今天做快速幂时我用了一个 static 成员来统计函数调用次数结果忘了在类外定义直接报链接错误解决完后倒是把 static 的语义彻底记住了。2.3 运算符优先级一道题引发的血案今天被一个看似简单的表达式坑了几分钟if (x 1 0)。我在判断一个数是奇数还是偶数。直觉告诉我这是“x按位与1然后判断是否等于0”。实际上C里的优先级比高所以x 1 0会被解析成x (1 0)也就是x false不管x是多少结果都是0条件判断永远不成立。这种问题真的只有踩过一次才知道疼建议使用位运算时能用括号就用括号别跟优先级赌命。同样经典的还有*p和(*p)的区别*p是先取出p指向的值然后p自增(*p)是把p指向的值自增。这两行代码一字之差语义完全不同在链表遍历里如果写错轻则死循环重则内存越界。2.4 随机数测试数据的好帮手刷题时经常需要造测试数据比如生成一个长度不定的数组来测排序算法。很多老教程还在用rand()和srand(time(0))但这个组合在C11之后已经算是过时方案了rand()的随机质量一般而且取值范围是[0, RAND_MAX]想生成[1, n]还得自己取模取模还会引入分布偏差。我现在的习惯是用random库核心就几行代码std::random_device rd; std::mt19937 gen(rd()); std::uniform_int_distributionint dis(1, 100); int value dis(gen); // 生成 [1, 100] 的随机数用这个方案生成测试数据比rand()稳定得多尤其在测边界条件的时候特别省心。今天做快速幂的验证时我生成了100组随机底数和指数把递归版和迭代版的结果逐一对比两边完全一致才敢确认代码没写错。3. 实操过程与核心环节实现3.1 题目一反转链表迭代版与递归版双实现先设计一个单链表结构struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} };迭代版反转链表的核心是三指针prev、cur、next每次先把 cur 的下一个节点存下来再改指向然后三个指针整体向后滑动。这个写法的关键点是循环结束条件cur ! nullptr循环结束后prev正好停在新的头节点ListNode* reverseList_iter(ListNode* head) { ListNode* prev nullptr; ListNode* cur head; while (cur) { ListNode* next cur-next; // 先保存防止断链 cur-next prev; // 反向指 prev cur; // prev 前进 cur next; // cur 前进 } return prev; }递归版的代码更短但理解难度反而更高ListNode* reverseList_rec(ListNode* head) { if (!head || !head-next) return head; ListNode* newHead reverseList_rec(head-next); head-next-next head; head-next nullptr; return newHead; }递归版的核心是“先处理后面的节点再回头处理当前节点”。建议在纸上画一遍链表的三节点走位把每一层递归时的 head 指向、newHead 指向都标清楚再回到代码里就顺了。今天我用一个5个节点的链表测试了两个版本结果一致但递归版在节点数上万时可能会栈溢出工程上更推荐迭代版。3.2 题目二快速幂位运算与分治思想快速幂解决的问题是“计算 x 的 n 次方”朴素写法是循环n次相乘时间复杂度 O(n)当 n 是 1e9 级别时显然不可行。快速幂的核心思路是二分x^n 可以拆成 (x^(n/2))^2这样只需要 O(log n) 次乘法。递归版快速幂long long fastPow_rec(long long x, long long n) { if (n 0) return 1; long long half fastPow_rec(x, n / 2); return n % 2 0 ? half * half : half * half * x; }迭代版利用的是“把指数拆成二进制”的思路。举个例子计算 x^1313 的二进制是 1101也就是 x^13 x^8 * x^4 * x^1。迭代时不断让底数自乘x x^2, x^4, x^8...同时根据当前二进制位是否为1决定是否乘进结果里long long fastPow_iter(long long x, long long n) { long long result 1; while (n 0) { if (n 1) result * x; x * x; n 1; } return result; }这里有个关键点两个版本都用了long long而不是int因为中间结果很容易超过 int 的范围。我测试 x3, n20 时结果已经是 3486784401早就超出 int 上限了。如果题目要求取模常规做法是在每步乘法后对某个质数取模避免溢出。今天还专门测了 n0 和 n1 这两个边界n0 返回 1n1 在循环里会直接把 x 乘进结果两个版本输出一致。3.3 题目三字符数组初始化与字符串转数组这个题目看起来基础但实际写时特别容易栽跟头。C风格字符串是char[]以 \0 结尾C的std::string是对象有自己的长度信息。把std::string转成 C 风格字符数组标准做法是std::string s hello; const char* cstr s.c_str(); // 只读版本最常见 std::vectorchar buf(s.begin(), s.end()); buf.push_back(\0); // 手动补终止符下面这个写法是反面教材也是很多人常犯的错误const char* p s.data(); // C17 之前 data() 返回的是 const char* char* q const_castchar*(p); // 强行去掉 const q[0] H; // 未定义行为可能直接崩为什么不能这么改因为std::string的内部缓冲区不保证以可写方式暴露给外部有的实现里data()返回的内存是只读的或共享的强行写入会导致未定义行为。正确做法是用s[0]或者直接复制到新的std::vectorchar里再修改。今天我用这个知识点配合按位运算写了一个小工具把字符串里的每个字符转成二进制形式用unsigned char类型避免符号位问题然后用按位与去提取每个bit。这个练习把“字符串处理”和“位运算”串在了一起比单纯背“按位与的规则”有用得多。3.4 编译、运行与GDB验证三道题的代码都在VS Code里编译通过后我用GDB对反转链表版做了断点调试。在cur-next prev;这行打断点每执行一次就打印prev、cur、next三个指针的地址和值能非常直观地看到“断链-反指-前进”的过程。这也是我今天最推荐的调试练习不要只看结果对不对要亲眼看着链表的指针是怎么一步一步变成反序的。如果你也用GDB推荐两个常用命令p *cur // 查看 cur 指向的结构体内容 p cur-next // 查看当前节点的 next 字段4. 常见问题与排查技巧实录4.1 段错误Segmentation Fault今天练反转链表时我故意把cur初始化为head-next跳过了第一个节点结果循环里解引用了空指针程序直接段错误。排查方法很简单先用GDB运行崩溃后会显示崩在哪一行再用bt命令查看调用栈通常一眼就能定位。段错误最常见的三种原因解引用空指针、指针越界、访问已释放的内存。训练链表、树这类题目时90%的崩溃都能归结到这三点。我的经验是每次访问一个指针之前先问一句“这个指针有没有可能是空的或悬空的”养成这个习惯后段错误会少很多。4.2 编译错误与链接错误今天遇到的最典型的编译错误是“invalid conversion from ‘const char*’ to ‘char*’”原因是把s.c_str()的返回值直接赋给char*了。遇到这种编译错误不要急着强转先想想设计意图你到底需不需要修改内部缓冲区如果需要就老老实实复制一份。链接错误也有一个经典案例就是前面提到的 static 成员变量没有在类外定义。错误信息会显示一堆 “undefined reference”很多人看到这个就懵了其实只要在类外补上int MyClass::count 0;就解决了。4.3 逻辑错误比编译错误更隐蔽今天快速幂迭代版第一次跑出来结果不对检查了二十分钟才发现原来是result * x;和x * x;的顺序反了。如果先让x自乘再判断当前二进制位就会导致底数领先指数一步结果自然全错。这类逻辑错误编译器不会报错代码也能正常编译运行只能靠测试数据去发现。建议在验证时多测边界值n0、n1、n2、n大数再结合随机数造多组数据对比别只测一个例子就结束。4.4 常见问题速查表问题现象可能原因定位思路解决方法程序运行时崩溃提示 segment fault解引用空指针或野指针用GDB看崩溃行检查该行访问的指针初始化所有指针使用前判空编译报 invalid conversionconst 无故被移除看报错行涉及的类型需要修改时复制一份否则用 const char*链接报 undefined referencestatic 成员未定义看哪个符号缺失在类外补定义条件判断结果老是不对运算符优先级搞混把表达式单独打印出来看统一加括号别省递归版链表反转栈溢出节点数过多看崩溃调用栈深度改用迭代版5. 训练节奏与记录方法复盘5.1 Day1到Day73的训练节奏参考有不少人问过我怎么坚持到73天的。我的体会是把训练切分成三个阶段目标非常关键Day1~Day20语法基础为主线每天只学一两个语法点配上最简单的练习目标是能看懂别人写的C代码。Day21~Day45数据结构开始进场数组、链表、栈、队列、树逐一出场重点练“把思路翻译成代码”的能力。Day46~Day73算法与语法交叉训练排序、二分、双指针、位运算、快速幂这些经典题型每天保持手感同时回头复习const、static、指针等语法细节。这个节奏不一定适合所有人但核心思路可以参考前期重语法广度中期重结构理解后期重算法与语法的结合运用。5.2 笔记怎么记才不白写到Day73这个阶段我已经不满足于“今天做了哪些题”这种流水账了。现在每道题我会固定记四个维度题目描述与考点、我的第一遍思路、标准解法的关键步骤、我栽过的坑或没想通的地方。比如今天反转链表这题笔记里记了一个很重要的自我提醒“断链前必须先保存下一个节点”。这句话就是我这道题的核心经验比抄一遍代码有用得多。如果你也写训练笔记建议用“哪句话是你下次看到就能立刻想起整道题解法”的标准来精简笔记而不是把代码原封不动贴上去。5.3 Day73之后的训练计划到了这个节点我的下一步计划是把更多精力转向工程化方向读STL容器的源码实现、写一个迷你版 vector/string、找一个开源C项目做代码阅读。毕竟刷题练的是“局部手艺”而工程练的是“系统配合”。目前的想法是先从模拟实现std::string开始用上今天复习的指针、const、动态内存这些知识让它们真正派上用场。最后再分享一个我个人的小习惯每做完三道题我会用一句话把它们串成一个场景。比如今天的三道题可以串成“用链表组织数据用位运算加速计算用字符串完成输入输出”这样一天下来脑子里留下的不是三块孤立的碎片而是一个能转起来的小系统。这个方法看起来很简单但对我坚持73天帮助非常大。