前 言 本书是Java版的《数据抽象和问题求解》，重点讲述数据抽象、数据结构和递归技术。考虑到计算机科学的动态性和多样性，本书涵盖各种主题，以求适用于不同课程的教学要求。可将本书用作初级数据结构教材，也可用作高级编程和算法设计教材。本书旨在使学生切实了解和掌握数据抽象、面向对象编程及其他主流的问题求解技术。 本书基于Paul Helman和Robert Veroff合著的Intermediate Problem Solving and Data Stractures:Walls and Mirrors(Benjamin/Cumming公司，1986年)，继承了原著的组织方式和理念，技术要点与文字内容、示例、图和练习题。Paul Helman和Robert Veroff教授把数据抽象和问题求解比作墙和镜子，并提出多种有利于教学的理念。 致读者 “墙”和“镜子”代表基本问题求解技术。“数据抽象”将模块实现细节与程序其余部分隔离，就像一堵将您和邻居隔开的墙。“递归”是重复技术，通过解决同类型的更小问题来解决问题，就像各映像逐渐变小的镜子。 本书风格上力求明晰精练，通俗易懂。各章添加了小结、自我测试题及答案，末尾有一个术语表。附录A提供Java参考资料。 若之前不了解Java语言基础知识，请阅读附录A，以理解选择语句、迭代语句、类、方法、参数、数组、字符串和文件。若要系统分析Java类，请阅读第3、8章。若要全面了解递归，请阅读第2、5章。 内容设计 本书根据Java语言的优缺点，采用针对性的教学方法，力求做到实用、明确和透彻。 先决条件 在学习本书前，若不了解Java语言，则应在教师指导下学习附录A，以了解如何过渡到Java。本书在基于对象的编程环境中介绍数据抽象。虽然讨论了Java类及其基本概念，分析如何将抽象数据类型实现为类，但本书的主题是ADT(抽象数据类型)，而非Java。 安排灵活 本书内容详尽。教师可按课程计划，根据需要选择。下面列出关联图，显示某一章的预备章节。 在第I部分，第3章介绍数据抽象，第2、5章探讨递归，对于这些重要主题，可根据学生背景，重排顺序。 第II部分亦如此。例如，可将第6章(栈)排在第8章(类关系)之前或之后。在第5章后，可任意安排第9章(算法效率和排序)。可将树放在队列之前，将图放在表之前；在讲授表后，将按任意顺序安排散列、平衡叉查找树或优先队列。可提前讲授第14章的外部方法，例如，可在第9章的归并排序后讲授。 数据抽象 在本书介绍的问题求解方法中，普遍使用了抽象数据类型(ADT)。一些例子说明如何将设计ADT作为解决方案总体设计的一部分。对于所有ADT，首先用英语和伪码编写规范，然后将ADT用于简单应用程序，最后考虑实现。ADT与数据结构的区别一直是中心议题。本书前面介绍了封装和Java类，以演示Java类如何对ADT的客户程序隐藏数据结构。列表、栈、队列、树、表、堆和优先队列的抽象数据类型是讨论的重点。 问题求解 本书介绍计算机科学家的思考过程及技术选用，讲述如何整合问题求解和编程能力。学习计算机科学家如何开发、分析和实现解决方案与学习算法机制同等重要。 在示例问题的上下文中，包含开发方案的分析技巧。在设计问题的解决方案时，广泛采用抽象、算法与数据结构的逐步完善以及递归。 第4章介绍Java引用和链表处理。第9章简介算法的数量阶分析。先定性，后定量地比较基于数组和基于引用的数据结构。各种可能的解决方案和实现的交替使用是问题求解的中心内容。 另外，在实现和验证解决方案时，编程风格、包含初始条件和结束条件的文档记录、调试工具和循环不变式是问题求解方法学的重要部分。 应用程序 在本书的重要主题中，列举了一些经典应用程序。例如，折半查找、快速排序和归并算法提供了递归的重要应用，并引入了数量阶分析。平衡查找树、散列和文件索引的主题讨论了查找应用。在介绍外部文件时，又讨论了查找和排序。 本书首先在递归上下文中介绍了识别和计算代数表达式的算法，后来又作为栈的应用讨论了这些问题。其他应用程序，如八皇后问题作为回溯例子，事件模拟作为队列的应用，图查找和遍历作为栈和队列的其他重要应用。 新添和修订内容 本版沿承了C++版的基本方法和理念。在介绍数据抽象和编程时，既作为一般概念，又在Java环境中讨论。在编写此版本时，我们逐一剖析每个句子、例子和图。为达到新颖、实用的目的，对原来的内容做了适当增删和修订。 本书修改了所有算法的伪码，以反映Java的面向对象方法；所有编程例子用Java语言编写。几项重要修订如下： ● 第1章的代码实现和风格基于一般Java惯例。 ● 第3章介绍Java类，简介继承。涉及Java接口、Object类、异常、无用单元收集和对象相等测试。此后将这些主题集成到ADT规范的讨论。Java接口分离规范和实现。本书的ADT存储对象(而非数据)，用异常标记错误。 ● 第4章分析Java引用，作为修订的链表处理的基础。链表节点是Node类实例。增加了一节，讲述链表的尾引用。完善了清单问题的解决方案，引入了对象串行化。 ● 第8章深入探讨继承，分析Java包、字段修饰符、抽象类、方法重载、接口和迭代器。 ● 第10章重新设计树类层次，为遍历操作使用树迭代器。第10、12章使用类定义树节点。 ● 附录A简要介绍Java。 ● 附录B是统一代码表。 ● 附录C简介Java API，提供附加Java资源的链接。 ● 新练习和编程问题。修改或替换了很多练习题和编程问题。 ● Java代码。充分挖掘Java优势，而非简单地将C++转换成Java实现。 本书概览 本书层次分明，组织精当，符合教材特点。教师可按具体专业要求做适当调整。 本书特色 本书的特色如下，以便读者学习和复习： ● 每章有“本章概述”。 ● 每章有“小节”。 ● 每章有“提示”，指明常见错误。 ● 每章有“自我测试题”，书末附有“自我检测题答案”。 ● 每章有“练习题”和“编程问题”。难度较大的题目的标有星号。答案在《教师资源手册》中。 ● 用英语和伪码编写所有主要ADT的规范。 ● 所有主要ADT的Java类定义。 ● 实例演示ADT在问题解决过程的作用。 ● 附录A简介Java。 ● 书末有一个“术语表”。 编排形式 本书分两部分。一般而言，第1—11章是一学期的课程。第1—2章可作为简介资料。可根据课程在全部课程中的安排来选用第11—14章。《教师资源手册》阐述本书在不同课程的使用。 第I部分：问题求解技术。 第1章简要介绍编程和软件工程的主要问题。第2章分析递归，供学生巩固基础；递归思维能力是计算机科学家必须掌握的实用技术之一，对理解问题本质极有价值。第5章深入分析递归。本书列举了大量递归实例，范围很广，从简单递归定义，到语言识别、查找和排序的递归算法。 第3章详细讨论数据抽象和抽象数据类型。在讨论了ADT列表的规范和使用后，接着讨论Java类、接口和异常，并使用它们来实现ADT。第4章讨论Java引用变量和链表时介绍了其他实现工具。 可根据学生背景，选择并按适当顺序讲授这些主题。 第II部分：用ADT解决问题。 第II部分一直将数据抽象作为问题求解技术。首先指定诸如栈、队列、二叉树、二叉查找树、表、堆和优先队列等基本ADT，然后将ADT实现为类。在实例中使用ADT，并比较各种实现。 第8章介绍继承、包、类关系和迭代器。第9章引入数量阶分析和大O表示法，分析了递归归并排序、快速排序等几种查找和排序算法的效率。 第II部分还包括几个高级主题，如平衡查找树(2-3树、2-3-4树、红-黑树和AVL树)和散列，并用它们实现表。分析这些实现，确定它们最适合支持的操作。 最后分析外部直接访问文件的数据存储。修改归并排序来排序数据，用外部散列和B-树索引执行查找。这些查找算法是内部散列方案和2-3树的泛化。 在线补充资料 在线可获得以下资料。 ● 源代码。读者可使用本书所有Java类、方法和程序。 ● 勘误表。虽然精心编写，但缺点与错误在所难免。特设立一个勘误表，并根据需要更新。欢迎您提出宝贵意见。 登录ftp站点，在/cseng/authors/carrano/java目录，可获得源代码和勘误表。 ● 教师资源手册。教师可联系Addison Wesley Longman的销售代表，获取章末练习题解决方案，以及教学笔记和建议。