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

目　　錄
前言
第一篇　線性表的解題策略
第1章　利用快速冪提高冪運(yùn)算效率　　2
1.1　快速冪取模　　　2
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之多重背包問(wèn)題　　　78
第一篇小結(jié)　　83
第二篇　樹(shù)的解題策略
第4章　利用劃分樹(shù)查找有序數(shù)　　86
4.1　離線構(gòu)建整個(gè)查詢區(qū)間的劃分樹(shù)　　87
4.2　在劃分樹(shù)上查找子區(qū)間[l, r]中
　　按序排列的第k個(gè)值　　88
4.3　利用劃分樹(shù)解題　　88
第5章　利用線段樹(shù)解決區(qū)間計(jì)算問(wèn)題　　97
5.1　線段樹(shù)的基本概念和基本操作　　97
5.2　線段樹(shù)動(dòng)態(tài)維護(hù)：?jiǎn)吸c(diǎn)更新　　101
5.3　線段樹(shù)動(dòng)態(tài)維護(hù)：子區(qū)間更新和
　　　　 懶惰標(biāo)記　　106
5.4 　線段樹(shù)動(dòng)態(tài)維護(hù)：子區(qū)間合并　　112
5.5　權(quán)值線段樹(shù)　　120
5.6　主席樹(shù)　　125
第6章　最小生成樹(shù)的拓展　　129
6.1　最小生成樹(shù)的應(yīng)用　　129
6.2　最優(yōu)比率生成樹(shù)　　143
6.3　最小k度限制生成樹(shù)　　148
6.4　次小生成樹(shù)　　154
第7章　利用改進(jìn)型的二叉搜索樹(shù)優(yōu)化
　　　　　　　　 動(dòng)態(tài)集合的操作　　171
7.1　伸展樹(shù)　　171
7.2　紅黑樹(shù)　　198
第8章　利用左偏樹(shù)實(shí)現(xiàn)優(yōu)先隊(duì)列的合并　　212
8.1　左偏樹(shù)的基本概念　　212
8.2　利用左偏樹(shù)解題　　216
第9章　利用動(dòng)態(tài)樹(shù)維護(hù)森林的連通性　　230
9.1　樹(shù)鏈剖分　　230
9.2　動(dòng)態(tài)樹(shù)　　241
第10章　利用跳躍表替代樹(shù)結(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ò)流問(wèn)題　　298
11.2.1　求解無(wú)源匯且容量有上下界
　　　　　　的網(wǎng)絡(luò)可行流問(wèn)題　　　298
11.2.2　求解有源匯且容量有上下界
　　　　　　　 的網(wǎng)絡(luò)最大流問(wèn)題　　　307
11.2.3　求解有源匯且容量有上下界
　　　　　　　 的網(wǎng)絡(luò)最小流問(wèn)題　　　316
11.3　計(jì)算最?。ㄗ畲螅┵M(fèi)用最大流　　321
第12章　二分圖匹配　　329
12.1　匈牙利算法　　329
12.2　穩(wěn)定婚姻問(wèn)題　　344
12.3　KM算法　　350
12.4　利用一一對(duì)應(yīng)的匹配性質(zhì)轉(zhuǎn)化
　　　　　　問(wè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　基于動(dòng)態(tài)規(guī)劃利用“分層圖”
　　　　　　求解最短路徑問(wèn)題　　417
14.3　利用“分層圖”思想優(yōu)化算法　　425
第15章　可簡(jiǎn)單圖化與圖的計(jì)數(shù)　　430
15.1　可簡(jiǎn)單圖化　　430
15.2　生成樹(shù)計(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