数据结构解题策略

目　　录

前言

第一篇　线性表的解题策略

第1章　利用快速幂提高幂运算效率　　2

1.1　快速幂取模　　　2

1.1.1　快速幂取模的概念　　　2

1.1.2　快速幂取模的应用　　　4

1.2　矩阵快速幂　　　10

1.2.1　矩阵快速幂的概念　　　10

1.2.2　矩阵快速幂的应用　　　14

第2章　高斯消元法　　22

2.1　高斯消元法求解线性方程组　　　22

2.2　高斯消元法求解模线性方程组　　　30

2.3　高斯消元法求解异或方程组　　　38

2.4　高斯消元求矩阵的秩　　　49

第3章　单调栈和单调队列　　52

3.1　单调栈　　　52

3.2　二维空间中应用单调栈　　　61

3.3　单调队列　　　65

3.4　单调队列优化DP　　　69

3.5　单调队列优化DP之多重背包问题　　　78

第一篇小结　　83

第二篇　树的解题策略

第4章　利用划分树查找有序数　　86

4.1　离线构建整个查询区间的划分树　　87

4.2　在划分树上查找子区间[l, r]中

　　按序排列的第k个值　　88

4.3　利用划分树解题　　88

第5章　利用线段树解决区间计算问题　　97

5.1　线段树的基本概念和基本操作　　97

5.2　线段树动态维护：单点更新　　101

5.3　线段树动态维护：子区间更新和

　　　　 懒惰标记　　106

5.4 　线段树动态维护：子区间合并　　112

5.5　权值线段树　　120

5.6　主席树　　125

第6章　最小生成树的拓展　　129

6.1　最小生成树的应用　　129

6.2　最优比率生成树　　143

6.3　最小k度限制生成树　　148

6.4　次小生成树　　154

第7章　利用改进型的二叉搜索树优化

　　　　　　　　 动态集合的操作　　171

7.1　伸展树　　171

7.2　红黑树　　198

第8章　利用左偏树实现优先队列的合并　　212

8.1　左偏树的基本概念　　212

8.2　利用左偏树解题　　216

第9章　利用动态树维护森林的连通性　　230

9.1　树链剖分　　230

9.2　动态树　　241

第10章　利用跳跃表替代树结构　　260

10.1　跳跃表的基本概念　　260

10.2　利用跳跃表解题　　265

第二篇小结　　279

第三篇　图的解题策略

第11章　网络流算法　　282

11.1　利用Dinic算法求解最大流　　282

11.2　求容量有上下界的网络流问题　　298

11.2.1　求解无源汇且容量有上下界

　　　　　　的网络可行流问题　　　298

11.2.2　求解有源汇且容量有上下界

　　　　　　　 的网络最大流问题　　　307

11.2.3　求解有源汇且容量有上下界

　　　　　　　 的网络最小流问题　　　316

11.3　计算最小（最大）费用最大流　　321

第12章　二分图匹配　　329

12.1　匈牙利算法　　329

12.2　稳定婚姻问题　　344

12.3　KM算法　　350

12.4　利用一一对应的匹配性质转化

　　　　　　问题的实验范例　　358

第13章　平面图、图的着色与偏序关系　　371

13.1　平面图　　371

13.2　图的着色　　380

13.3　黑白着色法判定二分图　　383

13.4　偏序关系　　395

第14章　分层图　　407

14.1　体验“分层图”思想内涵　　407

14.2　基于动态规划利用“分层图”

　　　　　　求解最短路径问题　　417

14.3　利用“分层图”思想优化算法　　425

第15章　可简单图化与图的计数　　430

15.1　可简单图化　　430

15.2　生成树计数　　435

15.3　基于遍历的图的计数　　446

15.4　基于组合分析的图的计数　　451

第16章　挖掘和利用图的性质　　460

16.1　挖掘和利用图的性质的方法　　460

16.2　挖掘和利用图的性质的实验范例460

第三篇小结　　468