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

编辑推荐

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

内容简介

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

作者简介

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

精彩书评

“《数据结构与算法Java语言描述》是一本使用和理解数据结构的极棒的编程手册，可使你在掌握足够的理论深入理解算法分析的同时而不会忽视其实际应用。”

——BarryWittman

副教授，

ElizabethtownCollege

“通读该书，读者会潜心进入Java集合框架中，获得使用Ant和JUnit工具的经验，并学习如何从零开始建立一个有趣的搜索引擎。该书是《ThinkJava》一书的出色的续集。”

——ChrisMayfield

副教授，

JamesMadisonUniversity

目录

目录
前言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

前言/序言

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

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

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

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

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

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

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

必备知识
《数据结构与算法Java语言描述》适用的读者包括计算机科学及相关领域的大学生、专业的软件工程师、软件工程培训师以及正在准备技术面试的相关人员。

在读《数据结构与算法Java语言描述》之前，你需要有很好的Java基础。具体说，你应当知道怎么定义一个从已有类扩展的新类或怎么实现一个接口。如果你对Java编程已经不熟悉了，这里有两《数据结构与算法Java语言描述》你需要先学习一下：

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

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

词汇方面的注释：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。

使用书中的代码
《数据结构与算法Java语言描述》的代码在一个Git库中，参见http://thinkdast.com/repo。

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

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

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

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

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

《数据结构与算法Java语言描述》中的例子使用Java开发工具包7（JavaSEDevelopmentKit7）开发和测试。如果你使用的是旧开发版本，有些例子将不能运行。如果你在使用一个更新的版本，这些代码都应当能正常运行。

《数据结构与算法Java语言描述》使用约定
《数据结构与算法Java语言描述》使用以下排版约定：

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

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

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

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

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

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

订阅者可在一个快捷搜索的数据库中获得成千上万的书籍、培训视频和出版前的手稿，如O’ReillyMedia，PrenticeHallProfessional，Addison-WesleyProfessional，MicrosoftPress，Sams，Que，PeachpitPress，FocalPress，CiscoPress，JohnWiley&Sons，Syngress，MorganKaufmann，IBMRedbooks，Packt，AdobePress，FTPress，Apress，Manning，NewRiders，McGraw-Hill，Jones&Bartlett，CourseTechnology以及其他数百家出版社。有关Safari图书在线的更多信息，请访问我们的网站。

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

美国：
O’ReillyMedia，Inc.
1005GravensteinHighwayNorthSebastopol，CA95472

中国：
北京市西城区西直门南大街2号成铭大厦C座807室（100035）奥莱利技术咨询（北京）有限公司
发表评论或咨询有关《数据结构与算法Java语言描述》的技术问题，请发送电子邮件至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。

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

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

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

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

CharlesRoumeliotis为O’Reilly公司编辑了《数据结构与算法Java语言描述》并作出了许多改进。如果你对《数据结构与算法Java语言描述》有看法或评论，请发邮件到feedback@greenteapress.com。