我在读《Algorithms_4th》的时候身边不少人都是照着书里的 Java 代码敲一遍运行通过就算“读完一章”了。我能理解这种效率取向但自己因为长期工作在纯 C 环境里根本没法直接抄代码只能把整本书的核心内容翻译成 C 去重新理解尤其是几何对象、信息处理、字符串与 I/O 这四块几乎每章都会碰到。一开始我感觉“吃亏”后来发现恰恰是“不能照搬”逼着我去抠每一个抽象背后的为什么收获比单纯读 Java 实现大得多。这篇文章就聊聊我用 C 视角重读这本书的方法、代码和踩过的坑适合正在用 C 刷题、做课程设计或者一直处于“Java 代码能看懂但自己写不出来”状态的同学。1. 我为什么偏要用 C 重读这本 Java 版算法书1.1 “看懂 Java 代码”和“能用 C 写出来”之间隔着什么书里的核心数据结构大多以 Java 形式给出LinkedList 类、BST 节点、EdgeWeightedGraph、各种 Comparator。Java 写起来确实省事节点不用考虑析构容器天然支持泛型垃圾回收替你兜底。但如果你切换到 C同样的“栈”或者“平衡树”第一反应必须是想清楚节点的内存归谁管是值语义还是引用语义复制一个容器对象是深拷贝还是浅拷贝这些问题是算法书不会直接讲的却是 C 里绕不开的关卡。我在第一次移植书里的符号表实现时狠狠吃过亏。Java 版的 SequentialSearchST 里每个 Node 只是被 next 指针串起来删除节点只需要将引用重新指向下一个节点剩下交给 GC。用 C 实现时如果直接写delete但忘了修正前驱节点的指针轻则内存泄漏重则野指针崩溃。后来我形成了条件反射每写一个涉及指针的类先画清楚对象的归属链再动手写构造函数、析构函数和拷贝控制。所以我的结论是不要因为 C 写起来“麻烦”就逃避。这种麻烦反而逼你区分算法的接口和实现比如栈这个抽象到底需要什么样的基本操作、节点生命周期应该谁来管。理解了这些再回头看书里的 Java 代码你会明白每个 API 的设计都是有意的而不是“随便写写”。1.2 C 视角重读的三个收益拷问抽象、审视复杂度、锤炼工程习惯第一个收益是拷问抽象。书中的 Date、Transaction、Point2D 等例子Java 里很容易通过implements ComparableDate获得排序能力换成 C你得自己定义operator、operator还要考虑是否要提供哈希支持、是否要用std::tie简化比较逻辑。这个“自己造排序接口”的过程会迫使你去理解 Comparable 背后到底在表达什么一个类型为什么可以比较依据什么规则比较规则不一致会引发什么后果。第二个收益是审视复杂度。Java 标准库里 List 和 Set 也有不同实现但 C 的使用者往往更敏感vector 的连续内存、list 的节点分散、deque 的分段连续都会直接反映在 CPU 缓存命中率和内存分配次数上。书里讲归并排序需要额外数组、快速排序是原地排序在 C 里就能很明显地看出内存分配对常数因子的影响。我在实现某种优先队列时曾比较过std::priority_queue和手写二叉堆实测差距主要来自比较函数的内联程度和容器底层布局这正是“算法分析”章节里谈到但很难在 Java 黑盒中体验的东西。第三个收益是锤炼工程习惯。Java 的包结构已经做了模块划分C 则强制你考虑头文件放什么、源文件放什么、命名空间怎么组织、模板是放头文件还是显式实例化。用 C 重写算法练习本质上是在做微型工程代码组织能力比照抄 Java 示例高一个台阶。我个人习惯是每个算法一个独立目录包含头文件、实现、测试用例三部分后面复习时直接跑测试比重新翻书快得多。2. 几何对象落地从抽象接口到值语义的 Point 类2.1 几何对象在算法书里到底扮演什么角色很多读者翻书时会觉得奇怪这本书不是讲算法吗怎么会出现点、区间、矩形这些几何对象其实它们大多不是主角而是排序、查找、贪心和并查集等算法的“测试载荷”。比如需要你按 x 坐标排序一堆点或者判断一组区间有没有重叠或者在平面点集中找出包含所有点的凸包这些题目天然适合验证排序和栈的应用。几何对象和普通字符串、整数最大的不同在于它们不止有一种比较方式。点既可以按 x 排序也可以按 y 排序还可以按极角排序区间可以按起点排序也可以按终点排序还可以按长度排序。这就在 C 中引出一个设计问题如果只给 Point 类写一个operator那它只能表达一种排序规则表达多种比较规则通常要借助函数对象或 lambda。Java 里对应的是传入不同 ComparatorC 同样以函数对象解决但常见的初学者错误是让operator里塞进太多业务规则导致排序意图不清晰。另一个特殊之处是几何对象常常需要浮点运算。距离计算涉及开方方向判断涉及叉积浮点数的精度误差是绕不开的。C 里不能直接拿double做相等比较也不能想当然认为排序后的相邻点就是空间上相邻的点。这些都让几何对象成为一个非常好的“算法落地练习材料”。2.2 一个够用的 Point2D 类比较器、叉积与哈希的 C 实现我在练习时写了一个精简的 Point2D去掉书里 Java 版本的大而全只保留自己真正会用到的部分#include cmath #include tuple #include functional struct Point2D { double x, y; Point2D(double x_ 0.0, double y_ 0.0) : x(x_), y(y_) {} double distanceTo(const Point2D rhs) const { double dx x - rhs.x; double dy y - rhs.y; return std::sqrt(dx * dx dy * dy); } }; // 按 (x, y) 字典序比较保证排序结果唯一 inline bool operator(const Point2D lhs, const Point2D rhs) { return std::tie(lhs.x, lhs.y) std::tie(rhs.x, rhs.y); } inline bool operator(const Point2D lhs, const Point2D rhs) { return lhs.x rhs.x lhs.y rhs.y; } // 叉积返回向量 oa 与 ob 的叉积 // 0 表示 b 在 oa 的顺时针方向 0 表示逆时针方向 inline double cross(const Point2D o, const Point2D a, const Point2D b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }选择按值传递而不是按引用传递是因为 Point2D 只包含两个 double正好一个 16 字节按值传比传引用再解引用更有可能被编译器放进寄存器反而高效。operator用std::tie实现避免手写多个 if 分支顺序表达得很清楚。这里我要提醒一个从算法书里看不出来的点叉积函数里三个参数 o、a、b 的语义要固定下来否则极角排序和凸包代码会非常难调。我习惯把 o 当作“观察点”或者“原点”返回值正负代表 a 到 b 的转向方向。实际开发时还可以再加一个struct PointHasher把两个 double 按位合并后交给std::unordered_set使用不过大多数情况下一个有序 vector 就够用了。2.3 从最近点对到区间调度几何题在 C 里的几个细节书里的算法在几何应用上并没有展开太多但通过课后练习可以补一个经典问题平面最近点对。暴力做法是两两比较复杂度 O(n^2)优化做法是分治按 x 坐标排序后不断切分合并时只检查中间带状区域里的点通常只需要比较常数个候选点。C 实现里有个容易踩坑的地方合并判断距离是否可能小于当前最优时不要拿平方根后的值到处比较建议全程保留距离平方最后再开方一次。区间调度则是贪心章节的经典例子。给出一组起止时间选择尽可能多的互不重叠区间正确策略是按结束时间升序排序再依次选择当前不冲突的区间。C 里的写法很直观sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { return a.end b.end; });这个 lambda 表面简单但提醒一个关键点排序比较器必须满足严格弱序如果 end 相等时直接返回 false可能会让 sort 认为两个区间相等进而影响后续排序稳定性。需要稳定排序时改用std::stable_sort需要处理并列时刻要决定是“先开始早的”还是“先结束早的”这些策略差异会影响最终结果数量。浮点精度问题在几何题里更是避不开。我见过有人直接判断cross(o, a, b) 0来认定三点共线结果因为 double 舍入误差漏掉了本应存在的共线点。正确做法是设一个极小值EPS比如 1e-12然后判断绝对值小于 EPS。这个习惯在纯算法书里很难学到但做计算几何题时会救你一命。3. 信息处理迁移符号表、排序与容器选择的思路转换3.1 从符号表接口到 map 与 unordered_mapAlgorithms_4th 里把符号表抽象成 STKey, Value 接口支持 put、get、delete、contains、isEmpty 等操作随后分别用链表、有序数组、二叉查找树、平衡树和哈希表来实现。这是非常好的分层教学法同一个接口多种底层结构复杂度各不相同。C 里面并不强制你先写接口再到实现标准库已经给了两套现成的容器std::map与std::unordered_map。std::map基于红黑树unordered_map基于哈希表。选哪个不完全看“大 O”要看实际使用模式。符号表章节里反复比较有序符号表和无序符号表前者可以范围查询、有序遍历、求 rank后者只有更快的平均单点访问。C 程序员经常默认unordered_map“更快”但我做频率统计的时候发现当键是短字符串且数据量不大时std::map的缓存局部性和较少的哈希计算开销反而可能胜出。所以算法书的价值正在于此看到 O(1) 的均摊复杂度时要追问它到底牺牲了什么是否值得。3.2 单词频率统计在 C 里为什么比 Java 更“麻烦”也更有意思书里有个经典案例统计文档中的单词频率找出出现次数最多的词。Java 里的做法通常是用 Scanner 切词再用 HashMap 计数。C 没有内置的 StringTokenizer需要借助istringstream或者手动拆分字符串还要处理标点符号、大小写归一化。这个过程看似繁琐实际上能把“信息处理”的每个环节都锻炼到分词、清洗、计数、排序。我写过一个完整版本核心代码大致是#include sstream #include unordered_map #include vector #include string #include algorithm std::vectorstd::pairstd::string, int topKFrequentWords( const std::string text, int k) { std::unordered_mapstd::string, int freq; std::istringstream iss(text); std::string word; while (iss word) { std::string clean; for (char c : word) { if (std::isalpha(static_castunsigned char(c))) clean.push_back(std::tolower(static_castunsigned char(c))); } if (!clean.empty()) freq[clean]; } std::vectorstd::pairstd::string, int items(freq.begin(), freq.end()); std::partial_sort(items.begin(), items.begin() std::min(k, (int)items.size()), items.end(), [](const std::pairstd::string, int a, const std::pairstd::string, int b) { return a.second ! b.second ? a.second b.second : a.first b.first; }); if ((int)items.size() k) items.resize(k); return items; }这里用了std::partial_sort而不是对所有词做全排序因为只需要前 K 个部分排序的复杂度更优。另外一个容易忽略的坑是std::isalpha和std::tolower的参数类型直接传入 char 在 char 是有符号类型时遇到非 ASCII 字节会产生不确定行为所以要先强制转换成unsigned char。这类细节在 Java 代码里完全不用考虑但是 C 环境下编译器的警告和运行时行为会直接告诉你“这里有问题”。3.3 “先排序后处理”的信息处理范式很多算法问题到最后都能化简成排序求中位数、去重、区间合并、求众数、链表归并无一例外都是“先让数据有序再线性扫描”。Algorithms_4th 的排序章节反复强调不同排序算法的稳定性和适应性C 标准库则把这些能力封装成了几个层次分明的函数。最常用的组合是先排序再 unique完成去重sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());这里unique只把重复元素移动到末尾并返回新的逻辑结尾真正删除要靠erase。我第一次写的时候漏了erase结果看到 vector 里元素数量没变才反应过来。还有一类查询状态统计比如累积和、前缀最值std::partial_sum可以一行搞定但注意它与迭代器绑定的语义如果目标区间和源区间重叠需要额外小心。另一个值得掌握的技巧是用nth_element找第 K 小的元素。它不保证其他部分有序只保证第 K 个元素处于最终排序位置平均复杂度 O(n)。这在处理信息流求中位数、TopK 问题时比全排序快得多也符合书里“下界与选择”那节的讨论。C 标准库这组算法的设计思想本质上和书里“排序算法并非越复杂越好而是看场景选工具”完全一致。4. 字符串与 I/OC 里最考验功底的组合拳4.1 std::string 和 Java String 的“气质”差异Java 的 String 是不可变对象任何拼接操作都会产生新对象C 的std::string是可变值类型操作符也会创造新字符串但reserve、append、replace可以在原地修改。这个差异最直接的影响是书里那些“通过创建新字符串来处理”的思路在 C 里可以用原地修改来优化但反过来如果你带着 Java 的习惯在循环里不停写s s c就可能触发大量内存分配。我做过一个小实验循环一万次在字符串末尾追加一个字符直接用s c很快但写成s s c就会因反复构造临时对象慢一个数量级。算法书不会讲这种工程性能差异因为 Java 那边编译器会做大量优化。明白了这个区别后我再写字符串算法时会首先考虑能不能用索引区间代替拼接能不能用原地交换代替拷贝能不能用 reserve 预留容量。还有编码问题。Java 的 String 内部按 UTF-16 存储书里讲字符索引时建立在“一个 char 是一个字符”的假设上。C 的std::string只是字节容器UTF-8 中一个汉字占 3 个字节直接用s[i]可能得到半个字符。我在处理中文文本的字符串排序时就被坑过后来明确区分了“字节长度”和“字符数”两个概念只在需要明确字符语义时才使用宽字符或 UTF 解析层。4.2 从 LSD 到三向快速排序字符串排序的 C 实现取舍字符串排序章节里有三条主线低位优先的 LSD、高位优先的 MSD、以及三向字符串快速排序。它们的共同点是想利用字符串的字符结构减少比较次数。Java 里因为 String 自带charAt实现起来很顺畅C 里也要用operator[]但要注意std::string的字符访问在未越界时是 O(1)这是好消息。实现 LSD 时最常见的错误是反复创建子串。比如有人会写string sub s.substr(d);再进入下一轮比较这在 C 中会复制字符串复杂度瞬间变成 O(n^2)。正确做法是始终传递原字符串和一个当前比较深度 d只通过s[d]访问字符而不是切出新字符串。三向字符串快速排序是书里非常妙的算法它把快速排序的三向切分推广到字符串代码紧凑但理解起来有门槛。下面是我实践后保留下来的简化版本// charAt 返回 s 在 d 位置的字符越界返回 -1 int charAt(const std::string s, int d) { return d (int)s.size() ? (unsigned char)s[d] : -1; } void threeWayStringQuickSort(std::vectorstd::string a, int lo, int hi, int d) { if (hi lo) return; int lt lo, gt hi; int v charAt(a[lo], d); int i lo 1; while (i gt) { int t charAt(a[i], d); if (t v) std::swap(a[lt], a[i]); else if (t v) std::swap(a[i], a[gt--]); else i; } // 处理小于 v 的分区、等于 v 的分区递归深度 d1、大于 v 的分区 threeWayStringQuickSort(a, lo, lt - 1, d); if (v 0) threeWayStringQuickSort(a, lt, gt, d 1); threeWayStringQuickSort(a, gt 1, hi, d); }这个版本刻意避免创建任何新字符串只是不断重排原 vector。因为所有字符串的公共前缀只被比较一次当待排序字符串大量共享前缀时它比标准std::sort要快很多。不过实际工程里我通常不会手写它而是根据数据特性判断如果字符串很短直接std::sort加默认比较器已经够快如果字符串长且前缀重复度高三向字符串快排才有明显优势。4.3 算法题目 I/O 快读快写的完整套路I/O 在算法书里往往被一笔带过但它其实是信息处理里最关键的一环尤其是面对大数据量输入时。我最早用 C 写算法练习时直接上std::cin和std::cout结果在输入有几万行时出现了明显的卡顿一度以为是算法写得有问题。后来才明白默认情况下 C 的 iostream 为了兼容 C 的 stdio做了同步每次读写都要经过额外的状态检查。最简单有效的优化是关闭同步std::ios::sync_with_stdio(false); std::cin.tie(nullptr);这两行的作用是切断 iostream 与 C 标准库的同步同时让cin不再每次输出后强制刷新。很多人知道要写但没想过原理。我再多说一句tie(nullptr)切断的是cin与cout的绑定避免读取输入时总是先刷新输出缓冲区。这两行在绝大多数算法场景里能把 I/O 速度提升到和scanf接近的水平。但当输入量达到几十万行并且需要逐行解析复杂格式时cin加getline配合istringstream仍可能成为瓶颈。我的做法是直接基于fread写一个极简快读#include cstdio #include cstring class FastScanner { static const int BUFSIZE 1 20; int idx, size; char buf[BUFSIZE]; char getChar() { if (idx size) { size (int)fread(buf, 1, BUFSIZE, stdin); idx 0; if (size 0) return 0; } return buf[idx]; } public: FastScanner() : idx(0), size(0) {} template typename T bool readInt(T out) { char c; T sign 1; T num 0; c getChar(); if (!c) return false; while (c ! - (c 0 || c 9)) { c getChar(); if (!c) return false; } if (c -) { sign -1; c getChar(); } for (; c 0 c 9; c getChar()) num num * 10 (c - 0); out num * sign; return true; } };这个快读本质上是手动维护一个输入缓冲区把 fread 读到的字节交给模板解析函数。其核心思路和算法书 “系统机制 vs 算法机制” 的划分很像真正的算法复杂度没变但常数因子被显著压缩。不过在项目工程里我建议再加上错误处理和 EOF 判断因为算法练习的输入数据基本规范而真实业务数据经常带着空行、多余空格和异常字符。5. 一次完整移植凸包算法背后的语言差异复盘5.1 为什么选 Graham Scan 做移植样本凸包问题要求找到包含所有点的最小凸多边形是计算几何的入门算法。它的算法流程要依赖 Point 类的比较、极角排序、叉积判断转向、栈结构回退几乎把我前面提到的点全部串起来几何对象、信息处理中的排序、以及 C 的容器操作。把它完整移植一遍比单独学排序或单独学栈更有整体感。书里没有直接讲凸包但它的思想离排序和栈都很近。我第一次实现时用了纯粹“跟着感觉走”的写法结果在共线点、浮点误差、排序顺序三个地方反复出错。后来重新组织思路把实现拆成“输入点预处理、按坐标排序、构造下凸包、构造上凸包、合并去重”五个阶段才稳定下来。5.2 Graham Scan 的完整 C 实现与关键解读我的版本使用 Andrew 变体它不需要像基础 Graham 算法那样先找极点再算极角排序而是直接按 (x, y) 排序后跑两个半圈的单调链构造代码更好写也更容易理解#include algorithm #include vector std::vectorPoint2D convexHull(std::vectorPoint2D pts) { if (pts.size() 1) return pts; std::sort(pts.begin(), pts.end(), [](const Point2D a, const Point2D b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); // 构造下凸包 std::vectorPoint2D lower; for (const auto p : pts) { while (lower.size() 2 cross(lower[lower.size() - 2], lower.back(), p) 0) { lower.pop_back(); } lower.push_back(p); } // 构造上凸包 std::vectorPoint2D upper; for (int i (int)pts.size() - 1; i 0; --i) { const auto p pts[i]; while (upper.size() 2 cross(upper[upper.size() - 2], upper.back(), p) 0) { upper.pop_back(); } upper.push_back(p); } lower.pop_back(); upper.pop_back(); lower.insert(lower.end(), upper.begin(), upper.end()); return lower; }这里最关键的是 while 循环里的转向判断当叉积小于等于 0 时说明新点会让前一个点不再处于凸包边界上应该弹出。如果改成只判断 0结果会保留所有共线点得到包含边上点的凸包如果坚持 0得到的是去掉共线点的极简凸包。到底取哪种取决于题目要求。书里讲 QuickHull 之类的问题时不会专门强调这些细节但实际做算法题时这就是最常见的失分点。另一个容易忽视的点是这个实现直接排序了传入的 points 副本所以不会破坏外部数据。如果是在内存受限环境里可以改成先拷贝迭代器范围但一般直接传值最安全。排序比较器里我没有使用operator而是单独写 lambda原因是operator是类型层面的默认总序而凸包算法要求的是确定性的 (x, y) 排序显式 lambda 能表达“这个用途不同”的语义也便于以后改成按 y 优先。5.3 移植过程中踩过的真实坑和我的查错清单第一个坑是叉积返回值精度。当三个点几乎共线时叉积会很接近 0可能因为 double 舍入变成绝对值极小的正数或负数导致凸包边界多一个点或少一个点。我现在会在涉及几何判断的地方统一增加 EPS 常量如下const double EPS 1e-12; bool isNonNegativeCross(double c) { return c -EPS; }但注意 EPS 不能设得太大否则会把确实弯曲的边界误判成共线进而丢掉真正的凸包顶点。这个平衡只能靠测试数据去调没有一劳永逸的公式。第二个坑是标准库容器与算法书伪代码的对应关系。书中描述的栈“push、pop、peek”在 Andrew 变体里用std::vector的push_back、pop_back、back实现语义完全一致。很多初学者会专门引入std::stack但std::stack不提供随机访问而凸包算法有时需要检查倒数第二个元素反而绕路。用std::vector作为后进先出的栈既能完成栈操作又能轻松访问栈底附近元素是这类算法里的自然选择。第三个坑出现在输出格式上。书里用 StdOut 打印结果C 用std::cout时需要注意浮点精度std::cout std::fixed std::setprecision(10) p.x p.y \n;如果不设置 precision默认会输出 6 位有效数字凸包坐标可能被截断到看不出差异的地步。我遇到过本地计算结果和题解完全一致但因为输出精度低被判错误的情况之后凡是输出浮点结果都先统一设定精度。我把这套移植经验整理成一份查错清单每次从 Java 版算法翻译成 C 都会过一遍对象的生命周期节点或容器元素何时创建、何时销毁、由谁拥有比较规则默认比较器是否满足严格弱序比较语义和业务语义是否一致浮点判断有没有在应该使用 EPS 的地方直接比较相等或全等I/O 边界EOF、空行、特殊字符、signed char 是否会引起无定义行为容器底层顺序访问还是随机访问多需不需要稳定排序是否需要保留中间元素最后再说一个个人习惯我不建议一上来就对着书里的代码“翻译”。更有效的做法是先把整个算法流程用伪代码写在纸上比如凸包问题就写“排序、构造下半部分、构造上半部分、合并”然后直接按这个流程写 C。写完后打开书里的 Java 实现做对照通常能发现两三个自己没有考虑到的边界条件。这个过程比“抄一遍”有价值得多因为你在拿 C 的工程约束反推算法的设计初衷。后来我读每一章几乎都会主动寻找这样一个“综合移植样本”书读到最后这些样本就成了我自己的复习目录。 
长河君 · 2026/10/19 14:57:37 · 阅读 1.2k 用C++重读《算法4》Java版：移植、思考与实践
我在读《Algorithms_4th》的时候身边不少人都是照着书里的 Java 代码敲一遍运行通过就算“读完一章”了。我能理解这种效率取向但自己因为长期工作在纯 C 环境里根本没法直接抄代码只能把整本书的核心内容翻译成 C 去重新理解尤其是几何对象、信息处理、字符串与 I/O 这四块几乎每章都会碰到。一开始我感觉“吃亏”后来发现恰恰是“不能照搬”逼着我去抠每一个抽象背后的为什么收获比单纯读 Java 实现大得多。这篇文章就聊聊我用 C 视角重读这本书的方法、代码和踩过的坑适合正在用 C 刷题、做课程设计或者一直处于“Java 代码能看懂但自己写不出来”状态的同学。1. 我为什么偏要用 C 重读这本 Java 版算法书1.1 “看懂 Java 代码”和“能用 C 写出来”之间隔着什么书里的核心数据结构大多以 Java 形式给出LinkedList 类、BST 节点、EdgeWeightedGraph、各种 Comparator。Java 写起来确实省事节点不用考虑析构容器天然支持泛型垃圾回收替你兜底。但如果你切换到 C同样的“栈”或者“平衡树”第一反应必须是想清楚节点的内存归谁管是值语义还是引用语义复制一个容器对象是深拷贝还是浅拷贝这些问题是算法书不会直接讲的却是 C 里绕不开的关卡。我在第一次移植书里的符号表实现时狠狠吃过亏。Java 版的 SequentialSearchST 里每个 Node 只是被 next 指针串起来删除节点只需要将引用重新指向下一个节点剩下交给 GC。用 C 实现时如果直接写delete但忘了修正前驱节点的指针轻则内存泄漏重则野指针崩溃。后来我形成了条件反射每写一个涉及指针的类先画清楚对象的归属链再动手写构造函数、析构函数和拷贝控制。所以我的结论是不要因为 C 写起来“麻烦”就逃避。这种麻烦反而逼你区分算法的接口和实现比如栈这个抽象到底需要什么样的基本操作、节点生命周期应该谁来管。理解了这些再回头看书里的 Java 代码你会明白每个 API 的设计都是有意的而不是“随便写写”。1.2 C 视角重读的三个收益拷问抽象、审视复杂度、锤炼工程习惯第一个收益是拷问抽象。书中的 Date、Transaction、Point2D 等例子Java 里很容易通过implements ComparableDate获得排序能力换成 C你得自己定义operator、operator还要考虑是否要提供哈希支持、是否要用std::tie简化比较逻辑。这个“自己造排序接口”的过程会迫使你去理解 Comparable 背后到底在表达什么一个类型为什么可以比较依据什么规则比较规则不一致会引发什么后果。第二个收益是审视复杂度。Java 标准库里 List 和 Set 也有不同实现但 C 的使用者往往更敏感vector 的连续内存、list 的节点分散、deque 的分段连续都会直接反映在 CPU 缓存命中率和内存分配次数上。书里讲归并排序需要额外数组、快速排序是原地排序在 C 里就能很明显地看出内存分配对常数因子的影响。我在实现某种优先队列时曾比较过std::priority_queue和手写二叉堆实测差距主要来自比较函数的内联程度和容器底层布局这正是“算法分析”章节里谈到但很难在 Java 黑盒中体验的东西。第三个收益是锤炼工程习惯。Java 的包结构已经做了模块划分C 则强制你考虑头文件放什么、源文件放什么、命名空间怎么组织、模板是放头文件还是显式实例化。用 C 重写算法练习本质上是在做微型工程代码组织能力比照抄 Java 示例高一个台阶。我个人习惯是每个算法一个独立目录包含头文件、实现、测试用例三部分后面复习时直接跑测试比重新翻书快得多。2. 几何对象落地从抽象接口到值语义的 Point 类2.1 几何对象在算法书里到底扮演什么角色很多读者翻书时会觉得奇怪这本书不是讲算法吗怎么会出现点、区间、矩形这些几何对象其实它们大多不是主角而是排序、查找、贪心和并查集等算法的“测试载荷”。比如需要你按 x 坐标排序一堆点或者判断一组区间有没有重叠或者在平面点集中找出包含所有点的凸包这些题目天然适合验证排序和栈的应用。几何对象和普通字符串、整数最大的不同在于它们不止有一种比较方式。点既可以按 x 排序也可以按 y 排序还可以按极角排序区间可以按起点排序也可以按终点排序还可以按长度排序。这就在 C 中引出一个设计问题如果只给 Point 类写一个operator那它只能表达一种排序规则表达多种比较规则通常要借助函数对象或 lambda。Java 里对应的是传入不同 ComparatorC 同样以函数对象解决但常见的初学者错误是让operator里塞进太多业务规则导致排序意图不清晰。另一个特殊之处是几何对象常常需要浮点运算。距离计算涉及开方方向判断涉及叉积浮点数的精度误差是绕不开的。C 里不能直接拿double做相等比较也不能想当然认为排序后的相邻点就是空间上相邻的点。这些都让几何对象成为一个非常好的“算法落地练习材料”。2.2 一个够用的 Point2D 类比较器、叉积与哈希的 C 实现我在练习时写了一个精简的 Point2D去掉书里 Java 版本的大而全只保留自己真正会用到的部分#include cmath #include tuple #include functional struct Point2D { double x, y; Point2D(double x_ 0.0, double y_ 0.0) : x(x_), y(y_) {} double distanceTo(const Point2D rhs) const { double dx x - rhs.x; double dy y - rhs.y; return std::sqrt(dx * dx dy * dy); } }; // 按 (x, y) 字典序比较保证排序结果唯一 inline bool operator(const Point2D lhs, const Point2D rhs) { return std::tie(lhs.x, lhs.y) std::tie(rhs.x, rhs.y); } inline bool operator(const Point2D lhs, const Point2D rhs) { return lhs.x rhs.x lhs.y rhs.y; } // 叉积返回向量 oa 与 ob 的叉积 // 0 表示 b 在 oa 的顺时针方向 0 表示逆时针方向 inline double cross(const Point2D o, const Point2D a, const Point2D b) { return (a.x - o.x) * (b.y - o.y) - (a.y - o.y) * (b.x - o.x); }选择按值传递而不是按引用传递是因为 Point2D 只包含两个 double正好一个 16 字节按值传比传引用再解引用更有可能被编译器放进寄存器反而高效。operator用std::tie实现避免手写多个 if 分支顺序表达得很清楚。这里我要提醒一个从算法书里看不出来的点叉积函数里三个参数 o、a、b 的语义要固定下来否则极角排序和凸包代码会非常难调。我习惯把 o 当作“观察点”或者“原点”返回值正负代表 a 到 b 的转向方向。实际开发时还可以再加一个struct PointHasher把两个 double 按位合并后交给std::unordered_set使用不过大多数情况下一个有序 vector 就够用了。2.3 从最近点对到区间调度几何题在 C 里的几个细节书里的算法在几何应用上并没有展开太多但通过课后练习可以补一个经典问题平面最近点对。暴力做法是两两比较复杂度 O(n^2)优化做法是分治按 x 坐标排序后不断切分合并时只检查中间带状区域里的点通常只需要比较常数个候选点。C 实现里有个容易踩坑的地方合并判断距离是否可能小于当前最优时不要拿平方根后的值到处比较建议全程保留距离平方最后再开方一次。区间调度则是贪心章节的经典例子。给出一组起止时间选择尽可能多的互不重叠区间正确策略是按结束时间升序排序再依次选择当前不冲突的区间。C 里的写法很直观sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { return a.end b.end; });这个 lambda 表面简单但提醒一个关键点排序比较器必须满足严格弱序如果 end 相等时直接返回 false可能会让 sort 认为两个区间相等进而影响后续排序稳定性。需要稳定排序时改用std::stable_sort需要处理并列时刻要决定是“先开始早的”还是“先结束早的”这些策略差异会影响最终结果数量。浮点精度问题在几何题里更是避不开。我见过有人直接判断cross(o, a, b) 0来认定三点共线结果因为 double 舍入误差漏掉了本应存在的共线点。正确做法是设一个极小值EPS比如 1e-12然后判断绝对值小于 EPS。这个习惯在纯算法书里很难学到但做计算几何题时会救你一命。3. 信息处理迁移符号表、排序与容器选择的思路转换3.1 从符号表接口到 map 与 unordered_mapAlgorithms_4th 里把符号表抽象成 STKey, Value 接口支持 put、get、delete、contains、isEmpty 等操作随后分别用链表、有序数组、二叉查找树、平衡树和哈希表来实现。这是非常好的分层教学法同一个接口多种底层结构复杂度各不相同。C 里面并不强制你先写接口再到实现标准库已经给了两套现成的容器std::map与std::unordered_map。std::map基于红黑树unordered_map基于哈希表。选哪个不完全看“大 O”要看实际使用模式。符号表章节里反复比较有序符号表和无序符号表前者可以范围查询、有序遍历、求 rank后者只有更快的平均单点访问。C 程序员经常默认unordered_map“更快”但我做频率统计的时候发现当键是短字符串且数据量不大时std::map的缓存局部性和较少的哈希计算开销反而可能胜出。所以算法书的价值正在于此看到 O(1) 的均摊复杂度时要追问它到底牺牲了什么是否值得。3.2 单词频率统计在 C 里为什么比 Java 更“麻烦”也更有意思书里有个经典案例统计文档中的单词频率找出出现次数最多的词。Java 里的做法通常是用 Scanner 切词再用 HashMap 计数。C 没有内置的 StringTokenizer需要借助istringstream或者手动拆分字符串还要处理标点符号、大小写归一化。这个过程看似繁琐实际上能把“信息处理”的每个环节都锻炼到分词、清洗、计数、排序。我写过一个完整版本核心代码大致是#include sstream #include unordered_map #include vector #include string #include algorithm std::vectorstd::pairstd::string, int topKFrequentWords( const std::string text, int k) { std::unordered_mapstd::string, int freq; std::istringstream iss(text); std::string word; while (iss word) { std::string clean; for (char c : word) { if (std::isalpha(static_castunsigned char(c))) clean.push_back(std::tolower(static_castunsigned char(c))); } if (!clean.empty()) freq[clean]; } std::vectorstd::pairstd::string, int items(freq.begin(), freq.end()); std::partial_sort(items.begin(), items.begin() std::min(k, (int)items.size()), items.end(), [](const std::pairstd::string, int a, const std::pairstd::string, int b) { return a.second ! b.second ? a.second b.second : a.first b.first; }); if ((int)items.size() k) items.resize(k); return items; }这里用了std::partial_sort而不是对所有词做全排序因为只需要前 K 个部分排序的复杂度更优。另外一个容易忽略的坑是std::isalpha和std::tolower的参数类型直接传入 char 在 char 是有符号类型时遇到非 ASCII 字节会产生不确定行为所以要先强制转换成unsigned char。这类细节在 Java 代码里完全不用考虑但是 C 环境下编译器的警告和运行时行为会直接告诉你“这里有问题”。3.3 “先排序后处理”的信息处理范式很多算法问题到最后都能化简成排序求中位数、去重、区间合并、求众数、链表归并无一例外都是“先让数据有序再线性扫描”。Algorithms_4th 的排序章节反复强调不同排序算法的稳定性和适应性C 标准库则把这些能力封装成了几个层次分明的函数。最常用的组合是先排序再 unique完成去重sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end());这里unique只把重复元素移动到末尾并返回新的逻辑结尾真正删除要靠erase。我第一次写的时候漏了erase结果看到 vector 里元素数量没变才反应过来。还有一类查询状态统计比如累积和、前缀最值std::partial_sum可以一行搞定但注意它与迭代器绑定的语义如果目标区间和源区间重叠需要额外小心。另一个值得掌握的技巧是用nth_element找第 K 小的元素。它不保证其他部分有序只保证第 K 个元素处于最终排序位置平均复杂度 O(n)。这在处理信息流求中位数、TopK 问题时比全排序快得多也符合书里“下界与选择”那节的讨论。C 标准库这组算法的设计思想本质上和书里“排序算法并非越复杂越好而是看场景选工具”完全一致。4. 字符串与 I/OC 里最考验功底的组合拳4.1 std::string 和 Java String 的“气质”差异Java 的 String 是不可变对象任何拼接操作都会产生新对象C 的std::string是可变值类型操作符也会创造新字符串但reserve、append、replace可以在原地修改。这个差异最直接的影响是书里那些“通过创建新字符串来处理”的思路在 C 里可以用原地修改来优化但反过来如果你带着 Java 的习惯在循环里不停写s s c就可能触发大量内存分配。我做过一个小实验循环一万次在字符串末尾追加一个字符直接用s c很快但写成s s c就会因反复构造临时对象慢一个数量级。算法书不会讲这种工程性能差异因为 Java 那边编译器会做大量优化。明白了这个区别后我再写字符串算法时会首先考虑能不能用索引区间代替拼接能不能用原地交换代替拷贝能不能用 reserve 预留容量。还有编码问题。Java 的 String 内部按 UTF-16 存储书里讲字符索引时建立在“一个 char 是一个字符”的假设上。C 的std::string只是字节容器UTF-8 中一个汉字占 3 个字节直接用s[i]可能得到半个字符。我在处理中文文本的字符串排序时就被坑过后来明确区分了“字节长度”和“字符数”两个概念只在需要明确字符语义时才使用宽字符或 UTF 解析层。4.2 从 LSD 到三向快速排序字符串排序的 C 实现取舍字符串排序章节里有三条主线低位优先的 LSD、高位优先的 MSD、以及三向字符串快速排序。它们的共同点是想利用字符串的字符结构减少比较次数。Java 里因为 String 自带charAt实现起来很顺畅C 里也要用operator[]但要注意std::string的字符访问在未越界时是 O(1)这是好消息。实现 LSD 时最常见的错误是反复创建子串。比如有人会写string sub s.substr(d);再进入下一轮比较这在 C 中会复制字符串复杂度瞬间变成 O(n^2)。正确做法是始终传递原字符串和一个当前比较深度 d只通过s[d]访问字符而不是切出新字符串。三向字符串快速排序是书里非常妙的算法它把快速排序的三向切分推广到字符串代码紧凑但理解起来有门槛。下面是我实践后保留下来的简化版本// charAt 返回 s 在 d 位置的字符越界返回 -1 int charAt(const std::string s, int d) { return d (int)s.size() ? (unsigned char)s[d] : -1; } void threeWayStringQuickSort(std::vectorstd::string a, int lo, int hi, int d) { if (hi lo) return; int lt lo, gt hi; int v charAt(a[lo], d); int i lo 1; while (i gt) { int t charAt(a[i], d); if (t v) std::swap(a[lt], a[i]); else if (t v) std::swap(a[i], a[gt--]); else i; } // 处理小于 v 的分区、等于 v 的分区递归深度 d1、大于 v 的分区 threeWayStringQuickSort(a, lo, lt - 1, d); if (v 0) threeWayStringQuickSort(a, lt, gt, d 1); threeWayStringQuickSort(a, gt 1, hi, d); }这个版本刻意避免创建任何新字符串只是不断重排原 vector。因为所有字符串的公共前缀只被比较一次当待排序字符串大量共享前缀时它比标准std::sort要快很多。不过实际工程里我通常不会手写它而是根据数据特性判断如果字符串很短直接std::sort加默认比较器已经够快如果字符串长且前缀重复度高三向字符串快排才有明显优势。4.3 算法题目 I/O 快读快写的完整套路I/O 在算法书里往往被一笔带过但它其实是信息处理里最关键的一环尤其是面对大数据量输入时。我最早用 C 写算法练习时直接上std::cin和std::cout结果在输入有几万行时出现了明显的卡顿一度以为是算法写得有问题。后来才明白默认情况下 C 的 iostream 为了兼容 C 的 stdio做了同步每次读写都要经过额外的状态检查。最简单有效的优化是关闭同步std::ios::sync_with_stdio(false); std::cin.tie(nullptr);这两行的作用是切断 iostream 与 C 标准库的同步同时让cin不再每次输出后强制刷新。很多人知道要写但没想过原理。我再多说一句tie(nullptr)切断的是cin与cout的绑定避免读取输入时总是先刷新输出缓冲区。这两行在绝大多数算法场景里能把 I/O 速度提升到和scanf接近的水平。但当输入量达到几十万行并且需要逐行解析复杂格式时cin加getline配合istringstream仍可能成为瓶颈。我的做法是直接基于fread写一个极简快读#include cstdio #include cstring class FastScanner { static const int BUFSIZE 1 20; int idx, size; char buf[BUFSIZE]; char getChar() { if (idx size) { size (int)fread(buf, 1, BUFSIZE, stdin); idx 0; if (size 0) return 0; } return buf[idx]; } public: FastScanner() : idx(0), size(0) {} template typename T bool readInt(T out) { char c; T sign 1; T num 0; c getChar(); if (!c) return false; while (c ! - (c 0 || c 9)) { c getChar(); if (!c) return false; } if (c -) { sign -1; c getChar(); } for (; c 0 c 9; c getChar()) num num * 10 (c - 0); out num * sign; return true; } };这个快读本质上是手动维护一个输入缓冲区把 fread 读到的字节交给模板解析函数。其核心思路和算法书 “系统机制 vs 算法机制” 的划分很像真正的算法复杂度没变但常数因子被显著压缩。不过在项目工程里我建议再加上错误处理和 EOF 判断因为算法练习的输入数据基本规范而真实业务数据经常带着空行、多余空格和异常字符。5. 一次完整移植凸包算法背后的语言差异复盘5.1 为什么选 Graham Scan 做移植样本凸包问题要求找到包含所有点的最小凸多边形是计算几何的入门算法。它的算法流程要依赖 Point 类的比较、极角排序、叉积判断转向、栈结构回退几乎把我前面提到的点全部串起来几何对象、信息处理中的排序、以及 C 的容器操作。把它完整移植一遍比单独学排序或单独学栈更有整体感。书里没有直接讲凸包但它的思想离排序和栈都很近。我第一次实现时用了纯粹“跟着感觉走”的写法结果在共线点、浮点误差、排序顺序三个地方反复出错。后来重新组织思路把实现拆成“输入点预处理、按坐标排序、构造下凸包、构造上凸包、合并去重”五个阶段才稳定下来。5.2 Graham Scan 的完整 C 实现与关键解读我的版本使用 Andrew 变体它不需要像基础 Graham 算法那样先找极点再算极角排序而是直接按 (x, y) 排序后跑两个半圈的单调链构造代码更好写也更容易理解#include algorithm #include vector std::vectorPoint2D convexHull(std::vectorPoint2D pts) { if (pts.size() 1) return pts; std::sort(pts.begin(), pts.end(), [](const Point2D a, const Point2D b) { if (a.x ! b.x) return a.x b.x; return a.y b.y; }); // 构造下凸包 std::vectorPoint2D lower; for (const auto p : pts) { while (lower.size() 2 cross(lower[lower.size() - 2], lower.back(), p) 0) { lower.pop_back(); } lower.push_back(p); } // 构造上凸包 std::vectorPoint2D upper; for (int i (int)pts.size() - 1; i 0; --i) { const auto p pts[i]; while (upper.size() 2 cross(upper[upper.size() - 2], upper.back(), p) 0) { upper.pop_back(); } upper.push_back(p); } lower.pop_back(); upper.pop_back(); lower.insert(lower.end(), upper.begin(), upper.end()); return lower; }这里最关键的是 while 循环里的转向判断当叉积小于等于 0 时说明新点会让前一个点不再处于凸包边界上应该弹出。如果改成只判断 0结果会保留所有共线点得到包含边上点的凸包如果坚持 0得到的是去掉共线点的极简凸包。到底取哪种取决于题目要求。书里讲 QuickHull 之类的问题时不会专门强调这些细节但实际做算法题时这就是最常见的失分点。另一个容易忽视的点是这个实现直接排序了传入的 points 副本所以不会破坏外部数据。如果是在内存受限环境里可以改成先拷贝迭代器范围但一般直接传值最安全。排序比较器里我没有使用operator而是单独写 lambda原因是operator是类型层面的默认总序而凸包算法要求的是确定性的 (x, y) 排序显式 lambda 能表达“这个用途不同”的语义也便于以后改成按 y 优先。5.3 移植过程中踩过的真实坑和我的查错清单第一个坑是叉积返回值精度。当三个点几乎共线时叉积会很接近 0可能因为 double 舍入变成绝对值极小的正数或负数导致凸包边界多一个点或少一个点。我现在会在涉及几何判断的地方统一增加 EPS 常量如下const double EPS 1e-12; bool isNonNegativeCross(double c) { return c -EPS; }但注意 EPS 不能设得太大否则会把确实弯曲的边界误判成共线进而丢掉真正的凸包顶点。这个平衡只能靠测试数据去调没有一劳永逸的公式。第二个坑是标准库容器与算法书伪代码的对应关系。书中描述的栈“push、pop、peek”在 Andrew 变体里用std::vector的push_back、pop_back、back实现语义完全一致。很多初学者会专门引入std::stack但std::stack不提供随机访问而凸包算法有时需要检查倒数第二个元素反而绕路。用std::vector作为后进先出的栈既能完成栈操作又能轻松访问栈底附近元素是这类算法里的自然选择。第三个坑出现在输出格式上。书里用 StdOut 打印结果C 用std::cout时需要注意浮点精度std::cout std::fixed std::setprecision(10) p.x p.y \n;如果不设置 precision默认会输出 6 位有效数字凸包坐标可能被截断到看不出差异的地步。我遇到过本地计算结果和题解完全一致但因为输出精度低被判错误的情况之后凡是输出浮点结果都先统一设定精度。我把这套移植经验整理成一份查错清单每次从 Java 版算法翻译成 C 都会过一遍对象的生命周期节点或容器元素何时创建、何时销毁、由谁拥有比较规则默认比较器是否满足严格弱序比较语义和业务语义是否一致浮点判断有没有在应该使用 EPS 的地方直接比较相等或全等I/O 边界EOF、空行、特殊字符、signed char 是否会引起无定义行为容器底层顺序访问还是随机访问多需不需要稳定排序是否需要保留中间元素最后再说一个个人习惯我不建议一上来就对着书里的代码“翻译”。更有效的做法是先把整个算法流程用伪代码写在纸上比如凸包问题就写“排序、构造下半部分、构造上半部分、合并”然后直接按这个流程写 C。写完后打开书里的 Java 实现做对照通常能发现两三个自己没有考虑到的边界条件。这个过程比“抄一遍”有价值得多因为你在拿 C 的工程约束反推算法的设计初衷。后来我读每一章几乎都会主动寻找这样一个“综合移植样本”书读到最后这些样本就成了我自己的复习目录。