高级数据结构PDF|Epub|txt|kindle电子书版本下载

高级数据结构PDF格式电子书版下载

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

第1章 哈希表1

1.1 哈希表的基本原理1

1.2 哈希表的基本概念2

1.3 哈希函数的构造3

1.4 哈希表的基本操作5

1.5 冲突的处理6

1.6 哈希表的性能分析11

1.7 哈希表的应用举例12

1.8 本章习题26

第2章 树与二叉树30

2.1 树30

2.1.1 树的存储结构31

2.1.2 树的遍历32

2.2 二叉树35

2.2.1 普通树转换成二叉树37

2.2.2 二叉树的遍历38

2.2.3 二叉树的其他操作39

2.2.4 二叉树的形态41

2.3 二叉排序树45

2.4 哈夫曼二叉树61

2.5 字典树67

2.6 本章习题79

第3章 优先队列与二叉堆86

3.1 优先队列86

3.2 二叉堆88

3.2.1 Put操作88

3.2.2 Get操作89

3.3 可并堆98

3.3.1 左偏树的定义98

3.3.2 左偏树的基本操作99

3.4 本章习题106

第4章 并查集113

4.1 并查集的主要操作113

4.2 并查集的实现114

4.2.1 并查集的数组实现114

4.2.2 并查集的链表实现114

4.2.3 并查集的树实现115

4.3 并查集的应用举例119

4.4 本章习题133

第5章 线段树140

5.1 线段树的应用背景140

5.2 线段树的初步实现140

5.2.1 线段树的结构140

5.2.2 线段树的性质141

5.2.3 线段树的存储141

5.2.4 线段树的常用操作142

5.2.4.1 线段树的构造142

5.2.4.2 线段树的查询143

5.2.4.3 线段树的修改143

5.2.4.4 线段树的延迟修改144

5.3 线段树在一些经典问题中的应用147

5.3.1 逆序对问题147

5.3.2 矩形覆盖问题150

5.4 线段树的扩展155

5.4.1 用线段树优化动态规划155

5.4.2 将线段树扩展到高维160

5.4.3 线段树与平衡树的结合167

5.5 线段树与其他数据结构的比较176

5.6 线段树的应用举例176

5.7 本章习题188

第6章 树状数组191

6.1 树状数组的问题模型191

6.2 树状数组的基本思想191

6.3 树状数组的实现193

6.3.1 子集的划分方法193

6.3.2 查询前缀和194

6.3.3 修改子集和194

6.4 树状数组的常用技巧195

6.4.1 查询任意区间和195

6.4.2 利用sum数组求出原数组a的某个元素值195

6.4.3 找到某个前缀和对应的前缀下标index195

6.4.4 成倍扩张／缩减196

6.4.5 初始化树状数组196

6.5 树状数组与线段树的比较196

6.6 树状数组扩展到高维的情形196

6.7 树状数组的应用举例197

6.8 本章习题213

第7章 伸展树216

7.1 伸展树的主要操作216

7.1.1 伸展操作217

7.1.2 伸展树的基本操作218

7.2 伸展树的算法实现219

7.3 伸展树的效率分析223

7.4 伸展树的应用举例225

7.5 本章习题237

第8章 Treap242

8.1 Treap的基本操作242

8.2 Treap的算法实现245

8.3 Treap的应用举例249

8.4 本章习题255

第9章 平衡树260

9.1 AVL树260

9.2 红-黑树268

9.3 SBT278

9.3.1 SBT的基本操作279

9.3.2 SBT的效率分析284

9.3.3 SBT的算法实现288

9.4 本章习题292

第10章 块状链表与块状树297

10.1 块状链表的基本思想297

10.2 块状链表的基本操作298

10.3 块状链表的扩张302

10.3.1 维护区间和以及区间最值302

10.3.2 维护局部数据有序化303

10.3.3 维护区间翻转303

10.4 块状链表与其他数据结构的比较303

10.5 分块思想在树上的应用——块状树303

10.6 块状链表的应用举例304

10.7 本章习题335

第11章 后缀树与后缀数组339

11.1 后缀树的简介339

11.2 后缀树的定义339

11.3 后缀树的构建340

11.3.1 后缀树的朴素构建算法340

11.3.2 后缀树的线性时间构建算法340

11.3.2.1 隐式树的朴素构建341

11.3.2.2 扩展规则约定342

11.3.2.3 后缀链加速343

11.3.2.4 进一步加速344

11.3.2.5 后缀树拓展到多串的形式345

11.3.2.6 代码实现345

11.3.2.7 相关证明351

11.4 后缀树的应用352

11.4.1 字符串（集合）的精确匹配352

11.4.1.1 情形一352

11.4.1.2 情形二353

11.4.1.3 情形三353

11.4.1.4 情形四354

11.4.2 公共子串问题354

11.4.2.1 情形五354

11.4.2.2 情形六355

11.4.2.3 情形七356

11.4.2.4 情形八356

11.4.2.5 情形九358

11.4.3 重复子串问题358

11.4.3.1 情形十358

11.4.3.2 情形十一359

11.4.3.3 情形十二360

11.5 后缀数组的简介361

11.6 后缀数组的定义361

11.7 后缀数组的构建362

11.7.1 一种直接的构建算法362

11.7.2 倍增算法362

11.7.2.1 倍增算法描述363

11.7.2.2 倍增算法代码363

11.7.3 由后缀树得到后缀数组365

11.7.4 DC3算法和DC算法366

11.7.4.1 DC3算法366

11.7.4.2 DC算法371

11.8 LCP的引入372

11.9 后缀数组的应用374

11.9.1 后缀排序的直接应用374

11.9.1.1 Burrows-Wheeler变换374

11.9.1.2 多模式串的匹配374

11.9.2 通过引入LCP优化375

11.9.2.1 多模式串的匹配375

11.9.2.2 重复子串问题376

11.9.2.3 最长回文子串379

11.9.2.4 最长公共子串380

11.9.3 后缀数组的应用举例381

11.10 本章习题399

第12章 树链剖分与动态树401

12.1 树链剖分的思想和性质401

12.2 树链剖分的实现及应用403

12.3 动态树的初探419

12.3.1 动态树的常用功能419

12.3.2 动态树的简单情形420

12.4 动态树的实现422

12.4.1 动态树的基本操作及其实现422

12.4.1.1 动态树的问题模型422

12.4.1.2 用Splay维护实路径422

12.4.2 动态树操作的时间复杂度分析424

12.4.2.1 动态树操作的次数425

12.4.2.2 Splay操作的平摊时间425

12.5 动态树的经典应用425

12.5.1 求最近公共祖先425

12.5.2 并查集操作425

12.5.3 求最大流426

12.5.4 求生成树426

12.6 动态树的应用举例426

12.7 本章习题443

致射445