数据结构与算法经典问题解析 Java语言描述PDF电子书下载

第1章 绪论 1

1.1 变量 1

1.2 数据类型 1

1.3 数据结构 2

1.4 抽象数据类型 2

1.5 什么是算法 3

1.6 为什么需要算法分析 3

1.7 算法分析的目的 3

1.8 什么是运行时间分析 4

1.9 如何比较算法 4

1.10 什么是增长率 4

1.11 常用的增长率 4

1.12 分析的类型 5

1.13 渐近表示 6

1.14 大O表示法 6

1.15 Ω表示法 7

1.16 ？表示法 8

1.17 重要说明 9

1.18 为什么称为渐近分析 9

1.19 渐近分析指南 9

1.20 渐近表示法的性质 11

1.21 常用的对数和累加公式 11

1.22 分治法主定理 12

1.23 分治法主定理的相关问题 12

1.24 问题规模减小和递归求解主定理 13

1.25 问题规模减小和递归求解主定理的变型 13

1.26 猜测和确认的方法 14

1.27 平摊分析 15

1.28 算法分析的相关问题 15

第2章 递归和回溯 28

2.1 引言 28

2.2 什么是递归 28

2.3 为什么要用递归 28

2.4 递归函数的格式 28

2.5 递归和内存（可视化） 29

2.6 递归与迭代 30

2.7 递归说明 30

2.8 递归算法的经典用例 30

2.9 递归的相关问题 31

2.10 什么是回溯 32

2.11 回溯算法的经典用例 32

2.12 回溯的相关问题 32

第3章 链表 34

3.1 什么是链表 34

3.2 链表抽象数据类型 34

3.3 为什么要用链表 35

3.4 数组概述 35

3.5 链表、数组和动态数组的比较 36

3.6 单向链表 36

3.7 双向链表 41

3.8 循环链表 46

3.9 一种存储高效的双向链表 51

3.10 松散链表 52

3.11 链表的相关问题 55

第4章 栈 72

4.1 什么是栈 72

4.2 如何使用栈 72

4.3 栈抽象数据类型 73

4.4 异常 73

4.5 应用 73

4.6 实现 73

4.7 栈的各种实现方法比较 77

4.8 栈的相关问题 78

第5章 队列 98

5.1 什么是队列 98

5.2 如何使用队列 98

5.3 队列抽象数据类型 99

5.4 异常 99

5.5 应用 99

5.6 实现 99

5.7 队列的相关问题 104

第6章 树 110

6.1 什么是树 110

6.2 术语 110

6.3 二叉树 111

6.4 二叉树的遍历 114

6.5 通用树（N叉树） 135

6.6 线索（无栈或无队列结构）二叉树遍历 141

6.7 表达式树 147

6.8 异或树 149

6.9 二叉搜索树 150

6.10 平衡二叉搜索树 164

6.11 AVL树 165

6.12 树的其他形式 178

6.12.1 红黑树 178

6.12.2 伸展树 179

6.12.3 增强树 179

6.12.4 替罪羊树 179

6.12.5 区间树 180

第7章 优先队列和堆 181

7.1 什么是优先队列 181

7.2 优先队列ADT 181

7.3 优先队列的应用 182

7.4 优先队列的实现 182

7.5 堆和二叉堆 183

7.6 二叉堆 184

7.7 优先队列（堆）的相关问题 190

第8章 并查集ADT 201

8.1 引言 201

8.2 等价关系和等价类 201

8.3 并查集ADT 202

8.4 应用 202

8.5 并查集ADT实现中的权衡 202

8.6 快速UNION实现（慢FIND） 203

8.7 快速UNION实现（快速FIND） 206

8.8 路径压缩 208

8.9 小结 209

8.10 并查集的相关问题 209

第9章 图算法 211

9.1 引言 211

9.2 术语 211

9.3 图的应用 214

9.4 图的表示 214

9.5 图的遍历 217

9.6 拓扑排序 225

9.7 最短路径算法 226

9.8 最小生成树 231

9.9 图算法的相关问题 235

第10章 排序 256

10.1 什么是排序 256

10.2 为什么需要排序 256

10.3 排序的分类 256

10.4 其他分类方法 257

10.5 冒泡排序 257

10.6 选择排序 258

10.7 插入排序 259

10.8 希尔排序 261

10.9 归并排序 262

10.10 堆排序 264

10.11 快速排序 264

10.12 树排序 266

10.13 排序算法比较 267

10.14 线性排序算法 267

10.15 计数排序 267

10.16 桶排序 268

10.17 基数排序 268

10.18 拓扑排序 269

10.19 外部排序 269

10.20 排序的相关问题 270

第11章 查找 279

11.1 什么是查找 279

11.2 为什么需要查找 279

11.3 查找的类型 279

11.4 符号表和散列 281

11.5 字符串查找算法 281

11.6 查找的相关问题 281

第12章 选择算法（中位数） 304

12.1 什么是选择算法 304

12.2 基于排序的选择算法 304

12.3 基于划分的选择算法 304

12.4 线性选择算法——中位数的中位数算法 305

12.5 按照排序顺序查找K个最小元素 305

12.6 选择算法的相关问题 305

第13章 符号表 314

13.1 引言 314

13.2 什么是符号表 314

13.3 符号表的实现 315

13.4 符号表实现方法的比较 315

第14章 散列 317

14.1 什么是散列 317

14.2 为什么用散列 317

14.3 散列表ADT 317

14.4 散列的例子 317

14.5 散列的组成部分 319

14.6 散列表 319

14.7 散列函数 319

14.8 负载因子 320

14.9 冲突 320

14.10 冲突解决技术 320

14.11 分离链接法 320

14.12 开放定址法 321

14.13 冲突解决技术的比较 322

14.14 散列如何达到O（1）的时间复杂度 322

14.15 散列技术 323

14.16 不适用散列表的问题 323

14.17 布鲁姆过滤器 323

14.18 散列的相关问题 325

第15章 字符串算法 335

15.1 引言 335

15.2 字符串匹配算法 335

15.3 蛮力法 336

15.4 Robin-Karp字符串匹配算法 336

15.5 基于有限自动机的字符串匹配算法 337

15.6 KMP算法 338

15.7 Boyce-Moore算法 342

15.8 存储字符串的数据结构 342

15.9 字符串的散列表实现 342

15.10 字符串的二叉搜索树实现 343

15.11 键树 343

15.12 三叉搜索树 345

15.13 二叉搜索树、键树和三叉搜索树的比较 349

15.14 后缀树 349

15.15 字符串的相关问题 353

第16章 算法设计技术 361

16.1 引言 361

16.2 分类 361

16.3 按实现方法分类 361

16.4 按设计方法分类 362

16.5 其他分类法 363

第17章 贪婪算法 364

17.1 引言 364

17.2 贪婪策略的定义 364

17.3 贪婪算法的要素 364

17.4 贪婪算法的适用范围 365

17.5 贪婪算法的优缺点 365

17.6 贪婪算法的应用 365

17.7 贪婪思想 365

17.8 贪婪算法的相关问题 368

第18章 分治算法 375

18.1 引言 375

18.2 分治策略的定义 375

18.3 分治法的适用范围 375

18.4 分治法的图形化描述 375

18.5 分治思想 376

18.6 主定理 377

18.7 分治法的应用 377

18.8 分治法的相关问题 378

第19章 动态规划算法 390

19.1 引言 390

19.2 动态规划策略的定义 390

19.3 动态规划策略的性质 390

19.4 动态规划的适用范围 390

19.5 动态规划的实现方法 391

19.6 动态规划算法的例子 391

19.7 动态规划思想 391

19.8 动态规划的相关问题 396

第20章 复杂度类型 425

20.1 引言 425

20.2 多项式／指数时间 425

20.3 决策问题的定义 426

20.4 决策过程 426

20.5 复杂度类型的定义 426

20.6 复杂度类型 426

20.7 归约 428

20.8 复杂度类型的相关问题 430

第21章 杂谈 433

21.1 引言 433

21.2 位运算的使用 433

21.2.1 按位与操作 433

21.2.2 按位或操作 434

21.2.3 按位异或操作 434

21.2.4 按位左移操作 434

21.2.5 按位右移操作 434

21.2.6 按位补操作 434

21.2.7 检测第K位是否置位 434

21.2.8 第K位置位 435

21.2.9 第K位清零 435

21.2.10 切换第K位 435

21.2.11 切换值为1的最右位 435

21.2.12 隔离值为1的最右位 435

21.2.13 隔离值为0的最右位 435

21.2.14 检查某个数是否是2的幂 436

21.2.15 将某个数乘以2的幂 436

21.2.16 将某个数除以2的幂 436

21.2.17 找到给定操作数的模 436

21.2.18 反转二进制数 436

21.2.19 位值1的计数 436

21.2.20 创建末尾位为0的掩码 437

21.2.21 交换奇偶位 438

21.2.22 不使用除法来计算平均数 438

21.3 其他编程问题 438

参考文献 442