本书是数据结构课程的优秀教材。主要讲述如何在正确的软件工程原则指导下,用精心定义的数据结构和算法实现高质量的程序。为使读者能更好地理解本书,各章在内容安排上从易到难,对于每章所涉及的数据结构,都先介绍其概念,然后举例说明其用途再讨论如何用Java编程语言实现,最后对各种实现的效率进行分析、对比。
第1章 软件工程
1.1 软件开发
1.2 软件质量
1.3 软件开发生命期模型
1.4 统建模语言
1.5 错误的处理
1.6 算法的分析
1.7 软件工程和数据结构
第2章 集合
2.1 本章简介
2.2 袋集合
2.3 使用袋的例子:bingo
2.4 袋的数组实现
2.5 分析袋的数组实现
第3章 链式结构
3.1 链式引用
3.2 管理链表
3.3 无链接的元素
3.4 袋的链式实现
3.5 分析袋的链式实现
第4章 递归
4.1 递归思想
4.2 递归编程
4.3 使用递归
4.4 分析递归算法
第5章 查找与排序
5,1 查找
5.2 排序
第6章 堆栈
6.1 堆栈ADT
6.2 使用堆栈:计算后缀表达式
6.3 使用堆栈:模拟递归
6.4 堆栈的链式实现
6.5 堆栈的数组实现
6.6 实现堆栈:java.util.Stack类
6.7 分析堆栈的实现
第7章 队列
7.1 队列ADT
7.2 使用队列:代码键
7.3 使用队列:模拟售票器
7.4 使用队列:基数排序法
7.5 队列的链式实现
7.6 队列的数组实现
7.7 使用循环数组来实现队列
7.8 队列实现的分析
第8章链表
8.1 链表ADT
8.2 使用有序链表:制订赛程
8.3 使用索引链表:Josephus问题
8.4 链表的数组实现
8.5 链表的链式实现
8.6 分析链表的实现
第9章树
9.1 树
9.2树的实现策略
9.3 树的遍历
9.4 实现二叉树
9.5 使用二叉树:表达式树
第10章 二叉查找树
10.1 二叉查找树
10.2 二叉查找树的链式实现
10.3 使用二叉查找树实现有序链表
10.4 平衡二叉查找树
10.5 实现二叉查找树:AVL树
10.6 实现二叉查找树:红黑树
10.7 实现二叉查找树:Java集合API
第11章 堆
11.1 堆
11.2 使用堆:堆排序
11.3 使用堆:优先队列
11.4 堆的链式实现
11.5 堆的数组实现
11.6 分析堆的实现
第12章 多叉查找树
12.1 合并树的概念
12.2 2-3树
12.3 2-4树
14.4 B-树
12.5 B-树的实现策略
第13章 散列
13.1 散列
13.2 散列函数
13.3 解决冲突
13.4 删除哈希表中的元素
第14章 图
14.1 无向图
14.2 有向图
14.3 网络
14.4 图的通用算法
14.5 图的实现策略
附录A Java面向对象概念
附录B Java类库
随着Java语言的普及,已经有越来越多的程序开发人员喜欢上这种简单易懂的面向对象语言。与此同时,随着学习和应用的深入,数据结构和算法设计的重要性愈发显现出来。对于以前接触过C或C++的程序员而言,使用C或C++开发诸如队列、堆栈、链表和树等数据结构并非难事。遗憾的是,现在介绍Java数据结构和算法的好书却较少,使大家在进一步学习、使用Java的过程中遇到了一些困难。本书正是为此目的而撰写的。作者使用浅显易懂的语句来阐述一个个常见的数据结构,并配以大量的例子和代码来帮助大家理解如何使用Java实现这些数据结构。此外,本书还从软件工程的高度来分析、比较各种数据结构的实现效率,指出各种算法的优缺点。特别值得一提的是,每章都提供了大量的习题供读者复习时使用。附录A简要地阐述了Java面向对象概念,以帮助大家能更好地学习本书的内容;而附录B提供了Java类库中许多常用类的参考资料,使大家能够更容易地开发出自己的Java程序。
这确是一本介绍Java数据结构的好书。为使读者能更好地阅读本书,各章在内容的安排上不仅从易到难,而且在组织形式上力求保持一致:对于每章所涉及的数据结构,都先介绍它们的概念,接着举例说明它们的用途,然后讨论如何实现它们,最后分析比较各种实现的效率。为方便读者的学习,书中所有例子的源代码都可下载(www.aw.com/cssupport)。
全书的翻译出版是集体工作的结晶。柳赐佳、周莎莎、施晓东、施惠琼、蔡桂凌、施琳琼、陈华、柳晁锦、柳晁惠、施卓成、张琼雯、张庭辉、方杰等负责全书的翻译工作,柳小艳、孔颂燕、梁锦伦等负责全书的审校工作,施金庭、柳聿荫、施群肖和缪彩珠等负责全书的录入和排版工作。全书最后由施平安负责统稿。
在翻译过程中,我们对书中出现的所有术语和难词难句都进行了仔细的推敲和研究,然而有些问题在译者本人的研究领域中也不曾遇到过,疏漏和争议之处在所难免,望广大读者提出宝贵的意见。
译者
2004年2月10日
本书的目标是成为数据结构与算法课程的教材。因为该课程一般作为计算课程体系中的第二门课,所以通常把它称为CS2课程。我们在设计本教材时力求体现计算技术课程的宗旨。
从教学方法上看,本教材承袭了JohnLewis和WilliamLoftus编著的前导课CSl((Java程序设计基础》(本书已由清华大学出版社出版)的风格和方法,本教材借鉴了其强调的许多特征。这两本书都以严格而一致的方法倡导了正确的学习顺序。
这就是说,本书假定学生没学过((Java程序设计基础L因此,在课程中可能涉及的材料(诸如递归或者排序),都在本书中进行了介绍。附录A概述了面向对象概念以及如何用Java实现它们。该附录可以作为复习材料,或使具有不同基础的学生以最快的速度熟悉它们。
我们了解CS2课程在专业课中的关键作用,并认为本教材能够很好地满足该课程的需教学方法
这类教材在总体教学方法上差异很大。教学方法建立在我们极力强调的一个重要原则之上。首先,介绍了—一贯需要探讨的各种集合。其次,强调了健壮的软件设计技术的重要性。最后对本书进行了组织以支持和巩固重要构想:数据结构和算法的研究。让我们进一步研究这些原则。
一致性
在讨论某类集合时,我们依次解决如下问题:
. 概念:从概念上讨论集合,建立它所提供的服务,即接口
. 用法:用例子说明如何使用集合的特定性质解决问题,而不管如何实现
. 实现:探讨了集合的各种实现的选择
. 分析:对集合的实现进行了比较
在讨论中根据需要插入Java集合API。如果支持API中的某种特定集合类型,则对其和实现进行讨论。因此,我们讨论了API,但并不力求彻底地讨论。而且我们会毫不犹豫地指出它的不足。
高层次分析。我们在第1章中建立了大O表示法的概念,并在全书中一直使用它。这种分析法比数学分析法更直观。
健壮的程序设计
纵观全书,我们始终优先考虑健壮的软件工程实践。集合实现的设计及使用它们的程序的设计,这些都遵循一致而正确的标准。
最重要的是集合的接口与底层实现相分离。一个其功能提供的服务总是在Java接口中正式定义的。每当需要以抽象形式加强其功能时,就把接口名用作集合的类型名。
除了遵循严格的设计原则外,我们在全文的讨论中一直强调它们。我们力求通过例子和反复的强调来讲授设计原则。
清楚的结构
本书内容经过仔细编排,使离题的可能性最小,这样还可以强化本书的写作意图。这种编排使本书不仅可以作为宝贵的参考资料,而且还可以在数据结构与算法的教学研究中起作用。
本书可以分成三部分:第一部分由前5章组成,讨论了影响数据结构与算法的各种问题。第二部分包括第6~8章,讨论了线性集合(堆栈、队列和链表)。第三部分包括第9~14章,讨论了非线性集合(树、堆栈、散列和图)。除了树以外,其他各种集合类型均以单独一章进行讨论。树分散在若干章节中讨论,探讨了捌·在各个方面的应用问题。
附录A讨论了基本的面向对象概念,以及如何用Java实现这些概念。对于以前曾学过此内容的学生,它可以作为复习资料,而且既可以在讨论本书的主要内容之前介绍,也可以根据需要在每个主题之前介绍。对于那些在其他语言(诸如C++或者C#)中学过I:画向对象概念,并且需要了解如何用Java实现那些概念的学生,本附录也可以作为专用的Java教程。 附录B是Java类库中许多常用类的参考资料。学生手头拥有此信息,更容易开发他各章节剖析
第1章讨论了软件质量的各个方面,并概述了软件开发问题。本章的设计目标是,在具体讨论始数据结构与算法设计之前,培养正确的思维习惯。本章还介绍了算法分析基础的基本概念。
第2章建立了集合的概念,强调了接口与实现分离的必要性。作为一个例子,介绍了袋集合,并讨论了—种基于数组的实现。
第3章讨论了使川引用建立:链式数据结构。讨论了与链表管理有关的基本问题,然后使用基本的链式数据结构,重新定义了(第2章中介绍的)袋集合的另—一种实现。
第4章简要介绍了递归的概念,以及怎样才能优雅地进行递归求解。本章研究了递的具体实现细节,并讨论了分析递归算法的基本思想。
第5章讨论了线性查找算法和折半查找算法,同时还讨论了几种排序算法:选择排序、插入排序、冒泡排序、快速排序和归并排序。本章强调了与查找和排序有关的编程问题,诸如使用comparable接口作为对象比较的基础。第5章后面讨论了基于特定数据结构的查找和排序(诸如堆排序)。
第6章开始研究特定集合。我们从堆栈开始,从概念和实现上研究了各种集合。堆栈是一种非常直观的集合。本章同时讨论了基于数组的实现和基于链表的实现方法,然后对它们进行了比较。
第7章讨论了先进先出队列的概念和实现。作为有效使用队列的例子,讨论了基数排序。本章提供的实现包括基本的链表实现,以及固定循环数组实现。
第8章讨论了3种链表类型:有序链表、无序链表和索引链表。对这3种链表类型进行了比较,讨论了它们共有的操作和每种链表特有的操作。在各种链表的设计中正确地使用了继承,这些链表同时使用数组和链接表实现。
第9章概述了树,引入了关键术语和概念。本章讨论了树的各种实现方法,以及使用二叉树来表示和计算算术表达式。
第10章根据第9章中建立的基本概念来定义经典的二叉查找树。分析了二叉查找树的链接实现,然后讨论了树结点的平衡是性能问题的关键。由此引出了二叉查找树的AVL和红黑树实现的讨论。
第11章讨论了堆的概念、使用和实现。作为堆的实用性的例子,讨论了堆排序。本章同时讨论了堆的基于链接的实现和基于数组的实现。
第12章是前几章讨论的自然延伸。本章分析了2-3树、2-4树和基本B—树的概念论了各种可选的实现方案。
第13章讨论了散列的概念及其相关问题。本章讨论了散列的各种Java集合API。
第14章讨论了无向图和有向图的概念,并引入了重要的术语。本章讨论了几个常用的图算法,并讨论了各种实现方法,包括邻接矩阵。
对于需要复习基本的面向对象概念和了解如何用Java实现它们的读者,附录A的参考资料堪称首选。该附录包含了抽象、类、封装、继承和多态性的概念,以及许多相关的Java语言结构,诸如接口。
附录B是标准的JavaAPI类库中常用类的参考资料。
辅助资料
本书的所有读者可以在www.aw.com/cssupport上得到如下辅助资料:本书所有程序的源代码;有资格的教师可以得到教学辅助资料:教师手册(包含作者的注解、教学提示等);本书部分练习题和编程题的答案;TestGen测试库(包含试题中的问题);Powerpoint幻灯片(介绍了本书的内容和附录A);动画软件(演示了某些集合的处理过程)。有关如何得到它们的信息,请联系当地的Addison-Wesley销售代理,或者发电子邮件给aw.cse@aw.com。