数据结构与算法分析 JAVA语言版PDF电子书下载

第1章　Java与面向对象程序设计 1

1.1　Java语言基础知识 1

1.1.1　基本数据类型及运算 1

1.1.2　流程控制语句 2

1.1.3　字符串 3

1.1.4　数组 5

1.2　Java的面向对象特性 7

1.2.1　类与对象 7

1.2.2　继承 9

1.2.3　接口 10

1.3　异常 12

1.4　Java与指针 13

第2章　数据结构与算法基础 15

2.1　数据结构 15

2.1.1　基本概念 15

2.1.2　抽象数据类型 17

2.1.3 小结 19

2.2　算法及性能分析 20

2.2.1 算法 20

2.2.2　时间复杂性 20

2.2.3　空间复杂性 24

2.2.4　算法时间复杂度分析 25

2.2.5　最佳、最坏与平均情况分析 27

2.2.6　均摊分析 28

第3章　线性表 32

3.1　线性表及抽象数据类型 32

3.1.1　线性表定义 32

3.1.2　线性表的抽象数据类型 33

3.1.3　List接口 34

3.1.4　Strategy接口 35

3.2　线性表的顺序存储与实现 37

3.3　线性表的链式存储与实现 43

3.3.1 单链表 43

3.3.2　双向链表 47

3.3.3　线性表的单链表实现 49

3.4　两种实现的对比 54

3.4.1　基于时间的比较 54

3.4.2　基于空间的比较 54

3.5　链接表 54

3.5.1　基于结点的操作 54

3.5.2　链接表接口 55

3.5.3　基于双向链表实现的链接表 57

3.6　迭代器 60

第4章　栈与队列 63

4.1　栈 63

4.1.1　栈的定义及抽象数据类型 63

4.1.2　栈的顺序存储实现 65

4.1.3　栈的链式存储实现 66

4.2　队列 68

4.2.1 队列的定义及抽象数据类型 68

4.2.2　队列的顺序存储实现 69

4.2.3 队列的链式存储实现 73

4.3　堆栈的应用 74

4.3.1 进制转换 75

4.3.2　括号匹配检测 75

4.3.3　迷宫求解 77

第5章　递归 81

5.1　递归与堆栈 81

5.1.1　递归的概念 81

5.1.2　递归的实现与堆栈 83

5.2　基于归纳的递归 84

5.3　递推关系求解 86

5.3.1 求解递推关系的常用方法 86

5.3.2　线性齐次递推式的求解 88

5.3.3 非齐次递推关系的解 89

5.3.4 Master Method 90

5.4　分治法 91

5.4.1 分治法的基本思想 91

5.4.2　矩阵乘法 94

5.4.3　选择问题 95

第6章　树 99

6.1　树的定义及基本术语 99

6.2　二叉树 102

6.2.1　二叉树的定义 102

6.2.2　二叉树的性质 103

6.2.3　二叉树的存储结构 105

6.3　二叉树基本操作的实现 110

6.4　树、森林 117

6.4.1　树的存储结构 117

6.4.2　树、森林与二叉树的相互转换 119

6.4.3　树与森林的遍历 121

6.4.4 由遍历序列还原树结构 123

6.5　Huffman树 124

6.5.1 二叉编码树 124

6.5.2　Huffman树及Huffman编码 125

第7章　图 130

7.1 图的定义 130

7.1.1 图及基本术语 130

7.1.2　抽象数据类型 134

7.2　图的存储方法 137

7.2.1　邻接矩阵 137

7.2.2　邻接表 139

7.2.3　双链式存储结构 140

7.3 图ADT实现设计 147

7.4　图的遍历 149

7.4.1　深度优先搜索 149

7.4.2　广度优先搜索 152

7.5　图的连通性 154

7.5.1 无向图的连通分量和生成树 154

7.5.2　有向图的强连通分量 155

7.5.3　最小生成树 156

7.6　最短距离 163

7.6.1　单源最短路径 163

7.6.2　任意顶点间的最短路径 168

7.7　有向无环图及其应用 170

7.7.1 拓扑排序 170

7.7.2　关键路径 173

第8章　查找 178

8.1　查找的定义 178

8.1.1　基本概念 178

8.1.2　查找表接口定义 179

8.2　顺序查找与折半查找 179

8.3　查找树 183

8.3.1　二叉查找树 183

8.3.2　AVL树 190

8.3.3　B-树 201

8.4　哈希 206

8.4.1　哈希表 206

8.4.2　哈希函数 208

8.4.3　冲突解决 209

第9章　排序 212

9.1　排序的基本概念 212

9.2　插入类排序 213

9.2.1　直接插入排序 213

9.2.2　折半插入排序 215

9.2.3　希尔排序 215

9.3　交换类排序 217

9.3.1　起泡排序 217

9.3.2　快速排序 219

9.4　选择类排序 221

9.4.1　简单选择排序 221

9.4.2　树型选择排序 223

9.4.3　堆排序 224

9.5　归并排序 228

9.6　基于比较的排序的对比 230

9.7　在线性时间内排序 231

9.7.1　计数排序 232

9.7.2　基数排序 233

参考书目 234