數(shù)據(jù)結(jié)構(gòu)解題策略

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