实用数据结构教程 Java语言描述PDF电子书下载

第1章 绪论 1

1.1 数据结构与数据类型 1

1.2 抽象数据类型 3

1.2.1 ADT的规格说明 4

1.2.2 ADT的实现 4

1.2.3 Java中ADT的规格说明与实现 4

1.3 串抽象数据类型 7

1.3.1 串ADT的规格说明 7

1.3.2 串ADT的实现 7

习题 9

第2章 算法 11

2.1 问题、算法和程序 11

2.2 算法的代价 12

2.3 算法分析 13

2.3.1 规模与基本操作 13

2.3.2 运行时间和增长率 13

2.3.3 最佳、最差和平均情况 15

2.4 大O符号 16

2.4.1 大O的定义 16

2.4.2 大O的性质 17

2.4.3 大O的计算 17

2.5 空间代价 19

2.6 递归算法 20

习题 24

第3章 数组 25

3.1 数组 25

3.1.1 子数组 27

3.1.2 有序数组 27

3.1.3 二维数组 28

3.2 插入 29

3.3 删除 30

3.4 查找 31

3.4.1 线性查找 31

3.4.2 二分查找 33

3.4.3 查找算法比较 35

3.5 归并 35

3.6 排序 37

3.6.1 冒泡排序 37

3.6.2 选择排序 39

3.6.3 插入排序 41

3.6.4 归并排序 42

3.6.5 快速排序 44

3.6.6 排序算法比较 47

习题 48

第4章 链表 50

4.1 链表 50

4.1.1 单向链表 51

4.1.2 双向链表 53

4.1.3 有序链表 56

4.1.4 循环链表 56

4.2 插入 56

4.2.1 单向链表插入 56

4.2.2 双向链表插入 58

4.3 删除 59

4.3.1 单向链表删除 60

4.3.2 双向链表删除 60

4.4 查找 62

习题 62

第5章 栈与队列 65

5.1 栈 65

5.1.1 栈的概念 65

5.1.2 栈的应用 66

5.1.3 栈ADT的规格说明 66

5.1.4 用数组实现栈 67

5.1.5 用单向链表实现栈 70

5.2 队列 72

5.2.1 队列的概念 72

5.2.2 队列的应用 72

5.2.3 队列ADT的规格说明 73

5.2.4 用数组实现队列 73

5.2.5 用单向链表实现队列 77

5.2.6 基数排序 79

习题 81

第6章 表 82

6.1 表的概念 82

6.2 表的应用 83

6.3 表ADT的规格说明 83

6.4 用数组实现表 84

6.5 用单向链表实现表 86

习题 88

第7章 二叉树 90

7.1 二叉树 90

7.1.1 二叉树的概念 90

7.1.2 满二叉树 92

7.1.3 平衡二叉树 93

7.1.4 二叉树结点类 94

7.2 二叉树的遍历 95

7.3 二叉查找树 97

7.3.1 二叉查找树的概念 97

7.3.2 查找 99

7.3.3 插入 101

7.3.4 删除 103

7.4 二叉查找树的平衡化重构 108

7.5 将二叉查找树保存到文件 109

7.5.1 使用前序遍历把二叉查找树保存到文件 110

7.5.2 使用中序遍历把二叉查找树保存到文件 111

习题 112

第8章 优先队列与堆 114

8.1 优先队列的概念 114

8.2 优先队列的应用 114

8.3 优先队列ADT的规格说明 115

8.4 优先队列的实现 115

8.5 完全二叉树与堆 116

8.5.1 完全二叉树 116

8.5.2 堆 117

8.6 用堆实现优先队列 119

8.7 堆排序 122

8.8 赫夫曼编码树 122

8.8.1 建立赫夫曼编码树 123

8.8.2 赫夫曼编码及其用法 127

习题 130

第9章 集合与映射 131

9.1 集合 131

9.1.1 集合的概念 131

9.1.2 集合的应用 132

9.1.3 集合ADT的规格说明 133

9.1.4 集合的实现 134

9.2 映射 147

9.2.1 映射的概念 147

9.2.2 映射的应用 147

9.2.3 映射ADT的规格说明 148

9.2.4 映射的实现 148

习题 154

第10章 散列表 156

10.1 散列表原理 156

10.2 闭桶散列表 158

10.2.1 插入 160

10.2.2 查找 160

10.2.3 删除 161

10.2.4 分析 161

10.2.5 设计 161

10.2.6 再散列 162

10.3 开桶散列表 163

10.3.1 插入 165

10.3.2 查找 167

10.3.3 删除 168

10.3.4 分析 169

10.3.5 设计 169

10.3.6 双散列 170

10.4 用散列表实现集合与映射 172

习题 173

第11章 树 174

11.1 树的概念 174

11.2 树的应用 175

11.3 左子结点／右兄弟结点表示法 176

11.4 树的遍历 180

11.5 父指针表示法 181

11.6 UNION/FIND算法与等价类问题 182

习题 186

第12章 图 187

12.1 图的概念 187

12.2 图的应用 189

12.3 图ADT的规格说明 190

12.4 图的实现 191

12.4.1 用邻接矩阵实现图 191

12.4.2 用邻接表实现图 193

12.5 图的遍历 195

12.5.1 深度优先搜索 195

12.5.2 广度优先搜索 197

12.6 拓扑排序 198

12.6.1 基于递归的拓扑排序算法 198

12.6.2 基于队列的拓扑排序算法 199

12.7 最短路径问题 200

12.7.1 单源最短路径 201

12.7.2 每对顶点间的最短路径 204

12.8 最小生成树 205

12.8.1 Prim算法 205

12.8.2 Kruskal算法 207

12.9 迷宫的生成和求解 209

12.9.1 迷宫的表示 210

12.9.2 用DFS算法生成迷宫 212

12.9.3 用Prim算法生成迷宫 213

12.9.4 用Kruskal算法生成迷宫 215

12.9.5 迷宫求解算法 216

习题 217

附录A 数学预备知识 218

附录B Java语言概要 224

附录C 课程实验 230

参考文献 233