数据结构：从应用到实现 JAVA版PDF电子书下载

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

1.1 对象与封装 1

1.1.1 对象 1

1.1.2 生存期、状态和消息 2

1.1.3 对象的客户 2

1.1.4 接口与实现的分离 2

1.2 类 2

1.2.1 状态与行为 3

1.2.2 方法重载 4

1.2.3 对象创建、构造器及垃圾回收 4

1.2.4 方法调用 7

1.2.5 静态域和静态方法 7

1.2.6 对象引用 9

1.3 继承 9

1.3.1 超类与子类 9

1.3.2 继承域与特化域 11

1.3.3 构造器 11

1.3.4 创建对象 12

1.3.5 继承方法和特化方法 12

1.3.6 方法覆盖 13

1.4 类Object 13

1.4.1 方法equals 14

1.4.2 方法toString 15

1.4.3 方法clone 15

1.5 异常 16

1.5.1 异常消息的解释 16

1.5.2 特有的错误处理 18

1.5.3 抛出异常 22

1.5.4 捕获异常 23

1.5.5 异常类 27

1.6 输入与输出 28

1.6.1 终端驱动IO 28

1.6.2 基于文件的输入与输出 29

1.6.3 字符串分解 32

1.6.4 编写异常类 33

1.7 类包 34

1.7.1 Java包 34

1.7.2 组建包 35

1.7.3 名字冲突解析 38

1.8 访问控制 39

1.8.1 私有访问 39

1.8.2 包访问 39

1.8.3 受保护访问 39

1.8.4 公有访问 40

1.8.5 一个例子 40

1.9 多态性 40

1.9.1 多态引用 41

1.9.2 提升类层次 42

1.9.3 降低类层次 42

1.9.4 instanceof操作符 43

1.10 抽象类 44

1.10.1 抽象类Shape 44

1.10.2 抽象类的性质 44

1.11 游乐园的例子 45

1.12 接口 47

1.12.1 Java接口结构 47

1.12.2 实现接口 47

1.12.3 接口作为类型 48

1.12.4 对接口的需求 48

1.12.5 扩展接口 49

1.13 通用性 49

1.13.1 把java.util.ArrayList用于集合 50

1.13.2 java.util.ArrayList的公有接口 51

1.13.3 通用类的实现 52

1.13.4 通用接口的实现 52

1.13.5 静态模板方法 54

1.14 总结 56

1.15 练习 58

1.16 程序设计问题 59

第2章 数据结构概观 62

2.1 什么是数据结构 62

2.2 我们学习什么数据结构 62

2.3 什么是抽象数据类型 64

2.4 OOP和Java在数据结构有什么优势 65

2.5 如何选择正确的数据结构 67

第3章 算法的效率 69

3.1 多项式的算术运算：一个具体例子 69

3.2 基本操作 70

3.3 输入规模 72

3.4 函数的渐近增长 72

3.5 阶与大0 73

3.5.1 典型运行时间的阶 75

3.5.2 多变元的阶 77

3.5.3 阶的相对顺序 77

3.5.4 阶的算术运算 78

3.6 最坏情况与平均情况 78

3.7 总结 80

3.8 练习 81

第4章 无序列表 84

4.1 无序列表的性质 84

4.2 顺序搜索 85

4.2.1 平均情况分析 86

4.2.2 基于搜索模式的数据重排列 87

4.3 类List 88

4.4 使用List的类ExpenseList 89

4.4.1 类Expense的接口 89

4.4.2 类Expense 90

4.4.3 类ExpenseList的接口 91

4.4.4 类ExpenseList的实现 92

4.4.5 对象的相等与搜索 94

4.5 链表 96

4.5.1 节点的定义 97

4.5.2 插入操作 98

4.5.3 删除操作 99

4.5.4 访问操作 100

4.5.5 循环链表 100

4.6 类LinkedList 102

4.7 类List的实现 106

4.8 总结 107

4.9 练习 108

4.10 程序设计问题 109

第5章 有序列表 112

5.1 介绍 112

5.2 二分搜索 113

5.2.1 分成两半 113

5.2.2 算法 114

5.3 排序：接口java.lang.Comparable 115

5.4 类OrderedList 117

5.5 合并有序列表 119

5.6 使用OrderedList的列表归并 123

5.6.1 Merger：一个实用类 123

5.6.2 归并类 125

5.7 类OrderedList的实现 126

5.8 总结 128

5.9 练习 129

5.10 程序设计问题 131

第6章 队列 133

6.1 队列的性质 133

6.2 UNIX打印队列 134

6.3 类Queue 135

6.4 使用Queue的类PrintQueue 136

6.5 类Queue的实现 139

6.5.1 设计1：使用基于数组的存储 139

6.5.2 设计2：使用LinkedList 141

6.6 总结 142

6.7 练习 143

6.8 程序设计问题 144

第7章 栈 146

7.1 栈的性质 146

7.2 栈的应用 147

7.2.1 括号匹配 147

7.2.2 后缀表达式求值 147

7.2.3 中缀表达式到后缀表达式的转换 149

7.3 类Stack 149

7.4 后缀表达式求值包 150

7.4.1 类PostfixEvaluator 150

7.4.2 类StatusKeeper 152

7.4.3 类StackKeeper 152

7.4.4 类PostfixEvaluator的实现 154

7.5 类Stack的实现 155

7.5.1 设计1：使用数组列表进行存储 156

7.5.2 设计2：使用链表进行存储 156

7.6 总结 157

7.7 练习 157

7.8 程序设计问题 159

第8章 递归 161

8.1 递归定义 161

8.1.1 列表 161

8.1.2 有序列表 162

8.1.3 阶乘函数 163

8.1.4 斐波那契数列 163

8.2 递归程序与退回 164

8.2.1 计算阶乘 164

8.2.2 计算斐波那契数列 166

8.2.3 关于链表的递归 166

8.3 对数组的递归：二分搜索 168

8.4 汉诺塔：一个应用 168

8.4.1 递归定义 169

8.4.2 递归程序 170

8.5 递归与栈 171

8.6 递归的缺点 171

8.7 尾递归 172

8.8 总结 174

8.9 练习 174

8.10 程序设计问题 175

第9章 二叉树和普通树 178

9.1 二叉树的性质 178

9.1.1 组件 178

9.1.2 节点位置代表的意义 179

9.1.3 结构 180

9.1.4 递归定义 181

9.2 二叉树的遍历 182

9.3 类BinaryTree 184

9.4 二叉树的存储与重构 186

9.4.1 二叉树的署名 187

9.4.2 从二叉树的署名构建二叉树 188

9.5 赫夫曼编码 190

9.5.1 统计编码与字典编码 190

9.5.2 算法 190

9.5.3 平均代码长度和前缀性质 191

9.5.4 使用BinaryTree的类Huffman 192

9.6 类BinaryTree的实现 196

9.7 基于栈的遍历 198

9.7.1 二叉树的中序遍历 198

9.7.2 类Visitor 200

9.8 普通树 200

9.8.1 例子：大学中的组织层次 200

9.8.2 例子：UNIX文件系统 200

9.8.3 实现中的空间问题 201

9.8.4 与二叉树的对应关系 202

9.8.5 普通树的署名 203

9.9 总结 204

9.10 练习 205

9.11 程序设计问题 207

第10章 二叉查找树和AVL树 210

10.1 比较树 210

10.1.1 使用比较树的搜索时间 211

10.1.2 比较树的高度 212

10.2 二叉查找树的性质 213

10.3 二叉查找树的操作 214

10.3.1 搜索操作 214

10.3.2 插入操作 215

10.3.3 删除操作 215

10.4 类BinarySearchTree 217

10.5 使用类BinarySearchTree 218

10.5.1 例子：树排序 218

10.5.2 例子：计数关键字 219

10.6 类BinarySearchTree的实现 220

10.6.1 搜索操作的实现 220

10.6.2 插入操作的实现 220

10.6.3 删除操作的实现 221

10.6.4 便利方法与遍历 223

10.7 AVL树 223

10.7.1 AVL树结构 224

10.7.2 搜索、插入和删除操作概述 225

10.7.3 旋转操作 225

10.7.4 插入操作 226

10.7.5 删除操作 227

10.7.6 AVL树操作的运行时间 231

10.7.7 AVL插入和删除：一般化 231

10.8 二分搜索：平均比较次数 234

10.9 总结 236

10.10 练习 236

10.11 程序设计问题 239

第11章 堆 241

11.1 作为优先队列的堆 241

11.2 堆的性质 242

11.3 堆的操作 242

11.3.1 插入操作 243

11.3.2 删除操作 243

11.3.3 运行时间分析 244

11.4 类Heap 244

11.5 使用堆的优先调度 245

11.5.1 纵览 245

11.5.2 使用堆的调度包 246

11.6 使用类Heap的排序 250

11.7 类Heap的实现 251

11.7.1 数组存储 251

11.7.2 使用ArrayList的实现 253

11.8 可更新堆 254

11.8.1 设计一个可更新堆 254

11.8.2 堆项的句柄 255

11.8.3 共享句柄数组 255

11.8.4 在堆中封装句柄 255

11.8.5 循环使用空闲句柄空间 256

11.9 总结 256

11.10 练习 257

11.11 程序设计问题 258

第12章 散列表 260

12.1 动机 260

12.2 散列 261

12.3 冲突解决方案 262

12.3.1 线性探查法 262

12.3.2 二次探查法 263

12.3.3 链表法 264

12.3.4 运行时间比较 265

12.4 类java.util.HashMap 265

12.4.1 表和负载因子 266

12.4.2 项的存储 267

12.4.3 添加项 267

12.4.4 再散列过程 269

12.4.5 搜索操作 270

12.5 二次探查法：探查位置的重复 270

12.6 总结 271

12.7 练习 271

12.8 程序设计问题 272

第13章 排序 273

13.1 插入排序 273

13.2 用分治法排序 275

13.2.1 快速排序 276

13.2.2 归并排序 280

13.3 堆排序 281

13.3.1 以线性时间构建堆 281

13.3.2 排序堆 283

13.4 基数排序 283

13.5 实现：类Quicksort 285

13.6 构建堆：线性运行时间 287

13.7 总结 288

13.8 练习 288

13.9 程序设计问题 290

第14章 图I：算法 292

14.1 使用图模拟关系 292

14.1.1 无向图 292

14.1.2 有向图 293

14.1.3 加权图 295

14.2 图的表示 295

14.3 图的遍历 297

14.3.1 无向图的深度优先搜索 297

14.3.2 无向图的广度优先搜索 298

14.3.3 遍历驱动器 299

14.3.4 有向图的遍历 300

14.4 有向图的拓扑排序 301

14.4.1 偏序和全序 301

14.4.2 拓扑编号 302

14.4.3 使用深度优先搜索的拓扑排序 302

14.4.4 使用广度优先搜索的拓扑排序 304

14.5 无向图的连通分支 305

14.6 加权有向图中的最短路径 306

14.7 总结 311

14.8 练习 311

第15章 图Ⅱ：实现 314

15.1 有向图类：DirGraph 314

15.1.1 顶点编号 315

15.1.2 类Neighbor 316

15.1.3 运用类DirGraph 317

15.2 无向图类：UndirGraph 317

15.3 深度优先搜索类：DFS 319

15.3.1 设计与接口 319

15.3.2 类Visitor 320

15.3.3 DFS的实现 321

15.4 拓扑排序类：DFSTopsort 322

15.4.1 TopVisitor：扩展类Visitor 322

15.4.2 DFSTopsort的实现 322

15.5 连通分支类：DFSConncomp 323

15.5.1 ConnVisitor：扩展类Visitor 323

15.5.2 DFSConncomp的实现 324

15.6 最短路径类：ShortestPaths 324

15.6.1 WeightedNeighbor：扩展类Neighbor 325

15.6.2 ShortestPaths的实现 325

15.7 图的实现 328

15.7.1 DirGraph的实现 328

15.7.2 类UndirGraph的实现 331

15.7.3 加权图的实现 331

15.8 总结 332

15.9 程序设计问题 332

索引 335