包邮高级数据结构-(C++版)

第1章 哈希表1．1 哈希表的基本原理1．2 哈希表的基本概念1．3 哈希函数的构造1．4 哈希表的基本操作1．5 冲突的处理1．6 哈希表的性能分析1．7 哈希表的应用举例1．8 本章习题第2章 树与二叉树2．1 树2．1．1 树的存储结构2．1．2 树的遍历2．2 二叉树2．2．1 普通树转换成二叉树2．2．2 二叉树的遍历2．2．3 二叉树的其他操作2．2．4 二叉树的形态2．3 二叉排序树2．4 哈夫曼二叉树2．5 字典树2．6 本章习题第3章 优先队列与二叉堆3．1 优先队列3．2 二叉堆3．2．1 Put操作3．2．2 Get操作3．3 可并堆3．3．1 左偏树的定义3．3．2 左偏树的基本操作3．4 本章习题第4章 并查集4．1 并查集的主要操作4．2 并查集的实现4．2．1 并查集的数组实现4．2．2 并查集的链表实现4．2．3 并查集的树实现4．3 并查集的应用举例4．4 本章习题第5章 线段树5．1 线段树的应用背景5．2 线段树的初步实现5．2．1 线段树的结构5．2．2 线段树的性质5．2．3 线段树的存储5．2．4 线段树的常用操作5．2．4．1 线段树的构造5．2．4．2 线段树的查询5．2．4．3 线段树的修改5．2．4．4 线段树的延迟修改5．3 线段树在一些经典问题中的应用5．3．1 逆序对问题5．3．2 矩形覆盖问题5．4 线段树的扩展5．4．1 用线段树优化动态规划5．4．2 将线段树扩展到高维5．4．3 线段树与平衡树的结合5．5 线段树与其他数据结构的比较5．6 线段树的应用举例5．7 本章习题第6章 树状数组6．1 树状数组的问题模型6．2 树状数组的基本思想6．3 树状数组的实现6．3．1 子集的划分方法6．3．2 查询前缀和6．3．3 修改子集和6．4 树状数组的常用技巧6．4．1 查询任意区间和6．4．2 利用sum数组求出原数组a的某个元素值6．4．3 找到某个前缀和对应的前缀下标index6．4．4 成倍扩张／缩减6．4．5 初始化树状数组6．5 树状数组与线段树的比较6．6 树状数组扩展到高维的情形6．7 树状数组的应用举例6．8 本章习题第7章 伸展树7．1 伸展树的主要操作7．1．1 伸展操作7．1．2 伸展树的基本操作7．2 伸展树的算法实现7．3 伸展树的效率分析7．4 伸展树的应用举例7．5 本章习题第8章 Treap8．1 Treap的基本操作8．2 Treap的算法实现8．3 Treap的应用举例8．4 本章习题第9章 平衡树9．1 AVL树9．2 红一黑树9．3 SBT9．3．1 SBT的基本操作9．3．2 SBT的效率分析9．3．3 SBT的算法实现9．4 本章习题第10章 块状链表与块状树10．1 块状链表的基本思想10．2 块状链表的基本操作10．3 块状链表的扩张10．3．1 维护区间和以及区间*值10．3．2 维护局部数据有序化10．3．3 维护区间翻转10．4 块状链表与其他数据结构的比较10．5 分块思想在树上的应用——块状树10．6 块状链表的应用举例10．7 本章习题第11章 后缀树与后缀数组11．1 后缀树的简介11．2 后缀树的定义11．3 后缀树的构建11．3．1 后缀树的朴素构建算法11．3．2 后缀树的线性时间构建算法11．3．2．1 隐式树的朴素构建11．3．2．2 扩展规则约定11．3．2．3 后缀链加速11．3．2．4 进一步加速11．3．2．5 后缀树拓展到多串的形式11．3．2．6 代码实现11．3．2．7 相关证明11．4 后缀树的应用11．4．1 字符串（集合）的精确匹配11．4．1．1 情形一11．4．1．2 情形二11．4．1．3 情形三11．4．1．4 情形四11．4．2 公共子串问题11．4．2．1 情形五11．4．2．2 情形六11．4．2．3 情形七11．4．2．4 情形八11．4．2．5 情形九11．4．3 重复子串问题11．4．3．1 情形十11．4．3．2 情形十一11．4．3．3 情形十二11．5 后缀数组的简介11．6 后缀数组的定义11．7 后缀数组的构建11．7．1 一种直接的构建算法11．7．2 倍增算法11．7．2．1 倍增算法描述11．7．2．2 倍增算法代码11．7．3 由后缀树得到后缀数组11．7．4 DC3算法和DC算法11．7．4．1 DC3算法11．7．4．2 DC算法11．8 LCP的引人11．9 后缀数组的应用11．9．1 后缀排序的直接应用11．9．1．1 Burrows-Wheeler变换11．9．1．2 多模式串的匹配11．9．2 通过引入LCP优化11．9．2．1 多模式串的匹配11．9．2．2 重复子串问题11．9．2．3 *长回文子串11．9．2．4 *长公共子串11．9．3 后缀数组的应用举例11．10 本章习题第12章 树链剖分与动态树12．1 树链剖分的思想和性质12．2 树链剖分的实现及应用12．3 动态树的初探12．3．1 动态树的常用功能12．3．2 动态树的简单情形12．4 动态树的实现12．4．1 动态树的基本操作及其实现12．4．1．1 动态树的问题模型12．4．1．2 用Splay维护实路径12．4．2 动态树操作的时间复杂度分析12．4．2．1 动态树操作的次数12．4．2．2 Splay操作的平摊时间12．5 动态树的经典应用12．5．1 求*近公共祖先12．5．2 并查集操作12．5．3 求*大流12．5．4 求生成树12．6 动态树的应用举例12．7 本章习题致谢