前言

优质

小牛编辑

137浏览

2023-12-01

本书背后的哲学

数据结构和算法是过去 50 年来最重要的发明之一，它们是软件工程师需要了解的基础工具。但是在我看来，这些话题的大部分书籍都过于理论，过于庞大，也是“自底向上”的：

过于理论

算法的数学分析基于许多简化假设，它们限制了实践中的可用性。这个话题的许多描述都掩盖了简化，并专注于数学。在这本书中，我介绍了这个话题的最实际的子集，并省略或不强调其余的内容。

过于庞大

这些话题的大多数书籍至少有 500 页，有些超过 1000 页。通过关注我认为对软件工程师最有用的话题，我把这本书限制在 200 页以下。

过于“自底向上”

许多数据结构的书籍着重于数据结构如何工作（实现），而不是使用它们（接口）。在这本书中，我从接口开始，“自顶向下”。读者在学习如何使用 Java 集合框架中的结构之后，再了解它们的工作原理。

最后，有些书将这个材料展示在上下文之外，缺少动机：这只是另一个数据结构！我试图使之生动起来，通过围绕一个应用 - 网页搜索 - 来组织这些话题，它广泛使用数据结构，并且是一个有趣和重要的话题。

这个应用激发了一些话题，通常不会在介绍性数据结构的课中涵盖，包括 Redis 的持久化数据结构。

我已经做出了一些艰难的决定，来进行取舍，但我也做了一些妥协。我包括了大多数读者永远不会使用的一些话题，但是可能在技术面试中，你需要知道这些话题。对于这些话题，我提出了传统的观点和我怀疑的理由。

本书还介绍了软件工程实践的基本方面，包括版本控制和单元测试。大多数章节都包括一个练习，允许读者应用他们学到的内容。每个练习都提供自动化测试，来检查解决方案。对于大多数练习，我在下一章的开头展示我的解决方案。

本书面向计算机科学及相关领域的大学生，专业软件工程师，软件工程培训人员和技术面试准备人员。

在你开始读这本书之前，你应该很熟悉 Java，尤其应该知道如何定义一个扩展现有类的新类，或实现一个interface。如果你不熟悉 Java 了，这里有两本书可以用于起步：

如果你不熟悉 Java 中的接口，你可能需要在 http://thinkdast.com/interface 上完成一个名为“什么是接口”的教程。

一个词汇注解：“接口”这个词可能会令人困惑。在应用编程接口（API）的上下文中，它指代一组提供某些功能的类和方法。

在 Java 的上下文中，它还指代一个与类相似的语言特性，它规定了一组方法。为了避免混淆，我将使用正常字体中的“接口”来表示接口的一般思想，代码字体的interface用于 Java 语言特性。

你还应该熟悉类型参数和泛型类型。例如，你应该知道如何使用类型参数创建对象，如ArrayList<Integer>。如果不是，你可以在 http://thinkdast.com/types 上了解类型参数。

你应该熟悉 Java 集合框架（JCF），你可以阅读 http://thinkdast.com/collections。特别是，你应该知道List interface，以及ArrayList和LinkedList类。

理想情况下，你应该熟悉 Apache Ant，它是 Java 的自动化构建工具。你可以在 http://thinkdast.com/anttut 上阅读 Ant 的更多信息。

你应该熟悉 JUnit，它是 Java 的单元测试框架。你可以在 http://thinkdast.com/junit 上阅读更多信息。

本书的代码位于 http://thinkdast.com/repo 上的 Git 仓库中。

Git 是一个“版本控制系统”，允许你跟踪构成项目的文件。Git 控制下的文件集合称为“仓库”。

GitHub 是一个托管服务，为 Git 仓库提供存储和方便的 Web 界面。它提供了几种使用代码的方法：

你可以通过按下Fork（派生）按钮，在 GitHub 上创建仓库的副本。如果你还没有 GitHub 帐户，则需要创建一个。派生之后，你可以在 GitHub 上拥有你自己的仓库，你可以使用它们来跟踪你编写的代码。然后，你可以“克隆”仓库，它将文件的副本下载到你的计算机。
或者，你可以克隆仓库而不进行派生。如果你选择此选项，则不需要 GitHub 帐户，但你无法将更改保存在 GitHub 上。
如果你不想使用 Git，你可以使用 GitHub 页面上的Download（下载）按钮或此链接http://thinkdast.com/zip，以 ZIP 压缩包格式下载代码。

克隆仓库或解压 ZIP 文件后，你应该有一个名为ThinkDataStructures的目录，其中有一个名为code的子目录。

本书中的示例是使用 Java SE 7 开发和测试的。如果你使用的是较旧的版本，一些示例将无法正常工作。如果你使用的是更新版本，那么它们都应该能用。

这本书是我为纽约市 Flatiron School 写的课程的一个改编版，它提供了编程和网页开发相关的各种在线课程。他们提供基于这个材料的课程，提供在线开发环境，来自教师和其他学生的帮助，以及结业证书。你可以在 http://flatironschool.com上找到更多信息。

在 Flatiron School，Joe Burgess，Ann John 和 Charles Pletcher 通过实现和测试，提供了来自初始规范的指导，建议和更正。谢谢你们！
我非常感谢我的技术审校员 Barry Whitman, Patrick White 和 Chris Mayfield，他提出了许多有用的建议，并捕获了许多错误。当然，任何剩余的错误都是我的错，而不是他们的错！
感谢 Olin College 的数据结构和算法课程中的教师和学生，他们读了这本书并提供了有用的反馈。

如果你对文本有任何意见或建议，请发送至：feedback@greenteapress.com。