本书是《数据抽象和问题求解—— Java语言描述》的第2版，相信本书会使您的教学或者学习大受裨益。Java目前已经成为计算机科学课程的主要语言之一，也非常适合以面向对象的方式讲解数据抽象原理。

本书基于Paul Helman和Robert Veroff合著的Intermediate Problem Solving and Data Structures:Walls and Mirrors(Benjamin/Cummings公司，1986年)，继承了原著的组织方式和理念，包括技术要点与正文内容、示例、图和练习题。Paul Helman和Robert Veroff教授把数据抽象和问题求解比喻为墙和镜子，并提出多种有利于教学的理念。

本书重点介绍数据抽象和其他主流的问题求解工具，非常适合作为计算机科学中级课程的教材。考虑到计算机科学的动态性和多样性，本书涵盖各种主题，以求适用于不同课程的教学要求。例如，可将本书用作数据结构入门级教材，也可用作高级程序设计和问题求解方面的教材。本书旨在使学生切实了解和掌握数据抽象、面向对象编程和其他高级问题求解技术。

第2版中的新增内容

基于Java 5：第2版进行了全面修订，以兼容Java的最新版本Java 5。书中的所有代码都修改为Java 5兼容版本。泛型是Java 5的重要部分，第9章将对它进行深入的讲解，并在后续章节中应用。

更多面向对象的Java知识：本书还增加了大量面向对象的Java语言知识，帮助学生从Java入门课程转向本课程。第1章概述了Java的重要概念，其中包括Java 5的新特性，例如Scanner类和自动装箱(autoboxing)。第9章重点介绍了Java的高级主题。

UML介绍：添加了UML(Unified Modeling Language，统一建模语言)的简要介绍，而且书中的所有伪代码都更新为使用UML。

使用Java集合框架：对Java集合框架(Java Collections Framework，JCF)的讨论贯穿全书，还新增了一些介绍JCF类的章节，提供了一些使用JCF类的示例。

其他扩充内容：其他的修订旨在提高整本书的可用性和可读性，包括一些新的练习和设计。

致学生

已经有成千上万的学生了解了“墙”和“镜子”的概念。“墙”和“镜子”代表两种贯穿全书的基本问题求解技术。“数据抽象”技术将模块的实现细节与程序的其余部分隔离开，就像一堵将您和邻居隔开的墙。“递归”是重复技术，通过解决同类型的小问题来解决问题，就像镜像一样，每次反射都会逐渐变小。

本书在编写时充分考虑了学生的需求。作者一直在从事教学工作，很明白清晰表述的重要性。本书在风格上力求明晰精练，通俗易懂。为了帮助学生学习本书，并通过练习进行复习，各章添加了小结、自我测试题及练习题，附录部分提供了自我测试题的答案和一个术语表。本书的第1章提供了Java参考资料。后面“本书概览”一节还列出了本书的主要特性。

第1章在章节概述中对学生掌握Java知识的情况作了几个基本的假定。有的学生可能是首次接触Java，或者需要对以前所学的Java知识进行全面回顾；而一些学生可能已经掌握了第1章中介绍的大部分编程知识。不管您属于哪一类，都需要知道if和switch分支结构，for、while和do迭代语句，类、方法、参数，数组，字符串和文件等。除了第1章中介绍的内容外，第9章还讨论了Java的一些高级主题，例如泛型和迭代器。本书还假定学生不具备使用递归方法的经验，所以在第3章和第6章中将讲述这方面的内容。

本书的所有Java源代码学生都可以使用。后面的“辅助资料”一节中将说明如何获取这些文件。

致教师

本书使用Java 5来描述数据抽象原理和数据结构。我们根据Java语言的优缺点，采用针对性的教学方法，力求做到实用、明确和透彻。

先决条件

本书要求学生了解Java的基础知识，或者了解另外一种高级语言，并有教师帮助他过渡到使用Java语言。对于没有Java语言背景的学生，可以通过第1章快速掌握其基本知识，为后面的学习打好基础。另外，本书还讨论了Java类，包括类的各种基本概念，诸如继承、多态性、接口和包。但本书只介绍这些与实现抽象数据类型(ADT)有关的内容，重点仍是ADT，而非Java。本书在基于对象的编程环境中介绍数据抽象，要求学生掌握面向对象设计和软件工程知识。这样，后面就会将注意力集中在数据抽象上。当然，我们还介绍了UML这种设计工具。

组织方式

本书分为两部分。一般而言，第1~11章是一学期的核心课程。第1~2章可作为学生的复习资料。可根据该课程在全部课程中的安排来选用第11~15章的内容。

安排灵活

本书内容详尽，教师可按课程计划，根据需要选择各章所讲的主题。下图列出了关联图，展示教师在教授某一章之前应帮助学生掌握的预备章节。

第I部分：问题求解技术

第I部分的前两章介绍了Java的基础知识、编程原理和软件工程，为进一步学习打下基础。第3章分析递归，帮助学生巩固基础知识；递归思维能力是计算机科学家必须掌握的实用技术之一，对理解问题的本质极具价值。这一章与后面的第6章全面、深入地讲解了递归技术，对它的应用也将贯穿全书。其中列举了大量递归实例，包括简单的递归定义，用于语言识别、查找和排序的递归算法等。

第4章详细讨论了数据抽象和抽象数据类型(ADT)。在讨论了ADT的规范和用法后，阐述了Java类、接口和包，并用它们来实现ADT。第5章在讨论Java引用变量和链表时介绍了其他的实现工具。

可根据学生的背景，选择并按适当顺序讲授这些主题。

第II部分：利用ADT解决问题

第II部分继续将数据抽象作为问题求解技术。首先指定栈、队列、二叉树、二叉查找树、表、堆和优先队列等基本ADT，然后将它们实现为类。在示例中使用ADT，并比较它们的实现。

第9章介绍继承、类之间的关系、泛型和迭代器，扩充学生的Java类知识。第10章介绍数量阶分析和大 O表示法，分析了递归归并排序、快速排序等几种查找和排序算法的效率。

第II部分还包括几个高级主题，如平衡查找树(2-3树、2-3-4树、红-黑树和AVL树)和散列，并用它们实现表。分析这些实现方案，确定它们最适合支持的操作。

最后分析从外部直接访问文件的数据存储器。修改归并排序来排序这些数据，用外部散列和B-树索引执行查找过程。这些查找算法是内部散列方案和2-3树的泛化。

在第I部分，可根据学生的背景选择讲授其中的主题。其中有3章介绍了数据抽象和递归。这两个主题都很重要，至于应首先介绍哪个，不同的人有不同的看法。本书是先介绍递归，后介绍数据抽象，但老师完全可以根据情况重新安排顺序。

第II部分亦是如此，老师可进行各种安排。例如，可在第7章(栈) 之前或之后讲解第9章(高级Java知识)的部分或者全部内容。在第6章后，可任意安排第10章(算法效率和排序)。可将树放在队列之前，或将图放在表之前；在讲授表后，可按任意顺序安排散列、平衡二叉查找树或优先队列。可提前讲授第15章的外部方法，例如，可在第10章的归并排序后讲授外部排序。

数据抽象

在本书介绍的问题求解方法中，普遍涉及到抽象数据类型(ADT)的设计和使用。一些例子说明如何将设计ADT作为解决方案总体设计的一部分。所有的ADT都是先用英语和伪码编写规范，然后将ADT用于简单的应用程序，最后考虑实现代码。ADT与实现它的数据结构的区别一直是中心议题。本书前面介绍了封装和Java类，以演示Java类如何对ADT的客户程序隐藏实现的数据结构。列表、栈、队列、树、表、堆和优先队列等抽象数据类型是讨论的重点。

问题求解

本书通过介绍计算机科学家的思考过程及所选用的技术，帮助学生学习如何整合问题求解和编程能力。学习计算机科学家如何开发、分析和实现解决方案与学习算法机制同等重要。

在示例问题中，包含了开发方案的分析技巧。抽象是对算法和数据结构的准确定义，而递归用于设计书中问题的解决方案。

本书先介绍Java引用和链表的处理，在构建数据结构时要用到它们。还简要介绍算法的数量阶分析。这种方式可先定性、后定量地分析基于数组和基于引用的数据结构的优缺点。强调各种可能的解决方案和实现之间的平衡是问题求解的中心内容。

在实现和验证解决方案时，编程风格、包含初始条件和结束条件的文档记录、调试工具和循环不变式是问题求解方法学的重要部分。这些内容将贯穿全书。

应用

在本书的重要主题中，列举了一些经典应用领域。例如，二叉查找、快速排序和归并算法提供了递归的重要应用，并引入了数量阶分析。平衡查找树、散列和文件索引等主题继续讨论了查找问题。在介绍外部文件时，又讨论了查找和排序。

本书首先在“递归”主题中介绍了识别和计算代数表达式的算法，后来又作为栈的应用讨论了这些问题。其他应用，如将八皇后(Eight Queens)问题作为回溯(backtracking)的例子，事件驱动模拟作为队列的一个应用，图查找和遍历作为栈和队列的其他重要应用。

本书概览

本书层次分明，组织精练，符合教材的特点。教师可按具体专业的要求做适当的调整。本书包含下面这些特色，不仅有助于学生第一次学习其中的内容，还有利于学生进行复习：

●       关键概念突出显示

●       每章有“小结”

●       每章有“提示”，指明常见错误

●       每章有“自我测试题”，书末附有“自我检测题答案”

●       每章有“练习题”和“编程问题”。难度较大的题目标有星号。答案在《教师资源手册》中

●       用英语和伪码编写所有主要ADT的规范

●       所有主要ADT的Java类定义

●       示例演示ADT在问题求解过程中的作用

●       附录包含Java资源和重要知识

●       书末有一个“术语表”。

辅助资料

本书的所有学生都可以通过www.aw.com/cssupport站点和www.tupwk.com.cn/ downpage在线获得以下资源：

●       源代码。包含书中所有Java类、方法和程序的源代码。

●       勘误表。虽然精心编写，但缺点与错误在所难免。特设立一个勘误表，并根据需要更新。欢迎您提出宝贵意见。

下面的内容只有教师才能使用。请通过书后的教附资料申请表从Prentice Hall驻北京办事处的销售代理商购买：

●       教师资源手册。这个手册包含教学技巧、示例库和章末练习题的答案。

●       试题库：其中包含很多选择题、判断正误题和简答题。

●       教学演示文档：能够演示书中的图文。