前    言

　　本书包括了讲述数据结果和算法的面向对象课程。它采用Java语言实现，并假定学生在此之前已经学过该语言的基础课程，这些课程覆盖了基本语句和数据类型的用法，以及数组和文件的基本操作。

Java集合框架

　　本书的一个显著特点就是：它的重点放在Java集合框架(Java Collection Framwork)上，这个框架是java.util包的一部分。它基本上是一个层次结构，各层(除了最底层之外)由不同的接口和在最底层实现这些接口的集合类组成。这些集合类实现了计算机科学课程中所讲授的绝大多数数据结构，比如可变大小的数组类、链表类、平衡树类以及散列-集合类。

　　使用Java集合框架有几个好处。首先，学生使用的代码都已经经过广泛测试，而不需要由教员或者教科书作者另外创建一套模块。其次，学生们有机会学习专家们的代码，这些代码一定会比他们之前见过的代码高效，同时更加简洁。最后，这个框架可以用于教学大纲中的后续课程，甚至对课程的研究也同样有帮助！

其他实现

　　尽管Java集合类非常重要，但是在数据结构和算法基础课中，它并不是惟一的研究热点。那些不同于Java集合框架中的方法也值得考虑。例如，因为HashSet类和HashMap类使用链式结构，所以我们用单独的一节来讨论开放寻址，同时还讨论了不同设计的取舍。另外，本书还覆盖了Java集合框架中尚未包含的数据结构(例如图)和算法(例如堆排序)。

图形用户接口

　　我们使用了一个简单的图形用户接口(GUI)来取代控制台输入和输出，它的输入只有一行，输出可以有任意多行。第1章给出了这个GUI的大概轮廓，附录B给出了更为详细的描述。使用这个GUI带来2个问题，一个问题是无法循环输入，另一个问题是输出是滚动的。但是它的主要的目的是让学生更好地理解事件驱动模式编程的特征：面向现实世界环境。

教学方法

　　本书提供了几种方法来提高教员的教学环境和学生的学习环境。每一章开头处都列举了学习目标。每章在结束时提供至少一个较大的编程作业。我们对每一个数据结构都进行了详细描述，同时还讲解使用每个方法的前置条件以及后置条件。另外，绝大多数方法均有例子演示如何调用这些方法以及调用的结果。

　　本书仔细研究了实现细节，特别是Java集合框架的实现细节，并在24个实验组成的套件中得到加强。我们将在后文介绍这些实验的组织。

支持材料

　　www.mhhe.com/collins网站上有所有的支持材料，它为学生们提供了以下信息：

● 实验概要及获取方法；

● 本书开发的所有项目的源代码；

● 一些小应用程序(applet)，用于那些具有强大可视化组件的项目。

　　另外，教员也可以从该网站上获取以下信息：

● 关于实验的教员选项；

● 每章的PowerPoint幻灯片(大约有1500张)；

● 所有习题的解答。

内容提要

　　第1章作为全书后续章节的基础，描述了Java的特性。大部分材料反映了面向对象的思想：继承、多态以及异常处理。本章有几个实验用于复习类以及继承和异常处理。查阅前言中“实验组织”小节，可以获取更多关于实验的信息。

　　第2章介绍了抽象类和接口，每个专题都有实验。我们将关注Collection接口，它是Java集合框架中许多类的根。我们创建了一个简单版本的单向链表类(LinkedCollection)，作为Collection接口的简单实现。创建这个类的目的主要是为了介绍Java集合框架几个重要特性(如迭代器和内置类)提供技术背景。迭代器实验可以帮助学生巩固对这个重要概念的理解。

　　第3章介绍了软件工程，概括了软件开发周期的4个阶段：分析、设计、实现以及维护。本章引入统一建模语言(UML)作为设计工具来描述继承、组合和集合。后面几章中用到的大O符号为对各种方法所需时间(独立于特定环境)进行估算提供了一种手段。我们将讨论运行时的效率和时间特性，对于每个主题都有相应的实验。

　　第4章的主题是递归，我们暂时将重点从数据结构转移到算法上来。本章介绍了回溯，目的不仅仅在于提供一种解决问题的通用方法，而且用来演示如何通过接口来创建多态引用。同时这个BackTrack类还提供如下用途：搜索迷宫；在棋盘上放置8个皇后，使得没有一个皇后会被另一个皇后攻击；同样还用来演示一个武士可以横跨所有棋盘中的所有方格，并且只在每个方格上横跨一次。而递归的其他应用(例如Hanoi塔游戏)进一步说明了递归方法的优点，特别是在与迭代方法比较时。Fibonacci数字实验、二分法搜索实验以及排列生成实验更进一步地说明了递归方法的优越性。递归方法在后面的章节中还将遇到，尤其是在讲解使用Java集合框架进行快速排序和归并排序时。递归虽然很少被用到，但是它是每个计算机专家必不可少的工具。

　　在第5章我们将从ArrayList数据结构和类开始学习Java集合框架。ArrayList数据结构属于“智能”数组：能够自动调整数组大小，并且可以利用任何索引进行插入和删除。我们将从ArrayList类中使用最广泛的方法描述开始展开对类设计的讨论，包括方法的前置条件、后置条件以及方法头部。紧接着是这个类的实现概要，而进一步的实现细节留在实验中。应用ArrayList类可以实现高精度算术运算，这对于公钥加密是非常重要的。我们将在相应的实验和程序工程中进一步扩展这个应用。还将有另外一个编程项目用来开发Deque类。

　　第6章介绍了LinkedList数据结构和类，刻画了如何使用线性方法在任意位置进行插入、删除和检索。这个特性为链表迭代器提供了非常合适的使用场合：遍历ArrayList对象，在当前位置进行插入、删除或者检索具有常数时间的方法。Java集合框架设计使用的是双向链表和环形结构，但是我们还考虑了其他方法。其应用是行编辑器，而链表迭代器非常适合于这类应用。这章后面的编程项目将进一步扩展这个应用。

　　第7章的主题是队列和堆栈。Java集合框架目前并不包括Queue类(队列类)，但是使用一个LinkedList字段就可以非常容易和高效地实现它。另外我们还介绍了一个连续的实现。像计算排队洗车的平均等待时间这样的特殊应用属于计算机模拟通用类。java.util包中Stack类的实现在Java集合框架之前就已经存在了。Stack类有两个应用：实现递归以及中后缀符号转换。有个实验扩展了第二个应用，并形成了一个状态评估编程项目的基础。

　　第8章论述了一般的二叉树，然后特别地介绍二叉搜索树。本章描述了二叉树的一些关键特性，这些特性对于后面理解关于AVL树、red-black树、堆以及决策树等的材料非常重要。学习二叉搜索树为第9章的主题(平衡二叉搜索树)做好了铺垫。二叉搜索树实际上是Java集合框架中red-black树的单色版本。

　　第9章我们将着重讨论平衡二叉搜索树，以及AVL树和red-black树。引用旋转机制可以达到树的重新平衡。通过Fibonacci树的帮助，可确定AVL树的高度与该树中的元素个数总是成对数关系。red-black树也有类似的性质。我们实现了AVLTree类，但是没有实现remove方法(在编程项目9.1完成)。

　　第10章的重点是red-black树，利用Java集合框架中的TreeMap和TreeSet类来实现。在Map对象中，每个元素均有惟一的键-值对。TreeMap对象存储在red-black树中，按照元素的键进行排序。有几个实验通过一些细节来指导学生在插入和删除之后如何重构树。相关的应用包括在字典中查找同义词。TreeSet对象是作为TreeMap对象实现的，每个元素拥有相同的值。TreeSet类的应用之一是一个简单的拼写检查器。有些编程项目就是要判断文本文件中每个词出现的频率，然后建立关键词索引。

　　第11章介绍了PriorityQueue接口，它目前还不属于Java集合框架。基于堆的实现允许以常数的平均时间插入元素，同时以最差对数量级的时间来删除最高优先级元素。其应用是数据压缩领域，特别是Huffman编码：给定文本文件，产生最小的无前缀(prefix-free)编码。本章的编程项目是将编码转换成原始的文本文件。而实验是将公平性整合到优先级队列中，这样那些在优先级队列中等待时间最长的元素将获得优先处理。

　　第12章的主题是排序。我们估计了基于比较方法的排序的最大下界。Java集合框架提供了两种排序方法：针对基本数据类型数组的快速排序，以及针对由实现List接口的对象构成的数组的归并排序。同时还引进了其他两种很重要的排序方法：树排序和堆排序。本章的实验通过一组随机产生的整数对所有这些排序方法进行了比较。本章的编程项目是对一个名字和社会保险号码的文件进行排序。

　　第13章首先回顾了顺序检索和二叉树检索，然后研究了散列方法。Java集合框架为由键-值对组成的元素提供了HashMap类。HashSet类是退化的HashMap类，因为可以将HashSet对象看作是所有元素具有相同值的HashMap对象。插入、删除和搜索的平均时间基本上是常数。在比较HashMap和TreeMap对象的实验中将进一步探索平均速度。还有一个链式散列(它是HashMap类的基础)与开放地址散列的比较。在本章后面的编程项目中将深入探讨这个比较。

　　第14章介绍了最通用的数据类型，即图、树以及网络。首先简要介绍了几个关键算法：宽度优先遍历、深度优先遍历、连通性、寻找最小生成树以及寻找两点间最短路径。本章开发的惟一的一个类是基于邻接表实现的(有向)Network类。其他的类(如UndirectedGraph类和UndirectedNetwork类)均可以直接定义为Network类的子类。本章后面有个实验研究了货郎问题，还有一个编程项目用来完成Network类的邻接矩阵版本。此外还介绍了另一个回溯应用，它用到了第4章引入的BackTrack类。

　　每一章均有一个网页包含那一章中开发的所有程序以及applet，恰当地演示了所介绍的概念。

附录

　　附录A中所包含的背景知识让学生们能够领会各章的数学问题。求和符号和对数的基本特性是非常重要的，这些数学知识将使得我们对二叉树和开放寻址散列表的分析更加深入。

　　附录B是GUI类和GUIListener类的简明使用手册。这些类支持本书中以及实验中所有程序输入输出的事件模型。理解事件模型以及每个独立线程的作用要比理解控制台输入输出要复杂一些。但是实际上所有的应用程序都是事件驱动的，我们将来还要花时间研究这些主题。

　　附录C介绍了Java集合框架的用户视图。对于每个方法均提供了方法描述：前置条件、后置条件以及方法头。这6个类和4个接口的关系如下：

　　ArrayList类实现了List接口，List接口扩展了Collection接口；

　　LinkedList类实现了List接口，List接口扩展了Collection接口；

　　TreeMap类实现了Map接口；

　　TreeSet类实现了Set接口，List接口扩展了Collection接口；

　　HashMap类实现了Map接口；

　　HashSet类实现了Set接口，List接口扩展了Collection接口；

实验组织

　　与本书相关的有24个网站实验室。学生和教师均可以访问URL：www.mhhe.com/collins。这些实验室不包括那些关键的材料，但是提供了增强的文字材料。比如，在研究完ArrayList类和LinkedList类之后，有两个实验针对这两个类进行与时间相关的实验。

　　这些实验是自包含的，因此教师在安排实验时，可以灵活掌握：

　　(1) 可将它们布置成封闭的实验室

　　(2) 也可以将它们布置成开放的实验室

　　(3) 还可以把它们布置成不计学分的家庭作业

　　除了可以促进学生主动学习这一明显好处之外，这些实验还鼓励学生使用科学的方法。每个实验室基本上都是一次实践。学生们观察一些现象，如Java集合框架中LinkedList类的组织，然后使用他们自己的代码制定并提交一个关于这种现象的假设。在测试之后，也许还要修改假设，提交从这次实验中得出的结论。

　　前面几章的实验要比后面几章多。这样，学生在课程开始时就可以开始实验，甚至是在布置编程项目之前。