數(shù)據(jù)結構解題策略

目　　錄
前言
第一篇　線性表的解題策略
第1章　利用快速冪提高冪運算效率　　2
1.1　快速冪取?！　　?
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章　單調(diào)棧和單調(diào)隊列　　52
3.1　單調(diào)?！　　?2
3.2　二維空間中應用單調(diào)?！　　?1
3.3　單調(diào)隊列　　　65
3.4　單調(diào)隊列優(yōu)化DP　　　69
3.5　單調(diào)隊列優(yōu)化DP之多重背包問題　　　78
第一篇小結　　83
第二篇　樹的解題策略
第4章　利用劃分樹查找有序數(shù)　　86
4.1　離線構建整個查詢區(qū)間的劃分樹　　87
4.2　在劃分樹上查找子區(qū)間[l, r]中
　　按序排列的第k個值　　88
4.3　利用劃分樹解題　　88
第5章　利用線段樹解決區(qū)間計算問題　　97
5.1　線段樹的基本概念和基本操作　　97
5.2　線段樹動態(tài)維護：單點更新　　101
5.3　線段樹動態(tài)維護：子區(qū)間更新和
　　　　 懶惰標記　　106
5.4 　線段樹動態(tài)維護：子區(qū)間合并　　112
5.5　權值線段樹　　120
5.6　主席樹　　125
第6章　最小生成樹的拓展　　129
6.1　最小生成樹的應用　　129
6.2　最優(yōu)比率生成樹　　143
6.3　最小k度限制生成樹　　148
6.4　次小生成樹　　154
第7章　利用改進型的二叉搜索樹優(yōu)化
　　　　　　　　 動態(tài)集合的操作　　171
7.1　伸展樹　　171
7.2　紅黑樹　　198
第8章　利用左偏樹實現(xiàn)優(yōu)先隊列的合并　　212
8.1　左偏樹的基本概念　　212
8.2　利用左偏樹解題　　216
第9章　利用動態(tài)樹維護森林的連通性　　230
9.1　樹鏈剖分　　230
9.2　動態(tài)樹　　241
第10章　利用跳躍表替代樹結構　　260
10.1　跳躍表的基本概念　　260
10.2　利用跳躍表解題　　265
第二篇小結　　279
第三篇　圖的解題策略
第11章　網(wǎng)絡流算法　　282
11.1　利用Dinic算法求解最大流　　282
11.2　求容量有上下界的網(wǎng)絡流問題　　298
11.2.1　求解無源匯且容量有上下界
　　　　　　的網(wǎng)絡可行流問題　　　298
11.2.2　求解有源匯且容量有上下界
　　　　　　　 的網(wǎng)絡最大流問題　　　307
11.2.3　求解有源匯且容量有上下界
　　　　　　　 的網(wǎng)絡最小流問題　　　316
11.3　計算最?。ㄗ畲螅┵M用最大流　　321
第12章　二分圖匹配　　329
12.1　匈牙利算法　　329
12.2　穩(wěn)定婚姻問題　　344
12.3　KM算法　　350
12.4　利用一一對應的匹配性質(zhì)轉(zhuǎn)化
　　　　　　問題的實驗范例　　358
第13章　平面圖、圖的著色與偏序關系　　371
13.1　平面圖　　371
13.2　圖的著色　　380
13.3　黑白著色法判定二分圖　　383
13.4　偏序關系　　395
第14章　分層圖　　407
14.1　體驗“分層圖”思想內(nèi)涵　　407
14.2　基于動態(tài)規(guī)劃利用“分層圖”
　　　　　　求解最短路徑問題　　417
14.3　利用“分層圖”思想優(yōu)化算法　　425
第15章　可簡單圖化與圖的計數(shù)　　430
15.1　可簡單圖化　　430
15.2　生成樹計數(shù)　　435
15.3　基于遍歷的圖的計數(shù)　　446
15.4　基于組合分析的圖的計數(shù)　　451
第16章　挖掘和利用圖的性質(zhì)　　460
16.1　挖掘和利用圖的性質(zhì)的方法　　460
16.2　挖掘和利用圖的性質(zhì)的實驗范例460
第三篇小結　　468