2019年6月16日23:27:3051.5K

摘要

在书中，作者选取许多具有典型意义的复杂编程和算法问题，生动描绘了历史上众大师们在探索解决方案中发生的轶事、走过的弯路和不断精益求精的历程，引导读者像真正的程序员和软件工程师那样富于创新性地思考，并透彻阐述和总结了许多独特而精妙的设计原则、思考和解决问题的方法以及实用程序设计技巧。解决方案的代码均以C/C++语言编写，不仅有趣，而且有很大的实战示范意义。每章后所附习题极具挑战性和启发性，书末给出了简洁的解答。

编程珠玑（第2版 修订版） 内容简介

《编程珠玑（第2版·修订版）》是计算机科学方面的经典名著。书的内容围绕程序设计人员面对的一系列实际问题展开。作者JonBentley以其独有的洞察力和创造力，引导读者理解这些问题并学会解决方法，而这些正是程序员实际编程生涯中至关重要的。本书的特色是通过一些精心设计的有趣而又颇具指导意义的程序，对实用程序设计技巧及基本设计原则进行了透彻而睿智的描述，为复杂的编程问题提供了清晰而完备的解决思路。《编程珠玑（第2版·修订版）》对各个层次的程序员都具有很高的阅读价值。

编程珠玑（第2版 修订版） 目录

第一部分　基础

第1章　开　篇

1．1　一次友好的对话

1．2　准确的问题描述

1．3　程序设计

1．4　实现概要

1．5　原理

1．6　习题

1．7　深入阅读

第2章　啊哈！算法

2．1　三个问题

2．2　处不在的二分搜索

2．3　基本操作的威力

2．4　排序

2．5　原理

2．6　习题

2．7　深入阅读

2．8　变位词程序的实现（边栏）

第3章　数据决定程序结构

3．1　一个调查程序

3．2　格式信函编程

3．3　一组示例

3．4　结构化数据

3．5　用于特殊数据的强大工具

3．6　原理

3．7　习题

3．8　深入阅读

第4章　编写正确的程序

4．1　二分搜索的挑战

4．2　编写程序

4．3　理解程序

4．4　原理

4．5　程序验证的角色

4．6　习题

4．7　深入阅读

第5章　编程小事

5．1　从伪代码到C程序

5．2　测试工具

5．3　断言的艺术

5．4　自动测试

5．5　计时

5．6　完整的程序

5．7　原理

5．8　习题

5．9　深入阅读

5．10　调试（边栏）

第二部分　性能

第6章　程序性能分析

6．1　实例研究

6．2　设计层面

6．3　原理

6．4　习题

6．5　深入阅读

第7章　粗略估算

7．1　基本技巧

7．2　性能估计

7．3　安全系数

7．4　Little定律

7．5　原理

7．6　习题

7．7　深入阅读

7．8　日常生活中的速算（边栏）

第8章　算法设计技术

8．1　问题及简单算法

8．2　两个平方算法

8．3　分治算法

8．4　扫描算法

8．5　实际运行时间

8．6　原理

8．7　习题

8．8　深入阅读

第9章　代码调优

9．1　典型的故事

9．2　急救方案集锦

9．3　大手术--二分搜索

9．4　原理

9．5　习题

9．6　深入阅读

第10章　节省空间

10．1　关键在于简单

10．2　示例问题

10．3　数据空间技术

10．4　代码空间技术

10．5　原理

10．6　习题

10．7　深入阅读

10．8　巨大的节省（边栏）

第三部分　应用

第11章　排　序

11．1　插入排序

11．2　一种简单的快速排序

11．3　更好的几种快速排序

11．4　原理

11．5　习题

11．6　深入阅读

第12章　取样问题

12．1　问题

12．2　一种解决方案

12．3　设计空间

12．4　原理

12．5　习题

12．6　深入阅读

第13章　搜　索

13．1　接口

13．2　线性结构

13．3　二分搜索树

13．4　用于整数的结构

13．5　原理

13．6　习题

13．7　深入阅读

13．8　一个实际搜索问题（边栏）

第14章　堆

14．1　数据结构

14．2　两个关键函数

14．3　优先级队列

14．4　一种排序算法

14．5　原理

14．6　习题

14．7　深入阅读

第15章　字符串

15．1　单词

15．2　短语

15．3　生成文本

15．4　原理

15．5　习题

15．6　深入阅读

第1版跋

第2版跋

附录A　算法分类

附录B　估算测试

附录C　时空开销模型

附录D　代码调优法则

附录E　用于搜索的C++类

部分习题提示

部分习题答案

索引

编程珠玑（第2版 修订版） 精彩文摘

这一部分的5章回顾程序设计的基础知识。第1章介绍一个问题的历史，我们把仔细的问题定义和直接的程序设计技术结合起来，得到优美的解决方案。这一章揭示了本书的中心思想：对实例研究的深入思考不仅很有趣，而且可以获得实际的益处。

第2章讨论3个问题，其中重点强调了如何由算法的融会贯通获得简单而高效的代码。第3章总结数据结构在软件设计中所起到的关键作用。

第4章介绍一个编写正确代码的工具——程序验证。在第9章、第11章和第14章中生成复杂（且快速）的函数时，大量使用了程序验证技术。第5章讲述如何把这些抽象的程序变成实际代码：使用脚手架程序来探测函数，用测试用例来测试函数并度量函数的性能。

本部分内容

第1章 开篇

第2章 啊哈！算法

第3章 数据决定程序结构

第4章 编写正确的程序

第5章 编程小事

一位程序员曾问我一个很简单的问题：“怎样给一个磁盘文件排序？”想当年我是一上来就犯了错误，现在，在讲这个故事之前，先给大家一个机会，看看能否比我当年做得更好。你会怎样回答上述问题呢？

我错就错在马上回答了这个问题。我告诉他一些有关如何在磁盘上实现归并排序的简要思路。我建议他深入研究算法教材，他似乎不太感冒。他更关心如何解决这个问题，而不是深入学习。于是我告诉他在一本流行的程序设计书里有磁盘排序的程序。那个程序有大约200行代码和十几个函数，我估计他很多需要一周时间来实现和测试该代码。

我以为已经解决了他的问题，但是他的踌躇使我返回到了正确的轨道上。其后就有了下面的对话，楷体部分是我的问题。

为什么非要自己编写排序程序呢？为什么不用系统提供的排序功能呢？

我需要在一个大系统中排序。由于不明的技术原因，我不能使用系统中的文件排序程序。

需要排序的内容是什么？文件中有多少条记录？每条记录的格式是什么？

文件很多包含1千万条记录，每条记录都是7位的整数。

等一下，既然文件这么小，何必非要在磁盘上进行排序呢？为什么不在内存里进行排序呢？

尽管机器有许多兆字节的内存，但排序功能只是大系统中的一部分，所以，估计到时只有1 MB的内存可用。

你还能告诉我其他一些与记录相关的信息吗？

每条记录都是7位的正整数，再无其他相关数据。每个整数很多只出现一次。

这番对话让问题更明确了。在美国，电话号码由3位“区号”后再跟7位数字组成。拨打含“免费”区号800（当时只有这一个号码）的电话是不收费的。实际的免费电话号码数据库包含大量的信息：免费电话号码、呼叫实际中转到的号码（有时是几个号码，这时需要一些规则来决定哪些呼叫在什么时间中转到哪里）、主叫用户的姓名和地址等。

这位程序员正在开发这类数据库的处理系统的一小部分，需要排序的整数就是免费电话号码。输入文件是电话号码的列表（已删除所有其他信息），号码重复出现算出错。期望的输出文件是以升序排列的电话号码列表。应用背景同时定义了相应的性能需求。当与系统的会话时间较长时，用户大约每小时请求一次有序文件，并且在排序未完成之前什么都干不了。因此，排序很多只允许执行几分钟，10秒钟是比较理想的运行时间。

对程序员来说，这些需求加起来就是：“如何给磁盘文件排序？”在试图解决这个问题之前，先将已知条件组织成一种更客观、更易用的形式。

输入：一个很多包含 n 个正整数的文件，每个数都小于 n，其中 n=107。如果在输入文件中有任何整数重复出现就是致命错误。没有其他数据与该整数相关联。

输出：按升序排列的输入整数的列表。

约束：很多有（大约）1 MB的内存空间可用，有充足的磁盘存储空间可用。运行时间很多几分钟，运行时间为10秒就不需要进一步优化了。

请花上一分钟思考一下该问题的规范说明。现在你打算给程序员什么样的建议呢？

显而易见的方法是以一般的基于磁盘的归并排序程序为起点，但是要对其进行调整，因为我们是对整数进行排序。这样就可以将原来的200行程序减少为几十行，同时也使得程序运行得更快，但是完成程序并使之运行可能仍然需要几天的时间。

另一种解决方案更多地利用了该排序问题的特殊性。如果每个号码都使用7个字节来存储，那么在可用的1 MB存储空间里大约可以存143 000个号码。如果每个号码都使用32位整数来表示的话，在1 MB存储空间里就可以存储250 000个号码。因此，可以使用遍历输入文件40趟的程序来完成排序。在第一趟遍历中，将0至249 999之间的任何整数都读入内存，并对这（很多）250 000 个整数进行排序，然后写到输出文件中。第二趟遍历排序250 000至499 999之间的整数，依此类推，到第40趟遍历的时候对9 750 000至9 999 999之间的整数进行排序。对内存中的排序来说，快速排序会相当高效，而且仅仅需要20 行代码（见第11章）。于是，整个程序就可以通过一两页纸的代码实现。该程序拥有所期望的特性——不必考虑使用中间磁盘文件；但是，为此所付出的代价是要读取输入文件40次。

归并排序读入输入文件一次，然后在工作文件的帮助下完成排序并写入输出文件一次。工作文件需要多次读写。

40趟算法读入输入文件多次，写输出文件仅一次，不使用中间文件。