動手學(xué)數(shù)據(jù)結(jié)構(gòu)與算法

第 1章　緒論 1
11　問題引入 1
12　什么是數(shù)據(jù)結(jié)構(gòu) 3
121　數(shù)據(jù)的邏輯結(jié)構(gòu) 3
122　數(shù)據(jù)的存儲結(jié)構(gòu) 4
123　數(shù)據(jù)的操作 5
13　算法分析 5
131　算法的基本概念 5
132　時間復(fù)雜度 6
133　空間復(fù)雜度 11
14　算法優(yōu)化 11
141　時間復(fù)雜度為O(n3)的算法11
142　時間復(fù)雜度為O(n2)的算法 12
143　時間復(fù)雜度為O(nlogn)的算法 13
144　時間復(fù)雜度為O(n)的算法 15
15　大型應(yīng)用實現(xiàn)：火車票管理系統(tǒng)總覽 16
16　小結(jié) 17
17　習(xí)題 18
第 2章　線性表 19
21　問題引入 19
22　線性表的定義 20
23　線性表的實現(xiàn) 20
231　線性表的順序?qū)崿F(xiàn) 20
232　線性表的鏈接實現(xiàn) 23
24　線性表的簡單應(yīng)用 27
241　大整數(shù)處理 27
242　多項式求和 32
25　大型應(yīng)用實現(xiàn)：列車運行計劃管理類 34
26　小結(jié) 36
27　習(xí)題 37
第3章　隊列與棧 38
31　問題引入 38
32　隊列 38
321　隊列的定義 39
322　隊列的順序?qū)崿F(xiàn) 39
323　隊列的鏈接實現(xiàn) 44
324　隊列的簡單應(yīng)用：排隊洗衣 45
33　棧 47
331　棧的定義 47
332　棧的順序?qū)崿F(xiàn) 48
333　棧的鏈接實現(xiàn) 50
334　棧的簡單應(yīng)用：括號匹配 52
34　大型應(yīng)用實現(xiàn)：排隊交易類 53
35　小結(jié) 55
36　習(xí)題 55
第4章　樹與優(yōu)先級隊列 57
41　問題引入 57
42　樹的定義 57
43　二叉樹 59
431　二叉樹的定義 59
432　二叉樹的順序?qū)崿F(xiàn) 63
433　二叉樹的鏈接實現(xiàn) 63
434　 二叉樹的簡單應(yīng)用：哈夫曼編碼
和哈夫曼樹 69
44　優(yōu)先級隊列 74
441　優(yōu)先級隊列的定義 74
442　優(yōu)先級隊列的實現(xiàn) 74
443　 優(yōu)先級隊列的簡單應(yīng)用：
任務(wù)調(diào)度 81
45　大型應(yīng)用實現(xiàn)：帶優(yōu)先級的排隊
交易類 82
46　小結(jié) 83
47　習(xí)題 83
第5章　集合與靜態(tài)查找表 85
51　問題引入 85
52　集合的定義 85
53　靜態(tài)查找表 86
531　無序查找的實現(xiàn) 86
532　有序查找的實現(xiàn) 87
54　集合的簡單應(yīng)用：并查集 89
55　大型應(yīng)用實現(xiàn)：列車運行圖類（1） 92
56　小結(jié) 94
57　習(xí)題 94
第6章　動態(tài)查找表 96
61　問題引入 96
62　動態(tài)查找表的定義 96
63　二叉查找樹 97
631　二叉查找樹的定義 97
632　二叉查找樹的實現(xiàn) 97
64　AVL樹102
641　AVL樹的定義 102
642　AVL樹的實現(xiàn) 104
65　紅黑樹 112
651　紅黑樹的定義 112
652　紅黑樹的實現(xiàn) 114
66　哈希表 123
661　哈希表的定義 124
662　哈希表的實現(xiàn) 124
67　大型應(yīng)用實現(xiàn)：旅客管理類129
68　小結(jié) 131
69　習(xí)題 132
第7章　排序 134
71　問題引入 134
72　排序的定義 134
73　插入排序 135
731　直接插入排序 135
732　二分插入排序 136
733　希爾排序 136
74　選擇排序 138
741　直接選擇排序 138
742　堆排序 139
75　交換排序 141
751　冒泡排序 141
752　快速排序 142
76　歸并排序 144
77　基數(shù)排序 145
78　小結(jié) 147
79　習(xí)題 148
第8章　外部查找與排序 150
81　問題引入 150
82　外部查找表的定義 150
83　B樹 151
831　B樹的定義 151
832　B樹的實現(xiàn) 152
84　B 樹 155
841　B 樹的定義 155
842　B 樹的實現(xiàn) 158
85　外排序 174
851　外排序的定義 174
852　外排序的實現(xiàn) 174
86　大型應(yīng)用實現(xiàn)：余票管理類與行程
管理類 177
87　小結(jié) 183
88　習(xí)題 183
第9章　圖 185
91　問題引入 185
92　圖的定義 185
93　圖的實現(xiàn) 188
931　鄰接矩陣 188
932　鄰接表 191
94　圖的遍歷 194
941　深度優(yōu)先搜索（DFS） 194
942　廣度優(yōu)先搜索（BFS） 196
95　圖的遍歷的簡單應(yīng)用 197
951　圖的連通性 197
952　歐拉回路 198
953　拓?fù)渑判?202
954　關(guān)鍵路徑 204
96　大型應(yīng)用實現(xiàn)：列車運行圖類（2） 206
97　小結(jié) 209
98　習(xí)題 209
第 10章　最小生成樹與最短路徑 211
101　問題引入 211
102　最小生成樹 211
1021　最小生成樹的定義 211
1022　克魯斯卡爾算法 212
1023　普里姆算法 214
103　單源最短路徑 217
1031　非加權(quán)圖的單源最短路徑 217
1032　加權(quán)圖的單源最短路徑 219
1033　 帶有負(fù)權(quán)值圖的單源最短
路徑 221
1034　無環(huán)圖的單源最短路徑 222
104　所有頂點對的最短路徑 223
105　大型應(yīng)用實現(xiàn)：列車運行圖類（3） 224
106　小結(jié) 226
107　習(xí)題 226
第 11章　算法設(shè)計思想 228
111　枚舉法 228
112　貪婪算法 229
113　分治法 230
114　回溯法 233
115　動態(tài)規(guī)劃 235
116　隨機算法 237
117　算法綜合分析：外賣配送任務(wù) 238
118　小結(jié) 240
119　習(xí)題 240
附錄A　書中部分命題的證明 242
A1　證明二叉樹的性質(zhì) 242
A2　 證明兩種遍歷方法是否能夠唯一確定
一棵二叉樹 244
A3　證明AVL樹的高度是對數(shù)級別的 245
A4　 證明AVL樹插入后至多只需要調(diào)整一個
結(jié)點即可恢復(fù)平衡 246
A5　 證明快速排序的平均時間復(fù)雜度為
O(nlogn) 246
A6　 證明歸并排序的時間復(fù)雜度為
O(nlogn) 247
附錄B　電子資源與運行環(huán)境配置 248
B1　動手練平臺 248
B2　電子資料倉庫 248
B3　本地環(huán)境搭建和倉庫代碼運行 249
B31　Linux環(huán)境 249
B32　Windows環(huán)境 255
B33　macOS環(huán)境 260