高级数据结构 C++版 第3版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本章习题 25

第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二叉树的形态 40

2.3二叉排序树 45

2.4哈夫曼二叉树 59

2.5字典树 65

2.6本章习题 75

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

3.1优先队列 82

3.2二叉堆 84

3.2.1Put操作 84

3.2.2Get操作 85

3.3可并堆 93

3.3.1左偏树的定义 93

3.3.2左偏树的基本操作 94

3.4本章习题 100

第4章 并查集 107

4.1并查集的主要操作 107

4.2并查集的实现 108

4.2.1并查集的数组实现 108

4.2.2并查集的链表实现 108

4.2.3并查集的树实现 109

4.3并查集的应用举例 113

4.4本章习题 126

第5章 线段树 133

5.1线段树的应用背景 133

5.2线段树的初步实现 133

5.2.1线段树的结构 133

5.2.2线段树的性质 134

5.2.3线段树的存储 134

5.2.4线段树的常用操作 135

5.2.4.1线段树的构造 135

5.2.4.2线段树的查询 136

5.2.4.3线段树的修改 136

5.2.4.4线段树的延迟修改 137

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

5.3.1逆序对问题 139

5.3.2矩形覆盖问题 143

5.4线段树的扩展 147

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

5.4.2将线段树扩展到高维 151

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

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

5.6线段树的应用举例 166

5.7本章习题 177

第6章 树状数组 180

6.1树状数组的问题模型 180

6.2树状数组的基本思想 180

6.3树状数组的实现 182

6.3.1子集的划分方法 182

6.3.2查询前缀和 183

6.3.3修改子集和 183

6.4树状数组的常用技巧 184

6.4.1查询任意区间和 184

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

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

6.4.4成倍扩张/缩减 185

6.4.5初始化树状数组 185

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

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

6.7树状数组的应用举例 186

6.8本章习题 200

第7章 伸展树 204

7.1伸展树的主要操作 204

7.1.1伸展操作 205

7.1.2伸展树的基本操作 206

7.2伸展树的算法实现 207

7.3伸展树的效率分析 212

7.4伸展树的应用举例 214

7.5本章习题 224

第8章 Treap 228

8.1Treap的基本操作 228

8.2Treap的算法实现 231

8.3Treap的应用举例 234

8.4本章习题 239

第9章 平衡树 245

9.1AVL树 245

9.2红-黑树 252

9.3SBT 262

9.3.1SBT的基本操作 263

9.3.2SBT的效率分析 269

9.3.3SBT的算法实现 272

9.4本章习题 276

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

10.1块状链表的基本思想 281

10.2块状链表的基本操作 282

10.3块状链表的扩张 286

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

10.3.2维护局部数据有序化 287

10.3.3维护区间翻转 287

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

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

10.6块状链表的应用举例 288

10.7本章习题 316

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

11.1后缀树的简介 320

11.2后缀树的定义 320

11.3后缀树的构建 321

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

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

11.3.2.1隐式树的朴素构建 322

11.3.2.2扩展规则约定 323

11.3.2.3后缀链加速 324

11.3.2.4进一步加速 325

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

11.3.2.6代码实现 326

11.3.2.7相关证明 332

11.4后缀树的应用 332

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

11.4.1.1情形一 333

11.4.1.2情形二 333

11.4.1.3情形三 334

11.4.1.4情形四 335

11.4.2公共子串问题 335

11.4.2.1情形五 335

11.4.2.2情形六 336

11.4.2.3情形七 336

11.4.2.4情形八 337

11.4.2.5情形九 338

11.4.3重复子串问题 338

11.4.3.1情形十 338

11.4.3.2情形十一 340

11.4.3.3情形十二 340

11.5后缀数组的简介 341

11.6后缀数组的定义 341

11.7后缀数组的构建 343

11.7.1一种直接的构建算法 343

11.7.2倍增算法 343

11.7.2.1倍增算法描述 343

11.7.2.2倍增算法代码 344

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

11.7.4DC3算法和DC算法 346

11.7.4.1DC3算法 346

11.7.4.2DC算法 351

11.8LCP的引入 352

11.9后缀数组的应用 354

11.9.1后缀排序的直接应用 354

11.9.1.1Burrows-Wheeler变换 354

11.9.1.2多模式串的匹配 355

11.9.2通过引入LCP优化 355

11.9.2.1多模式串的匹配 355

11.9.2.2重复子串问题 356

11.9.2.3最长回文子串 359

11.9.2.4最长公共子串 360

11.9.3后缀数组的应用举例 360

11.10本章习题 377

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

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

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

12.3动态树的初探 396

12.3.1动态树的常用功能 396

12.3.2动态树的简单情形 397

12.4动态树的实现 399

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

12.4.1.1动态树的问题模型 399

12.4.1.2用Splay维护实路径 400

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

12.4.2.1动态树操作的次数 402

12.4.2.2Splay操作的平摊时间 402

12.5动态树的经典应用 403

12.5.1求最近公共祖先 403

12.5.2并查集操作 403

12.5.3求最大流 403

12.5.4求生成树 403

12.6动态树的应用举例 403

12.7本章习题 418

致谢 421