第1 章 引論 ············································································································································1
1.1 算法及其復(fù)雜性的概念 ··········································································································1
1.1.1 算法與程序 ························································································································1
1.1.2 算法復(fù)雜性的概念 ·············································································································1
1.1.3 算法復(fù)雜性的漸近性態(tài)·······································································································3
1.2 算法的表達(dá)與數(shù)據(jù)表示 ··········································································································5
1.2.1 問題求解 ···························································································································5
1.2.2 表達(dá)算法的抽象機(jī)制 ··········································································································5
1.3 抽象數(shù)據(jù)類型 ··························································································································8
1.3.1 抽象數(shù)據(jù)類型的基本概念 ···································································································8
1.3.2 使用抽象數(shù)據(jù)類型的好處 ···································································································9
1.4 數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類型和抽象數(shù)據(jù)類型 ··············································································· 10
1.5 用C 語言描述數(shù)據(jù)結(jié)構(gòu)與算法 ··························································································· 11
1.5.1 變量和指針 ······················································································································ 11
1.5.2 函數(shù)與參數(shù)傳遞 ·············································································································· 12
1.5.3 結(jié)構(gòu) ······························································································································· 13
1.5.4 動(dòng)態(tài)存儲(chǔ)分配 ················································································································· 14
1.6 遞歸 ········································································································································ 15
1.6.1 遞歸的基本概念 ·············································································································· 15
1.6.2 間接遞歸 ························································································································ 17
本章小結(jié) ········································································································································· 18
習(xí)題1 ·············································································································································· 18
算法實(shí)驗(yàn)題1 ·································································································································· 19
第2 章 表 ············································································································································· 21
2.1 表的基本概念 ······················································································································· 21
2.2 用數(shù)組實(shí)現(xiàn)表 ······················································································································· 22
2.3 用指針實(shí)現(xiàn)表 ······················································································································· 26
2.4 用間接尋址方法實(shí)現(xiàn)表 ······································································································· 30
2.5 用游標(biāo)實(shí)現(xiàn)表 ······················································································································· 32
2.6 循環(huán)鏈表 ································································································································ 37
2.7 雙鏈表 ···································································································································· 39
2.8 表的搜索游標(biāo) ······················································································································· 43
2.8.1 用數(shù)組實(shí)現(xiàn)表的搜索游標(biāo) ································································································ 43
2.8.2 單循環(huán)鏈表的搜索游標(biāo)···································································································· 44
VI
2.9 應(yīng)用舉例 ································································································································ 45
本章小結(jié) ········································································································································· 47
習(xí)題2 ·············································································································································· 47
算法實(shí)驗(yàn)題2 ·································································································································· 49
第3 章 棧 ············································································································································· 52
3.1 棧的基本概念 ······················································································································· 52
3.2 用數(shù)組實(shí)現(xiàn)棧 ······················································································································· 53
3.3 用指針實(shí)現(xiàn)棧 ······················································································································· 55
3.4 應(yīng)用舉例 ································································································································ 57
本章小結(jié) ········································································································································· 60
習(xí)題3 ·············································································································································· 60
算法實(shí)驗(yàn)題3 ·································································································································· 62
第4 章 隊(duì)列 ········································································································································· 64
4.1 隊(duì)列的基本概念 ··················································································································· 64
4.2 用指針實(shí)現(xiàn)隊(duì)列 ··················································································································· 64
4.3 用循環(huán)數(shù)組實(shí)現(xiàn)隊(duì)列 ··········································································································· 67
4.4 應(yīng)用舉例 ································································································································ 70
本章小結(jié) ········································································································································· 74
習(xí)題4 ·············································································································································· 74
算法實(shí)驗(yàn)題4 ·································································································································· 75
第5 章 排序與選擇算法 ····················································································································· 78
5.1 簡(jiǎn)單排序算法 ······················································································································· 78
5.1.1 冒泡排序算法 ················································································································· 79
5.1.2 插入排序算法 ················································································································· 79
5.1.3 選擇排序算法 ················································································································· 80
5.1.4 簡(jiǎn)單排序算法的計(jì)算復(fù)雜性 ····························································································· 80
5.2 快速排序算法 ······················································································································· 81
5.2.1 算法基本思想及實(shí)現(xiàn) ······································································································· 81
5.2.2 算法的性能 ····················································································································· 82
5.2.3 隨機(jī)快速排序算法 ·········································································································· 83
5.2.4 非遞歸快速排序算法 ······································································································· 83
5.2.5 三數(shù)取中劃分算法 ·········································································································· 84
5.2.6 三劃分快速排序算法 ······································································································· 85
5.3 合并排序算法 ······················································································································· 86
5.3.1 算法基本思想及實(shí)現(xiàn) ······································································································· 86
5.3.2 對(duì)基本算法的改進(jìn) ·········································································································· 87
5.3.3 自底向上的合并排序算法 ································································································ 88
5.3.4 自然合并排序算法 ·········································································································· 88
5.3.5 鏈表結(jié)構(gòu)的合并排序算法 ································································································ 89
5.4 線性時(shí)間排序算法 ··············································································································· 90
VII
5.4.1 計(jì)數(shù)排序算法 ················································································································· 90
5.4.2 桶排序算法 ····················································································································· 91
5.4.3 基數(shù)排序算法 ················································································································· 92
5.5 中位數(shù)與第k 小元素 ············································································································ 94
5.5.1 平均情況下的線性時(shí)間選擇算法 ······················································································ 94
5.5.2 最壞情況下的線性時(shí)間選擇算法 ······················································································ 95
5.6 應(yīng)用舉例 ································································································································ 98
本章小結(jié) ······································································································································· 100
習(xí)題5 ············································································································································ 100
算法實(shí)驗(yàn)題5 ································································································································ 101
第6 章 樹 ··········································································································································· 104
6.1 樹的定義 ······························································································································ 104
6.2 樹的遍歷 ······························································································································ 106
6.3 樹的表示法 ·························································································································· 108
6.3.1 父結(jié)點(diǎn)數(shù)組表示法 ········································································································ 108
6.3.2 兒子鏈表表示法 ············································································································ 108
6.3.3 左兒子右兄弟表示法 ····································································································· 108
6.4 二叉樹的基本概念 ············································································································· 109
6.5 二叉樹的運(yùn)算 ······················································································································ 111
6.6 二叉樹的實(shí)現(xiàn) ······················································································································ 112
6.6.1 二叉樹的順序存儲(chǔ)結(jié)構(gòu)··································································································· 112
6.6.2 二叉樹的結(jié)點(diǎn)度表示法··································································································· 113
6.6.3 用指針實(shí)現(xiàn)二叉樹 ········································································································· 113
6.7 線索二叉樹 ··························································································································· 118
6.8 二叉搜索樹 ··························································································································· 119
6.9 線段樹 ·································································································································· 128
6.10 序列樹 ································································································································ 134
6.11 應(yīng)用舉例 ···························································································································· 142
本章小結(jié) ······································································································································· 147
習(xí)題6 ············································································································································ 147
算法實(shí)驗(yàn)題6 ································································································································ 149
第7 章 散列表 ··································································································································· 154
7.1 集合的基本概念 ················································································································· 154
7.1.1 集合的定義和記號(hào) ········································································································ 154
7.1.2 定義在集合上的基本運(yùn)算 ······························································································ 155
7.2 簡(jiǎn)單集合的實(shí)現(xiàn)方法 ········································································································· 156
7.2.1 用位向量實(shí)現(xiàn)集合 ········································································································ 156
7.2.2 用鏈表實(shí)現(xiàn)集合 ············································································································ 158
7.3 散列技術(shù) ······························································································································ 161
7.3.1 符號(hào)表 ·························································································································· 161
VIII
7.3.2 開散列 ·························································································································· 163
7.3.3 閉散列 ·························································································································· 164
7.3.4 散列函數(shù)及其效率 ········································································································ 168
7.3.5 閉散列的重新散列技術(shù)·································································································· 169
7.4 應(yīng)用舉例 ······························································································································ 170
本章小結(jié) ······································································································································· 171
習(xí)題7 ············································································································································ 172
算法實(shí)驗(yàn)題7 ································································································································ 173
第8 章 優(yōu)先隊(duì)列 ······························································································································· 176
8.1 優(yōu)先隊(duì)列的定義 ················································································································· 176
8.2 優(yōu)先隊(duì)列的簡(jiǎn)單實(shí)現(xiàn) ········································································································· 177
8.3 優(yōu)先級(jí)樹和堆 ····················································································································· 177
8.4 用數(shù)組實(shí)現(xiàn)堆 ····················································································································· 179
8.5 可并優(yōu)先隊(duì)列 ····················································································································· 181
8.5.1 左偏樹的定義 ··············································································································· 182
8.5.2 用左偏樹實(shí)現(xiàn)可并優(yōu)先隊(duì)列 ··························································································· 182
8.6 應(yīng)用舉例 ······························································································································ 185
本章小結(jié) ······································································································································· 190
習(xí)題8 ············································································································································ 190
算法實(shí)驗(yàn)題8 ································································································································ 191
第9 章 并查集 ··································································································································· 194
9.1 并查集的定義及其簡(jiǎn)單實(shí)現(xiàn) ····························································································· 194
9.2 用父結(jié)點(diǎn)數(shù)組實(shí)現(xiàn)并查集 ································································································· 195
9.3 應(yīng)用舉例 ······························································································································ 198
本章小結(jié) ······································································································································· 201
習(xí)題9 ············································································································································ 201
算法實(shí)驗(yàn)題9 ································································································································ 202
第10 章 圖 ········································································································································· 205
10.1 圖的基本概念 ··················································································································· 205
10.2 抽象數(shù)據(jù)類型圖 ··············································································································· 208
10.3 圖的表示法 ························································································································ 209
10.3.1 鄰接矩陣表示法 ·········································································································· 209
10.3.2 鄰接表表示法 ·············································································································· 209
10.3.3 緊縮鄰接表表示法 ······································································································· 210
10.4 用鄰接矩陣實(shí)現(xiàn)圖 ············································································································ 211
10.4.1 用鄰接矩陣實(shí)現(xiàn)賦權(quán)有向圖 ·························································································· 211
10.4.2 用鄰接矩陣實(shí)現(xiàn)賦權(quán)無向圖 ························································································· 213
10.4.3 用鄰接矩陣實(shí)現(xiàn)有向圖 ································································································ 213
10.4.4 用鄰接矩陣實(shí)現(xiàn)無向圖 ································································································ 213
10.5 用鄰接表實(shí)現(xiàn)圖 ··············································································································· 214
IX
10.5.1 用鄰接表實(shí)現(xiàn)有向圖 ··································································································· 214
10.5.2 用鄰接表實(shí)現(xiàn)無向圖 ··································································································· 217
10.5.3 用鄰接表實(shí)現(xiàn)賦權(quán)有向圖 ···························································································· 218
10.5.4 用鄰接表實(shí)現(xiàn)賦權(quán)無向圖 ···························································································· 221
10.6 圖的遍歷 ···························································································································· 222
10.6.1 廣度優(yōu)先搜索 ·············································································································· 222
10.6.2 深度優(yōu)先搜索 ·············································································································· 224
10.7 最短路徑 ···························································································································· 225
10.7.1 單源最短路徑 ·············································································································· 225
10.7.2 Bellman-Ford 最短路徑算法 ························································································· 228
10.7.3 所有頂點(diǎn)對(duì)之間的最短路徑 ························································································· 230
10.8 無圈有向圖 ························································································································ 231
10.8.1 拓?fù)渑判?···················································································································· 231
10.8.2 DAG 的最短路徑 ········································································································· 233
10.8.3 DAG 的最長(zhǎng)路徑 ········································································································· 234
10.8.4 DAG 所有頂點(diǎn)對(duì)之間的最短路徑 ················································································ 234
10.9 最小支撐樹 ························································································································ 235
10.9.1 最小支撐樹性質(zhì) ·········································································································· 235
10.9.2 Prim 算法 ···················································································································· 235
10.9.3 Kruskal 算法 ················································································································ 237
10.10 圖匹配 ······························································································································ 239
10.11 應(yīng)用舉例 ·························································································································· 241
本章小結(jié) ······································································································································· 243
習(xí)題10 ·········································································································································· 244
算法實(shí)驗(yàn)題10 ······························································································································ 245
參考文獻(xiàn) ··············································································································································· 250