数据结构、算法与应用 Java语言描述PDF电子书下载

第1章 Java综述 1

1.1 简介 2

1.2 Java程序结构 2

1.2.1 独立运行的程序和Applet 2

1.2.2 包 3

1.2.3 引入类和包 4

1.2.4 超类和子类 4

1.3 Java编译器和虚拟机 5

1.4 文档注释 6

1.5 数据类型 7

1.6 方法 8

1.6.1 参数 8

1.6.2 重载方法 9

1.7 异常 10

1.7.1 抛出一个异常 10

1.7.2 处理异常 11

1.8 自定义数据类型 12

1.8.1 Currency类 12

1.8.2 Currency的数据成员 13

1.8.3 Currency的方法成员 14

1.8.4 Currency的构造函数 14

1.8.5 创建Currency的实例 15

1.8.6 Currency的存取器（获取）方法 15

1.8.7 Currency的存取器（设置）方法 16

1.8.8 调用方法和访问数据成员 17

1.8.9 Currency的输出和算术方法 18

1.8.10 main方法 19

1.9 访问修饰符 21

1.10 继承和方法重写 21

1.11 重访Currency 23

1.12 定义一个异常类 25

1.13 泛型方法 26

1.13.1 Computable接口 26

1.13.2 泛型方法abc 27

1.13.3 java.lang.Comparable接口 28

1.13.4 Operable接口 28

1.13.5 Zero和CloneableObject接口 28

1.13.6 MyInteger封装类 29

1.13.7 使用数据类型和方法作为参数 29

1.14 垃圾收集 33

1.15 递归 33

1.15.1 递归函数 33

1.15.2 归纳 34

1.15.3 递归方法 35

1.16 测试和调试 39

1.16.1 什么是测试 39

1.16.2 设计测试数据 41

1.16.3 调试 43

1.17 参考资料和选择性读物 44

第2章 性能分析 45

2.1 什么是性能 45

2.2 空间复杂度 46

2.2.1 空间复杂度的组成 46

2.2.2 范例 49

2.3 时间复杂度 51

2.3.1 时间复杂度的组成 51

2.3.2 运算计数 52

2.3.3 最佳、最差和平均运算计数 56

2.3.4 步骤计数 61

第3章 渐近表示法 73

3.1 简介 73

3.2 渐近表示法 75

3.2.1 O表示法 75

3.2.2 Ω和Θ表示法 77

3.3 渐近数学（可选） 79

3.3.1 O表示法 79

3.3.2 Ω表示法 81

3.3.3 Θ表示法 82

3.3.4 o表示法 84

3.3.5 属性 84

3.4 复杂度分析范例 86

3.5 实用的复杂度 89

3.6 参考资料和选择性读物 91

第4章 性能测量 92

4.1 简介 92

4.2 选择实例规模 92

4.3 开发测试数据 93

4.4 建立试验 93

4.5 缓存管理 98

4.5.1 一个简单的计算机模型 98

4.5.2 遗漏缓存对运行时间的影响 99

4.5.3 矩阵乘法 99

4.6 参考资料和选择性读物 102

第5章 线性列表——数组表示形式 103

5.1 数据对象和结构 104

5.2 线性列表数据结构 105

5.2.1 抽象数据类型LinearList 105

5.2.2 LinearList接口 105

5.2.3 LinearListAsAbstractClass抽象类 106

5.3 数组表示形式 108

5.3.1 表示形式 108

5.3.2 改变一维数组的长度 109

5.3.3 类ArrayLinearList 110

5.3.4 ArrayLinearList的Iterator 114

5.4 矢量表示形式 121

5.5 在单个数组中的多个列表 124

5.6 性能测量 126

5.7 java.util.ArrayList类 128

5.8 参考资料和选择性读物 129

第6章 线性列表——链表表示 130

6.1 单向链表和链 131

6.1.1 表示形式 131

6.1.2 ChainNode类 132

6.1.3 Chain类 133

6.1.4 对ADT LinearList的扩展 137

6.1.5 ExtendedChain类 138

6.1.6 性能测量 139

6.2 循环列表和头节点 144

6.3 双向链表 146

6.4 链表术语表 147

6.5 应用 148

6.5.1 箱排序 148

6.5.2 基数排序 151

6.5.3 凸包 153

第7章 线性列表——模拟指针 158

7.1 需要模拟指针 158

7.2 模拟指针 159

7.3 内存管理 160

7.3.1 SimulatedSpace1类 161

7.3.2 SimulatedSpace2类 162

7.3.3 评价模拟内存管理 162

7.4 与垃圾收集比较 163

7.5 模拟链 164

7.5.1 SimulatedChain类 164

7.5.2 性能测量 165

7.6 内存管理链 167

7.7 应用程序——并查问题 168

7.7.1 等价类 168

7.7.2 应用程序 169

7.7.3 第一个并查解决方案 171

7.7.4 第二个并查解决方案 171

第8章 数组和矩阵 175

8.1 数组 175

8.1.1 抽象数据类型 175

8.1.2 对一个Java数组进行索引 176

8.1.3 行优先和列优先的映射 176

8.1.4 数组的数组表示形式 178

8.1.5 行优先和列优先的表示形式 178

8.1.6 不规则的二维数组 179

8.2 矩阵 180

8.2.1 定义和操作 180

8.2.2 Matrix类 182

8.3 特殊矩阵 186

8.3.1 定义和应用程序 186

8.3.2 对角线矩阵 188

8.3.3 三对角线矩阵 190

8.3.4 三角形矩阵 190

8.3.5 对称矩阵 191

8.4 稀疏矩阵 194

8.4.1 目的 194

8.4.2 使用单线性表的表示 195

8.4.3 使用多线性表的表示 202

8.4.4 性能测量 204

第9章 堆栈 208

9.1 定义和应用 208

9.2 抽象数据类型 210

9.3 数组表示 211

9.3.1 实现为子类 211

9.3.2 类arrayStack 213

9.3.3 性能测量 214

9.4 链式表示 217

9.4.1 类DerivedLinkedStack 217

9.4.2 类LinkedStack 217

9.4.3 性能测量 218

9.5 应用 219

9.5.1 括号匹配 219

9.5.2 汉诺塔 220

9.5.3 重排有轨电车 222

9.5.4 开关箱路由 227

9.5.5 离线等价类问题 229

9.5.6 迷宫中的老鼠 232

9.6 参考资料和选择性读物 241

第10章 队列 242

10.1 定义和应用 242

10.2 抽象数据类型 243

10.3 数组表示 244

10.3.1 表示方法 244

10.3.2 ArrayQueue类 246

10.4 链式表示 249

10.5 应用 252

10.5.1 有轨电车的重新安排 252

10.5.2 线路路由 254

10.5.3 图像组件编号 257

10.5.4 机械工厂模拟 260

10.6 参考资料和选择性读物 272

第11章 跳表和散列表 273

11.1 字典 273

11.2 抽象数据类型 275

11.3 线性表表示 276

11.4 跳表表示（可选） 278

11.4.1 理想情形 278

11.4.2 插入和删除 279

11.4.3 分配层级 280

11.4.4 类SkipNode 280

11.4.5 类SkipList 281

11.4.6 SkipList方法的复杂度 285

11.5 散列表表示 285

11.5.1 理想散列 285

11.5.2 散列函数和散列表 287

11.5.3 线性探查法 290

11.5.4 使用链表的散列 295

11.6 一个应用——文本压缩 300

11.6.1 LZW压缩 301

11.6.2 LZW压缩的实现 302

11.6.3 LZW解压缩 306

11.6.4 LZW解压缩的实现 306

11.6.5 性能评估 309

11.7 参考资料和选择性读物 311

第12章 二叉树和其他树 312

12.1 树 312

12.2 二叉树 315

12.3 二叉树的属性 316

习题 318

12.4 二叉树的表示 318

12.4.1 基于数组的表示 318

12.4.2 链接表示 319

12.5 常见的二叉树操作 320

12.6 二叉树遍历 320

12.7 ADT BinaryTree 325

12.8 类LinkedBinaryTree 326

12.9 应用 329

12.9.1 信号放大器的布置 329

12.9.2 并查（Union-Find）问题 334

12.10 参考资料和选择性读物 343

第13章 优先级队列 344

13.1 定义和应用 344

13.2 抽象数据类型 345

13.3 线性表 346

13.4 堆 347

13.4.1 定义 347

13.4.2 插入元素到最大堆 348

13.4.3 从最大堆中删除元素 348

13.4.4 最大堆的初始化 349

13.4.5 MaxHeap类 350

13.5 左倾树 354

13.5.1 基于高度和基于宽度的最小和最大左倾树 354

13.5.2 插入到最大HBLT 356

13.5.3 从最大HBLT中删除 356

13.5.4 合并两棵最大HBLT 356

13.5.5 初始化 358

13.5.6 MaxHBLT类 358

13.6 应用 362

13.6.1 堆排序 362

13.6.2 机器调度 363

13.6.3 哈夫曼编码 366

13.7 参考资料和选择性读物 371

第14章 比赛树 373

14.1 优胜树及其应用 373

14.2 抽象数据类型WinnerTree 377

14.3 优胜树的实现 377

14.3.1 表示 377

14.3.2 初始化一棵优胜树 378

14.3.3 重新进行比赛 378

14.3.4 类CompleteWinnerTree 378

14.4 失败树 379

14.5 应用 381

14.5.1 使用首次适应法的容器装包 381

14.5.2 使用下一适应法的容器装包 385

14.6 参考资料和选择性读物 388

第15章 二叉搜索树 389

15.1 定义 390

15.1.1 二叉搜索树 390

15.1.2 可索引二叉搜索树 391

15.2 抽象数据类型 392

15.3 二叉搜索树的操作及其实现 393

15.3.1 BinarySearchTree类 393

15.3.2 搜索 393

15.3.3 插入一个元素 394

15.3.4 删除一个元素 395

15.3.5 二叉搜索树的高度 397

15.4 有重复记录的二叉搜索树 399

15.5 索引的二叉搜索树 400

15.6 应用 401

15.6.1 柱状图 401

15.6.2 最优容器装包 404

15.6.3 交叉分配 406

第16章 平衡搜索树 413

16.1 AVL树 414

16.1.1 定义 414

16.1.2 AVL树的高度 415

16.1.3 AVL树的表示 415

16.1.4 AVL搜索树的搜索 415

16.1.5 AVL搜索树的插入 415

16.1.6 从AVL搜索树中删除 418

16.2 红黑树 421

16.2.1 定义 421

16.2.2 红黑树的表示 423

16.2.3 红黑树的搜索 423

16.2.4 红黑树的插入 423

16.2.5 从红黑树中删除 427

16.2.6 实现的考虑和复杂度 430

16.3 伸展树 432

16.3.1 引言 432

16.3.2 伸展操作 432

16.3.3 分摊复杂度 434

16.4 B-树 436

16.4.1 索引顺序存取法（ISAM） 436

16.4.2 m-叉搜索树 436

16.4.3 m叉排序B-树 438

16.4.4 B-树的高度 439

16.4.5 搜索B-树 439

16.4.6 插入元素到B-树 440

16.4.7 从B-树中删除 442

16.4.8 节点结构 445

16.5 参考资料和选择性读物 446

第17章 图 447

17.1 定义 447

17.2 应用和更多的定义 449

习题 451

17.3 属性 452

17.4 ADT Gaph 453

17.5 不带权值的图的表示 454

17.5.1 邻接矩阵 455

17.5.2 链式邻接表 456

17.5.3 数组邻接表 457

17.6 带权图的表示形式 458

17.7 类的实现 459

17.7.1 不同的类 459

17.7.2 邻接矩阵类 460

17.7.3 到类Chain的扩展 463

17.7.4 链表类 464

17.8 图的搜索方法 466

17.8.1 广度优先搜索 466

17.8.2 广度优先搜索的实现 468

17.8.3 Graph.bfs的复杂度分析 468

17.8.4 深度优先搜索 470

17.8.5 深度优先搜索的实现 471

17.8.6 Graph.dfs的复杂度分析 471

17.9 重访的应用 472

17.9.1 查找路径 472

17.9.2 连通图和连通分量 474

17.9.3 生成树 476

第18章 贪婪方法 479

18.1 最优化问题 479

18.2 贪婪方法 480

18.3 应用 483

18.3.1 集装箱装载 483

18.3.2 0/1背包问题 485

18.3.3 拓扑排序 487

18.3.4 二分覆盖 490

18.3.5 单源最短路径 493

18.3.6 最小生成树 497

18.4 参考资料和选择性读物 507

第19章 分而治之 508

19.1 方法 508

19.2 应用 515

19.2.1 缺陷棋盘 515

19.2.2 归并排序 517

19.2.3 快速排序 522

19.2.4 选择 528

19.2.5 最近顶点对 530

19.3 求解递归等式 538

19.4 复杂度下界 540

19.4.1 最小最大问题的下界 541

19.4.2 排序的下界 542

第20章 动态规划 544

20.1 方法 544

20.2 应用 546

20.2.1 0/1背包问题 546

20.2.2 矩阵乘法链 550

20.2.3 所有对最短路径 555

20.2.4 带负值的单源最短路径 558

20.2.5 不相交网子集 562

20.3 参考资料和选择性读物 568

第21章 回溯法 569

21.1 方法 569

21.2 应用 574

21.2.1 集装箱装载 574

21.2.2 0/1背包问题 581

21.2.3 最大集团 584

21.2.4 旅行售货员 587

21.2.5 电路板排列 589

第22章 分支限界法 595

22.1 方法 595

22.2 应用 598

22.2.1 集装箱装载 598

22.2.2 0/1背包问题 605

22.2.3 最大集团 607

22.2.4 旅行售货员 609

22.2.5 电路板排列 612