秒懂算法：用常识解读数据结构与算法 ([美] 杰伊•温格罗 (Jay Wengrow))（Z-Library）

图灵社区的电子书没有采用专有客 户端，您可以在任意设备上，用自 己喜欢的浏览器和PDF阅读器进行 阅读。 但您购买的电子书仅供您个人使用， 未经授权，不得进行传播。 我们愿意相信读者具有这样的良知 和觉悟，与我们共同保护知识产权。 如果购买者有侵权行为，我们可能 对该用户实施包括但不限于关闭该 帐号等维权措施，并可能追究法律 责任。

内 容 提 要 本书是简单易懂的数据结构与算法入门书。作者略过复杂的数学公式，用“通俗讲解 × 逐步图示 × 代码实现”的方式介绍了数据结构与算法的基本概念，培养读者的算法思维。全书共有 20 章。读者将了 解数据结构与算法为何如此重要，如何快速使用大 O 记法判断代码的运行效率，以及如何用动态规划优 化算法。本书的重点内容包括冒泡排序、选择排序、插入排序等排序算法，以及深度优先搜索、广度优 先搜索、迪杰斯特拉算法等图算法。在学习算法的过程中，读者也将通晓数组、哈希表、栈、队列、链表、 图等常用数据结构的适用场景。 本书适合初级和中级程序员阅读，不局限于某一种编程语言。 定价：99.80元 读者服务热线：(010)84084456-6009　印装质量热线：(010)81055316 反盗版热线：(010)81055315 广告经营许可证：京东市监广登字 20170147 号 著　　　　[美] 杰伊 • 温格罗（Jay Wengrow） 译　　　　姜　喆 责任编辑　张海艳 责任印制　彭志环 人民邮电出版社出版发行　　北京市丰台区成寿寺路11号 邮编　100164　　电子邮件　315@ptpress.com.cn 网址　https://www.ptpress.com.cn 北京　　　　　　印刷 开本：800×1000　1/16 印张：22.5 2022年 9 月第 1 版 字数：532千字 2022年 9 月北京第 1 次印刷 著作权合同登记号 图字：01-2021-4204号 ◆ ◆ ◆

版 权 声 明 Copyright © 2020 The Pragmatic Programmers, LLC. Original English language edition, entitled A Common-Sense Guide to Data Structures and Algorithms, Second Edition. Simplified Chinese-language edition copyright © 2022 by Posts & Telecom Press. All rights reserved. 本书中文简体字版由 The Pragmatic Programmers, LLC. 授权人民邮电出版社有限公司独家出 版。未经出版者书面许可，不得以任何方式复制或抄袭本书内容。 版权所有，侵权必究。

前 言 1 1 2 3 4 5 8 10 9 6 7 本书赞誉 如果你和我一样，在接触编程前没有受惠于“传统”的计算机科学教育，那么这本书就是一 个绝佳的帮手。它能帮助你学习算法思维的基础，以及如何使用并实现一系列常见数据结构。全 书语言清晰简洁，行文诙谐生动，尽可能少地使用专业术语。这本书非常适合那些想要学习编程 基础的人。 ——John Anderson，Infinity Interactive 技术副总裁 在 30 多年编程生涯中，我学到了一件事——始终注重基础。这本书对我来说是一个绝佳的 帮手，让我能重新确信自己过去的所有想法。对于那些未来会继续使用的核心技巧，它也能帮我 重新巩固其基础。如果你觉得这本书能帮助你通过白板测试，那么还是不要买比较好。那些测试 本来也很讨厌。买这本书是为了继续培养编程思维。无论你是处在职业生涯早期，还是像我一样 有丰富经历，都会想掌握全部数据结构，以及和它们互补的常用（甚至不常用的）算法。你甚至 还可以学到优化代码的方式、时机以及原因。你会让自己的代码成功运行，提升它的效率，并且 让它更加优雅。与此同时，你还能学到优化过程中的取舍。 ——Scott Hanselman，微软程序员、教授、博主、播主 尽管已经从事软件开发 15 年，我还是从这本书中学到了很多。要是 20 年前在大学学习这些 概念的时候就读到这本书该多好。这本书就好像让我获得了超能力，能注意到何时可以使用哈希 表优化代码的时间复杂度。忘掉代码的样子，忘掉它给你的感觉，忘掉你对它的想法，忘掉你至 今为止形成的习惯。把这些全部忘记，因为它们不能最大化代码的效率！ ——Nigel Lowry，Lemmata 首席顾问 这本书是学习数据结构和算法的绝佳资源。无论是对于动态规划等主题的通俗易懂的解释， 还是每章结尾用来检验理解的习题，这些内容对各种背景的开发者来说都是弥足珍贵的。 ——Jason Pike，KEYSYS Consulting 高级软件工程师 一本完美的算法和数据结构入门书。强烈推荐！ ——Brian Schau，Schau Consulting 首席开发者

2 前 言

前 言 1 1 2 3 4 5 8 10 9 6 7 前 言 数据结构与算法不仅仅是抽象概念。精通它们可以让你写出高效的代码，从而让软件运行得 更快，占用的内存更少。这对于如今的软件应用非常重要，因为它们存在于更加移动化的平台， 并且要处理更多的数据。 但这一主题的大部分资料有一个通病——晦涩难懂。大多数教材使用了很多数学术语。如果 你不是数学家，那么就很难明白它们到底在说什么。即便那些声称让算法学习更加“简单”的书， 好像也都假定读者学过高深的数学知识。很多人因此避开了这些概念。他们觉得自己还不够“聪 明”，无法理解它们。 然而事实上，数据结构与算法都可以归结于常识。数学符号只是一种特定语言，所有数学知 识都能用常识去解释。在本书中，我将用常识（以及很多图表）来解释这些概念。我保证这样学 习起来既简单又轻松。 一旦理解了概念，你就能写出高效、快速并且优雅的代码。你可以比较不同代码的优劣，还 能合理判断特定情况下的最优解。 在本书中，我特地用更实际的方式来解释概念，还介绍了你立刻就可以利用的一些思想。你 当然能从书中学到计算机科学知识，但本书旨在让看似抽象的概念变得更切实际。读完本书后， 你将能编写出更好的代码和更快速的软件。 目标读者 本书适合以下读者。  计算机科学专业的学生，想要一本用简洁语言解释数据结构与算法的教材。本书可以作 为你目前使用的“经典”教材的补充。  有编程基础的初级开发者，想要学习计算机科学基础，拓展编程知识和技巧，以提高编 码水平。  自学编程的开发者，未受过正规计算机科学教育（或者学过但是忘光了），想要借助数据 结构与算法的力量让代码更优雅、更具扩展性。 无论你的水平如何，我都力求让你能理解并享受本书。

2 前 言 新增内容 在英文版上一版出版后的几年里，我曾给不同的受众讲授书中的内容。在此过程中，我不断 地优化自己的阐述，也发现了一些有趣而重要的新内容。而且也有人提出需要习题来实践这些 概念。 因此本书新增了如下内容。  上一版内容修正。为了叙述更清晰，我对上一版内容做了很多修改。尽管上一版确实让 这些复杂主题易于理解，我发现仍有改进的空间。 上一版章节中的许多小节在本书中已经完全重写，并且添加了一些全新的内容。我觉得 光是这些改动就值得出版新版了。  新章节和新主题。本书新增了 6 章内容，介绍了一些我特别感兴趣的主题。 本书一直注重理论与实践的结合，但我又加入了更多你可以直接投入实践的内容。第 7 章 和第 20 章这两章专注于日常代码，教你如何使用数据结构与算法知识写出更高效的软件。 我在“递归”这一主题上使出了浑身解数。尽管上一版有一章介绍的是递归，但我又增 加了全新的一章（第 11 章）来介绍如何编写递归代码。编写递归代码可能会困扰初学 者，第 11 章会教你如何去做。据我所知没有人写过这一主题，所以我觉得这一章既独特 又有价值。第 12 章也是新增的，“动态规划”这一主题很受欢迎，也是提高递归代码效 率的关键。 数据结构的种类很多，我很难抉择应该介绍哪些。不过，学习堆和字典树的需求与日俱 增，我也觉得它们很神奇，因此增加了第 16 章和第 17 章。  习题和答案。本书每章末尾都有习题，你可以用它们来实践书中的内容。书末的附录中 提供了详细解答。这两个重要改动让本书的学习体验更加完整。 本书内容 正如你所想的那样，本书讲解了很多数据结构和算法。具体来说，结构如下。 第 1章和第 2章，解释什么是数据结构和算法，并探索时间复杂度这一判断算法效率的概念。 在此过程中，我还会提到数组、集合以及二分查找。 第 3 章，用便于理解的方式介绍大 O 记法。大 O 记法的使用贯穿全书，因此这一章非常 重要。 第 4 章、第 5 章和第 6 章，进一步学习大 O 记法，用它来给日常代码提速。在此过程中，我 会介绍不同的排序算法，比如冒泡排序、选择排序和插入排序。

前 言 3 1 2 3 4 5 8 10 9 6 7 第 7 章，应用所学知识来分析真实代码的效率。 第 8 章和第 9 章，讨论另外几个数据结构，比如哈希表、栈和队列。我将展示它们对代码速 度和优雅程度的影响，以及如何使用它们解决实际问题。 第 10 章，介绍递归这一计算机科学的核心概念。我们会在这一章中分析递归，学习它在特 定情况下的重要价值。第 11 章会讲述如何编写递归代码，让你免于困惑。 第 12 章，展示优化递归代码、防止其失控的方法。第 13 章会展示如何用递归实现快速排序 或是快速选择这样飞快的算法，提升你的算法开发能力。 接下来的几章，即第 14 章、第 15 章、第 16 章、第 17 章和第 18 章，介绍链表、二叉查找 树、堆、字典树、图等基于节点的数据结构，以及它们各自的适用场景。 第 19 章，介绍空间复杂度。当设备磁盘空间相对较小，或是要处理大数据时，这一概念尤 为重要。 最后一章，即第 20 章，介绍优化代码效率的各种实用技巧，并为改进日常代码提供新思路。 如何阅读本书 你需要按顺序阅读本书。有些书的某些章节可以单独翻阅或是跳过，但本书不行。本书中每 一章的内容都需要前面的章节作为前置，而且本书的结构也经过巧妙设计，使得你可以一边阅 读，一边加深理解。 话虽这么说，后半部分的某些章并不互相依赖。下一页的图描述了各章间的依赖关系。 如果你想的话，那么确实可以跳过第 10~13 章。（哦！下一页的这幅图就是基于树这一数据 结构。第 15 章会对该图进行介绍。） 还有一点很重要：为了让本书易于理解，在首次介绍某个概念时，我不会一下子全部解释清 楚。有时，分析一个复杂概念的最佳方法就是循序渐进，理解了一部分之后再介绍下一部分。如 果我定义了一个术语，那么在你学习完这个主题前，请先不要把它当作正式定义。 这样做有利也有弊。为了让本书更好懂，我会先过度简化某些概念，然后再慢慢解释，而不 是确保每句话在学术意义上都完全正确。但也不用太担心，因为最后你肯定能得到全面且准确的 解释。

4 前 言 代码示例 本书中的概念并不局限于特定编程语言。因此我选择用多种语言来展示书中的例子。这些语 言包括 Ruby、Python 和 JavaScript。如果你对这些语言有基本的认识就再好不过了。 尽管如此，我还是试着在编写示例时遵循一条原则：即便你不熟悉这个例子所用的语言，应 该也能看懂。为了达到这一目的，我没有严格遵循每种语言最受欢迎的编程范式，因为某些范式 可能会让新接触那种语言的人感到困惑。 我明白一本不停切换语言的书会带来一定程度的思维转换成本。不过，我觉得保持一本书在 语言上的不可知性是很重要的。而且无论是什么语言，我都会试着让代码方便阅读和理解。 在“代码实现”小标题下有一些长一点儿的代码片段。我当然希望你学习这些示例，但要阅 读下一部分并不需要理解每一行代码。如果这些较长的代码对你造成障碍，那么就暂时跳过（或 者略读）。

前 言 5 1 2 3 4 5 8 10 9 6 7 最后还有一点很重要：不是每个代码片段都“适用于生产环境”。重点在于解释清楚当前的 概念。尽管我确实尝试让代码尽量完整，还是可能漏掉一些边界情况。肯定有一些地方能让你做 进一步优化，因此你可以尽情去做。 在线资源 本书网址是 https://pragprog.com/titles/jwdsal2，你可以在上面找到本书的更多信息。还可以 提交勘误，比如内容上的建议或者拼写错误，来帮助改进本书。① 电子书 扫描如下二维码，即可购买本书中文版电子书。 致谢 虽然写书这件事看起来好像是一个人的工作，但是如果没有一路支持我的这么多人，本书就 不可能付梓。感谢你们所有人。 感谢我美丽的妻子 Rena，感谢你一路相伴，给予我情感上的支持。当我像个隐士一样躲在 黑暗中写作时，你处理好了所有事情。感谢我可爱的孩子们：Tuvi、Leah、Shaya 和 Rami。感谢 你们在我写这本“酸法”书时展现的耐心。没错，我终于写完了。 感谢我的父母：Howard Wengrow 先生和 Debbie Wengrow 夫人。感谢你们激发我对计算机编 程的兴趣，并帮助我一路前行。你们可能不知道，正是因为你们在我 9 岁生日时帮我请了一位计 算机家教，我才能走上这条职业道路，并且写出本书。 感谢我妻子的父母：Paul Pinkus 先生和 Kreindel Pinkus 夫人。感谢你们对我和我的家人一如 既往的支持。你们的智慧和热情对我来说意义非凡。 当第一次把书稿提交给 Pragmatic Bookshelf 出版公司时，我自以为写得很好。但出版公司优 秀的工作人员提出的建议以及需求让本书变得更加出色，远超我自己所能。感谢我的编辑 Brian —————————— ① 也可以通过图灵社区下载示例代码或提交中文版勘误：ituring.cn/book/2978。——编者注

6 前 言 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 月

目 录 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17 目 录 第 1 章 数据结构为何重要 ............................ 1 1.1 数据结构 ................................................... 2 1.2 数组：基础数据结构 ................................ 3 1.3 速度计量 ................................................... 4 1.4 读取 .......................................................... 4 1.5 查找 .......................................................... 7 1.6 插入 .......................................................... 9 1.7 删除 ......................................................... 11 1.8 集合：差之毫厘，“慢”之千里 ............ 12 1.9 小结 ......................................................... 15 习题 .................................................................. 15 第 2 章 算法为何重要 ................................... 17 2.1 有序数组 .................................................. 18 2.2 有序数组的查找 ...................................... 20 2.3 二分查找 .................................................. 21 2.4 二分查找与线性查找 ............................... 25 2.5 小结 ......................................................... 27 习题 .................................................................. 28 第 3 章 哦！大 O 记法 .................................. 29 3.1 大 O：对 N 个元素来说需要多少步 ....... 29 3.2 大 O 的灵魂 ............................................. 30 3.2.1 深入大 O 的灵魂 .......................... 32 3.2.2 同样的算法，不同的场景 ........... 32 3.3 第三类算法 .............................................. 33 3.4 对数 ......................................................... 34 3.5 O(log N)的含义 ........................................ 34 3.6 实际例子 .................................................. 35 3.7 小结 ......................................................... 36 习题 .................................................................. 36 第 4 章 使用大 O 给代码提速 ..................... 38 4.1 冒泡排序 .................................................. 38 4.2 冒泡排序实战 .......................................... 39 4.3 冒泡排序的效率 ...................................... 44 4.4 平方问题 .................................................. 45 4.5 线性解法 .................................................. 47 4.6 小结 ......................................................... 48 习题 .................................................................. 49 第 5 章 用或不用大 O 来优化代码 ............. 50 5.1 选择排序 .................................................. 50 5.2 选择排序实战 .......................................... 51 5.3 选择排序的效率 ...................................... 55 5.4 忽略常数 .................................................. 56 5.5 大 O 类别 ................................................. 57 5.5.1 实际例子 ..................................... 58 5.5.2 关键步骤 ..................................... 59 5.6 小结 ......................................................... 59 习题 .................................................................. 60 第 6 章 根据情况进行优化 ........................... 61 6.1 插入排序 .................................................. 61 6.2 插入排序实战 .......................................... 62 6.3 插入排序的效率 ...................................... 67 6.4 平均情况 .................................................. 68 6.5 实际例子 .................................................. 70

2 目 录 6.6 小结 ......................................................... 72 习题 .................................................................. 72 第 7 章 日常代码中的大 O ........................... 74 7.1 偶数平均数 .............................................. 74 7.2 构词程序 ................................................. 75 7.3 数组抽样 ................................................. 77 7.4 摄氏温度平均值 ...................................... 78 7.5 衣服标签 ................................................. 79 7.6 1 的个数 ................................................... 80 7.7 回文检查 ................................................. 80 7.8 计算所有的积 .......................................... 81 7.9 密码破解程序 .......................................... 84 7.10 小结 ....................................................... 86 习题 .................................................................. 86 第 8 章 查找迅速的哈希表 ........................... 89 8.1 哈希表 ..................................................... 89 8.2 用哈希函数进行哈希 .............................. 90 8.3 好玩又赚钱的同义词典（赚钱是 重点） ..................................................... 91 8.4 哈希表查找 .............................................. 92 8.5 解决冲突 ................................................. 94 8.6 创造高效的哈希表 .................................. 96 8.7 用哈希表整合数据 .................................. 98 8.8 用哈希表优化速度 .................................. 99 8.9 小结 ....................................................... 103 习题 ................................................................ 103 第 9 章 用栈和队列打造优雅的代码 ........ 104 9.1 栈 ........................................................... 104 9.2 抽象数据类型 ........................................ 106 9.3 栈实战 ................................................... 107 9.4 受限数据结构的重要性 ......................... 112 9.5 队列 ....................................................... 113 9.6 队列实战 ............................................... 114 9.7 小结 ....................................................... 116 习题 ................................................................ 116 第 10 章 用递归不停递归 .......................... 117 10.1 用递归代替循环 .................................. 117 10.2 基准情形 ............................................. 118 10.3 阅读递归代码 ...................................... 119 10.4 计算机眼中的递归 .............................. 121 10.4.1 调用栈 .................................... 121 10.4.2 栈溢出 .................................... 123 10.5 文件系统遍历 ...................................... 123 10.6 小结 ..................................................... 125 习题 ................................................................ 125 第 11 章 学习编写递归代码 ...................... 127 11.1 递归类别：重复执行 .......................... 127 11.2 递归类别：计算 .................................. 130 11.3 自上而下递归：新的思维方式 ........... 132 11.3.1 自上而下的思考过程 ............. 133 11.3.2 数组的和 ................................ 133 11.3.3 字符串倒序 ............................ 134 11.3.4 x 的个数 ................................. 135 11.4 台阶问题 ............................................. 136 11.5 易位构词生成 ...................................... 139 11.6 小结 ..................................................... 142 习题 ................................................................ 143 第 12 章 动态规划 ....................................... 144 12.1 不必要的递归调用 .............................. 144 12.2 大 O 小改 ............................................. 147 12.3 递归的效率.......................................... 148 12.4 重复子问题.......................................... 149 12.5 动态规划与记忆化 .............................. 150 12.6 自下而上的动态规划 .......................... 153 12.6.1 自下而上的斐波那契函数 ..... 154 12.6.2 记忆化与自下而上 ................ 154 12.7 小结 ..................................................... 155 习题 ................................................................ 155

目 录 3 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 18 17 第 13 章 飞快的递归算法 ........................... 156 13.1 分区 ..................................................... 156 13.2 快速排序 .............................................. 161 13.3 快速排序的效率 .................................. 165 13.3.1 快速排序鸟瞰 ......................... 166 13.3.2 快速排序的时间复杂度 ......... 167 13.4 最坏情况下的快速排序 ....................... 169 13.5 快速选择 .............................................. 171 13.5.1 快速选择的效率 ..................... 172 13.5.2 代码实现：快速选择 ............. 173 13.6 基于排序的其他算法 ........................... 173 13.7 小结 ..................................................... 175 习题 ................................................................ 175 第 14 章 基于节点的数据结构 .................. 176 14.1 链表 ..................................................... 176 14.2 链表实现 .............................................. 177 14.3 读取 ..................................................... 179 14.4 查找 ..................................................... 180 14.5 插入 ..................................................... 181 14.6 删除 ..................................................... 185 14.7 链表操作的效率 .................................. 187 14.8 链表实战 .............................................. 187 14.9 双链表 .................................................. 188 14.9.1 代码实现：双链表插入 ......... 189 14.9.2 前后移动 ................................ 190 14.10 队列的双链表实现 ............................. 190 14.11 小结.................................................... 192 习题 ................................................................ 192 第 15 章 用二叉查找树加速万物 .............. 193 15.1 树 ......................................................... 193 15.2 二叉查找树 .......................................... 195 15.3 查找 ..................................................... 196 15.3.1 二叉查找树的查找效率 ......... 198 15.3.2 logN 层 ................................... 198 15.3.3 代码实现：二叉查找树 查找 ........................................ 199 15.4 插入 ..................................................... 200 15.4.1 代码实现：二叉查找树 插入 ........................................ 202 15.4.2 插入顺序 ................................ 203 15.5 删除 ..................................................... 203 15.5.1 删除有两个子节点的节点 ..... 204 15.5.2 找到后继节点 ........................ 205 15.5.3 有右子节点的后继节点 ......... 206 15.5.4 完整的删除算法 ..................... 208 15.5.5 代码实现：二叉查找树 删除 ........................................ 208 15.5.6 二叉查找树删除的效率 ......... 211 15.6 二叉查找树实战 .................................. 211 15.7 二叉查找树遍历 .................................. 212 15.8 小结 ..................................................... 215 习题 ................................................................ 216 第 16 章 使用堆分清主次 ........................... 217 16.1 优先队列 .............................................. 217 16.2 堆 ......................................................... 218 16.2.1 堆条件 .................................... 219 16.2.2 完全树 .................................... 220 16.3 堆的性质 .............................................. 221 16.4 堆的插入 .............................................. 222 16.5 寻找尾节点 .......................................... 223 16.6 堆的删除 .............................................. 224 16.7 堆和有序数组 ...................................... 227 16.8 重新解决尾节点问题........................... 228 16.9 用数组实现堆 ...................................... 230 16.9.1 遍历基于数组的堆 ................. 231 16.9.2 代码实现：堆插入 ................. 232 16.9.3 代码实现：堆删除 ................. 233 16.9.4 堆的其他实现方法 ................. 235 16.10 用堆实现优先队列 ............................ 235 16.11 小结 ................................................... 236 习题 ................................................................ 236 第 17 章 字典树又何妨 ............................... 237 17.1 字典树 ................................................. 237

4 目 录 17.1.1 字典树节点 ............................ 238 17.1.2 Trie 类 .................................. 238 17.2 存储单词 .............................................. 239 17.3 字典树查找 .......................................... 241 17.4 字典树查找的效率 .............................. 245 17.5 字典树插入 .......................................... 246 17.6 实现自动补全 ...................................... 249 17.6.1 收集所有单词 ........................ 249 17.6.2 递归过程分析 ........................ 251 17.7 完成自动补全功能 .............................. 254 17.8 带有值的字典树：更好的自动补全 .... 255 17.9 小结 ..................................................... 256 习题 ................................................................ 257 第 18 章 连接万物的图 ............................... 258 18.1 图 ......................................................... 258 18.1.1 图和树 .................................... 259 18.1.2 图的术语 ................................ 259 18.1.3 图的基本实现 ........................ 260 18.2 有向图 ................................................. 260 18.3 面向对象的图实现 .............................. 261 18.4 图的搜索 .............................................. 262 18.5 深度优先搜索 ...................................... 264 18.5.1 深度优先搜索步骤详解 ......... 265 18.5.2 代码实现：深度优先搜索 ..... 271 18.6 广度优先搜索 ...................................... 272 18.6.1 广度优先搜索步骤详解 ......... 273 18.6.2 代码实现：广度优先搜索 ..... 280 18.6.3 对比广度优先搜索与深度 优先搜索 ................................ 281 18.7 图的搜索效率 ...................................... 283 18.8 加权图 ................................................. 285 18.8.1 加权图的代码实现 ................. 286 18.8.2 最短路径问题 ........................ 287 18.9 迪杰斯特拉算法 .................................. 288 18.9.1 迪杰斯特拉算法的准备 工作 ........................................ 288 18.9.2 迪杰斯特拉算法的步骤 ......... 289 18.9.3 迪杰斯特拉算法详解 ............. 289 18.9.4 找到最短路径 ........................ 295 18.9.5 代码实现：迪杰斯特拉 算法 ........................................ 296 18.9.6 迪杰斯特拉算法的效率 ......... 301 18.10 小结 ................................................... 301 习题 ................................................................ 302 第 19 章 对付空间限制 ............................... 304 19.1 空间复杂度的大 O 记法 ...................... 304 19.2 时间和空间的取舍 .............................. 306 19.3 递归的隐藏成本 .................................. 308 19.4 小结 ..................................................... 310 习题 ................................................................ 310 第 20 章 代码优化技巧 ............................... 312 20.1 前置工作：确定目前的时间复杂度 ..... 312 20.2 从这里开始：最理想复杂度 ............... 312 20.3 魔法查找 ............................................. 313 20.3.1 魔法查找：查找作者 ............. 314 20.3.2 使用其他数据结构 ................ 315 20.3.3 两数之和问题 ........................ 317 20.4 找规律 ................................................. 319 20.4.1 硬币游戏 ................................ 319 20.4.2 举例法 .................................... 320 20.4.3 交换和问题 ............................ 321 20.5 贪心算法 ............................................. 325 20.5.1 数组最大值 ............................ 326 20.5.2 最大子数组和 ........................ 326 20.5.3 贪心的股价预测 .................... 331 20.6 更换数据结构 ...................................... 335 20.6.1 易位构词检查器 .................... 335 20.6.2 分组排序 ................................ 338 20.7 小结 ..................................................... 340 20.8 临别感言 ............................................. 340 习题 ................................................................ 341 附录 习题答案（图灵社区下载）

1.1 数据结构 1 1 2 3 4 5 8 10 9 6 7 第 1 章 数据结构为何重要 在学习写代码时，人们会关注，而且也应该关注，代码能否正常运行。对他们来说，评价代 码的标准很简单：它能正常工作吗？ 随着软件工程师不断积累经验，他们开始意识到代码质量的奥妙。他们发现，两段功能相同 的代码也存在优劣之分。 衡量代码质量有众多标准，其中一个重要的标准就是代码的可维护性。代码的可维护性体现 在可读性、结构、模块化程度等方面。 不过，高质量代码还有另一个特征，那就是代码的效率。举例来说，你可以找两段功能相同 的代码，但其中一段比另一段运行起来会更快。 观察以下两个打印从 2 到 100 的偶数的函数。 def print_numbers_version_one(): number = 2 while number <= 100: # 如果 number 是偶数，就把它打印出来： if number % 2 == 0: print(number) number += 1 def print_numbers_version_two(): number = 2 while number <= 100: print(number) # 根据偶数的定义，给 number 加上 2，就能得到下一个偶数： number += 2 你觉得这两个函数哪一个运行得更快呢？