多年以来,当程序员们推选出最心爱的计算机图书时,《编程珠玑》总是位于前列。正如自然界里珍珠出自细沙对牡蛎的磨砺,计算机科学大师Jon Bentley以其独有的洞察力和创造力,从磨砺程序员的实际问题中凝结出一篇篇不朽的编程“珠玑”,成为世界计算机界名刊《ACM通讯》历史上最受欢迎的专栏,最终结集为两部不朽的计算机科学经典名著,影响和激励着一代又一代程序员和计算机科学工作者。本书为第一卷,主要讨论计算机科学中最本质的问题:如何正确选择和高效地实现算法。
在书中,作者选取许多具有典型意义的复杂编程和算法问题,生动描绘了历史上众大师们在探索解决方案中发生的轶事、走过的弯路和不断精益求精的历程,引导读者像真正的程序员和软件工程师那样富于创新性地思考,并透彻阐述和总结了许多独特而精妙的设计原则、思考和解决问题的方法以及实用程序设计技巧。解决方案的代码均以C/C++语言编写,不仅有趣,而且有很大的实战示范意义。每章后所附习题极具挑战性和启发性,书末给出了简洁的解答。
历史上最伟大的计算机科学著作之一
融深邃思想、实战技术与趣味轶事于一炉的奇书
带你真正领略计算机科学之美
计算机编程充满乐趣,有时候,它又是一门优雅的科学,还要靠它去开发和使用新的软件工具。编程与人息息相关:客户实际想解决什么问题?如何让用户容易与程 序沟通?是编程让我接触到相当广泛的话题,从有机化学到拿破仑战争。本书描述了编程的所有这些方面的知识,而且远不止这些。
这是一部短文集,每篇短文独立成章,但所有短文又依据逻辑分成了几组。第1章至第4章描述操纵程序的技术;第5章至第8章给出了一些程序员的实用技巧,这是本书技术性最低的部分;第9章至第12章讲解输入和输出设计;第13章至第15章介绍了3个有用的子程序。这些分类主题在每个部分的引言中进行了 详细说明。
本书大多数章都是以我在《ACM通讯》杂志中的“编程珠玑”(Programming Pearls)专栏文章为基础的。各部分的引言中描述了这些文章的发表历史。既然已经发表过,为什么我还要费劲写这本书呢?自首次发表以来,这些专栏文章 发生了很大变化,有了数千处小改进:有了新的问题和解决方案,纠正了小错误,并采纳了很多读者的意见。与此同时,我删除了一些旧的内容以免重复,并加入了 很多新的内容,其中有一章是全新的。
然而,写本书的最大理由是,我想把各章组成一个有机的整体,我想展示一整串珠玑。我1986年出版的《编程珠玑》是类似的13篇短文的结集,围绕性能 这个中心主题来组织,该主题在最早两年的《ACM通讯》专栏中占据了突出位置。本书中也有几章再次谈及效率的话题,但全书考察的编程领域范围要大得多。
读者阅读本书时不要太快,一次一章,仔细地读。试解一下书中提出的问题——有些问题并不像看起来那样容易。有些章末尾的“深入阅读”并不是学术意义上的参考文献列表,而是我推荐的一些好书,这些书是我个人藏书的重要部分。
我很高兴能借此机会感谢许多人所作的重要贡献。Al Aho、Peter Denning、Brian Kernighan和Doug McIlroy对各章提出了详细意见。我还要感谢以下诸位提出有益的见解:Bill Cleveland、Mike Garey、Eric Grosse、Gerard Holzmann、Lynn Jelinski、David Johnson、Arno Penzias、Ravi Sethi、Bjarne Stroustrup、Howard Trickey和Vic Vyssotsky。感谢允许我引用他们信件的几个人,特别是Peter Denning、Bob Floyd、Frank Starmer、Vic Vyssotsky和Bruce Weide。我特别要感谢ACM鼓励我把专栏文章出版成书,还要感谢《ACM通讯》的许多读者,他们对原始专栏文章提出了不少意见,使得本书这个扩充版本 的出版十分必要。贝尔实验室(特别是其计算科学研究中心)在我写这些专栏文章时,提供了极佳的支持环境。感谢所有的人。
Jon Bentley
于新泽西州Murray Hill
作者简介
Jon Bentley
世界著名计算机科学家,被誉为影响算法发展的十位大师之一。他先后任职于卡内基-梅隆大学(1976~1982)、贝尔实验室(1982~2001)和Avaya实验室(2001年至今)。在卡内基-梅隆大学担任教授期间,他培养了包括Tcl语言设计者John Ousterhout、Java语言设计者James Gosling、《算法导论》作者之一Charles Leiserson在内的许多计算机科学大家。2004年荣获Dr. Dobb's程序设计卓越奖。
译者简介
黄倩
工学博士,中国计算机学会高级会员,先后就读于南京大学、中国科学院计算技术研究所,先后工作于联发博动科技(北京)有限公司、河海大学计算机与信息学院。主要从事视频处理、机器学习方面的研究工作,获国家自然科学基金资助1项,发表论文十余篇。
钱丽艳
北京大学信息科学技术学院基础实验教学研究所软件实验室主任、高级工程师、毕业于国防科技大学,目前主要从事数值计算、程序设计方面的研究工作。
本书作者Jon Bentley是美国著名的程序员和计算机科学家,他于20世纪70年代前后在很有影响力的《ACM通讯》(Communications of the ACM)上以专栏的形式连续发表了一系列短文,成功地总结和提炼了自己在长期的计算机程序设计实践中积累下来的宝贵经验。这些短文充满了真知灼见,而且文 笔生动、可读性强,对于提高职业程序员的专业技能很有帮助,因此该专栏大受读者欢迎,成为当时该学术期刊的王牌栏目之一。可以想象当时的情形颇似早年金庸 先生在《明报》上连载其武侠小说的盛况。后来在ACM的鼓励下,作者经过仔细修订和补充整理,对各篇文章的先后次序做了精心编排,分别在1986年和 1988年结集出版了Programming Pearls(《编程珠玑》)和More Programming Pearls(《编程珠玑(续)》)这两本书,二者均成为该领域的名著。《编程珠玑(第2版)》在2000年问世,书中的例子都改用C语言书写,并多处提 到如何用C++和Java中的类来实现。《编程珠玑(续)》虽未再版,例子多以Awk语言写成,但其语法与C相近,容易看懂。
作者博览群书,旁征博引,无论是计算机科学的专业名著,如《计算机程序设计艺术》,还是普通的科普名著,如《啊哈!灵机一动》,都在作者笔下信手拈 来、娓娓道出,更不用说随处可见的作者自己的真知灼见了。如果说《计算机程序设计艺术》这样的巨著代表了程序员们使用的“坦克和大炮”一类的重型武器,这 两本书则在某种程度上类似于鲁迅先生所说的“匕首与投枪”一类的轻型武器,更能满足职业程序员的日常需要。或者说前者是武侠小说中提高内力修为的根本秘 籍,后者是点拨临阵招数的速成宝典,二者同样都是克敌制胜的法宝,缺一不可。在无止境地追求精湛技艺这一点上,程序员、数学家和武侠们其实是相通的。
在美国,这两本书不仅被用作大学低年级数据结构与算法课程的教材,还用作高年级算法课程的辅助教材。例如,美国著名大学麻省理工学院的电气工程与计算 机科学开放式核心课程算法导论就将这两本书列为推荐读物。这两本书覆盖了大学算法课程和数据结构课程的大部分内容,但是与普通教材的侧重点又不一样,不强 调单纯从数学上来进行分析的技巧,而是强调结合实际问题来进行分析、应用和实现的技巧,因此可作为大学计算机专业的算法、数据结构、软件工程等课程的教师 参考用书和优秀课外读物。书中有许多真实的历史案例和许多极好的练习题以及部分练习题的提示与解答,非常适合自学。正如作者所建议的那样,阅读这两本书 时,读者需要备有纸和笔,最好还有一台计算机在手边,边读边想、边想边做,这样才能将阅读这两本书的收益最大化。
人民邮电出版社引进版权,同时翻译出版了《编程珠玑(第2版)》和《编程珠玑(续)》,使这两个中译本珠联璧合,相信这不仅能极大地满足广大程序员读者的需求,还有助于提高国内相关课程的授课质量和学生的学习兴趣。
本书主要由黄倩和钱丽艳翻译,刘田审校,翻译过程中得到了张怀勇先生的帮助,在此表示感谢。由于本书内容深刻,语言精妙,而译者的水平和时间都比较有限,错误和不当之处在所难免,敬请广大读者批评指正。