编程珠玑（第二版） (2008 年度畅销榜NO.68 )

本书是作者编程经验的结晶，由发表在杂志上的专栏文章构成，每一章内容相对独立，但都是编程过程中的有机组成部分。本书内容包括问题定义、算法、数据结构、程序验证与测试、程序优化与效率问题，以及这些技巧在排序、查找和字符串处理等方面的几个实际应用。
本书每章末尾都附带有相关内容的问题，附录中给出了一些问题的提示和解答。仔细思考问题或与同事进行讨论，可以巩固所学知识，将作者的经验应用到自己的编程实践中。本书主要针对有过大型项目编程经验的程序员。
书中代码

目 录

第一部分 预备知识 1
第1章 开篇 2
1.1 一次友好的对话 2
1.2 精确的问题陈述 3
1.3 程序设计 3
1.4 实现纲要 4
1.5 原则 5
1.6 问题 6
1.7 进阶阅读 7
第2章 啊哈！算法 1
2.1 三个问题 1
2.2 无所不在的二分查找法 1
2.3 原语的力量 3
2.4 归拢：排序 4
2.5 原则 5
2.6 问题 5
2.7 进阶阅读 6
2.8 实现变位词程序（补充材料） 7
第3章 数据结构程序 1
3.1 调查程序 1
3.2 表单字母编程 3
3.3 数组例子 5
3.4 构造数据 6
3.5 针对特定数据的强大工具 6
3.6 原则 8
3.7 问题 9
3.8 进阶阅读 10
第4章 编写正确的程序 1
4.1 二分查找的挑战 1
4.2 编写程序 2
4.3 理解程序 4
4.4 原则 6
4.5 程序验证的任务 7
4.6 问题 7
4.7 进阶阅读 9
第5章 编程中的次要问题 1
5.1 从伪代码到C语言 1
5.2 测试装备 2
5.3 断言的艺术 4
5.4 自动化测试 6
5.5 定时 7
5.6 完整的程序 8
5.7 原则 9
5.8 问题 9
5.9 进阶阅读 10
5.10 调试[补充材料] 10
第二部分 性能 1
第6章 性能透视 2
6.1 案例研究 2
6.2 设计层次 3
6.3 原则 4
6.4 问题 5
6.5 进阶阅读 5
第7章 封底计算 1
7.1 基本技能 1
7.2 性能估计 3
7.3 安全系数 5
7.4 利特尔法则 6
7.5 原则 6
7.6 问题 6
7.7 进阶阅读 7
7.8 日常生活中的快速计算[补充材料] 8
第8章 算法设计技术 1
8.1 问题和简单算法 1
8.2 两个二次算法 2
8.3 分治算法 3
8.4 扫描算法 4
8.5 重要性 5
8.6 原则 6
8.7 问题 7
8.8 进阶阅读 8
第9章 代码优化 1
9.1 一个典型的故事 1
9.2 第一个辅助采样器 2
9.3 主要的外科手术——二分查找 5
9.4 原则 8
9.5 问题 9
9.6 进阶阅读 10
第10章 压缩空间 1
10.1 关键——简单性 1
10.2 一个演示问题 1
10.3 数据空间技术 3
10.4 编码空间技术 6
10.5 原则 7
10.6 问题 8
10.7 进阶阅读 9
10.8 巨大的压缩[补充材料] 9
第三部分 产品 1
第11章 排序 2
11.1 插入排序 2
11.2 简单快速排序 3
11.3 更好的快速排序 6
11.4 原则 8
11.5 问题 9
11.6 进阶阅读 10
第12章 抽样问题 1
12.1 一个实际问题 1
12.2 一种解决方案 1
12.3 设计空间 3
12.4 原则 5
12.5 问题 5
12.6 进阶阅读 6
第13章 查找 1
13.1 接口 1
13.2 线性结构 2
13.3 二分查找树 6
13.4 整数结构 7
13.5 原则 9
13.6 问题 10
13.7 进阶阅读 11
13.8 实际查找问题[补充内容] 11
第14章 堆 1
14.1 数据结构 1
14.2 两个关键函数 2
14.3 优先队列 5
14.4 排序算法 8
14.5 原则 10
14.6 问题 10
14.7 进阶阅读 11
第15章 珍珠字符串 1
15.1 单词 1
15.2 词组 4
15.3 生成文本 6
15.4 原则 10
15.5 问题 11
15.6 进阶阅读 11
第一版本的尾声 12
第二版的尾声 14

“《编程珠玑》第一版是我职业生涯早期阅读过的最有影响力的书籍之一，第一次从该书中学到的许多观点很久以后仍然使我受益匪浅。Jon在第二版中对素材进行了大量更新，这些新例子的新鲜程度给我留下了深刻的印象。” —Steve McConnell，《Code Complete》等多部畅销书作者 如果让程序员们列出他们最喜欢的书籍，Jon Bentley的《编程珠玑》常常可以位于经典之列。如同珍珠来自于曾经折磨牡蛎的沙粒，程序设计的珍珠也来自曾经折磨程序员的实际问题。Bentley的珍珠超出了可靠工程学的范畴、在洞察力和创造力的王国中为那些恼人的问题提供了独特而巧妙的解决方案。通过一些精心设计的有趣而且颇具指导意义的程序，书中充满了对实用程序设计技巧及基本设计原则的清晰而机智的描述。因此，《编程珠玑》得到各个层次程序员的青睐并不让人感觉意外。 本次修订是14年来的第一次，Bentley彻底更新了书中的素材，从而反映当前的程序设计方法和环境。此外还增加了关于以下三个方面的新内容： l 测试、调试和定时。 l 集合表示。 l 字符串问题。 所有原来的程序都重新进行了改写，并生成了等量的新代码。您可以获取所有程序的C或C++实现。 新版本中保持不变的是Bentley对于程序设计问题本质的关注，以及他针对这些问题给出的优美解决方案。不论您是第一次阅读Bentley的经典，还是想再次领略他作品中的新观点，这本书都肯定会成为您最喜爱的书目之一。

Jon Bentley是位于新泽西州Murray Hill的朗讯贝尔实验室计算机科学研究中心的技术委员会委员。Jon自1998年就成为《Dr. Dobb's Journal》杂志的特约编辑。他的“编程珠玑”专栏多年来一直是顶级学术杂志《Communications of the ACM》最风行的特色专栏之一，而本书正是建立在这些专栏的基础之上。 请分别从以下网址访问Addison-Wesley和ACM： http://www.awl.com/cseng和http://info.acm.org/。

计算机程序设计涉及诸多方面。Fred Brooks在《Mythical Man Month》中描述了一幅广阔的画卷；他的作品侧重于讲述管理在大型软件项目中所扮演的关键角色。更为具体一点的是Steve McConnell在《Code Complete》中介绍的优美的程序设计风格，书中涉及的那些主题对于优秀的软件和程序员来说都是至关重要的。但不幸的是，合理软件工程原则指导下的精巧的应用程序并非总是可以打动人心——除非软件按时全部完成并运转正常。 关于本书 本书涉及的主题是计算机专业领域中更为迷人的一个方面：这是一些超出了可靠工程学范畴、位于洞察力和创造力王国中的程序设计珍珠。如同珍珠来自于曾经折磨牡蛎的沙粒，程序设计的珍珠也来自曾经折磨程序员的实际问题。书中这些有趣的程序将会教给您重要的程序设计技巧和基本的设计原则。 书中的内容大多出自发表在Communications of the Association for Computing Machinery上的Programming Pearls专题，它们被整理、修订，并于1986年作为本书的第一版出版。本书重新编辑了第一版的大部分内容，并加入了三个新的主题。 阅读本书的惟一要求是读者有过使用高级语言进行程序设计的经验。一些高级的技术（比如C++模版）在书中也会偶尔出现，对这些主题不熟悉的读者可以直接跳过这些章节，而不会造成阅读障碍。 尽管书中的每一章都可以自成体系，但在整体上仍然存在逻辑上的分组。第I部分的第1到5章回顾了程序设计的基础知识：问题定义、算法、数据结构、以及程序验证和测试。第II部分内容主要围绕效率问题展开，效率问题不仅本身十分重要，而且常常是进入有趣的程序设计问题的最好切入点。第III部分将会把这些技巧应用到几个关于排序、查找和字符串处理的基本问题之上。 给读者的提示：不要读得太快。请仔细阅读，并尝试解决书中提到的问题——某些问题看似容易，但可能需要您花费一到两个小时的精力才能解决。然后，请认真解答每章末尾提出的问题：通过思考解决方案，您从本书学到的大部分知识将得以巩固。如果可能的话，在翻看书后给出的提示和解决方案之前最好和朋友或同事讨论您的观点。每章末尾给出的附加阅读材料并不代表学术界的参考资料列表；我推荐了一些优秀的参考书目，它们也是我个人书库中最为重要的组成部分。 本书是为程序员所写。我希望这些问题、提示、解决方案和附加阅读材料将会给程序员带来帮助。事实上，本书已经在多门课程中发挥了它的作用，其中包括算法、程序验证和软件工程。附录1中的算法目录是给职业程序员的一个参考，同时说明了如何将本书应用于算法和数据结构方面的课程。 代码 本书第一版中的伪码程序其实已全部实现了，但只有我一个人可以看到这些真正的代码。在第二版中，我重新编写了原有的程序并编写了同样数量的新代码。您可以从本书的网站（www.programmingpearls.com）上获得这些程序。代码中包含了许多用于测试、调试和定时的脚手架。网站上也提供一些其他相关资料。因为现在程序员可以从网上获得十分多的软件，所以这一版本的一个新主题就是介绍如何评价和使用软件组件。 本书的程序采用了简洁的代码风格：短变量名、较少的空行、少数或没有错误检查。在大型软件项目中这是不合适的，但它有利于表达算法的关键思想。答案5.1给出了关于这种风格的更详细的背景。 书中包含了一些真正的C和C++程序，但大多数函数都表示成伪码的风格：采用较少的空格并避免不优雅的语法。符号for i = [0, n) 将i从0迭代到n-1。在这种风格的for循环中，左右圆括号表示开放的范围（其中不包含边界值），而左右方括号则表示封闭的范围（其中包含边界值）。表达式function(i, j) 仍然表示调用一个带有参数i 和 j的函数，array[i, j] 也仍然会访问一个数组元素。 书中列出了许多程序在“我的机器”上运行的情况，该机器的配置是奔腾II 400MHz处理器、128MB内存、Windows NT 4.0操作系统。我还记录了程序在其他几台机器上的运行情况，书中给出了我所观察到的一些根本区别。所有实验都采用了最大程度的编译器优化。我建议您在自己的机器上进行计时，并打赌您将会找出类似的运行时规律。 致第一版读者 我希望你翻阅本书的第一反应是“看起来的确与第一版很像。”几分钟之后，我希望你将会发觉“我从未看过此书。” 这一版与第一版关注的问题相同，但它被置于更大的背景之中。计算机技术已经在关键领域——例如数据库、网络、用户界面——发生了根本的变化，大多数程序员都应该熟悉这些技术。第一版的程序在本书中仍然得以保留。但与第一版相比，本书像是一个更大池塘中的一条更大的鱼。 原书第4章中关于实现二进制查找的一节现在被放到了介绍测试、调试和定时的第5章中。原来的第11章得到了扩展并被拆分为新的第12章（关于原来的问题）和第13章（关于集合表示）。原来的第13章介绍了一种运行在64KB地址空间上的拼写检查；现在它已经被去掉了，但它的思想仍然存在于第13.8节。新的第15章是关于字符串问题的。许多新节被添加到原来的章中，另外一些节则被删掉了。由于引入了新的问题、新的解决方案以及四个新的附录，本书比上一版本在长度上增加了25%。 许多旧的案例研究在这一版本中没有发生变化，但也有一些老故事根据现在的情况被重新改写。 第一版致谢 我要感谢许多人对我的支持。在Communications of the ACM上设立专题的想法最初来自Peter Denning和Stuart Lynn。Peter勤奋地为ACM工作，他使这个专题成为可能并录用我从事此项工作。ACM总部的成员，尤其是Roz Steier和Nancy Adriance给了我许多支持，他们让这些专题文章能以原有的形式发表。我尤其要感谢ACM的是：它鼓励专题以原有的形式发表；同时感谢许多CACM的读者，是你们对专题的热心评论使这个扩充版本变得必要并有可能完成。 Al Aho、Peter Denning、Mike Garey、David Johnson、Brian Kernighan、John Linderman、Doug McIlroy和Don Stanat在百忙中抽出时间仔细阅读了本书的每一个章节。我还要感谢以下诸位提出的宝贵意见：Henry Baird、Bill Cleveland、David Gries、Eric Grosse、Lynn Jelinski、Steve Johnson、Bob Melville、Bob Martin、Arno Penzias、Marilyn Roper、Chris Van Wyk、Vic Vyssotsky 和Pamela Zave。另外，Al Aho、Andrew Hume、Brian Kernighan、Ravi Sethi、Laura Skinger和Bjarne Stroustrup 在成书过程中提供了巨大的帮助；西点军校EF 485基地的学员测试了本书手稿的倒数第二个草稿。感谢所有人。 第二版致谢 Dan Bentley、Russ Cox、Brian Kernighan、Mark Kernighan、John Linderman、Steve McConnell、Doug McIlroy、Rob Pike、Howard Trickey和Chris Van Wyk仔细阅读了本书第二版。我还要感谢以下诸位提出的宝贵意见：Paul Abrahams、Glenda Childress、Eric Grosse、Ann Martin、Peter McIlroy、Peter Memishian、Sundar Narasimhan、Lisa Ricker、Dennis Ritchie、Ravi Sethi、Carol Smith、Tom Szymanski和Kentaro Toyama。感谢Peter Gordon以及他在Addison-Wesley的同事，他们为这一版的出版提供了许多帮助。