數據結構解題策略

目 錄
前言
第一篇 線性表的解題策略
第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