算法分析與設(shè)計

第1章 緒論 1
1.1 引論 1
1.2 從問題到程序 3
1.3 抽象數(shù)據(jù)類型 7
1.4 算法的分析 13
1.4.1 算法設(shè)計 13
1.4.2 算法的復(fù)雜性測度 14
1.5 算法描述及語句簡介 16
1.5.1 C中的標(biāo)準(zhǔn)數(shù)據(jù)類型 17
1.5.2 C中的運算符 18
1.5.3 C中的語句簡介 19
小結(jié) 22
練習(xí)一 22
一、填空題 22
二、選擇題 23
三、簡答題 24
第2章 遞歸技術(shù) 25
2.1 遞歸過程 25
2.2 遞歸技術(shù) 26
2.3 遞歸過程的實現(xiàn) 29
2.4 遞歸函數(shù) 29
2.5 遞歸方程 33
2.6 遞歸方程求解 35
2.6.1 迭代法 36
2.6.2 套用差分方程法 37
2.6.3 套用公式法 38
2.6.4 生成函數(shù)與求和 39
2.7 遞歸消除 42
2.7.1 簡單遞歸消除 42
2.7.2 基于棧的遞歸消除 44
小結(jié) 46
練習(xí)二 46
一、填空題 46
二、選擇題 46
三、簡答題 47
第3章 樹 48
3.1 樹的結(jié)構(gòu)定義及基本操作 48
3.2 二叉樹 51
3.2.1 定義及基本操作 51
3.2.2 二叉樹性質(zhì) 52
3.2.3 二叉樹存儲結(jié)構(gòu) 54
3.3 遍歷二叉樹和線索二叉樹 57
3.3.1 遍歷二叉樹 58
3.3.2 線索二叉樹 60
3.4 樹和森林 64
3.4.1 樹的存儲結(jié)構(gòu) 64
3.4.2 樹和森林的遍歷 67
3.4.3 森林與二叉樹的轉(zhuǎn)換 68
3.5 樹的計數(shù) 73
3.6 哈夫曼樹 74
小結(jié) 77
練習(xí)三 78
一、填空題 78
二、選擇題 78
三、簡答題 79
第4章 圖及有向圖的應(yīng)用 81
4.1 基本定義與術(shù)語 81
4.2 圖的存儲結(jié)構(gòu) 84
4.2.1 圖的鄰接矩陣表示法 84
4.2.2 鄰接表表示法 86
4.3 圖的遍歷 88
4.3.1 深度優(yōu)先搜索 89
4.3.2 廣度優(yōu)先搜索 91
4.4 單源最短路徑問題 93
4.5 頂點對之間最短路徑 95
4.6 拓?fù)渑判?97
4.7 關(guān)鍵路徑 101
小結(jié) 104
練習(xí)四 104
一、填空題 104
二、選擇題 105
三、簡答題 106
第5章 無向圖 108
5.1 最小生成樹 108
5.1.1 最小生成樹性質(zhì) 109
5.1.2 Prim算法 109
5.1.3 Kruskal算法 111
5.2 無向圖遍歷 113
5.3 迷宮問題 114
5.4 最短路徑 117
小結(jié) 120
練習(xí)五 120
一、填空題 120
二、選擇題 120
三、簡答題 121
第6章 查找 123
6.1 基本概念 123
6.2 順序表查找 124
6.2.1 順序查找 125
6.2.2 折半查找 126
6.3 分塊查找 128
6.4 樹表 130
6.5 散列表的查找 141
6.5.1 散列表的概念 142
6.5.2 散列函數(shù)的構(gòu)造 142
6.5.3 處理沖突的方法 144
6.5.4 散列表分析 145
小結(jié) 146
練習(xí)六 146
一、填空題 146
二、選擇題 147
三、簡答題 149
第7章 排序 150
7.1 排序的定義 150
7.2 交換排序 151
7.2.1 冒泡法排序 151
7.2.2 快速排序 153
7.3 插入法排序 156
7.3.1 直接插入排序 156
7.3.2 希爾排序 157
7.4 選擇排序 158
7.4.1 簡單選擇排序 158
7.4.2 堆排序 159
7.5 歸并排序 161
7.5.1 排序文件的合并 162
7.5.2 二路歸并排序 162
7.6 基數(shù)排序 163
7.7 各種內(nèi)部排序方法的比較和選擇 165
小結(jié) 166
練習(xí)七 166
一、填空題 166
二、選擇題 167
三、簡答題 168
第8章 集合操作 170
8.1 集合的基本概念 170
8.1.1 集合的概念 170
8.1.2 集合的表示法 170
8.1.3 常見的一些集合 171
8.1.4 集合間的關(guān)系 171
8.1.5 集合例題 171
8.2 集合的基本運算 172
8.2.1 集合的運算 172
8.2.2 文氏圖 173
8.2.3 集合運算律 174
8.2.4 集合論進(jìn)一步研究 175
8.3 鏈表結(jié)構(gòu)與順序搜索 176
8.3.1 鏈表結(jié)構(gòu) 176
8.3.2 鏈表的運算 179
小結(jié) 181
練習(xí)八 181
一、填空題 181
二、選擇題 181
三、簡答題 182
第9章 動態(tài)規(guī)劃 183
9.1 動態(tài)規(guī)劃法的概念 183
9.1.1 動態(tài)規(guī)劃模型的基本要素 184
9.1.2 動態(tài)規(guī)劃的基本定理和基本方程 184
9.1.3 動態(tài)規(guī)劃法的基本步驟 186
9.1.4 動態(tài)規(guī)劃與其他算法的比較 186
9.2 計算二項式系數(shù) 187
9.3 最佳折半查找樹 188
9.3.1 查找樹的期望深度 189
9.3.2 最佳折半查找樹的動態(tài)規(guī)劃算法 190
9.4 資源分配問題 191
9.5 多機系統(tǒng)的可靠性設(shè)計 193
9.6 背包問題 195
9.7 貨郎擔(dān)問題 196
小結(jié) 198
練習(xí)九 198
一、填空題 198
二、選擇題 199
三、簡答題 199
第10章 貪心法 201
10.1 貪心算法 201
10.2 背包問題 202
10.3 多處理機調(diào)度 205
10.4 單源最短路徑 210
10.5 最佳合并順序 212
小結(jié) 213
練習(xí)十 214
一、填空題 214
二、選擇題 214
三、簡答題 214
第11章 回溯法 215
11.1 一般方法 215
11.2 效能統(tǒng)計 218
11.3 哈密爾頓回路 220
11.4 圖的可著色性 223
11.5 子集和問題 224
小結(jié) 225
練習(xí)十一 225
一、填空題 225
二、選擇題 225
三、簡答題 225
第12章 分治與平衡 227
12.1 分治算法 227
12.2 合并排序 230
12.3 快速排序 231
12.4 整數(shù)乘法和矩陣乘法 237
12.4.1 整數(shù)乘法 237
12.4.2 strassen矩陣乘法 239
12.5 馬的周游路線問題 241
小結(jié) 243
練習(xí)十二 244
一、填空題 244
二、選擇題 244
三、簡答題 244
第13章 NP完全問題 245
13.1 確定圖靈機 245
13.2 不確定圖靈機 249
13.3 P和NP類 251
13.4 NP完全性和COOK定理 254
13.5 若干NP完全問題 258
小結(jié) 260
練習(xí)十三 261
一、填空題 261
二、選擇題 261
三、簡答題 261
參考文獻(xiàn) 262