数据结构与算法Java语言描述_[美]Allen B. Downey（艾伦 B. D.）_9787519821944

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

前言本书背后的哲理数据结构与算法是过去几十年来最重要的创新之一，是软件工程师需要掌握的基础工具。但在我看来，大部分有关数据结构与算法的书籍都太过于理论化、太厚而且太自底向上化了：太过于理论化算法的数学分析基于简化的假设，这些假设限制了它在实践中的实用性。很多关于数据结构与算法的讲解都忽略了其简单化而关注其数学基础。在本书中，我对这部分提出了最实用的讲解而省略或不再强调其他方面内容。太厚许多有关数据结构与算法的书籍至少有 500 页，一些甚至超过 1000 页。我重点关注的是我认为对软件工程师最有用的话题，这样使得本书厚度很薄。太自底向上化许多讲述数据结构的书关注于它是怎样工作的（实现），而很少涉及怎样使用它们（接口）。在本书中，我采取了自顶向下策略，从接口开始讲起。你在学习 Java 集合框架中结构的工作原理细节之前，先学到怎么使用它们。最后，有些书在讲解这一话题时脱离了上下文而且没有吸引力：只是一个又一个烦人的数据结构！我尝试结合一个 Web 搜索应用来组织这个话题，从而使其变得生动有趣。Web 搜索应用广泛使用了数据结构，并且是一个有趣而重要的话题。Web 搜索应用还带来了一些通常不在初学数据结构类的部分涉及的主题，包括 Redis 的持久性数据结构。对于该放弃什么内容，我已经做出了艰难的决定，但我已经做出了一些妥协。在本书中包括几个大多数人永远不会使用的主题，但他们可能在技术面试中需要知道这些内容。对于这些主题，我既提出了传统的做法，同时也给出了我怀疑的理由。本书还介绍了软件工程实践的基本知识，包括版本控制和单元测试。大多数章节包括一个练习，你可实践所学的知识。每个练习都提供了检查解决方案的自动测试。对于大多数练习，我在下一章的开头都介绍了我的解决方法。必备知识本书适用的读者包括计算机科学及相关领域的大学生、专业的软件工程师、软件工程培训师以及正在准备技术面试的相关人员。在读本书之前，你需要有很好的 Java 基础。具体说，你应当知道怎么定义一个从已有类扩展的新类或怎么实现一个接口。如果你对 Java 编程已经不熟悉了，这里有两本书你需要先学习一下： Downey 和 Mayfield 编写的《Think Java》(OReilly Media，2016)，适用于没有一点编程基础的人。 Sierra 和 Bates 编写的《Head First Java》 (OReilly 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 图书在线为企业、政府机构、教育机构和个人提供了一系列计划和定价方案。订阅者可在一个快捷搜索的数据库中获得成千上万的书籍、培训视频和出版前的手稿，如 OReilly 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 图书在线的更多信息，请访问我们的网站。联系方式请将您发现的问题以及建议及时报告给出版商：美国：OReilly Media，Inc.1005 Gravenstein Highway North Sebastopol，CA 95472中国：北京市西城区西直门南大街2号成铭大厦C座807室（100035）奥莱利技术咨询（北京）有限公司发表评论或咨询有关本书的技术问题，请发送电子邮件至 bookquestions@ oreilly.com。关于我们的书籍、课程、会议和新闻的更多信息，请参阅我们的网站：http://www.oreilly.comhttp://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 为 OReilly 公司编辑了本书并作出了许多改进。如果你对本书有看法或评论，请发邮件到 feedback@greenteapress.com。

你还可能感兴趣

我要评论