数据结构、算法与应用 Java语言描述PDF|Epub|txt|kindle电子书版本网盘下载

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

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 Java综述1

1.1 简介2

1.2 Java程序结构2

1.2.1 独立运行的程序和Applet2

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 重访Currency23

1.12 定义一个异常类25

1.13 泛型方法26

1.13.1 Computable接口26

1.13.2 泛型方法abc27

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 抽象数据类型LinearList105

5.2.2 LinearList接口105

5.2.3 LinearListAsAbstractClass抽象类106

5.3 数组表示形式108

5.3.1 表示形式108

5.3.2 改变一维数组的长度109

5.3.3 类ArrayLinearList110

5.3.4 ArrayLinearList的Iterator114

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 类arrayStack213

9.3.3 性能测量214

9.4 链式表示217

9.4.1 类DerivedLinkedStack217

9.4.2 类LinkedStack217

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 类SkipNode280

11.4.5 类SkipList281

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 BinaryTree325

12.8 类LinkedBinaryTree326

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 插入到最大HBLT356

13.5.3 从最大HBLT中删除356

13.5.4 合并两棵最大HBLT356

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 抽象数据类型WinnerTree377

14.3 优胜树的实现377

14.3.1 表示377

14.3.2 初始化一棵优胜树378

14.3.3 重新进行比赛378

14.3.4 类CompleteWinnerTree378

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 Gaph453

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