信息學(xué)競(jìng)賽寶典 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)

第 1章 鏈表
1.1　何謂鏈表　/　1
1.2　簡(jiǎn)單靜態(tài)鏈表　/　2
1.3　動(dòng)態(tài)鏈表　/　3
1.3.1　鏈表的建立　/　3
1.3.2　鏈表的顯示　/　4
1.3.3　查找節(jié)點(diǎn)元素x的位置　/　4
1.3.4　返回鏈表的長(zhǎng)度　/　4
1.3.5　獲得節(jié)點(diǎn)元素值　/　5
1.3.6　節(jié)點(diǎn)的插入 　/　5
1.3.7 節(jié)點(diǎn)的刪除　/　6
1.3.8　釋放鏈表　/　7
1.4　數(shù)組與鏈表的比較　/　7
1.5　課后練習(xí)　/　8

第 2章 堆棧
2.1　堆棧的定義　/　9
2.2　數(shù)組仿真堆?！?　9
2.3　單調(diào)?！?　12
2.4　后序表達(dá)式　/　16
2.5　課后練習(xí)　/　19

第3章 隊(duì)列
3.1　隊(duì)列的定義　/　21
3.2　數(shù)組仿真隊(duì)列　/　21
3.3　數(shù)組循環(huán)隊(duì)列　/　23
3.4　單調(diào)隊(duì)列　/　29
3.5　課后練習(xí)　/　31

第4章 樹
4.1　樹的介紹　/　32
4.1.1　樹的概念及表示　/　32
4.1.2　樹的相關(guān)術(shù)語(yǔ)　/　33
4.2　二叉樹　/　34
4.2.1　二叉樹的概念　/　34
4.2.2 二叉樹的性質(zhì)　/　35
4.3　二叉樹的表示　/　42
4.3.1　二叉樹數(shù)組表示法　/　42
4.3.2　二叉樹結(jié)構(gòu)體數(shù)組表示法　/　45
4.3.3 二叉樹鏈表表示法　/　48
4.4　二叉樹的遍歷　/　50
4.4.1　二叉樹的前序遍歷　/　50
4.4.2　二叉樹的中序遍歷　/　53
4.4.3　二叉樹的后序遍歷　/　54
4.4.4　二叉樹的圖形化顯示　/　55
4.4.5　已知前序、中序遍歷序列求后序遍歷序列　/　61
4.4.6 已知后序、中序遍歷序列求前序遍歷序列　/　62
4.4.7　已知前序、后序遍歷序列求中序遍歷序列　/　63
4.4.8 表達(dá)式處理　/　66
4.5　最優(yōu)二叉樹及應(yīng)用　/　71
4.5.1　最優(yōu)二叉樹　/　71
4.5.2　哈夫曼編碼　/　72
4.6　一般樹轉(zhuǎn)換成二叉樹　/　74
4.7　堆排序的實(shí)現(xiàn)　/　76
4.8　優(yōu)先隊(duì)列的實(shí)現(xiàn)　/　80
4.9　樹的一些應(yīng)用　/　86
4.9.1　樹的最小支配集　/　86
4.9.2　樹的最小點(diǎn)覆蓋　/　91
4.9.3 樹的最大獨(dú)立集　/　93
4.9.4　樹的直徑　/　95
4.9.5　樹的重心　/　100
4.10　二叉查找樹　/　102

第5章 圖
5.1　圖的介紹 　/　109
5.1.1　圖的基本概念　/　109
5.1.2　鄰接數(shù)組表示法　/　111
5.1.3　加權(quán)邊的圖　/　113
5.2　前向星　/　113
5.2.1　前向星表示法　/　113
5.2.2　前向星的DFS　/　117
5.2.3　前向星的BFS　/　120
5.3　生成樹問題　/　122
5.3.1　Kruskal算法　/　123
5.3.2　Prim算法　/　126
5.4　最短路問題　/　128
5.4.1　Dijkstra算法　/　128
5.4.2　Dijkstra算法的堆優(yōu)化　/　132
5.4.3 Floyd算法　/　133
5.4.4 最小環(huán)問題　/　135
5.4.5　Bellman-Ford算法　/　137
5.4.6　SPFA及優(yōu)化　/　140
5.5　拓?fù)渑判颉?　147
5.5.1　拓?fù)渑判蚪榻B　/　147
5.5.2　關(guān)鍵路徑　/　152
5.6　DAG最長(zhǎng)路　/　157
5.7　邊和頂點(diǎn)的可行遍性　/　159
5.7.1　歐拉圖　/　159
5.7.2　哈密爾頓環(huán)　/　164
5.8　無向圖的一些應(yīng)用　/　171
5.8.1　最大團(tuán)問題　/　171
5.8.2　無向圖的割點(diǎn)和橋　/　175
5.8.3　無向圖的雙連通分量　/　185
5.9 Kosaraju算法　/　191
5.10　樹的一些應(yīng)用　/　194
5.10.1　次小生成樹算法　/　194
5.10.2　基環(huán)樹　/　200
5.10.3　度限制生成樹　/　206
5.10.4　最小樹形圖　/　208

第6章 哈希
6.1　哈?！?　215
6.2　字符串哈?！?　223
6.3　哈希樹　/　228

第7章 樹狀數(shù)組
7.1　樹狀數(shù)組介紹　/　230
7.2　樹狀數(shù)組的簡(jiǎn)單應(yīng)用　/　232
7.3　樹狀數(shù)組的區(qū)間更新　/　236
7.4　樹狀數(shù)組維護(hù)區(qū)間最值　/　239
7.5　樹狀數(shù)組求逆序?qū)Α?　244
7.6　樹狀數(shù)組的應(yīng)用　/　246
7.7　二維樹狀數(shù)組　/　249
7.8　課后練習(xí)　/　253

第8章 并查集
8.1　基礎(chǔ)并查集　/　254
8.2　帶權(quán)并查集　/　259
8.3　種類并查集　/　261
8.4　課后練習(xí)　/　266

第9章 線段樹
9.1　線段樹的基本操作　/　267
9.2　懶惰標(biāo)記的使用　/　282
9.3 線段樹區(qū)間乘與加　/　284
9.4　課后練習(xí)　/　287

第 10章 二分圖
10.1　二分圖的概念及判定　/　288
10.2　二分圖最大匹配問題　/　291
10.3　最小點(diǎn)覆蓋問題　/　297
10.4　最小邊覆蓋問題　/　299
10.5　最小路徑覆蓋問題　/　303
10.6　最佳匹配問題　/　309
10.7　課后練習(xí)　/　314