Java 数据结构和算法(第二版) (2009 年度畅销榜NO.311 )

本书介绍了计算机编程中使用的数据结构和算法，对于在计算机应用中如何操作和管理数据以取得最优性能提供了深入浅出的讲解。全书共分为15章，分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、二叉树、红黑树、哈希表及图形等知识。附录中则提供了运行专题Applet和例程、相关书籍和问题解答。本书提供了学完一门编程语言后进一步需要知道的知识。本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程，在学生掌握了编程的基础后才开始本书的学习。

出版说明\r\n献词\r\n简介\r\n第1章 综述\r\n 数据结构和算法能起到什么作用?\r\n 数据结构的概述\r\n 算法的概述\r\n 一些定义\r\n 面向对象编程\r\n 软件工程\r\n 对于C++程序员的Java\r\n Java数据结构的类库\r\n 小结\r\n 问题\r\n第2章 数组\r\n Array专题Applet\r\n Java中数组的基础知识\r\n 将程序划分成类\r\n 类接口\r\n Ordered专题applet\r\n 有序数组的Java代码\r\n 对数\r\n 存储对象\r\n 大O表示法\r\n 为什么不用数组表示一切?\r\n 小结\r\n 问题\r\n 实验\r\n 编程作业\r\n第3章 简单排序\r\n 如何排序? \r\n 冒泡排序\r\n 选择排序\r\n 插入排序\r\n 对象排序\r\n 几种简单排序之间的比较\r\n 小结\r\n 问题\r\n 实验\r\n 编程作业\r\n第4章 栈和队列\r\n 不同的结构类型\r\n 栈\r\n 队列\r\n 优先级队列\r\n 解析算术表达式\r\n 小结\r\n 问题\r\n 实验\r\n 编程作业\r\n第5章 链表\r\n 链结点(Link)\r\n LinkList专题Applet\r\n 单链表\r\n 查找和删除指定链结点\r\n 双端链表\r\n 链表的效率\r\n 抽象数据类型\r\n 有序链表\r\n 双向链表\r\n 迭代器\r\n 小结\r\n 问题\r\n 实验\r\n 编程作业\r\n第6章 递归\r\n 三角数字\r\n 阶乘\r\n 变位字\r\n 递归的二分查找\r\n 汉诺(Hanoi)塔问题\r\n 归并排序\r\n 消除递归\r\n 一些有趣的递归应用\r\n 小结\r\n 问题\r\n 实验\r\n 编程作业\r\n第7章 高级排序\r\n 希尔排序\r\n 划分\r\n 快速排序\r\n 基数排序\r\n 小结\r\n 问题\r\n 实验\r\n 编程作业\r\n第8章 二叉树\r\n 为什么使用二叉树?\r\n 树的术语\r\n 一个类比\r\n 二叉搜索树如何工作\r\n 查找节点\r\n 插入一个节点\r\n 遍历树\r\n 查找最大值和最小值\r\n 删除节点\r\n 二叉树的效率\r\n 用数组表示树\r\n 重复关键字\r\n 完整的tree.java程序\r\n 哈夫曼(Huffman)编码\r\n 小结\r\n 问题\r\n 实验\r\n 编程作业\r\n第9章 红-黑树\r\n第10章 2-3-4树和外部存储\r\n第11章 哈希表\r\n第12章 堆\r\n第13章 图\r\n第14章 带权图\r\n第15章 应用场合\r\n附录A 运行专题applet和示例程序\r\n附录B 进一步学习\r\n附录C 问题答案

Robert Lafore先生从1982年就开始编写计算机编程方面的书。他的畅销书有《Object-Oriented Pro-gramming in C++》，此书在世界上的销量已经超过200000册，还有《Assembly Language for the IBM PC》、《C Programming in Turbo C++》和《C++Interactive Course》。Lafore先生拥有数学和电子工程的学位，他从PDP-5时代就开始活跃在编程领域了。

在简介中简要说明： ● 第二版的新颖之处 ● 本书相关内容 ● 为什么它与众不同 ● 本书是为哪些读者而作 ● 在开始读书之前需要知道的知识 ● 所需的软件和设备 ● 本书是如何组织的 第二版的新颖之处. 本书的第二版在第一版的基础上有所扩充, 使之能更好地适应教师的计算机科学课堂教学, 并使读者在阅读上更加容易. 除去新增的章节, 还添加了章末问题. 实验和编程作业. 新增章节 在本版中加入了许多有趣的新内容. 其中许多为编制上机作业提供了基础. 这些新主题有： ● 深度优先搜索和游戏模拟 ● 约瑟夫(Josephus)问题 ● 数据压缩中的赫夫曼编码 ● 旅行售货员问题 ● 汉密尔顿(Hamilton)回路 ● 骑士旅行问题 ● 弗洛伊德(Floyd)算法 ● 沃赛尔(Warshall)算法 ● 2-3树 ● 背包问题 ● 从n个事物中取k个的组合方案 ● 哈希函数的数字折叠法 ● 基数排序 章末问题 每章结束后都会有几个简短的问题, 它们涵盖了该章的所有重点. 在附录C“问题答案”中可以找到相应的答案. 这些问题是用来给读者自测的, 以确保他们已经基本理解该章的内容. 实验 本书中收入了一些希望读者去做的活动. 这些实验经常包括使用专题applet或通过示例程序来检查某算法的一些特性, 当然有些实验只需要使用纸和笔, 或只需要“思维实验”. 编程作业 最重要的是, 在每章的结尾收入了一些(经常是五道)富有挑战性的编程题目. 它们的难度各不相同, 简单的题只是示例程序的变形, 最有挑战性的是那些在该章中讨论过的但并没有样例的程序问题. 本书没有附编程作业的答案和解法, 但可以看下面的注释. 注释 编程作业是为教师在留作业时提供参考用的. 为此, 那些有资格证明的教师可以得到编程作业题的参考解法的源程序和可执行文件. 请访问Sams Web网站获取相关信息. 本书相关内容 本书是一本有关计算机编程中所应用的数据结构和算法的书. 数据结构是指数据在计算机存储空间中(或磁盘中)的安排方式. 算法是指软件程序用来操作这些结构中的数据的过程. 几乎所有的计算机程序都使用数据结构和算法, 即使最简单的程序也不例外. 比如设想一个打印地址标签的程序, 这个程序使用一个数组来存储地址, 并且使用一个简单的for循环来遍历数组, 打印每一个地址. 在上面例子中的数组就是一个数据结构, 用for循环来顺序访问该数组, 这就构造了一个简单的算法. 对于一个仅有少量数据的简单程序来说, 上述的这种方法已经足够了. 但是如果用程序来处理中等规模以上的数据或解决那些不太平常的问题时, 就需要用一些更加复. 杂的技术来应付它们. 仅仅知道诸如Java或C++等计算机语言的语法是远远不够的. 本书提供了学完一门编程语言后进一步需要知道的知识. 本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程, 在学生掌握了编程的基础后才开始本书的学习. 本书的不同之处 有关数据结构和算法的书很多, 本书的不同之处有如下三条： ● 我们在写书过程中的主要目标是使本书所涉及到的知识尽可能地容易理解. ● 书中称作专题applet(Workshop applet)的演示程序可以将知识生动化, 它可以一步一步地通过“活动的图像”来展示数据结构和算法是如何工作的. ● 示例程序是用Java编写的, 它比那些传统的用来演示计算机问题的语言, 如C. C++或Pascal更好理解. 让我们来更加详细地讨论上述特性. 容易理解 传统的计算机课本中充满了理论. 数学公式和抽象的代码示例. 而本书将精力集中在那些可以解决现实问题的技术和方法的解释上, 竭力避免那些复杂的证明和笨重的数学公式. 本书中还有许多图表, 它们可以增加文字所不能表达的效果. 许多数据结构和算法的书都包括了大量的软件工程内容. 软件工程是一门有关设计和实现大型复杂的软件项目的学科. 然而我们认为数据结构和算法除去这些附加的规则后也是相当的复杂, 所以我们在本书中故意不强调软件工程的知识. (我们会在第1章中讨论数据结构和算法与软件工程的关系. ) 当然, 我们在本书中使用了面向对象的方法, 随着讨论的深入, 会涉及到面向对象设计的各个方面, 本书在第1章中还包含一个关于OOP的小教程. 但是, 我们的重点还是在数据结构和算法本身. 专题applet Sams Web网站上可以下载由涉及本书中所讨论主题的Java应用小程序(applet)组成的演示程序. 这些小程序(我们称之为”专题applet”)可以在绝大多数Web浏览器中运行(请参阅附录A). 专题applet通过“慢动作”的图像演示使读者能更好地理解一个算法的运行过程. 例如, 在一个专题applet中, 每按一下按钮, 柱状图会按照由小到大的顺序进行一步排列. 图中显示了排序算法中变量的值, 图中的文字表明了正在进行的步骤, 这样使读者能够清楚地看到在算法执行时计算机代码是如何工作的. 另一个小程序模拟了一棵二叉树. 通过观察箭头的上下移动, 可以跟踪插入或删除树中节点的每一步. 本书中有20多个专题applet, 每一章至少会有一个. 专题applet可以将数据结构和算法的真实一面清晰地表达出来, 这比文字描述要好得多. 当然, 我们在本书中同样会给出文字描述. 通过专题applet. 文字和图例的结合, 可使读者更容易理解书中的知识. 这些专题applet是可独立运行的图形化程序, 可以把它们当作学习工具来补充书中的材料. 请注意这些程序与我们下面要讨论的示例代码是不太一样的. 注释 关于专题applet, 在Sams网站(http：／／www.samspublishing. com／)中有Java. class形式的文件. 请在输入框中输入本书的ISBN号(没有连字符), 然后点击搜索. 当本书的名称显示出来后, 请点击可以下载小程序那页的链接. Java示例代码 Java语言比C和C++等语言都简单易懂且易写. 最大的原因就在于它没有指针. 有些人很惊讶为什么在建造复杂数据结构和算法时不需要指针. 事实上, 取消指针不仅意味着代码更加易写易懂, 还为程序提供了更高的安全性和更少的出错可能性. Java是一门现代的面向对象的语言, 这意味着可以使用面向对象的方法来进行编程. 这一点非常重要, 因为面向对象编程(OOP)不仅比过去的面向过程的方法拥有更多毋庸置疑的好处和优点, 而且在正式的程序开发中正在迅速地取代面向过程的方法. 读者如果对面向对象编程(OOP)不太熟悉的话, 请不必惊慌, 因为它并不那么难懂, 尤其是通过象Java这种没有指针的语言环境采学习就更方便了. 第1章将讲述面向对象编程的基础. 注释 与专题applet一样, 示例程序(源代码和可执行文件)可以在Sams网站中下载. 本书的读者对象 本书可以用来当作数据结构和算法课程的课本, 它通常是计算机科学课程表中二年级的课程. 当然, 它还适用于专业程序员和那些虽然仅有一些编程语言基础但是还想更上一层楼的人. 本书还可以作为其他正式教科书的补充教材. 在阅读前所需的知识 在开始阅读本书之前, 只需要知道一些编程语言的知识. 尽管示例代码是用Java写的, 但是并不是只有懂得Java才能明白我们在解释什么. Java也不难懂, 况且我们尽可能使用了普通的语法, 避开形式复杂的或Java专用的结构. 当然, 如果对Java已经很熟悉, 那是最好. 因为Java的语法规则与C++分接近, 所以如果会用C++, 对阅读本书也同样有帮助. 对于示例程序来说, Java和C++的区别不大(只是对指针的接受程度不同), 第1章中会讨论这两种语言. 阅读本书所需的软件 运行专题applet需要诸如Microsoft Internet Explorer或Netscape Communicator等Web浏览器, 还可以使用applet察看工具, 在许多的Java开发系统中都可以找到这些工具, 包括在附录A中讨论的Sun公司的免费系统. 可以使用Microsoft Windows中的MS-DOS环境(使用MS-DOS命令)或类似的文本环境来运行示例程序. 如果希望对示例程序进行修改或编写自己的程序, 还需要一个Java开发系统. 这些系统有的是收费的, 当然还可以从Sun公司下载一个优秀的免费系统, 请参阅附录A. 本书的组织结构 本节是为教师和那些希望快速了解本书内容的人而准备的. 下面的内容假定读者对数据结构和算法中的问题和术语已经相当熟悉. 前两章试图使读者尽可能轻松地进入数据结构和算法的世界. 第1章“综述”, 给读者一个各主题的总体印象并介绍少量后面要用到的术语. 对于那些对面向对象编程不太熟悉的读者, 本章总结了一些相关的知识. 对于那些知道C++而不熟悉Java的程序员, 本章对这两种语言的主要差别进行了描述. 第2章“数组”, 集中讨论数组. 这里面包含有两层意思：如何使用类来对数据存储结构进行封装和类的接口. 其中包括数组和有序数组的查找. 插入. 删除. 线性查找和二分查找. 专题applet通过对无序和有序的数组进行操作来解释上述算法. 第3章“简单排序”介绍三种简单的(但是慢速的)排序方法：冒泡排序. 选择排序和插入排序. 每一种排序都有一个相应的专题applet. 第4章“栈和队列”涉及到三种可以被认为是抽象数据类型(ADT)的数据结构：栈. 队和优先级队列. 这些结构在本书中大量重复出现, 是许多算法的基础. 每一种结构都有一个相应的专题applet. ADT的概念也会在本章中讨论. 第5章“链表”介绍了链表中的双向链表和双端链表. 本章还解释了Java中被称作“无痛指针”的使用, 并用一个专题applet演示了链表的插入. 查找和删除是如何进行的. 第6章“递归”探索了递归的知识, 这是书中仅有的非数据结构的几章之一. 本章给出了大量的递归例子, 包括汉诺塔问题和归并排序, 它们都有相应的专题applet. 第7章“高级排序”研究了几种高级的排序方法：希尔排序和快速排序. 专题applet演示了希 尔排序, 快速排序的基础一一划分(partitioning)和两种形式的快速排序. 第8章“二叉树”开始了对树的探索. 本章中介绍了最简单最通用的树型结构：不平衡的二叉搜索树. 一个专题applet演示了此类树的插入. 删除和遍历是如何进行的. 第9章“红-黑树”解释了红-黑树, 它是最有效的平衡树之一. 专题applet演示了平衡这种树所需的旋转和颜色转换. 第10章“2-3-4树和外部存储”将2-3—4树作为多叉树的一个例子进行了讲解. 专题applet会演示它们是如何工作的. 我们还将讨论2-3树和2-3-4树与B树的关系, 这些知识对于存储外部(磁盘)的文件十分有用. 第11章“哈希表”转到哈希表这个新的讨论领域. 专题applet演示了几种方法：线性. 二次探测和再哈希及链地址法. 本章中还讨论了哈希表方法在组织外部文件方面的应用. 第12章“堆”讨论了一种特殊的树——堆, 用它作为优先队列的一种有效的实现手段. 第13章“图”和第14章“带权图”处理图的相关问题, 前者处理未加权图和简单的查找算法, 后者处理带权图和更加复杂的算法, 如最小生成树和最短路径. 第15章“应用场合”总结了前几章描述过的各种数据结构, 还着重讨论了如何在给定情况下应用合适的数据结构的问题. 附录A“运行专题applet和示例程序”提供了如何使用这两种软件的细节. 此部分同时讲解了如何使用来自Sun公司的软件开发工具集, 可以用它来修改示例程序或开发自己的程序, 还可以通过它来运行专题applet和示例程序. 附录B“进一步学习”介绍了一些关于数据结构和相关内容的进阶书籍. 附录C“问题答案”包括了书中章末问题的解答. 请好好享受吧! 希望我们能使学习的过程尽可能地没有痛苦, 依我们的理想, 学习的过程甚至应该是快乐的. 如果我们实现了这个理想, 请让我们一起分享你所得到的快乐, 如果没有, 请告诉我们何处应该改进. 本书可帮助读者： 通过由基于Java的演示程序所组成的可视专题讨论来掌握数据结构和算法 学会如何为常见和不太常见的编程条件选择正确的算法 利用数据结构和算法为现实世界的处理过程建模 了解不同的数据结构的优势和弱点, 考虑如何利用它们改进编程的效率 学会如何用面向对象的编程简化数据结构和算法 本书以一种易懂的方式教授如何安排和操纵数据的问题, 其中不乏一些难题, 了解这些知识以期使计算机的应用获得最好的表现, 不管使用何种语言或平台, 掌握了数据结构和算法将改进程序的质量和性能： 书中提供了一套独创的可视讨论专题用以阐明主要的论题, 它使用Java语言说明重要的概念, 而避免了C／C++语言的复杂性, 以便集中精力论述数据结构和算法. 经验丰富的作者Robert Lafore先生提供了许多简单明了的例子, 避免了对于这类命题常见的冗长. 繁琐的数学证明 在第二版中, 他利用Java语言最新特性, 修改并扩充了他的例子在每一章后都有问题和练习, 使读者有机会测试自己的理解程度