数据结构与算法.Java版

本书读者对象
本书计划用于计算机科学的第二门大学生课程。假定同学们熟悉Java或C的基本控制结构，并且熟悉诸如变量以及将问题分解为函数（方法）之类的初级概念。本书只需要同学们具有微积分之前的数学知识。
为什么选择本书？
本书提供了你想在一本数据结构教材中学到的一切内容：大量的习题、易懂的文字、可在线获得的代码，以及合适的深度。当然，每位作者都会做出同样的声明。那么又是什么使得本书与众不同呢？
本书具有以下出众的特点：
* 使用Java 1.5的新特性。
* 提供了数量极多的图形，它们都是用统一建模语言（Unified Modeling Language，UML）绘制的。
* 具有"倒金字塔"风格，以及预先学习最重要的内容。
* 循序渐进地介绍抽象的概念。
* 广泛使用游戏作为示例。
Java 1.5版在该语言中增加了多种人们期盼已久的特性。在全书的许多示例中解释和使用了这些新特性。具体地讲：
* 新的增强型for循环允许程序员简明地提示："对这个数组或集合的每个元素……"。在附录A中以及第5章介绍集合时将讨论这种 循环。
* 现在自动对基本类型进行装箱和取消装箱，从而把程序员从如下笨拙的构造中解脱出来：

((Integer)(numbers.get(i))).intValue()

在第2章中讨论引用类型时将会介绍这种新特性。
* 新的java.util.Scanner类（附录A）最终使得从键盘读取输入成为可能，而不必编写大量的代码。
* 最大的改变可能是引入了泛型类型（generic type）（第4章），它允许程序员指定集合的元素类型，从而提高了程序清晰性和类型安全性。
本书在解释概念时使用了许多图形，因为过长的文字、代码和方程式会使读者感到枯燥。而好的图形可以清楚地解释新概念，提供即时的回顾，并且可以作为回顾书中内容的醒目的标志。因为统一建模语言（UML）已经成为软件图形事实上的标准，所以本书中的图形都是用UML的子集绘制的。本书甚至有意省略了一些中间的UML特性，如访问级标签和聚合菱形，因为我感觉它们引起的混淆更甚于所带来的清晰性。这种表示法是逐步引入的（主要集中在本书的第I部分），并在附录B中进行了回顾。
相关的书写特性是在代码中使用加重的字体。许多文本要么没有提供字体突出显示，要么使用字体来突出显示关键字。当输出代码时，这种语法突出显示是有用的（有助于防止印刷错误）。但是，它既不会使代码更易读，也不会强调重要的过程。本书使用粗斜体文本来突出显示当前讨论中特别感兴趣的代码部分。如果没有什么内容要特别强调，就只突出显示方法和字段名称，以描绘出类的主要部分的轮廓。
用新闻记者的话来讲，本书是采用"倒金字塔"风格编写的：最重要的内容出现在最前面，更细微的细节和更高级的主题分布在各章中介绍。在学完任意一章之后，都可以合理地停止讲授课程。这使得老师能够根据需要自由地加快或放慢进度，而不必担心在课程结束之前没有涉猎到重要的主题。
最前面的许多文字由于过于抽象会使读者感到压抑。这是经过充分培训的计算机科学家很容易犯的一个错误，他们在深入研究细节之前，更喜欢阅读总的纲要。另一方面，如果学生在编写一个"真正的"程序之前，必须全神贯注地学习继承、多态性、递归和算法分析，那么他们很可能失去兴趣（如果不是失去知觉的话）。我常常听到学生要求更具体的示例，而从未听到一个人抱怨示例太多。
在时刻谨记这一点的情况下，我尽力在每一章中及早提供示例。让学生尽可能早地与完整、有效的程序打交道。在具体问题的环境中消化抽象的概念要容易得多。
困难的概念也是尽可能循序渐进地介绍的。例如，在调用栈出现在递归的环境中之前就会对其进行讨论。
本书的大多数示例都是游戏，通常涉及骰子、纸牌和棋盘。游戏激发了学生的想象力，给他们提供了关心正在讨论的数据结构或算法的某种理由。虽然这些游戏的编程工作足够简单，无需编写一页页的代码，但是与找出最大公约数之类的客观任务相比，它们提出了更现实的挑战。在接近书的中间位置，一个涉及字典（其中包含有数万个单词）的游戏提供了学习高效数据结构和算法的激发人的动机。
本书的特点是在本书的开始处就完成了每个项目的开发，而且通常提供了代码的多个版本，并考虑了替代的设计。学生因此会经历精心设计程序的过程，而不仅仅是热衷于得到结果。虽然程序的重要部分都得到了详尽的介绍，但是本书把某些增强功能（如检查有效输入）留做复习题。
本书给出了每个程序完整、有效的代码，并且可在线获取它们。我记得，对一名学生来说，当把算法或数据结构的困难部分留做习题时，会使他倍感苦恼。所有的代码全都包括在本书中，甚至B树的代码也是如此；我知道没有任何其他的大学生教材这样完整地提供这方面的内容。
使用本书中的代码并不需要预先下载任何类。后面的类利用了前面的类。如果需要，可以把后面的这些类轻松地修改成使用来自Java集合框架的内置类；本书中开发的类使用了一致的方法名称。
希望同学们在学完本书后会获得相当多的技能来快速开发正确、高效、通用的程序。
本书的组织结构
本书分为5个部分：面向对象程序设计、线性结构、算法、树和集合，以及高级主题。
第Ⅰ部分介绍面向对象程序设计，用3章分别介绍3个重要的原则：封装、多态性和继承。各所学校对本书这一部分的使用有极大的差异。如果某所学校在第一门计算机课程中就讲授了对象，则可以非常快地介绍这一部分，或者完全跳过不讲（尽管绝大多数学生都会通过复习这部分内容而获益）。另外一些学校的第一门计算机课程是用C或其他某种语言讲授的，那么这可能就要在这部分内容上花更多的时间。另外，本书的这一部分（以及附录A）适合于介绍面向对象程序设计的短期课程。
第Ⅱ部分介绍栈、队列和表，并为它们提供了基于数组的实现和链表实现。读者将会学到如何使用这些结构以及如何构建它们，然后将会学到在Java集合框架中的什么位置找到它们。
在第Ⅲ部分，读者将开始从单纯的编程步入计算机科学的旅程。这一部分将会介绍算法分析，包括渐近表示法和分析简单算法的逐步过程。在学完这些困难的内容之后，读者将会学习介绍最简单的查找和排序算法的相对较短的一章，这时可以轻松一下。到介绍递归时，读者已经理解了调用栈、排序问题，并且能够感知到递归算法（如归并排序和快速排序）提供的更好性能。
第Ⅳ部分重点关注数据结构，介绍了树和集合实现（有序表、二叉树和散列表）。
第Ⅴ部分介绍高级主题，教师可从中自由选择他们感兴趣的主题，包括高级线性结构、串、高级树、图、内存管理，以及磁盘存储涉及的问题。
习题、复习题和项目
大多数小节的末尾都提供了习题。求解这些习题应该花不了几分钟的时间。习题适合于在课堂上或考试中提出。
各章的末尾都提供了复习题。它们稍微棘手一些，可能要花5~10分钟来求解。这些复习题适合于作为考试题或家庭作业。
最后，各章的末尾都给出了一个或多个项目。它们通常要花一小时或更长的时间来求解，适合于作为独立的家庭作业或实验室作业。
致谢
我想感谢这些人：我的妻子Heather，她审校了上面的内容并远远超出了她应尽的责任，同时她还提醒我注意饮食；Dan Friedman，当我在研究所撰写本书的一个早期版本时，他使我相信我不是在闹着玩，而是在做一件严肃的工作；James Ernest（21世纪的Sid Sackson），他允许我使用他的游戏设计；Alan Apt，他给我提供了很多指导，并且还在重要的时间给我提出了一针见血的意见；Paul Purdon和David Wise，他们照亮了数据结构和算法的一些黑暗的角落；同时我还要感谢多年来给我提供评论、建议和审校的所有人，包括Kevin和Rebecca Djang、Jerry Franke、Matt Jadud、Sid Kitchel、Jim Levenick、印第安那大学和路易斯-克拉克学院的计算机科学系的无数学生，以及匿名评论人。

Peter Drake
俄勒冈州波特兰市









第Ⅰ部分 面向对象程序设计
第1章 封装

1.1 软件开发 2
1.1.1 良好的程序 2
1.1.2 封装 3
1.1.3 软件开发周期 5
习题 6
1.2 类和对象 7
1.2.1 类 7
1.2.2 对象、字段和方法 8
1.2.3 构造函数 9
1.2.4 访问器、修改器和this 11
1.2.5 静态与非静态 12
1.2.6 完成Die类 13
习题 14
1.3 使用对象 14
1.3.1 Beetle类 14
1.3.2 toString()方法 15
1.3.3 BeetleGame类 19
习题 24
1.4 小结 24
1.5 术语 25
1.6 复习题 26
1.7 项目 27


第2章 多态性

2.1 引用类型 29
2.1.1 null 30
2.1.2 引用和相等性 30
2.1.3 多态类型对象 31
2.1.4 基本类型和包装器 33
2.1.5 String 33
习题 34
2.2 数组 34
2.2.1 声明、分配和初始化 34
2.2.2 多维数组 35

2.2.3 示例：Domineering 37
习题 42
2.3 接口 43
习题 47
2.4 重载 47
习题 48
2.5 小结 48
2.6 术语 49
2.7 复习题 50
2.8 项目 50

第3章 继承

3.1 扩展类 53
3.1.1 多态性和继承 55


3.1.2 继承链 57
3.1.3 is-a和has-a 58
习题 60
3.2 Object类 61
3.2.1 Object类的方法 61
3.2.2 隐式构造函数 62
习题 62
3.3 包和访问级别 63
访问级别 64
习题 65
3.4 小结 65
3.5 术语 66
3.6 复习题 66
3.7 项目 66

第Ⅱ部分 线 性 结 构
第4章 栈和队列

4.1 Stack接口 70
4.1.1 泛型 71
4.1.2 示例：Idiot's Delight 72
习题 77
4.2 调用栈 78
习题 80
4.3 异常 80

习题 86
4.4 Queue接口 86
习题 91
4.5 小结 91
4.6 术语 91
4.7 复习题 92
4.8 项目 93


第5章 基于数组的结构

5.1 收缩和加长数组 95
5.1.1 Card类 96
5.1.2 收缩数组 97
5.1.3 加长数组 100
习题 101
5.2 实现栈和队列 101
5.2.1 ArrayStack类 101
5.2.2 ArrayQueue类 103
习题 105
5.3 List接口 106
5.3.1 接口 106
5.3.2 ArrayList类 107
习题 110
5.4 迭代器 111
5.4.1 Iterator接口 111
5.4.2 Iterable接口 112
5.4.3 ArrayIterator类 112
5.4.4 示例：Go Fish 114
习题 120
5.5 初识Java集合框架 121
抽象类 121
习题 122
5.6 小结 123
5.7 术语 123
5.8 复习题 123
5.9 项目 124


第6章 链表结构

6.1 表节点 125
习题 128
6.2 栈和队列 128
6.2.1 LinkedStack类 128
6.2.2 LinkedQueue类 131
习题 133
6.3 LinkedList类 134
6.3.1 Predecessor接口 136
6.3.2 两指算法 138
6.3.3 ListIterator类 139
习题 140
6.4 再论Java集合框架 141
习题 142
6.5 小结 142
6.6 术语 142
6.7 复习题 143
6.8 项目 143

第Ⅲ部分 算 法
第7章 算法分析

7.1 计时 146
习题 148
7.2 渐近表示法 148
习题 152
7.3 统计步骤数 153
习题 157
7.4 最好、最坏和平均情况 157
习题 158
7.5 平摊分析 159
习题 160
7.6 小结 160
7.7 术语 161
7.8 复习题 161
7.9 项目 162


第8章 查找和排序

8.1 线性查找 163
习题 164
8.2 折半查找 164
8.2.1 折半查找分析 165
8.2.2 假定n是2的幂 166
习题 167
8.3 插入排序 167
习题 169
8.4 Comparable接口 170
习题 173
8.5 排序链表 173
习题 174
8.6 小结 174
8.7 术语 175
8.8 复习题 175
8.9 项目 176


第9章 递归

9.1 递归地思考 177
习题 183
9.2 分析递归算法 183
习题 186
9.3 归并排序 186
归并排序分析 189
习题 189
9.4 快速排序 190
快速排序分析 192
习题 193
9.5 避免递归 193
9.5.1 尾部递归 194
9.5.2 动态规划 195
习题 197
9.6 小结 197
9.7 术语 198
9.8 复习题 198
9.9 项目 200




第Ⅳ部分 树 和 集 合
第10章 树

10.1 二叉树 202
10.1.1 有关树的术语 203
10.1.2 实现二叉树 205
习题 208
10.2 树的遍历 210
习题 213
10.3 广义树 213
10.3.1 表示广义树 214
10.3.2 示例：智能的Tic Tac Toe玩家 215
习题 221
10.4 小结 221
10.5 术语 221
10.6 复习题 223
10.7 项目 223

第11章 集合

11.1 Set接口 224
习题 229
11.2 有序表 230
11.2.1 查找 232
11.2.2 插入 233
11.2.3 删除 233
习题 234
11.3 二叉查找树 234
11.3.1 查找 235
11.3.2 插入 236
11.3.3 删除 238
习题 241
11.4 散列表 242
11.4.1 直接定址法 242
11.4.2 散列函数和散列码 244
11.4.3 冲突解决方法 245
11.4.4 查找 248
11.4.5 插入 249
11.4.6 删除 250
习题 250
11.5 再论Java集合框架 251
映射 252
习题 252
11.6 小结 253
11.7 术语 253
11.8 复习题 254
11.9 项目 255

第Ⅴ部分 高 级 主 题
第12章 高级线性结构

12.1 位向量 258
BitSet 264
习题 264
12.2 稀疏数组 265
习题 267
12.3 多维数组的连续表示法 267
习题 271
12.4 高级查找和排序 271
12.4.1 插值查找 271
12.4.2 比较排序的下界 273
12.4.3 桶排序 273
习题 275
12.5 小结 275
12.6 术语 276
12.7 复习题 276
12.8 项目 276



第13章 字符串

13.1 String和StringBuilder 277
习题 280
13.2 字符串匹配 280
13.2.1 朴素的字符串匹配 282
13.2.2 RK指纹识别算法 283
13.2.3 KMP跳跃算法 285
习题 289
13.3 小结 289
13.4 术语 290
13.5 复习题 290
13.6 项目 291


第14章 高级主题

14.1 堆 292
14.1.1 优先级队列 294
14.1.2 堆排序 296
14.1.3 Java的PriorityQueue类 297
习题 298
14.2 不相交集合簇 298
14.2.1 按高度合并 300
14.2.2 路径压缩 301
习题 302
14.3 数字查找树 302
习题 308
14.4 红黑树 308
14.4.1 红黑树的性质 308
14.4.2 查找 309
14.4.3 插入 309
14.4.4 删除 311
14.4.5 实现 312
习题 320
14.5 小结 320
14.6 术语 321
14.7 复习题 321
14.8 项目 321


第15章 图

15.1 术语 323
习题 327
15.2 表示法 327
习题 332
15.3 图的遍历 332
习题 334
15.4 拓扑排序 335
习题 339
15.5 最短路径 339
15.5.1 Dijkstra的单源点算法 340
15.5.2 Floyd-Warshall所有顶点对算法 341
习题 342
15.6 最小生成树 342
习题 346
15.7 小结 346
15.8 术语 346
15.9 复习题 348
15.10 项目 348


第16章 内存管理

16.1 显式内存管理 350
16.1.1 自由表 352
16.1.2 使用节点池 356
习题 358
16.2 自动内存管理 358
16.2.1 引用计数 358
16.2.2 标记和清理无用单元收集 359
16.2.3 复制无用单元收集 359
习题 365
16.3 小结 366
16.4 术语 366
16.5 复习题 367
16.6 项目 367



第17章 输出到磁盘

17.1 与文件交互 368
17.1.1 文本文件 368
17.1.2 数据文件 372
习题 376
17.2 压缩 376
17.2.1 霍夫曼编码方式 376
17.2.2 Lempel-Ziv编码方式 381
习题 384
17.3 外部排序 384
习题 389
17.4 B树 389
17.4.1 查找 390
17.4.2 插入 390
17.4.3 删除 391
17.4.4 实现 392
习题 404
17.5 小结 405
17.6 术语 405
17.7 复习题 406
17.8 项目 406

第Ⅵ部分 附 录
附录A Java知识回顾

A.1 第一个程序 408
A.2 变量和类型 410
A.3 循环 412
A.4 与用户交互 414
A.5 分支 414
A.6 方法和中断 417
A.7 常量 418
A.8 运算符 420
A.9 调试 423
A.10 编码约定 424


附录B 统一建模语言

B.1 类图 428
B.2 实例图 431


附录C 求和公式

C.1 求和符号 433
C.2 常量求和 434
C.3 前n个整数之和 434
C.4 二等分与加倍之和 435
C.5 函数之和的上限 435
C.6 常数因子 436


附录D 进一步的阅读材料

D.1 数据结构和算法 437
D.2 Java 437
D.3 游戏 437