高級(jí)數(shù)據(jù)結(jié)構(gòu)

第1章  哈希表
  1.1  哈希表的基本原理
  1.2  哈希表的基本概念
  1.3  哈希函數(shù)的構(gòu)造
  1.4  哈希表的基本操作
  1.5  沖突的處理
  1.6  哈希表的性能分析
  1.7  哈希表的應(yīng)用舉例
  1.8  本章習(xí)題
第2章  樹(shù)與二叉樹(shù)
  2.1  樹(shù)
    2.1.1  樹(shù)的存儲(chǔ)結(jié)構(gòu)
    2.1.2  樹(shù)的遍歷
  2.2  二叉樹(shù)
    2.2.1  普通樹(shù)轉(zhuǎn)換成二叉樹(shù)
    2.2.2  二叉樹(shù)的遍歷
    2.2.3  二叉樹(shù)的其他操作
    2.2.4  二叉樹(shù)的形態(tài)
  2.3  二叉排序樹(shù)
  2.4  哈夫曼二叉樹(shù)
  2.5  字典樹(shù)
  2.6  本章習(xí)題
第3章  優(yōu)先隊(duì)列與二叉堆
  3.1  優(yōu)先隊(duì)列
  3.2  二叉堆
    3.2.1  Put操作
    3.2.2  Get操作
  3.3  可并堆
    3.3.1  左偏樹(shù)的定義
    3.3.2  左偏樹(shù)的基本操作
  3.4  本章習(xí)題
第4章  并查集
  4.1  并查集的主要操作
  4.2  并查集的實(shí)現(xiàn)
    4.2.1  并查集的數(shù)組實(shí)現(xiàn)
    4.2.2  并查集的鏈表實(shí)現(xiàn)
    4.2.3  并查集的樹(shù)實(shí)現(xiàn)
  4.3  并查集的應(yīng)用舉例
  4.4  本章習(xí)題
第5章  線段樹(shù)
  5.1  線段樹(shù)的應(yīng)用背景
  5.2  線段樹(shù)的初步實(shí)現(xiàn)
    5.2.1  線段樹(shù)的結(jié)構(gòu)
    5.2.2  線段樹(shù)的性質(zhì)
    5.2.3  線段樹(shù)的存儲(chǔ)
    5.2.4  線段樹(shù)的常用操作
    5.2.4.1  線段樹(shù)的構(gòu)造
    5.2.4.2  線段樹(shù)的查詢
    5.2.4.3  線段樹(shù)的修改
    5.2.4.4  線段樹(shù)的延遲修改
  5.3  線段樹(shù)在一些經(jīng)典問(wèn)題中的應(yīng)用
    5.3.1  逆序?qū)?wèn)題
    5.3.2  矩形覆蓋問(wèn)題
  5.4  線段樹(shù)的擴(kuò)展
    5.4.1  用線段樹(shù)優(yōu)化動(dòng)態(tài)規(guī)劃
    5.4.2  將線段樹(shù)擴(kuò)展到高維
    5.4.3  線段樹(shù)與平衡樹(shù)的結(jié)合
  5.5  線段樹(shù)與其他數(shù)據(jù)結(jié)構(gòu)的比較
  5.6  線段樹(shù)的應(yīng)用舉例
  5.7  本章習(xí)題
第6章  樹(shù)狀數(shù)組
  6.1  樹(shù)狀數(shù)組的問(wèn)題模型
  6.2  樹(shù)狀數(shù)組的基本思想
  6.3  樹(shù)狀數(shù)組的實(shí)現(xiàn)
    6.3.1  子集的劃分方法
    6.3.2  查詢前綴和
    6.3.3  修改子集和
    6.4  樹(shù)狀數(shù)組的常用技巧
    6.4.1  查詢?nèi)我鈪^(qū)間和
    6.4.2  利用SHill數(shù)組求出原數(shù)組a的某個(gè)元素值
    6.4.3  找到某個(gè)前綴和對(duì)應(yīng)的前綴下標(biāo)index
    6.4.4  成倍擴(kuò)張／縮減
    6.4.5  初始化樹(shù)狀數(shù)組
  6.5  樹(shù)狀數(shù)組與線段樹(shù)的比較
  6.6  樹(shù)狀數(shù)組擴(kuò)展到高維的情形
  6.7  樹(shù)狀數(shù)組的應(yīng)用舉例
  6.8  本章習(xí)題
第7章  伸展樹(shù)
  7.1  伸展樹(shù)的主要操作
    7.1.1  伸展操作
    7.1.2  伸展樹(shù)的基本操作
  7.2  伸展樹(shù)的算法實(shí)現(xiàn)
  7.3  伸展樹(shù)的效率分析
  7.4  伸展樹(shù)的應(yīng)用舉例
  7.5  本章習(xí)題
第8章  Treap
  8.1  Treap的基本操作
  8.2  Treap的算法實(shí)現(xiàn)
  8.3  Treap的應(yīng)用舉例
  8.4  本章習(xí)題
第9章  平衡樹(shù)
  9.1  AVL樹(shù)
  9.2  紅—黑樹(shù)
  9.3  SBT
    9.3.1  SBT的基本操作
    9.3.2  SBT的效率分析
    9.3.3  SBT的算法實(shí)現(xiàn)
  9.4  本章習(xí)題
第10章  塊狀鏈表與塊狀樹(shù)
  10.1  塊狀鏈表的基本思想
  10.2  塊狀鏈表的基本操作
  10.3  塊狀鏈表的擴(kuò)張
    10.3.1  維護(hù)區(qū)間和以及區(qū)間最值
    10.3.2  維護(hù)局部數(shù)據(jù)有序化
    10.3.3  維護(hù)區(qū)間翻轉(zhuǎn)
  10.4  塊狀鏈表與其他數(shù)據(jù)結(jié)構(gòu)的比較
  10.5  分塊思想在樹(shù)上的應(yīng)用——塊狀樹(shù)
  10.6  塊狀鏈表的應(yīng)用舉例
  10.7  本章習(xí)題
第11章  后綴樹(shù)與后綴數(shù)組
  11.1  后綴樹(shù)的簡(jiǎn)介
  11.2  后綴樹(shù)的定義
  11.3  后綴樹(shù)的構(gòu)建
    11.3.1  后綴樹(shù)的樸素構(gòu)建算法
    11.3.2  后綴樹(shù)的線性時(shí)間構(gòu)建算法
    11.3.2.1  隱式樹(shù)的樸素構(gòu)建
    11.3.2.2  擴(kuò)展規(guī)則約定
    11.3.2.3  后綴鏈加速
    11.3.2.4  進(jìn)一步加速
    11.3.2.5  后綴樹(shù)拓展到多串的形式
    11.3.2.6  代碼實(shí)現(xiàn)
    11.3.2.7  相關(guān)證明
  11.4  后綴樹(shù)的應(yīng)用
    11.4.1  字符串（集合）的精確匹配
    11.4.1.1  情形一
    11.4.1.2  情形二
    11.4.1.3  情形三
    11.4.1.4  情形四
    11.4.2  公共子串問(wèn)題
    11.4.2.1  情形五
    11.4.2.2  情形六
    11.4.2.3  情形七
    11.4.2.4  情形八
    11.4.2.5  情形九
    11.4.3  重復(fù)子串問(wèn)題
    11.4.3.1  情形十
    11.4.3.2  情形十一
    11.4.3.3  情形十二
  11.5  后綴數(shù)組的簡(jiǎn)介
  11.6  后綴數(shù)組的定義
  11.7  后綴數(shù)組的構(gòu)建
    11.7.1  一種直接的構(gòu)建算法
    11.7.2  倍增算法
    11.7.2.1  倍增算法描述
    11.7.2.2  倍增算法代碼
    11.7.3  由后綴樹(shù)得到后綴數(shù)組
    11.7.4  DC3算法和DC算法
    11.7.4.1  DC3算法
    11.7.4.2  DC算法
  11.8  LCP的引入
  11.9  后綴數(shù)組的應(yīng)用
    11.9.1  后綴排序的直接應(yīng)用
    11.9.1.1  Burrows—Wheeler變換
    11.9.1.2  多模式串的匹配
    11.9.2  通過(guò)引入LCP優(yōu)化
    11.9.2.1  多模式串的匹配
    11.9.2.2  重復(fù)子串問(wèn)題
    11.9.2.3  最長(zhǎng)回文子串
    11.9.2.4  最長(zhǎng)公共子串
    11.9.3  后綴數(shù)組的應(yīng)用舉例
  11.10  本章習(xí)題
第12章  樹(shù)鏈剖分與動(dòng)態(tài)樹(shù)
  12.1  樹(shù)鏈剖分的思想和性質(zhì)
  12.2  樹(shù)鏈剖分的實(shí)現(xiàn)及應(yīng)用
  12.3  動(dòng)態(tài)樹(shù)的初探
    12.3.1  動(dòng)態(tài)樹(shù)的常用功能
    12.3.2  動(dòng)態(tài)樹(shù)的簡(jiǎn)單情形
  12.4  動(dòng)態(tài)樹(shù)的實(shí)現(xiàn)
    12.4.1  動(dòng)態(tài)樹(shù)的基本操作及其實(shí)現(xiàn)
    12.4.1.1  動(dòng)態(tài)樹(shù)的問(wèn)題模型
    12.4.1.2  用Splay維護(hù)實(shí)路徑
    12.4.2  動(dòng)態(tài)樹(shù)操作的時(shí)間復(fù)雜度分析
    12.4.2.1  動(dòng)態(tài)樹(shù)操作的次數(shù)
    12.4.2.2  Splay操作的平攤時(shí)間
  12.5  動(dòng)態(tài)樹(shù)的經(jīng)典應(yīng)用
    12.5.1  求最近公共祖先
    12.5.2  并查集操作
    12.5.3  求最大流
    12.5.4  求生成樹(shù)
  12.6  動(dòng)態(tài)樹(shù)的應(yīng)用舉例
  12.7  本章習(xí)題
致謝