数据结构与算法Java语言描述

本书作者强调实践知识和技能胜过理论，在书中为你展示了怎样使用数据结构实现有效的算法，并分析和测试了算法的性能。在本书中你将探索Java集合框架（JCF）中重要的类，它们是如何实现的，以及如何执行。书中的每一章都提供了动手练习及其在线测试代码。本书主要内容有：学习使用列表和映射等数据结构并理解它们是如何工作的。构建一个应用程序，用于读取维基百科页、解析页面内容并导航结果树。通过分析代码预测其运行时间和所需的内存空间。分别使用哈希表和二叉搜索树编写实现Map接口的类。创建一个简单的Web搜索引擎，包括一个网络爬虫、一个存储Web页面内容的索引器和一个返回用户查询结果的检索器。

Allen B. Downey是奥林工程学院计算机科学领域的教授,曾经在韦尔斯利学院、科尔比学院和伯克利大学执教。他拥有伯克利大学计算机科学博士学位及麻省理工学院硕士和学士学位。他编写的其他书籍有：《Think Java》、《Think Python》、《Think Stats》和《Think Bayes》。

如果你是一名正在学习计算机科学的学生，或者你是一个正在准备技术面试的软件开发者，本书将以一种更清晰、更具体，以及更吸引人的方式帮助你学习并回顾软件工程中重要的部分-----数据结构和算法。 “本书是一本使用和理解数据结构的极棒的编程手册，可使你在掌握足够的理论深入理解算法分析的同时而不会忽视其实际应用。”

前言
本书背后的哲理
数据结构与算法是过去几十年来最重要的创新之一，是软件工程师需要掌握 的基础工具。但在我看来，大部分有关数据结构与算法的书籍都太过于理论化、 太厚而且太“自底向上”化了：

太过于理论化 算法的数学分析基于简化的假设，这些假设限制了它在实践中的实用性。 很多关于数据结构与算法的讲解都忽略了其简单化而关注其数学基础。在 本书中，我对这部分提出了最实用的讲解而省略或不再强调其他方面内容。

太厚许多有关数据结构与算法的书籍至少有 500 页，一些甚至超过 1000 页。 我重点关注的是我认为对软件工程师最有用的话题，这样使得本书厚度很 薄。

太“自底向上”化 许多讲述数据结构的书关注于它是怎样工作的（实现），而很少涉及怎样 使用它们（接口）。在本书中，我采取了自顶向下策略，从接口开始讲起。 你在学习 Java 集合框架中结构的工作原理细节之前，先学到怎么使用它们。
最后，有些书在讲解这一话题时脱离了上下文而且没有吸引力：只是一个又 一个烦人的数据结构！我尝试结合一个 Web 搜索应用来组织这个话题，从而 使其变得生动有趣。Web 搜索应用广泛使用了数据结构，并且是一个有趣而 重要的话题。

Web 搜索应用还带来了一些通常不在初学数据结构类的部分涉及的主题，包 括 Redis 的持久性数据结构。

对于该放弃什么内容，我已经做出了艰难的决定，但我已经做出了一些妥协。 在本书中包括几个大多数人永远不会使用的主题，但他们可能在技术面试中 需要知道这些内容。对于这些主题，我既提出了传统的做法，同时也给出了 我怀疑的理由。

本书还介绍了软件工程实践的基本知识，包括版本控制和单元测试。大多数 章节包括一个练习，你可实践所学的知识。每个练习都提供了检查解决方案 的自动测试。对于大多数练习，我在下一章的开头都介绍了我的解决方法。

必备知识
本书适用的读者包括计算机科学及相关领域的大学生、专业的软件工程师、 软件工程培训师以及正在准备技术面试的相关人员。

在读本书之前，你需要有很好的 Java 基础。具体说，你应当知道怎么定义一 个从已有类扩展的新类或怎么实现一个接口。如果你对 Java 编程已经不熟悉 了，这里有两本书你需要先学习一下：

Downey 和 Mayfield 编写的《Think Java》(O’Reilly Media，2016)，适用 于没有一点编程基础的人。

Sierra 和 Bates 编写的《Head First Java》 (O’Reilly Media，2005)，适用 于学过另一种编程语言的人。
如果你不熟悉 Java 的接口，你可能需要学习 http://thinkdast.com/interface 上 提供的教程“What Is an Interface?”。

词汇方面的注释：Interface（接口）一词比较容易使人混淆。在应用程序接口
（API）中，它指提供一定功能的一组类和方法。

在 Java 语言中，Interface（接口）还指一种语言特征，它与类相似，定义了 一组方法。

你也应该熟悉类型参数与通用类型。比如，你应知道怎样创建一个有类型 参数的对象，如 ArrayList。如果你对类型参数不熟悉，请参阅 http://thinkdast.com/types。

你应该熟悉 Java 集合框架（JCF），可参阅 http://thinkdast.com/collections。 特别是，你应熟悉 List 接口、ArrayList 类和 LinkedList 类。

你最好也应该熟悉 Apache 的 Ant，它是 Java 的自动编译工具，可参阅 http:// thinkdast.com/anttut。

你也应该熟悉 JUnit，它是 Java 的单元测试框架，可参阅 http://thinkdast.com/ junit。

使用书中的代码
本书的代码在一个 Git 库中，参见 http://thinkdast.com/repo。

Git 是一个版本控制系统，它允许你跟踪组成项目的文件。Git 控制下的一个 文件集称为一个仓库（repository）。

GitHub 是一个主机服务，为 Git 仓库提供了存储空间和便捷的 Web 接口。它 提供了以下几种使用代码的方式：
? 可以按下 Fork 按钮创建一个 Git Hub 仓库的备份。如果你还没有一个 GitHub 账户，需要注册一个。备份后，你将在 GitHub 上拥有自己的仓库， 可以使用它跟踪你编写的代码。然后你可以克隆这个仓库，将文件的一个 备份下载到你的计算机上。

? 另一个做法是，可以不使用 Fork 备份而直接克隆仓库。如果你选择这么做， 就不需要 GitHub 账户，但不能在 GitHub 上保存你的修改。

? 如果你一点也不想使用 Git，可以按下 GitHub 页或链接 http://think dast. com/zip 上的 Download 按钮下载代码的 ZIP 压缩包。

当你克隆仓库或对 ZIP 文件解压后，就会找到一个 ThinkDataStructures 目录， 其下有一个子目录 code。

本书中的例子使用 Java 开发工具包 7（Java SE Development Kit 7）开发和测 试。如果你使用的是旧开发版本，有些例子将不能运行。如果你在使用一个 更新的版本，这些代码都应当能正常运行。

本书使用约定
本书使用以下排版约定：

斜体（Italic）
表示强调、按键、菜单选项、URL 网址和 email 地址。

黑体（Bold） 表示首次定义的新术语。

等宽字体（Constant width） 表示程序代码清单，以及段落内的文件名、文件扩展，程序中的元素如变 量、函数名、数据类型、语句和关键字。

等宽黑体 (Constant width bold)
表示由用户输入的命令或其他文本。
Safari 图书在线
Safari 图书在线（www.safaribooksonline.com）是一个应需而变的数字图书馆， 它以书籍和视频的形式提供了来自全球范围内技术和企业领域资深作者撰写 的专业内容。

专业技术人员、软件开发人员、网页设计师、商业和创意专业人士使用 Safari
图书在线作为研究解决问题、学习和认证培训的首要资源。

Safari 图书在线为企业、政府机构、教育机构和个人提供了一系列计划和定价 方案。

订阅者可在一个快捷搜索的数据库中获得成千上万的书籍、培训视频和 出版前的手稿，如 O’Reilly Media，Prentice Hall Professional，Addison- Wesley Professional，Microsoft Press，Sams，Que，Peachpit Press，Focal Press，Cisco Press，John Wiley & Sons，Syngress，Morgan Kaufmann，IBM Redbooks，Packt，Adobe Press，FT Press，Apress，Manning，New Riders， McGraw-Hill，Jones & Bartlett，Course Technology 以及其他数百家出版社。 有关 Safari 图书在线的更多信息，请访问我们的网站。

联系方式
请将您发现的问题以及建议及时报告给出版商：

美国：
O’Reilly Media，Inc.
1005 Gravenstein Highway North Sebastopol，CA 95472

中国：
北京市西城区西直门南大街2号成铭大厦C座807室（100035） 奥莱利技术咨询（北京）有限公司
发表评论或咨询有关本书的技术问题，请发送电子邮件至 bookquestions@ oreilly.com。

关于我们的书籍、课程、会议和新闻的更多信息，请参阅我们的网站：

http://www.oreilly.com
http://www.oreilly.com.cn

我们的 Facebook：http://facebook.com/oreilly。 我们的 Twitter：http://twitter.com/oreillymedia。
我们的 YouTube：http://www.youtube.com/oreillymedia。

致谢
这本书是我在纽约 Flatiron 学校编写的全部课程内容的一个改编版，这所学校 提供了各种与编程和 Web 开发相关的在线课堂。他们基于这个材料有一个课 堂，提供在线开发环境、来自讲师和其他学生的帮助，以及结业证书。你可 在网站 http://flatironschool.com 上找到更多信息。

在 Flatiron 学校，Joe Burgess、Ann John 和 Charles Pletcher 提供了指导、 建议以及对初始版本从实现到测试整个过程的修改。感谢你们！

非常感谢技术评论员 Barry Whitman、Patrick White 以及 Chris Mayfield， 他们发现了许多错误并提供了许多有帮助的建议。当然，书中还有错误的 话，那是我的过失，与他们无关！

? 感谢 OlinCollege 学院数据结构与算法课程的指导教师与学生们，他们阅 读了本书并给出了有益的反馈意见。

Charles Roumeliotis 为 O’Reilly 公司编辑了本书并作出了许多改进。 如果你对本书有看法或评论，请发邮件到 [email protected]。

目录
前言1
第 1 章 接口7
为什么有两种列表？8
List 接口9
练习 111
第 2 章 算法分析14
选择排序算法15
大 O 表示法17
练习 218
第 3 章 ArrayList 类22
对 MyArrayList 类中方法的分类22
对 add 方法分类24
问题规模26
链接数据结构27
练习 329
关于垃圾回收的注记32
第 4 章 LinkedList 类33
MyLinkedList 方法的分类33
比较 MyArrayList 和 MyLinkedList36
性能分析36
结果的解释39
练习 441
第 5 章 双向链表43
结果的性能分析43
分析 LinkedList 方法的性能45
在 LinkedList 末尾添加47
双向链表48
选择一个结构49
第 6 章 树的遍历51
搜索引擎51
解析 HTML52
使用 JSOUP54
遍历 DOM 树56
深度优先搜索57
Java 栈58
迭代 DFS59
第 7 章 到达哲学61
准备开始61
Iterable 接口和 Iterator 类62
WikiFetcher64
练习 565
第 8 章 索引器68
选择数据结构68
TermCounter70
练习 672
第 9 章 Map 接口77
实现 MyLinearMap77
练习 778
分析 MyLinearMap79
第 10 章 哈希方法82
哈希方法82
哈希方法是如何工作的？84
哈希方法和变体86
练习 887
第 11 章 HashMap89
练习 989
分析 MyHashMap90
权衡考虑92
对 MyHashMap 的性能分析93
修改 MyHashMap94
UML 类图96
第 12 章 TreeMap98
哈希方法有什么问题？98
二叉搜索树99
练习 10101
实现 TreeMap102
第 13 章 二叉搜索树106
一个简单的 MyTreeMap106
搜索值107
实现 put108
中序遍历算法110
对数方法111
自平衡树114
另一个练习114
第 14 章 持久性115
Redis116
Redis 客户端和服务器117
构建一个 Redis 支持的索引118
Redis 数据类型120
练习 11122
更多建议123
一些设计提示125
第 15 章 爬行维基百科126
Redis 支持的索引器126
查找的分析129
索引分析129
图的遍历130
练习 12131
第 16 章 布尔搜索135
爬虫解决方案135
信息检索137
布尔搜索138
练习 13139
Comparable 和 Comparator 接口141
扩展部分143
第 17 章 排序145
插入排序146
练习 14148
合并排序的分析149
基数排序151
堆排序153
有界堆155
空间复杂性156