上篇 討論綫性錶
第1 章 數組　　 3
1.1 數組的基本概念　　 3
1.1.1 數組是一種順序存儲結構　　 3
1.1.2 數組是程序設計中使用頻率最高的數據類型　　 4
1.2 優化數組的存儲方式　　 6
1.2.1 規則矩陣的壓縮存儲　　 6
1.2.2 稀疏矩陣的壓縮存儲　　 7
1.2.3 01 矩陣的壓縮存儲　　11
1.3 排序與順序統計　　 14
1.3.1 排序的基本概念　　 14
1.3.2 計數排序與貪心策略　　 15
1.3.3 采用“二分”策略的排序方法　　 21
1.3.4 順序統計的基本方法　　 28
第2 章 鏈式存儲結構　　 34
2.1 鏈錶的基本概念　　 34
2.1.1 單鏈錶　　 34
2.1.2 循環鏈錶　　 35
2.1.3 雙嚮鏈錶　　 35
2.2 鏈錶的基本運算　　 35
2.2.1 構建單鏈錶　　 36
2.2.2 插入操作　　 36
2.2.3 刪除操作　　 36
2.2.4 讀取操作　　 36
2.3 鏈錶的應用　　 37
第3 章 兩種存取方式特殊的綫性錶　　 43
3.1 “後進先齣”的棧　　 43
3.1.1 棧的基本運算　　43
3.1.2 棧的應用　　44
3.2 “先進先齣”的隊列　　52
3.2.1 隊列的基本運算　　52
3.2.2 隊列的應用　　54
第4 章 散列技術　　59
4.1 散列錶　　59
4.2 散列函數的設計　　59
4.3 消除衝突的基本方法　　61
4.3.1 使用開放尋址法消除衝突　　61
4.3.2 使用分離鏈接法消除衝突　　67
第5 章 後綴數組　　71
5.1 後綴數組的基本概念　　71
5.2 采用倍增算法求解rank 數組　　73
5.3 利用rank 數組計算最長公共前綴　　74
5.3.1 計算最長公共前綴是一個典型的RMQ 問題　　75
5.3.2 計算最長公共前綴的基本方法　　75
5.4 後綴數組的應用　　78
5.4.1 利用後綴數組處理單個字符串　　78
5.4.2 兩個字符串的公共子串問題　　87
5.4.3 多個字符串共享子串的問題　　90
上篇 小結　　97
中篇 討論樹型問題
第6 章 樹的基本概念和遍曆規則　　101
6.1 樹的遞歸定義　　101
6.2 節點的分類　　101
6.3 有關度的定義　　 101
6.4 樹的深度（高度）　　 102
6.5 森林　　 102
6.6 有序樹和無序樹　　 102
6.7 樹的錶示方法　　 103
6.8 樹的遍曆規則　　 103
6.8.1 先根次序遍曆樹　　 103
6.8.2 後根次序遍曆樹　　 104
第7 章 樹的存儲結構　　105
7.1 采用數組存儲入邊信息　　 105
7.1.1 存儲無權樹的入邊信息　　 105
7.1.2 存儲加權樹的入邊信息　　 106
7.2 采用數組存儲所有兒子的地址信息　　 108
7.2.1 采用整數存儲兒子的數組下標　　 108
7.2.2 采用指針存儲兒子的地址　　 109
7.3 采用鄰接錶存儲齣邊信息　　 110
7.3.1 采用數組存儲方式的鄰接錶　　 110
7.3.2 采用單鏈錶存儲方式的鄰接錶　　 114
7.4 無根樹的一般存儲方式　　 116
第8 章 二叉樹　　123
8.1 二叉樹的基本概念和存儲結構　　 123
8.1.1 二叉樹的基本概念　　 123
8.1.2 二叉樹的存儲結構　　 125
8.2 將普通有序樹和森林轉換成對應的二叉樹　　128
8.2.1 將普通有序樹轉換成對應的二叉樹　　 128
8.2.2 將普通有序樹組成的森林轉換成對應的二叉樹　　 129
8.3 二叉樹的遍曆　　 130
8.3.1 前序遍曆　　 130
8.3.2 中序遍曆　　 130
8.3.3 後序遍曆　　 131
8.3.4 由兩種遍曆確定二叉樹結構　　 133
第9 章 並查集　　135
9.1 並查集的基本概念　　 135
9.2 查找元素所在樹的根節點並進行路徑壓縮　　 137
9.3 閤並兩個元素所在的集閤　　138
第10 章 堆　　143
10.1 二叉堆的概念　　 143
10.2 在插入或刪除節點時維護堆性質　　 144
10.2.1 插入節點　　 144
10.2.2 刪除最小值元素　　 144
10.3 建堆　　 145
10.4 堆排序　　 146
第11 章 最優二叉樹　　 154
11.1 最優二叉樹的基本概念　　 154
11.2 構造最優二叉樹　　 155
第12 章 綫段樹　　160
12.1 綫段樹的基本概念　　 160
12.1.1 用於區間運算的綫段樹　　 160
12.1.2 用於數據統計的綫段樹　　 161
12.1.3 綫段樹的數據結構　　 162
12.2 綫段樹的基本操作　　 162
12.2.1 建立綫段樹　　 162
12.2.2 在區間內插入綫段或數據　　 163
12.2.3 刪除區間內的綫段或數據　　 164
12.2.4 計算區間內的綫段或數據狀態　　 165
12.3 綫段樹在靜態統計問題上的應用　　 165
12.4 綫段樹在動態統計問題上的應用　　 168
第13 章 二叉查找樹　　 176
13.1 二叉排序樹　　 176
13.1.1 二叉排序樹的基本概念　　 176
13.1.2 二叉排序樹的基本操作　　 177
13.2 靜態二叉排序樹　　 180
13.2.1 靜態二叉排序樹的特徵　　 180
13.2.2 靜態二叉排序樹的構造方法　　 180
13.2.3 在靜態二叉排序樹上進行數據統計　　　 181
13.3 子樹大小平衡樹（SBT） 　　 186
13.3.1 SBT 的性質　　 186
13.3.2 鏇轉　　 186
13.3.3 動態維護SBT 的平衡特性　　 191
13.3.4 SBT 的基本操作　　 196
中篇 小結　　 205
下篇 討論圖型問題
第14 章 圖的基本概念及其存儲結構　　 209
14.1 圖的基本概念　　 209
14.2 圖的簡單分類　　 211
14.2.1 無嚮圖和有嚮圖　　 212
14.2.2 無權圖和加權圖　　 212
14.2.3 稀疏圖和稠密圖　　 212
14.2.4 完全圖和補圖　　 212
14.2.5 樹和森林　　 213
14.2.6 圖的生成樹和生成森林　　 213
14.2.7 平麵圖　　 214
14.2.8 二分圖　　 214
14.2.9 相交圖和區間圖　　 214
14.3 圖的存儲結構　　 215
14.3.1 存儲節點間相鄰關係的相鄰矩陣　　 215
14.3.2 存儲邊信息的3 種數據結構　　 217
第15 章 圖的遍曆及其應用　　 220
15.1 廣度優先遍曆（BFS 算法） 　　 220
15.1.1 BFS 算法的基本概念　　 220
15.1.2 BFS 算法的應用　　 222
15.2 深度優先遍曆（DFS 算法） 　　 233
15.2.1 DFS 的基本概念　　 233
15.2.2 在DFS 遍曆過程中記錄節點顔色變化的時間　　 239
15.2.3 根據節點顔色對邊進行分類　　 240
15.2.4 分析DFS 森林的結構　　 242
15.2.5 使用DFS 算法進行拓撲排序　　 244
15.2.6 使用DFS 算法計算歐拉迴路　　 248
第16 章 有嚮圖的強連通分量和傳遞閉包　　255
16.1 判定仙人掌圖　　255
16.2 計算強連通分量　　259
16.3 傳遞閉包的應用　　266
第17 章 無嚮圖的連通性分析　　271
17.1 計算節點的low 函數　　271
17.2 計算連通圖的割點和橋　　272
17.2.1 計算連通圖的割點　　272
17.2.2 計算連通圖的橋　　273
17.3 計算雙連通子圖　　275
17.4 分析連通圖的連通程度　　276
17.4.1 連通圖的頂連通度　　277
17.4.2 連通圖的邊連通度　　278
第18 章 最小生成樹　　279
18.1 基本概念　　279
18.2 最小生成樹的應用價值　　279
18.3 最小生成樹的計算策略　　281
18.4 計算最小生成樹的兩種算法　　281
18.4.1 Kruskal 算法　　282
18.4.2 Prim 算法　　283
18.5 最小生成樹算法的應用實例　　285
第19 章 加權圖的單源最短路徑問題　　293
19.1 基本概念　　293
19.1.1 單源算法是高效解決所有最短路徑問題的基礎　　293
19.1.2 負權迴路影響單源最短路徑的計算　　294
19.1.3 鬆弛技術是單源算法的核心　　295
19.2 求解單源最短路徑問題的3 種算法　　296
19.2.1 Dijkstra 算法　　296
19.2.2 Bellman-Ford 算法　　298
19.2.3 SPFA 算法　　299
19.3 單源最短路徑算法的應用實例　　301
第20 章 二分圖的匹配問題　　310
20.1 基本概念　　310
20.1.1 圖的匹配概念　　 310
20.1.2 二分圖的概念和判定方法　　 311
20.2 計算無權二分圖的最大匹配　　 315
20.2.1 匈牙利算法的基本思路　　316
20.2.2 匈牙利算法的基本流程　　316
20.2.3 匈牙利算法的應用實例　　317
20.3 計算帶權二分圖的最佳匹配　　 320
20.3.1 最佳匹配的概念　　 320
20.3.2 KM算法的基本思路　　 321
20.3.3 KM算法的基本流程和應用實例　　 323
第21 章 最大流問題　　327
21.1 基本概念　　 327
21.2 在可增廣路徑的基礎上計算最大流　　 329
21.2.1 可增廣路徑的基本概念　　 329
21.2.2 基於最大流定理上的最大流算法　　 334
21.3 按層次計算最大流的Dinic 算法　　 334
21.3.1 Dinic 算法的基本思路　　 334
21.3.2 Dinic 算法的基本流程　　 335
21.4 利用最大流最小割定理解題　　 339
21.4.1 割的概念　　 339
21.4.2 最小割的計算方法和應用實例　　 340
21.5 計算多源多匯網絡的可行流　　 346
21.6 網絡增加容量下界因素後的流量計算問題　　 348
21.6.1 求容量有上下界的網絡的最大流　　 348
21.6.2 求容量有上下界的網絡的最小流　　 353
21.7 網絡增加費用因素後的流量計算問題　　 358
21.7.1 計算最小費用最大流　　 359
21.7.2 計算容量有上下界的網絡的最小費用最小流　　 364
下篇 小結　　 370
· · · · · · (收起)