编程珠玑(英文影印版.第2版)（计算机科学的不朽经典）

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

part i: preliminaries　1
column 1: cracking the oyster　3
a friendly conversation·precise problem statement·program design·implementation sketch·principles·problems·further reading
column 2: aha! algorithms　11
three problems·ubiquitous binary search·the power of primitives·getting it together: sorting·principles·problems·further reading·implementing an anagram program
column 3: data structures programs　21
a survey program·form-letter programming·an array of examples·structuring data·powerful tools for specialized data·principles·problems·further reading
column 4: writing correct programs　33
the challenge of binary search·writing the program·understanding the program·principles·the roles of program verification·problems·further reading
column 5: a small matter of programming　45
from pseudocode to c·a test harness·the art of assertion·automated testing·timing·the complete program·principles·problems·further reading·debugging
part ii: performance　59
column 6: perspective on performance　61
a case study·design levels·principles·problems·further reading
column 7: the back of the envelope　67
basic skills·performance estimates·safety factors·little's law·principles·problems·further reading·quick calculations in everyday life
column 8: algorithm design techniques　77
the problem and a simple algorithm·two quadratic algorithms·a divide-and-conquer algorithm·a scanning algorithm·what does it matter?·principles·problems·further reading
column 9: code tuning　87
a typical story·a first aid sampler·major surgery——binary search·principles·problems·further reading

　　计算机编程有很多方面。Fred Brooks在《人月神话》一书中为我们描绘了全景，他的文章强调了管理在大型软件项目中所起的关键作用。而Steve McConnell在《代码大全》一书中更具体地传授了良好的编程风格。这两本书所讨论的是好软件的关键因素和专业程序员应有的特征。遗憾的是，仅仅熟练地运用这些可靠的工程原理，不见得一定能够如期完成软件并顺利运行。
　　关于本书
　　本书描述了计算机编程更具魅力的一面：在可靠的工程之外，在洞察力和创造力范围内结晶而出的编程珠玑。正如自然界中的珍珠来自于磨砺牡蛎的细沙一样，这些编程珠玑来自于磨砺程序员的实际问题。书中的程序都很有趣，传授了重要的编程技巧和基本的设计原理。
　　本书大部分内容最初发表在《ACM通讯》中我主持的“编程珠玑”专栏。这些内容经过汇总和修订，在1986年结集出版，成为了本书的第1版。第1版的13篇文章中，有12篇都在本版中做了大幅修订；此外，本版还补充了3篇新的内容。
　　阅读本书只需要读者具有某种高级语言的编程经验。书中偶尔会出现一些高级技术(如C++中的模板等)，对此不熟悉的读者可以跳过这些内容，基本上不影响阅读。
　　本书每一章都独立成篇，各章之间却又有着逻辑分组。第1章至第5章构成本书的第一部分，这部分回顾了编程的基本原理：问题定义、算法、数据结构以及程序验证和测试。第二部分围绕效率这个主题展开。效率问题有时本身就很重要，又永远都是进入有趣编程问题的绝佳跳板。第三部分用这些技术来解决排序、搜索和字符串等重要问题。
　　阅读本书的一个提示：不要读得太快。要仔细阅读，一次读一章。要尝试解答书中提出的问题——有些问题需要集中精力思考一两个小时才会想清楚。然后，要努力解答每章末尾的习题：当读者写下答案时，从本书学到的大部分知识就会跃然纸上。如有可能，要先与朋友和同事讨论一下自己的思路，再去查阅本书末尾的提示和答案。每章末尾的“深入阅读”并不算是学术意义上的参考文献表，而只是我个人推荐的一些好书，我自己就收藏了这些书。
　　本书是为程序员而写的。我希望书中的习题(problems)、提示(hints)、答案(solutions)和深入阅读(further reading)对每个人都有用。本书已用作算法、程序验证和软件工程等课程的教材。附录A中的算法分类可供实际编程人员参考，该附录同时还说明了如何在算法和数据结构课程中使用本书。
　　代码
　　本书第1版中的伪代码程序其实都已实现，但当时未公开。在本版中，我重写了所有的老程序，并且编写了差不多等量的新代码。这些程序可以在http：／／netlib．bell-labs．com／cm／cs／pearls／下载。代码中包含许多对函数进行测试、调试和计时的脚手架程序。该网站还提供了其他相关的材料。由于现在许多软件都能在线获得，因此本版的一个新增内容就是：如何评估和使用软件组件。
　　本书的程序采用了简洁的代码风格：短变量名，很少空行，很少或没有错误检测。这种风格不适用于大型软件项目，却有助于表达算法的核心思想。第5章第1个习题的答案详细介绍了这种风格。
　　本书包含几个实际的C和C++程序，其余大多数函数都用伪代码来表示，这样既节省了空间，又避免了繁琐的语法。记号for i=[0，n)表示在从0至n—1的范围内对i进行迭代。在这类for循环中，左圆括号和右圆括号代表开区间(不包括端点值)，而左方括号和右方括号代表闭区间(包括端点值)。表达式function(i,j)仍表示用参数i和j调用函数，而array[i,j]仍表示访问数组元素。
　　本版所提供的许多程序的运行时间都基于“我的电脑”——一台128MB内存、运行Windows NT 4．0操作系统的400 MHz Pentium II。我测试了这些程序在其他几台机器上的运行时间，书中记录了我观察到的一些显著的差异。所有的实验都使用了最高级别的编译器优化。建议读者在自己的计算机上对这些程序计时，我敢打赌读者将会发现相似比率的运行时间。
　　致第1版的读者
　　我希望你们在翻阅本版时的第一感觉是“看起来很眼熟啊”，而过几分钟又得出结论：“以前从来没读过。”
　　本版与第1版主题相同，但涉及的范围更广。计算技术已经在数据库、网络和用户界面等重要领域取得了长足的进展。大多数程序员应当都熟悉这些技术。但是，这些领域的中心仍然是那些核心编程问题，这些问题仍然是本书的主题。相对于第1版而言，本版可以比喻为一条稍微长大了的鱼，游进了一个大得多的池塘。
　　第1版第4章关于实现二分搜索的一节内容经过扩充成为了本版中关于测试、调试和计时的第5章。第1版第11章经过扩充，在本版中分成了第12章(还讨论原来的问题)和第13章(讨论集合表示)。第1版第13章描述的在64KB地址空间运行的拼写检查器已被删除，但其要点仍保留在13．8节中。新增的第15章讨论字符串问题。本版在第1版的各章中插入了许多新节，同时删除了一些旧节。新增的习题、答案以及4个附录使得本版篇幅比第1版增加了25％。
　　本版保留了许多原有的实例研究，因为它们具有历史价值。有些老故事则用现代术语做了改写。
　　第1版的致谢
　　对许多人给予我的诸多帮助，我一直心存感激。Peter Denning和Stuart Lynn最早设想在《ACM通讯》上开设专栏。Peter在计算机学会(ACM)内做了大量的工作，促成了该专栏，并动员我来主持这个专栏。ACM总部的员工(特别是Roz Steier和Nancy Adriance)在本书各篇文章最初发表时给予了大力协助。我要特别感谢ACM鼓励我以目前这种经过修订的形式来出版各篇文章，还要特别感谢《ACM通讯》的众多读者，他们对原始各篇文章的反馈意见使得这个扩充版本既有必要，又成为可能。

　　“《编程珠玑》第1版是对我职业生涯早期影响最大的一本书，其中的许多真知灼见多年之后仍然使我受益匪浅。Jon在第2版中对素材进行了大量更新，许多新内容让我耳目一新。”
　　——Steve McConnell， 《代码大全》作者
　　“对每一位遇到的程序员，我都会毫不迟疑地建议他阅读并不断重读这部经典之作。”
　　——Slashdot