数据结构与算法经典问题解析

译者序

前言

第1章绪论1

1.1变量1

1.2数据类型1

1.3数据结构2

1.4抽象数据类型2

译者序

前言

第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.11AVL树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优先队列ADT181

7.3优先队列的应用182

7.4优先队列的实现182

7.5堆和二叉堆183

7.6二叉堆184

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

第8章并查集ADT201

8.1引言201

8.2等价关系和等价类201

8.3并查集ADT202

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散列表ADT317

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.4RobinKarp字符串匹配算法336

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

15.6KMP算法338

15.7Boyce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