数据结构与问题求解：Java语言描述（第3版）（用Java语言讲述数据结构的经典教材）

.第3章 递归
3．1 什么是递归
3．2 背景；数学归纳法证明
3．3 基本的递归
3．4 数值应用
3．5 分治算法
3．6 动态规划
3．7 回溯
第4章 排序算法
4．1 排序为什么重要
4．2 预备知识
4．3 插入排序及其他简单排序算法的分析
4．4 谢尔排序
4．5 归并排序
4．6 快速排序
4．7 快速选择
4．8 排序的下界
第5章 随机化
5．1 为什么需要随机数
5．2 随机数生成器
5．3 非均匀分布随机数
5．4 产生随机排列
5．5 随机化算法
5．6 随机化素数检验
第二部分 应用
第6章 娱乐和游戏
6．1 单词搜索迷宫
6．2 tic-tac-toe游戏
第7章 栈和编译器
7．1 平衡符号检查器
7．2 简单计算器
第8章 实用程序
8．1 文件压缩
8．2 交叉引用生成器
第9章 模拟
9．1 约瑟夫问题
9．2 事件驱动模拟
第10章 图和路径
10．1 图的定义
10．2 非加权的最短路径问题
10．3 非负权值的最短路径算法
10．4 含负权值的最短路径问题
10．5 无环图的路径问题
第三部分 实现..
第11章 内部类和arraylist的实现
11．1 迭代器与嵌套类
11．2 迭代器和内部类
11．3 abstractcollection类
11．4 stringbbuilder
11．5 使用迭代器的arraylist的实现
第12章 栈和队列
12．1 动态数组的实现
12．2 链表实现
12．3 两种实现方式的比较
12．4 java．util．stack类
12．5 双向队列
第13章 链表
13．1 基本思想
13．2 java实现
13．3 双向链表和循环链表
13．4 有序链表
13．5 集合类api中linkedlist类的实现
第14章 树
14．1 普通的树
14．2 二叉树
14．3 递归和树
14．4 树的遍历：迭代器类
第15章 二叉查找树
15．1 基本思想
15．2 顺序统计量
15．3 二叉查找树操作的分析
15．4 avl树
15．5 红黑树
15．6 aa树
15．7 集合类api中treeset类和treemap类的实现
15．8 b树
第16章 散列表
16．1 基本概念
16．2 散列函数
16．3 线性探测法
16．4 二次探测法
16．5 分别链接散列
16．6 散列表与二叉查找树
16．7 散列表的应用
第17章 优先级队列：二叉堆
17．1 基本概念
17．2 基本操作的实现
17．3 buildheap操作：线性时间的堆构造
17．4 高级操作：decreasekey和merge
17．5 内排序：堆排序
17．6 外排序
第四部分 高级数据结构
第18章 伸展树
18．1 自调整和均摊法的分析
18．2 基本的自底向上的伸展树
18．3 基本的伸展树操作
18．4 自底向上伸展的分析
18．5 自顶向下的伸展树
18．6 自顶向下伸展树的实现
18．7 伸展树与其他搜索树的比较
第19章 归并优先级队列
19．1 斜堆
19．2 偶堆
第20章 不相交集类
20．1 等价关系
20．2 动态等价及应用
20．3 快速查找算法
20．4 快速并算法
20．5 java实现
20．6 按秩并和路径压缩的最坏情况
附录a 运算符...
附录b 位运算符

.　　第一部分讨论大O表示法和算法范型，包括递归和随机化。我用一章介绍排序，另一章描述基本数据结构。用集合类API讲述数据结构的接口和运行时间。至此，教师可以有几种方法介绍剩余的内容，具体包括下面两种。
　　(1)在第三部分中，当描述每个数据结构时讨论对应的实现(集合类API的版本或者较简单的版本)。教师可以要求学生以各种方式扩展类，如习题中所建议的。
　　(2)先说明如何使用集合类API的每个类，在课程的稍后部分再介绍实现。第二部分中的实例研究可以用来支持这种方法。因为完整的实现在每个较新的Java编译器上都可使用，教师可以在程序设计项目中使用集合类API。这种方式的详细介绍将在稍后讨论。
　　第四部分描述了高级的数据结构，如伸展树、偶堆和不相交集数据结构。如果时间允许的话，可以讲述这些内容，或者将其作为下一门课程的内容。
　　逐章内容的组织
　　第一部分集中讲基本的算法和构件块。第1章提供了时间复杂度和大O表示法的完整讨论，还讨论和分析了二分搜索。第2章非常重要，因为它覆盖了集合类API，并直观地论证了每个数据结构所支持的操作的运行时间是多少(在第三部分讨论这些数据结构的实现，包括集合类API风格的版本和简化的版本)。这一章还讨论了迭代器模式以及嵌套、局部和匿名类。内部类推迟到第三部分，作为实现技术讨论。第3章讨论递归，首先介绍归纳法证明，然后讨论分治、动态规划和回溯。有一节专门描述一些递归的数值计算算法，这些算法可用来实现RSA密码系统。对许多学生来讲，第3章后半部分的材料更适合在后续课程中学习。第4章对一些基本的排序算法进行了描述、编码和分析，包括插入排序、谢尔排序、归并排序和快速排序，以及间接排序。它也证明了排序算法的标准下界，并讨论了与选择相关的问题。第5章讨论了随机数，包括它们的生成和在随机化算法中的使用。
　　第二部分提供了一些实例研究，每一章围绕一个主题。第6章通过游戏介绍了一些重要技术。第7章通过平衡符号检查算法和标准运算符优先级解析算法讨论了计算机语言中栈的使用，而且提供了两个算法的完整实现代码。第8章讨论了文件压缩和交叉引用生成的基本实用程序。第9章泛泛地介绍了模拟的问题，首先介绍了一个可视为模拟的问题，然后介绍了更一般的事件驱动模拟。最后，第10章说明如何用数据结构来有效地实现图中的一些最短路径算法。
　　第三部分介绍数据结构的实现。第11章讨论了作为一种实现技术的内部类，并说明它们在ArrayList实现中的使用。在第三部分的剩余章节中提供了使用简单协议(各种insert、find和remove)的实现。在某些情况下，提供了使用更复杂Java语法的集合类API实现(复杂性还源自所需操作的数量较大)。在这一部分用到了一些数学知识，特别是第15章～第17章，教师可以根据教学情况跳过这些内容。第12章提供了栈和队列的实现：首先用扩展数组来实现，然后用链表来实现，最后讨论集合类API的版本。第13章讨论通用链表。单链表用一个简单的协议来说明，使用双向链表的更复杂的集合类API版本的实现在该章的最后讨论。第14章描述了树，并介绍了基本的遍历方式。第15章非常具体，它提供了二叉查找树的一些实现。一开始说明了基本的二叉查找树，然后延伸出支持顺序统计量的二叉查找树。该章讨论了AVL树但没有给出其实现，不过实现了更实用的红黑树和AA树。然后是集合类API中TreeSet和TreeMap的实现，最后研究了B树。第16章讨论了散列表，并在研究了一个较简单的可选方案后，介绍了作为HashSet和HashMap一部分的二次探测法的实现。第17章描述了二叉堆，并研究了堆排序和外排序。Java 5的集合类API中有优先级队列，因此我们实现了标准的版本。
　　第四部分的内容适用于更高级的课程或作为一般的参考，其中的算法对一年级的学生也适用。但为了完备性，这一部分包含了超出一年级学生理解范围的复杂数学分析。第18章描述了伸展树，它是一种在实际应用中效果非常好的二叉查找树，在某些需要优先级队列的应用中，它是二叉堆的竞争者。第19章描述了支持归并操作的优先级队列，并提供了偶堆的实现。最后，第20章研究了不相交集的标准数据结构。
　　章之间的依赖性
　　一般来讲，大多数章是互相独立的，下面是一些需要注意的依赖关系。
　　·第1章 这一章应该在第2章和第4章之前介绍。递归(第3章)可以在这一章前面讲，但是，这样教师就要忽略掉某些避免低效率递归的细节问题。
　　·第2章 这一章可以在第二部分或第三部分之前讲，也可以和它们结合在一起讲。
　　·第3章 3．1节～3．3节的内容应该在讨论递归排序算法、树、Tic-Tac-Toe实例研究和最短路径算法之前讲，而RSA密码系统、动态规划和回溯(须先讨论Tic-Tac-Toe)可以选讲。
　　·第4章 这一章应该在第1章和第3章之后讲，不过没有第1章和第3章也能介绍谢尔排序。谢尔排序不是递归的(因此不需要第3章)，其运行时间的严格分析太复杂了，超出了本书的范围(因此几乎不需要第1章)。
　　·第11章 这部分材料应该在集合类API的实现之前讨论。
　　·第12章和第13章 这两章可以交换次序讲授。不过我宁愿先讲第12章，因为我相信它们比链表简单。
　　·第14章和第15章 这两章可以交换次序讲授或同时讲授。
　　独立部分
　　其余部分几乎没有或完全没有依赖关系。
　　·第5章 有关随机数的部分可以在需要时介绍。
　　·第二部分 第6章-第10章可以与集合类API一起讲，也可以在集合类API后面讲，这几章本身可以是任意次序。这一部分有一些对前面几章的引用，包括6．2节参考了3．7节的讨论，8．2节参考了7．1节中类似的词法分析代码。
　　·第16章和第17章 这两章可以在任何时候讲。
　　·第四部分 第18章～第20章的内容是独立的，通常应包含在后续课程中。
　　数学
　　我试图为强调理论的数据结构课程和需要更多分析的后续课程提供数学上的严密性。这些内容以独立的定理的形式(在某些情况下，是以独立的节或小节的形式)与书的正文相区分。在不强调理论的课程中，教师可以跳过这些内容。
　　在所有的情况下，定理的理解并不需要定理的证明。这是接口(定理的陈述)和它的实现(证明)分开的另一个实例。某些数学内容(如3．4节)可以跳过，不会影响其他部分的理解。
　　课程的组织
　　教授这门课的一个关键问题是确定如何使用第一部分到第三部分的材料。第1章讨论大O表示法。有一个习题要求学生写一个短程序并将运行时间与分析结果相比较，它可以用来测试学生的
　　理解程度。
　　第2章的关键的思想是以分类的方式说明不同的数据结构能够以不同的效率支持不同的访问模式。任何实例研究(除了使用递归的Tic-Tac-Toe)都可以用来说明数据结构的应用。这样学生能了解数据结构以及它们是如何使用的，但不知道它们是如何有效地实现的。这就是本书与传统方法的区别所在。以这种方式观察事物将极大地提高学生抽象思维的能力。学生还可以提供某些集合类API组件的简单实现(第2章中的习题给出了一些建议)，并看到已有的集合类API的高效数据结构实现和他们自己写的低效数据结构实现之间的区别。也可以要求学生扩充实例研究，但他们同样不需要知道数据结构的任何细节。
　　数据结构的有效实现可以在后面讨论，递归可以在教师认为合适的任何时候介绍，但是必须在二叉查找树以前。排序的细节可以在递归之后的任何时候讨论。这时，可以用同样的实例研究，根据对数据结构实现的修改进行实验，继续我们的课程。例如，学生可以用不同形式的平衡二叉查找树做实验。
　　选择更传统的方法的教师可以在讨论了第三部分中数据结构的实现后，再讨论第二部分中的实例研究。再重申一次，本书各章的安排尽可能设计成了互相独立的。
　　习题
　　习题有各种形式，我提供了四种。基本的简答题是一些简单的问题，或需要对本书描述的算法做手工的模拟。理论题考查一些需要数学分析或者理论上具有比较有趣的解的问题。实践题包含一些简单的程序设计问题，包括有关语法或某些有技巧的代码行的问题。最后，程序设计题包含一些扩展性习题。
　　教学特色
　　·书中的注释(加灰底的段落)用来突出要点。
　　·关键概念列出重要的术语及它们的定义。
　　·每章最后的常见错误列出了经常容易犯的错误。
　　·在大部分章的最后提供了可供进一步阅读的参考文献。
　　补充材料
　　本书有各种可用的补充材料。对本书的所有读者，下面的资源可以在http：／／www．aw-bc．com／cssupport找到。
　　·本书的源代码文件。(在每章后面的网上资源列出了该章代码的文件名。)
　　·本书中所有图的PowerPoint幻灯片。
　　此外，通过验证的教师可以使用以下的补充材料。访问http：／／www．aw-bc．com／computing，并按英文书名Data Structures and Problem Solvlng Using Java进行搜索，一旦到达了本书的目录页，选择Instructor Resources链接即可。
　　·Instructor Guide给出了获得材料的几种途径。材料包括测试题的实例、作业、教学大纲以及部分习题的答案。
　　致谢
　　在完成本书的过程中，许许多多人都给予了我帮助。在以前版本和相关C++版本中我已向他们表示了谢意。但还有很多人给我发过电子邮件指出错误或解释的不一致，这些问题我已经在这个版本中改正了，但无法一一向他们致谢。
　　对本版，我要感谢Addison-Wesley的朋友们，他们是本书的编辑Michael Hirsch、项目编辑Juliet Silveri和Gillian Hall，以及市场部的Michelle Brown。同时也感谢文字编辑Penelope Hull、校对Holly McLean-Aldis，以及封面设计Joyce Wells。
　　本书的某些材料是根据我的教材Efficient C Programming：A Practical Approach(Prentice Hall，1995)改编的，并得到了出版者的允许。我已经在章后面的适当位置包含了该参考文献。
　　我的主页http：／／www．cs．fiu．edu／～weiss将包含更新的源代码、勘误表以及用来接受错误报告的链接。...
　　 M．A．W
　　于佛罗里达州迈阿密市