前言

数据结构与算法不仅仅是抽象概念。精通它们可以让你写出高效的代码，从而让软件运行得更快，占用的内存更少。这对于如今的软件应用非常重要，因为它们存在于更加移动化的平台，并且要处理更多的数据。

但这一主题的大部分资料有一个通病——晦涩难懂。大多数教材使用了很多数学术语。如果你不是数学家，那么就很难明白它们到底在说什么。即便那些声称让算法学习更加“简单”的书，好像也都假定读者学过高深的数学知识。很多人因此避开了这些概念。他们觉得自己还不够“聪明”，无法理解它们。

然而事实上，数据结构与算法都可以归结于常识。数学符号只是一种特定语言，所有数学知识都能用常识去解释。在本书中，我将用常识（以及很多图表）来解释这些概念。我保证这样学习起来既简单又轻松。

一旦理解了概念，你就能写出高效、快速并且优雅的代码。你可以比较不同代码的优劣，还能合理判断特定情况下的最优解。

在本书中，我特地用更实际的方式来解释概念，还介绍了你立刻就可以利用的一些思想。你当然能从书中学到计算机科学知识，但本书旨在让看似抽象的概念变得更切实际。读完本书后，你将能编写出更好的代码和更快速的软件。

目标读者

本书适合以下读者。

• 计算机科学专业的学生，想要一本用简洁语言解释数据结构与算法的教材。本书可以作为你目前使用的“经典”教材的补充。
• 有编程基础的初级开发者，想要学习计算机科学基础，拓展编程知识和技巧，以提高编码水平。
• 自学编程的开发者，未受过正规计算机科学教育（或者学过但是忘光了），想要借助数据结构与算法的力量让代码更优雅、更具扩展性。

无论你的水平如何，我都力求让你能理解并享受本书。

新增内容

在英文版上一版出版后的几年里，我曾给不同的受众讲授书中的内容。在此过程中，我不断地优化自己的阐述，也发现了一些有趣而重要的新内容。而且也有人提出需要习题来实践这些概念。

因此本书新增了如下内容。

• 上一版内容修正。为了叙述更清晰，我对上一版内容做了很多修改。尽管上一版确实让这些复杂主题易于理解，我发现仍有改进的空间。

  上一版章节中的许多小节在本书中已经完全重写，并且添加了一些全新的内容。我觉得光是这些改动就值得出版新版了。

   

• 新章节和新主题。本书新增了6章内容，介绍了一些我特别感兴趣的主题。

  本书一直注重理论与实践的结合，但我又加入了更多你可以直接投入实践的内容。第7章和第20章这两章专注于日常代码，教你如何使用数据结构与算法知识写出更高效的软件。

  我在“递归”这一主题上使出了浑身解数。尽管上一版有一章介绍的是递归，但我又增加了全新的一章（第11章）来介绍如何编写递归代码。编写递归代码可能会困扰初学者，第11章会教你如何去做。据我所知没有人写过这一主题，所以我觉得这一章既独特又有价值。第12章也是新增的，“动态规划”这一主题很受欢迎，也是提高递归代码效率的关键。

  数据结构的种类很多，我很难抉择应该介绍哪些。不过，学习堆和字典树的需求与日俱增，我也觉得它们很神奇，因此增加了第16章和第17章。

   

• 习题和答案。本书每章末尾都有习题，你可以用它们来实践书中的内容。书末的附录中提供了详细解答。这两个重要改动让本书的学习体验更加完整。

本书内容

正如你所想的那样，本书讲解了很多数据结构和算法。具体来说，结构如下。

第1章和第2章，解释什么是数据结构和算法，并探索时间复杂度这一判断算法效率的概念。在此过程中，我还会提到数组、集合以及二分查找。

第3章，用便于理解的方式介绍大O记法。大O记法的使用贯穿全书，因此这一章非常重要。

第4章、第5章和第6章，进一步学习大O记法，用它来给日常代码提速。在此过程中，我会介绍不同的排序算法，比如冒泡排序、选择排序和插入排序。

第7章，应用所学知识来分析真实代码的效率。

第8章和第9章，讨论另外几个数据结构，比如哈希表、栈和队列。我将展示它们对代码速度和优雅程度的影响，以及如何使用它们解决实际问题。

第10章，介绍递归这一计算机科学的核心概念。我们会在这一章中分析递归，学习它在特定情况下的重要价值。第11章会讲述如何编写递归代码，让你免于困惑。

第12章，展示优化递归代码、防止其失控的方法。第13章会展示如何用递归实现快速排序或是快速选择这样飞快的算法，提升你的算法开发能力。

接下来的几章，即第14章、第15章、第16章、第17章和第18章，介绍链表、二叉查找树、堆、字典树、图等基于节点的数据结构，以及它们各自的适用场景。

第19章，介绍空间复杂度。当设备磁盘空间相对较小，或是要处理大数据时，这一概念尤为重要。

最后一章，即第20章，介绍优化代码效率的各种实用技巧，并为改进日常代码提供新思路。

如何阅读本书

你需要按顺序阅读本书。有些书的某些章节可以单独翻阅或是跳过，但本书不行。本书中每一章的内容都需要前面的章节作为前置，而且本书的结构也经过巧妙设计，使得你可以一边阅读，一边加深理解。

话虽这么说，后半部分的某些章并不互相依赖。下一页的图描述了各章间的依赖关系。

如果你想的话，那么确实可以跳过第10~13章。（哦！下一页的这幅图就是基于树这一数据结构。第15章会对该图进行介绍。）

还有一点很重要：为了让本书易于理解，在首次介绍某个概念时，我不会一下子全部解释清楚。有时，分析一个复杂概念的最佳方法就是循序渐进，理解了一部分之后再介绍下一部分。如果我定义了一个术语，那么在你学习完这个主题前，请先不要把它当作正式定义。

这样做有利也有弊。为了让本书更好懂，我会先过度简化某些概念，然后再慢慢解释，而不是确保每句话在学术意义上都完全正确。但也不用太担心，因为最后你肯定能得到全面且准确的解释。

代码示例

本书中的概念并不局限于特定编程语言。因此我选择用多种语言来展示书中的例子。这些语言包括Ruby、Python和JavaScript。如果你对这些语言有基本的认识就再好不过了。

尽管如此，我还是试着在编写示例时遵循一条原则：即便你不熟悉这个例子所用的语言，应该也能看懂。为了达到这一目的，我没有严格遵循每种语言最受欢迎的编程范式，因为某些范式可能会让新接触那种语言的人感到困惑。

我明白一本不停切换语言的书会带来一定程度的思维转换成本。不过，我觉得保持一本书在语言上的不可知性是很重要的。而且无论是什么语言，我都会试着让代码方便阅读和理解。

在“代码实现”小标题下有一些长一点儿的代码片段。我当然希望你学习这些示例，但要阅读下一部分并不需要理解每一行代码。如果这些较长的代码对你造成障碍，那么就暂时跳过（或者略读）。

最后还有一点很重要：不是每个代码片段都“适用于生产环境”。重点在于解释清楚当前的概念。尽管我确实尝试让代码尽量完整，还是可能漏掉一些边界情况。肯定有一些地方能让你做进一步优化，因此你可以尽情去做。

在线资源

本书网址是https://pragprog.com/titles/jwdsal2，你可以在上面找到本书的更多信息。还可以提交勘误，比如内容上的建议或者拼写错误，来帮助改进本书。1

1也可以通过图灵社区本书主页下载示例代码或提交中文版勘误。——编者注

更多信息

扫描下方二维码，即可获取电子书相关信息及读者群通道入口。

致谢

虽然写书这件事看起来好像是一个人的工作，但是如果没有一路支持我的这么多人，本书就不可能付梓。感谢你们所有人。

感谢我美丽的妻子Rena，感谢你一路相伴，给予我情感上的支持。当我像个隐士一样躲在黑暗中写作时，你处理好了所有事情。感谢我可爱的孩子们：Tuvi、Leah、Shaya和Rami。感谢你们在我写这本“酸法”书时展现的耐心。没错，我终于写完了。

感谢我的父母：Howard Wengrow 先生和Debbie Wengrow 夫人。感谢你们激发我对计算机编程的兴趣，并帮助我一路前行。你们可能不知道，正是因为你们在我9岁生日时帮我请了一位计算机家教，我才能走上这条职业道路，并且写出本书。

感谢我妻子的父母：Paul Pinkus先生和Kreindel Pinkus夫人。感谢你们对我和我的家人一如既往的支持。你们的智慧和热情对我来说意义非凡。

当第一次把书稿提交给Pragmatic Bookshelf出版公司时，我自以为写得很好。但出版公司优秀的工作人员提出的建议以及需求让本书变得更加出色，远超我自己所能。感谢我的编辑Brian MacDonald，你教会了我正确的写书方式。你的见解让每个章节都变得更深刻。书中到处都能看到你付出的心血。感谢原主编Susannah Pfalzer和执行编辑Dave Rankin，你们让我看到了本书的潜力，帮我把基于理论的书稿打造成一本适合普通程序员的书。感谢发行人Andy Hunt和Dave Thomas，感谢你们让Pragmatic Bookshelf成为最棒、作者最愿意合作的出版公司，也感谢你们相信本书。

感谢天赋异禀的软件开发者和艺术家Colleen McGuckin，感谢你把我拙劣的草图变成美丽的数字图像。你凭借高超的画技和对细节的追求创作出了非凡的图画。要是没有它们，本书肯定一文不值。

有许多专家对本书进行了评审，我感到非常幸运。你们的反馈非常到位，让本书的内容变得尽可能准确。我要感谢你们对本书做出的贡献。

第1版的评审人如下：Alessandro Bahgat、Ivo Balbaert、Alberto Boschetti、Javier Collado、Mohamed Fouad、Derek Graham、Neil Hainer、Peter Hampton、Rod Hilton、Jeff Holland、Jessica Janiuk、Aaron Kalair、Stephan Kämper、Arun S. Kumar、Sean Lindsay、Nigel Lowry、Joy McCaffrey、Daivid Morgan、Jasdeep Narang、Stephen Orr、Kenneth Parekh、Jason Pike、Sam Rose、Frank Ruiz、Brian Schau、Tibor Simic、Matteo Vaccari、Stephen Wolff和Peter W. A. Wood。

第2版的评审人如下：Rinaldo Bonazzo、Mike Browne、Craig Castelaz、Jacob Chae、Zulfikar Dharmawan、Ashish Dixit、Dan Dybas、Emily Ekhdal、Derek Graham、Rod Hilton、Jeff Holland、Grant Kazan、Sean Lindsay、Nigel Lowry、Dary Merckens、Kevin Mitchell、Nouran Mhmoud、Daivid Morgan、Brent Morris、Emanuele Origgi、Jason Pike、Ayon Roy、Brian Schau、Mitchell Volk和Peter W. A. Wood。

除了正式的评审人，还要感谢那些在我创作过程中，对书稿提出建议的读者。你们的建议、评价和问题都是无价之宝。

还要感谢Actualize所有的职员、学生和校友的支持。本书原本是Actualize的一个项目，你们都曾通过不同方式参与其中。最后，特别感谢Luke Evans为我提供了创作本书的灵感。

感谢以上所有人让本书得以出版。

联系方式

我喜欢和读者联系，并且诚挚邀请你们在LinkedIn上联系我。我很乐意通过你们的好友请求——只要发信息说你是本书读者就行。我期待听到你们的感想。

杰伊·温格罗
jay@actualize.co
2020年5月