本书具有以下特点：

* 使用Java 1.5的新特性。

* 提供了数量极多的图形，它们都是用统一建模语言（Unified Modeling Language，UML）绘制的。

* 具有“倒金字塔”风格，以及预先学习最重要的内容。

* 循序渐进地介绍抽象的概念。

* 广泛使用游戏作为示例。

Java 1.5版在该语言中增加了多种人们期盼已久的特性。在全书的许多示例中解释和使用了这些新特性。具体地讲：

* 新的增强型for循环允许程序员简明地提示：“对这个数组或集合的每个元素……”。在附录A中以及第5章介绍集合时将讨论这种  循环。

* 现在自动对基本类型进行装箱和取消装箱，从而把程序员从如下笨拙的构造中解脱出来：

 本书读者对象

本书计划用于计算机科学的第二门大学生课程。假定同学们熟悉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   

俄勒冈州波特兰市

??

??

??

??

VI

版

V

第Ⅰ部分  面向对象程序设计

第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

??

??

??

??

XII

版

XI