数据结构与问题求解 Java语言描述PDF电子书下载

第一部分 算法和构件块 2

第1章 算法分析 2

1.1 什么是算法分析 2

1.2 算法运行时间的实例 5

1.3 连续子序列最大和的问题 6

1.3.1 简单的O（n3）算法 7

1.3.2 改进的O（N2）算法 8

1.3.3 线性算法 9

1.4 一般的大O规则 11

1.5 对数 14

1.6 静态查找问题 15

1.6.1 顺序查找 15

1.6.2 二分搜索 16

1.6.3 插值查找 18

1.7 算法分析的检查 18

1.8 大O分析的局限性 19

小结 20

关键概念 20

常见错误 21

网上资源 21

习题 21

参考文献 26

第2章 集合类API 27

2.1 引言 27

2.2 迭代器模式 28

2.2.1 基本的迭代器设计 29

2.2.2 基于继承的迭代器和工厂方法 30

2.3 集合类API：容器和迭代器 32

2.3.1 Collection接口 32

2.3.2 Iterator接口 35

2.4 泛型算法 36

2.4.1 Comparator函数对象 37

2.4.2 Collections类 37

2.4.3 二分搜索 39

2.4.4 排序 40

2.5 List接口 40

2.5.1 ListIterator接口 41

2.5.2 LinkedList类 42

2.6 栈和队列 44

2.6.1 栈 44

2.6.2 栈与计算机语言 45

2.6.3 队列 46

2.6.4 集合类API中的栈和队列 46

2.7 集合 47

2.7.1 TreeSet类 48

2.7.2 HashSet类 48

2.8 映射 52

2.9 优先级队列 55

小结 57

关键概念 57

常见错误 58

网上资源 58

习题 59

参考文献 61

第3章 递归 62

3.1 什么是递归 62

3.2 背景：数学归纳法证明 63

3.3 基本的递归 65

3.3.1 以任何数制打印数 66

3.3.2 为什么可行 67

3.3.3 原理解析 68

3.3.4 太多的递归可能是危险的 69

3.3.5 树的预习 70

3.3.6 其他实例 71

3.4 数值应用 74

3.4.1 模运算 74

3.4.2 模的幂运算 75

3.4.3 最大公因子和乘法逆元素 76

3.4.4 RSA密码系统 78

3.5 分治算法 79

3.5.1 连续子序列最大和的问题 80

3.5.2 对一个基本的分治情况的分析 82

3.5.3 分治算法运行时间的通用上界 84

3.6 动态规划 86

3.7 回溯 89

小结 92

关键概念 92

常见错误 93

网上资源 93

习题 94

参考文献 96

第4章 排序算法 97

4.1 排序为什么重要 97

4.2 预备知识 98

4.3 插入排序及其他简单排序算法的分析 98

4.4 谢尔排序 101

4.5 归并排序 103

4.5.1 有序数组的线性时间合并 103

4.5.2 归并排序算法 105

4.6 快速排序 106

4.6.1 快速排序算法 107

4.6.2 快速排序的分析 108

4.6.3 挑选中心点 111

4.6.4 一种划分策略 112

4.6.5 键等于中心点 113

4.6.6 三个元素的中值划分 114

4.6.7 小规模数组 114

4.6.8 Java快速排序程序 115

4.7 快速选择 117

4.8 排序的下界 118

小结 119

关键概念 119

常见错误 120

网上资源 120

习题 120

参考文献 123

第5章 随机化 124

5.1 为什么需要随机数 124

5.2 随机数生成器 125

5.3 非均匀分布随机数 129

5.4 产生随机排列 130

5.5 随机化算法 131

5.6 随机化素数检验 133

小结 135

关键概念 135

常见错误 136

网上资源 136

习题 136

参考文献 138

第二部分 应用 140

第6章 娱乐和游戏 140

6.1 单词搜索迷宫 140

6.1.1 理论 140

6.1.2 Java实现 142

6.2 Tic-Tac-Toe游戏 146

6.2.1 α-β剪枝 146

6.2.2 置换表 148

6.2.3 计算机象棋 151

小结 152

关键概念 152

常见错误 152

网上资源 152

习题 153

参考文献 154

第7章 栈和编译器 155

7.1 平衡符号检查器 155

7.1.1 基本算法 155

7.1.2 实现 156

7.2 简单计算器 163

7.2.1 后缀机 164

7.2.2 中缀到后缀的转化 165

7.2.3 实现 166

7.2.4 表达式树 172

小结 173

关键概念 173

常见错误 174

网上资源 174

习题 174

参考文献 175

第8章 实用程序 176

8.1 文件压缩 176

8.1.1 前缀编码 177

8.1.2 赫夫曼算法 178

8.1.3 实现 180

8.2 交叉引用生成器 191

8.2.1 基本思想 191

8.2.2 Java实现 191

小结 194

关键概念 194

常见错误 195

网上资源 195

习题 195

参考文献 197

第9章 模拟 198

9.1 约瑟夫问题 198

9.1.1 简单实现方案 199

9.1.2 更高效的算法 200

9.2 事件驱动模拟 202

9.2.1 基本思路 202

9.2.2 实例：调制解调器银行的模拟 203

小结 209

关键概念 209

常见错误 209

网上资源 209

习题 209

第10章 图和路径 211

10.1 图的定义 211

10.2 非加权的最短路径问题 221

10.2.1 理论 221

10.2.2 Java实现 223

10.3 非负权值的最短路径算法 224

10.3.1 理论：Dijkstra算法 224

10.3.2 Java实现 227

10.4 含负权值的最短路径问题 228

10.4.1 理论 228

10.4.2 Java实现 229

10.5 无环图的路径问题 230

10.5.1 拓扑排序 230

10.5.2 无环图最短路径算法的理论 232

10.5.3 Java实现 233

10.5.4 应用：关键路径分析 234

小结 236

关键概念 236

常见错误 237

网上资源 237

习题 238

参考文献 240

第三部分 实现 242

第11章 内部类和ArrayList的实现 242

11.1 迭代器与嵌套类 242

11.2 迭代器和内部类 244

11.3 AbstractCollection类 246

11.4 StringBuilder 249

11.5 使用迭代器的ArrayList的实现 250

小结 254

关键概念 254

常见错误 254

网上资源 254

习题 255

第12章 栈和队列 257

12.1 动态数组的实现 257

12.1.1 栈 257

12.1.2 队列 260

12.2 链表实现 265

12.2.1 栈 265

12.2.2 队列 267

12.3 两种实现方式的比较 270

12.4 java.util.Stack类 270

12.5 双向队列 271

小结 271

关键概念 272

常见错误 272

网上资源 272

习题 272

第13章 链表 273

13.1 基本思想 273

13.1.1 头结点 274

13.1.2 迭代器类 275

13.2 Java实现 276

13.3 双向链表和循环链表 281

13.4 有序链表 283

13.5 集合类API中LinkedList类的实现 284

小结 292

关键概念 292

常见错误 293

网上资源 293

习题 293

第14章 树 296

14.1 普通的树 296

14.1.1 定义 296

14.1.2 实现 297

14.1.3 应用：文件系统 298

14.2 二叉树 301

14.3 递归和树 306

14.4 树的遍历：迭代器类 307

14.4.1 后序遍历 310

14.4.2 中序遍历 313

14.4.3 前序遍历 314

14.4.4 层次遍历 316

小结 317

关键概念 317

常见错误 318

网上资源 318

习题 318

第15章 二叉查找树 321

15.1 基本思想 321

15.1.1 操作 322

15.1.2 Java实现 323

15.2 顺序统计量 329

15.3 二叉查找树操作的分析 332

15.4 AVL树 335

15.4.1 性质 335

15.4.2 单旋转 337

15.4.3 双旋转 339

15.4.4 AVL插入小结 341

15.5 红黑树 341

15.5.1 自下而上的插入 342

15.5.2 自上而下的红黑树 344

15.5.3 Java实现 345

15.5.4 自上而下的删除 350

15.6 AA树 352

15.6.1 插入 353

15.6.2 删除 354

15.6.3 Java实现 355

15.7 集合类API中TreeSet类和TreeMap类的实现 358

15.8 B树 371

小结 376

关键概念 376

常见错误 377

网上资源 377

习题 378

参考文献 379

第16章 散列表 382

16.1 基本概念 382

16.2 散列函数 383

16.3 线性探测法 385

16.3.1 线性探测法的直观分析 386

16.3.2 实际上所发生的：初始聚类 386

16.3.3 find操作的分析 387

16.4 二次探测法 388

16.4.1 Java实现 392

16.4.2 二次探测法的分析 398

16.5 分别链接散列 399

16.6 散列表与二叉查找树 399

16.7 散列表的应用 400

小结 400

关键概念 400

常见错误 401

网上资源 401

习题 401

参考文献 403

第17章 优先级队列：二叉堆 404

17.1 基本概念 404

17.1.1 结构性 405

17.1.2 堆的有序性 406

17.1.3 允许的操作 406

17.2 基本操作的实现 408

17.2.1 插入 408

17.2.2 deleteMin操作 410

17.3 buildHeap操作：线性时间的堆构造 411

17.4 高级操作：decreaseKey和merge 414

17.5 内排序：堆排序 414

17.6 外排序 416

17.6.1 为什么需要新的算法 417

17.6.2 外排序模型 417

17.6.3 简单算法 417

17.6.4 多路归并 418

17.6.5 多阶段归并 419

17.6.6 置换选择法 420

小结 421

关键概念 422

常见错误 422

网上资源 422

习题 422

参考文献 425

第四部分 高级数据结构 428

第18章 伸展树 428

18.1 自调整和均摊法的分析 428

18.1.1 均摊法时间限度 429

18.1.2 简单的自调整策略（并不管用） 429

18.2 基本的自底向上的伸展树 430

18.3 基本的伸展树操作 432

18.4 自底向上伸展的分析 432

18.5 自顶向下的伸展树 436

18.6 自顶向下伸展树的实现 439

18.7 伸展树与其他搜索树的比较 442

小结 442

关键概念 443

常见错误 443

网上资源 443

习题 443

参考文献 444

第19章 归并优先级队列 445

19.1 斜堆 445

19.1.1 归并是基本操作 445

19.1.2 满足堆有序性的树的简化归并 446

19.1.3 斜堆：一个简单的修改 446

19.1.4 斜堆的分析 447

19.2 偶堆 448

19.2.1 偶堆操作 449

19.2.2 偶堆的实现 450

19.2.3 应用：Dijkstra最短加权路径算法 455

小结 457

关键概念 457

常见错误 457

网上资源 457

习题 457

参考文献 458

第20章 不相交集类 459

20.1 等价关系 459

20.2 动态等价及应用 459

20.2.1 应用：生成迷宫 460

20.2.2 应用：最小生成树 462

20.2.3 应用：最近的共同祖先问题 463

20.3 快速查找算法 466

20.4 快速并算法 466

20.4.1 智能并算法 468

20.4.2 路径压缩 469

20.5 Java实现 470

20.6 按秩并和路径压缩的最坏情况 471

小结 476

关键概念 477

常见错误 478

网上资源 478

习题 478

参考文献 479

附录A 运算符 481

附录B 位运算符 482