Data Structures and Algorithms in Java（Java数据结构与算法）

引用

Goodrich, M. T., Tamassia, R., & Goldwasser, M. H. (2014). Data Structures and Algorithms in Java (6th ed.). Wiley.

章节概要

全书共15章，736页，书末附参考文献和索引。据 Wiley 介绍，习题按目的分类：巩固题检查理解，创造题要求编写新的类，项目题要求写出完整的程序。与许多数据结构教材不同，本书用前两章讲 Java 语言和面向对象设计，之后才出现数据结构；第一个数据结构（数组）要到第103页才出现。

第1–2章：Java入门；面向对象设计

第1章复习语言基础：类与对象，字符串、包装类、数组和枚举类型，表达式，控制流，简单的输入输出，以及包。最后一节把软件开发当作一个过程来讲，包括设计、伪代码、编码、文档与风格、测试与调试。第2章讲面向对象设计的目标、原则和模式，然后依次是继承，接口与抽象类，异常，类型转换与泛型，嵌套类。

第3章：基本数据结构

先讲数组，例子有保存游戏记录、数组排序、用字符数组做简单加密和二维数组。接着依次是单向链表、循环链表和双向链表，每种都给出实现，本章最后讨论等价性判断和数据结构的克隆。

第4章：算法分析

本章从实验研究及其局限讲起，引入“本书使用的七个函数”，再展开用大O记号进行的渐近分析，最后讲简单的论证方法，包括归纳法和循环不变式。

第5章：递归

由阶乘、绘制英制刻度尺、二分查找和文件系统等例子入手，进入递归算法的分析，线性递归、二元递归和多重递归，递归算法的设计，Java 中递归失控的危险，以及尾递归的消除。Wiley 指出，本章是第6版新增的，把以前分散在几章中的内容集中到了一起。

第6–7章：栈、队列和双端队列；列表与迭代器抽象数据类型

第6章把这三种结构分别作为抽象数据类型介绍，再用数组实现，必要时也用链表实现；应用包括反转数组，以及匹配括号和 HTML 标签。第7章讲列表抽象数据类型、带有动态数组摊还分析的数组列表、位置列表、迭代器和 Java Collections Framework，最后以一个用“移至队首”启发式维护访问频率的案例收尾。

第8–9章：树；优先队列

第8章定义一般树和二叉树，给出链式和数组两种表示，并用较长的一节讲遍历（先序、后序、广度优先、中序、欧拉巡游）。第9章定义优先队列抽象数据类型，先用无序列表和有序列表实现，再用堆实现，并把选择排序、插入排序和堆排序作为借助优先队列的排序来讲，最后是可调整优先队列。

第10–11章：映射、散列表和跳表；搜索树

第10章讲映射抽象数据类型、散列表（散列函数、冲突处理、装载因子与重新散列）、有序映射、跳表，以及集合、多重集合和多重映射。第11章从二叉搜索树和一个用于平衡的 Java 框架讲起，然后依次是 AVL 树、伸展树、(2,4)树和红黑树。

第12–13章：排序与选择；文本处理

第12章讲归并排序和快速排序、比较排序的下界、桶排序与基数排序、各种排序算法的比较，以及用剪枝搜索做选择。第13章转向字符串：模式匹配（暴力法、Boyer-Moore、Knuth-Morris-Pratt）、字典树、用贪心法做文本压缩，以及动态规划。

第14–15章：图算法；内存管理与B树

第14章给出图的抽象数据类型、四种图的表示、深度优先和广度优先搜索、传递闭包、拓扑排序、最短路径和最小生成树。第15章探讨语言之下的一层：Java 虚拟机中的栈与堆、垃圾回收、存储层次与缓存、B树以及外存排序。

核心概念

第1–5章：语言、设计、分析与递归

• 面向对象设计的原则与模式：第2章引入的一套术语，后面用来解释各种结构为何这样构造。
• 泛型与接口：用 Java 表达每个抽象数据类型所依靠的机制。
• 大O记号与渐近分析：此后每一种结构都用它来衡量运行时间。
• 递归：有自己分析方法和失败方式的技术，用专门一章来讲。

第6–11章：线性结构、树与映射

• 抽象数据类型：只规定操作的规格说明，书中每个都配有一个 Java 接口。
• 摊还分析：用于动态数组，也用于带星号小节中的伸展树。
• 位置列表与迭代器：在不暴露内部表示的前提下指明序列中位置的方法。
• 堆、散列表与平衡搜索树：分别是优先队列、映射和有序映射的核心结构。

第12–15章：算法与系统

• 分治排序与排序下界：归并排序与快速排序的对比，以及比较排序的局限。
• 字典树与动态规划：文本处理一章的工具。
• 图的遍历、最短路径与生成树：图一章的核心。
• 存储层次与B树：数据结构与机器实际运行之间的联系。

评析

优点

• 先接口，后实现。 据 Wiley 介绍，每个抽象数据类型都有对应的 Java 接口，具体结构则是实现这些接口的类，集中在 net.datastructures 包中，设计上与 Java Collections Framework 互补。第7章把书中的位置列表直接与 Collections Framework 作比较，有助于读者从教学代码过渡到库代码。
• 有意安排的顺序。 算法分析（第4章）和递归（第5章）排在依赖它们的栈、树和排序之前；最难的结构——平衡树（第11章）——在映射和优先队列确立了写法之后才出现。
• 按目的分类的习题。 分为巩固题、创造题和项目题，课程可以把简短的检查题用作作业，把完整的程序用作大作业。
• 一本书的覆盖面较广。 文本处理、图算法和外存都与经典结构并列，本书可以作为通向专门的算法课程的桥梁。

局限

• 读者需要先付出 Java 的“门票”。 前一百页左右讲语言和面向对象设计。对需要的读者这是帮助，但已经会写 Java 的读者会略过这部分；希望与语言无关的读者则会发现代码与泛型、迭代器、嵌套类等 Java 惯用法绑得很紧。
• 较新的 Java 特性不在其中。 Wiley 的改动说明提到了 Java 7 引入的类型推断，而目录中没有任何内容指向更晚的语言特性，因此用较新的 Java 风格写出的代码，与书中印刷的示例会有所不同。
• 算法部分比较简略。 文本处理一章约四十页，图一章约七十五页，所以本书是在介绍这些主题，而不是充分展开。
• 有些小节分析较重。 目录中有几个小节带星号（例如自底向上构建堆、跳表的概率分析、伸展树的摊还分析）。初学者可以预期把它们留到第二遍再读。

在课程中的定位

本书是第二门课的教材：它假定读者已学过一门程序设计课程，并在一种语言中构建数据结构。在本课程列出的书中，Wengrow 的 A Common-Sense Guide to Data Structures and Algorithms 和 Bhargava 的 Grokking Algorithms 是更平易或以图解见长的入门书，可用于第一遍阅读或作为配套；两者都不是围绕 Java 类库组织的。Pat Morin 的 Open Data Structures 涵盖类似内容，为每种结构给出精确的接口、实现和运行时间证明，并提供 Java、C++ 和伪代码三种在线免费版本，很适合作为第二参考，补充 Goodrich 等人讲得较轻的证明。

Brass 的 Advanced Data Structures 是研究生水平的教材，把数据结构当作算法设计来讲，代码用 C 写成；Okasaki 的 Purely Functional Data Structures 讨论函数式语言中的不可变结构。二者都适合作为读完本书之后的下一步，而不是本书的替代品。

如何使用本书

本书适合已学完第一门程序设计课程、想用 Java 实现经典数据结构的本科二年级学生。目录中没有单独的数学章节，第4章自己会引入增长函数、大O记号和归纳证明。已经会 Java 的读者可以从第2章或第3章开始。

一个学期的实用安排：

• 核心： 按顺序读第3章到第9章，并在读到用到其分析的结构之前先读第4章；第5章应在树一章之前读完。
• 后半部分： 第10章和第11章（映射与搜索树）以及第12章（排序）；平衡树可按课程需要挑选（例如 AVL 树和红黑树）。
• 选读： 第13章到第15章，作为通向算法课程的桥梁或自学材料；初读时跳过带星号的小节。

不要只看代码，要自己动手写：根据接口实现栈、队列和位置列表，再把每一个与 Java Collections Framework 中对应的类作比较。每一小节之后做巩固题，创造题和项目题留到各章结束时再做。