目錄
叢書序
前言
第1章 緒論 1
1.1 引例 1
1.2 基本概念 3
1.2.1 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)和數(shù)據(jù)對象 3
1.2.2 數(shù)據(jù)結(jié)構(gòu) 4
1.2.3 數(shù)據(jù)類型和抽象數(shù)據(jù)類型 6
1.3 算法和算法分析 9
1.3.1 算法的定義及算法描述 9
1.3.2 算法評價(jià) 10
1.3.3 算法的時(shí)間復(fù)雜度 12
1.3.4 算法的空間復(fù)雜度 16
小結(jié) 17
習(xí)題 18
上機(jī)實(shí)驗(yàn)題 20
第2章 C/C++語言知識 21
2.1 指針 21
2.1.1 指針變量 21
2.1.2 指針運(yùn)算 22
2.1.3 數(shù)組與指針 27
2.2 結(jié)構(gòu)體 31
2.2.1 結(jié)構(gòu)體的定義 31
2.2.2 結(jié)構(gòu)體數(shù)組 33
2.2.3 結(jié)構(gòu)體指針 34
2.3 共用體 37
2.4 C++運(yùn)算符 39
2.4.1 動態(tài)申請與釋放內(nèi)存運(yùn)算符 39
2.4.2 引用 41
2.5 C程序分析 42
小結(jié) 44
習(xí)題 44
上機(jī)實(shí)驗(yàn)題 47
第3章 線性表 48
3.1 引例 48
3.2 線性表的概念及運(yùn)算 49
3.2.1 線性表的定義 49
3.2.2 線性表的抽象數(shù)據(jù)類型定義 49
3.3 線性表的順序表示和實(shí)現(xiàn) 50
3.3.1 線性表的順序存儲表示 50
3.3.2 順序表基本運(yùn)算的實(shí)現(xiàn) 51
3.4 引例中讀書興趣小組活動管理的順序表解決 56
3.5 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 61
3.5.1 單鏈表的定義和表示 62
3.5.2 單鏈表基本運(yùn)算的實(shí)現(xiàn) 62
3.5.3 順序表和鏈表的比較 70
3.6 引例中讀書興趣小組活動管理的鏈表解決 71
3.7 鏈表知識的擴(kuò)展 76
3.7.1 單循環(huán)鏈表 76
3.7.2 雙向鏈表 77
3.8 線性表應(yīng)用舉例 78
小結(jié) 85
習(xí)題 86
上機(jī)實(shí)驗(yàn)題 89
第4章 棧和隊(duì)列 90
4.1 引例 90
4.2 棧 92
4.2.1 棧的概念及運(yùn)算 92
4.2.2 棧的順序表示和實(shí)現(xiàn) 93
4.2.3 棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 95
4.3 引例中棧相關(guān)問題的解決 98
4.3.1 行編輯的解決 98
4.3.2 數(shù)制轉(zhuǎn)換的解決 99
4.3.3 表達(dá)式求值的解決 100
4.3.4 遞歸實(shí)現(xiàn)的解決 107
4.4 隊(duì)列 109
4.4.1 隊(duì)列的概念及運(yùn)算 109
4.4.2 隊(duì)列的順序表示和實(shí)現(xiàn) 111
4.4.3 隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 114
4.4.4 引例中銀行個(gè)人業(yè)務(wù)模擬問題的解決 117
小結(jié) 119
習(xí)題 120
上機(jī)實(shí)驗(yàn)題 123
第5章 串 124
5.1 引例 124
5.2 串的概念及運(yùn)算 124
5.2.1 串的定義 124
5.2.2 串的抽象數(shù)據(jù)類型定義 125
5.3 串的順序表示和實(shí)現(xiàn) 126
5.3.1 串的順序存儲表示 126
5.3.2 順序串基本運(yùn)算的實(shí)現(xiàn) 127
5.4 串的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 129
5.4.1 串的鏈?zhǔn)酱鎯Ρ硎?129
5.4.2 鏈串基本運(yùn)算的實(shí)現(xiàn) 130
5.5 串的模式匹配 132
5.5.1 Brute-Force算法 132
5.5.2 KMP算法 134
5.6 引例的解決 138
5.6.1 名和姓對換問題的解決 138
5.6.2 文本文件中單詞計(jì)數(shù)和查找問題的解決 139
小結(jié) 140
習(xí)題 140
上機(jī)實(shí)驗(yàn)題 142
第6章 數(shù)組和廣義表 143
6.1 引例 143
6.2 數(shù)組 144
6.2.1 數(shù)組的概念及運(yùn)算 144
6.2.2 數(shù)組的順序存儲表示 145
6.2.3 引例中求矩陣馬鞍點(diǎn)問題的解決 146
6.3 特殊矩陣的壓縮存儲 147
6.3.1 對稱矩陣 147
6.3.2 引例中求對稱矩陣的和與乘積問題的解決 148
6.3.3 三角矩陣 150
6.3.4 引例中求三角矩陣的和與乘積問題的解決 151
6.3.5 對角矩陣 152
6.4 廣義表 153
6.4.1 廣義表的概念及運(yùn)算 153
6.4.2 廣義表的存儲結(jié)構(gòu) 155
6.4.3 引例中m元多項(xiàng)式表示問題的解決 157
小結(jié) 158
習(xí)題 158
上機(jī)實(shí)驗(yàn)題 160
第7章 樹和二叉樹 161
7.1 引例 161
7.2 樹的概念及運(yùn)算 162
7.2.1 樹的定義 162
7.2.2 樹的抽象數(shù)據(jù)類型定義 164
7.3 二叉樹 165
7.3.1 二叉樹的概念及運(yùn)算 165
7.3.2 二叉樹的性質(zhì) 167
7.3.3 二叉樹的存儲結(jié)構(gòu) 169
7.4 遍歷二叉樹 172
7.4.1 遍歷二叉樹的概念和實(shí)現(xiàn) 172
7.4.2 根據(jù)遍歷序列確定二叉樹 178
7.4.3 遍歷算法應(yīng)用 179
7.5 線索二叉樹 182
7.5.1 線索二叉樹的概念 182
7.5.2 線索二叉樹的構(gòu)造和遍歷 184
7.6 樹和森林 186
7.6.1 樹的存儲結(jié)構(gòu) 186
7.6.2 樹、森林與二叉樹的相互轉(zhuǎn)換 189
7.6.3 樹與森林的遍歷 191
7.7 引例的解決 193
7.7.1 哈夫曼樹用于編碼的原理和方法 193
7.7.2 引例中字符編碼和譯碼問題的解決 196
7.7.3 引例中報(bào)文編碼和譯碼問題的解決 202？
小結(jié) 202
習(xí)題 203
上機(jī)實(shí)驗(yàn)題 206
第8章 圖 207
8.1 引例 207
8.2 圖的概念及運(yùn)算 210
8.2.1 圖的定義 210
8.2.2 圖的術(shù)語 211
8.2.3 圖的抽象數(shù)據(jù)類型定義 215
8.3 圖的存儲結(jié)構(gòu) 216
8.3.1 鄰接矩陣法 216
8.3.2 鄰接表法 219
8.4 圖的遍歷 222
8.4.1 圖的深度優(yōu)先遍歷 222
8.4.2 圖的廣度優(yōu)先遍歷 225
8.4.3 引例中按中轉(zhuǎn)次數(shù)查詢最優(yōu)航線的解決 228
8.5 最小生成樹 231
8.5.1 最小生成樹和通信網(wǎng)絡(luò)建立 231
8.5.2 普里姆算法 231
8.5.3 克魯斯卡爾算法 236
8.5.4 引例中通信網(wǎng)絡(luò)建立問題的解決 240
8.6 最短路徑 241
8.6.1 兩類最短路徑問題及應(yīng)用 241
8.6.2 迪杰斯特拉算法 242
8.6.3 引例中按距離、飛行時(shí)間、票價(jià)查詢最優(yōu)航線的解決 246
8.6.4 弗洛伊德算法 248
8.6.5 引例中醫(yī)院選址問題的解決 253
8.7 拓?fù)渑判?254
8.7.1 拓?fù)渑判蚝驼n程計(jì)劃制定 254
8.7.2 拓?fù)渑判蛩惴?255
8.7.3 引例中課程計(jì)劃制定問題的解決 258
8.8 關(guān)鍵路徑 260
8.8.1 AOE 網(wǎng)和關(guān)鍵路徑 260
8.8.2 關(guān)鍵路徑算法 261
8.8.3 引例中工程工期計(jì)算問題的解決 268
小結(jié) 270
習(xí)題 270
上機(jī)實(shí)驗(yàn)題 273
第9章 查找 274
9.1 引例 274
9.2 查找的基本概念 277
9.3 線性表的查找 278
9.3.1 順序查找 278
9.3.2 折半查找 279
9.4 樹表的查找 282
9.4.1 二叉排序樹 283
9.4.2 平衡二叉樹 292
9.4.3 B-樹 296
9.4.4 B+樹 303
9.5 散列表 304
9.5.1 散列表的基本概念 304
9.5.2 散列函數(shù)的構(gòu)造方法 305
9.5.3 處理沖突的方法 307
9.5.4 散列表的查找及其分析 308
9.6 引例的解決 312
9.6.1 手機(jī)選擇中查找相關(guān)問題的解決 312
9.6.2 火車票信息查詢中查找相關(guān)問題的解決 314
9.6.3 學(xué)生課程成績管理中查找相關(guān)問題的解決 316
9.6.4 手機(jī)通訊錄的解決 320
小結(jié) 321
習(xí)題 322
上機(jī)實(shí)驗(yàn)題 325
第10章 內(nèi)部排序 326
10.1 引例 326
10.2 排序的基本概念 327
10.3 插入排序 328
10.3.1 直接插入排序 328
10.3.2 折半插入排序 329
10.3.3 希爾排序 330
10.4 交換排序 332
10.4.1 冒泡排序 332
10.4.2 快速排序 334
10.5 選擇排序 337
10.5.1 簡單選擇排序 337
10.5.2 堆排序 338
10.6 歸并排序 343
10.7 基數(shù)排序 345
10.7.1 多關(guān)鍵字排序 345
10.7.2 基數(shù)排序 346
10.8 內(nèi)部排序方法的比較討論 353
10.9 引例的解決 354
10.9.1 手機(jī)選擇中排序相關(guān)問題的解決 354
10.9.2 火車票信息查詢中排序相關(guān)問題的解決 355
10.9.3 學(xué)生課程成績管理中排序相關(guān)問題的解決 357
小結(jié) 360
習(xí)題 360
上機(jī)實(shí)驗(yàn)題 363
參考文獻(xiàn) 364
索引 365