目錄
叢書(shū)序
前言
第1章 緒論 1
1.1 引例 1
1.2 基本概念 3
1.2.1 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)和數(shù)據(jù)對(duì)象 3
1.2.2 數(shù)據(jù)結(jié)構(gòu) 4
1.2.3 數(shù)據(jù)類(lèi)型和抽象數(shù)據(jù)類(lèi)型 6
1.3 算法和算法分析 9
1.3.1 算法的定義及算法描述 9
1.3.2 算法評(píng)價(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++語(yǔ)言知識(shí) 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 動(dòng)態(tài)申請(qǐng)與釋放內(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ù)類(lèi)型定義 49
3.3 線性表的順序表示和實(shí)現(xiàn) 50
3.3.1 線性表的順序存儲(chǔ)表示 50
3.3.2 順序表基本運(yùn)算的實(shí)現(xiàn) 51
3.4 引例中讀書(shū)興趣小組活動(dòng)管理的順序表解決 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 引例中讀書(shū)興趣小組活動(dòng)管理的鏈表解決 71
3.7 鏈表知識(shí)的擴(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)問(wè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ù)模擬問(wèn)題的解決 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ù)類(lèi)型定義 125
5.3 串的順序表示和實(shí)現(xiàn) 126
5.3.1 串的順序存儲(chǔ)表示 126
5.3.2 順序串基本運(yùn)算的實(shí)現(xiàn) 127
5.4 串的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 129
5.4.1 串的鏈?zhǔn)酱鎯?chǔ)表示 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 名和姓對(duì)換問(wèn)題的解決 138
5.6.2 文本文件中單詞計(jì)數(shù)和查找問(wèn)題的解決 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ù)組的順序存儲(chǔ)表示 145
6.2.3 引例中求矩陣馬鞍點(diǎn)問(wèn)題的解決 146
6.3 特殊矩陣的壓縮存儲(chǔ) 147
6.3.1 對(duì)稱(chēng)矩陣 147
6.3.2 引例中求對(duì)稱(chēng)矩陣的和與乘積問(wèn)題的解決 148
6.3.3 三角矩陣 150
6.3.4 引例中求三角矩陣的和與乘積問(wèn)題的解決 151
6.3.5 對(duì)角矩陣 152
6.4 廣義表 153
6.4.1 廣義表的概念及運(yùn)算 153
6.4.2 廣義表的存儲(chǔ)結(jié)構(gòu) 155
6.4.3 引例中m元多項(xiàng)式表示問(wèn)題的解決 157
小結(jié) 158
習(xí)題 158
上機(jī)實(shí)驗(yàn)題 160
第7章 樹(shù)和二叉樹(shù) 161
7.1 引例 161
7.2 樹(shù)的概念及運(yùn)算 162
7.2.1 樹(shù)的定義 162
7.2.2 樹(shù)的抽象數(shù)據(jù)類(lèi)型定義 164
7.3 二叉樹(shù) 165
7.3.1 二叉樹(shù)的概念及運(yùn)算 165
7.3.2 二叉樹(shù)的性質(zhì) 167
7.3.3 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 169
7.4 遍歷二叉樹(shù) 172
7.4.1 遍歷二叉樹(shù)的概念和實(shí)現(xiàn) 172
7.4.2 根據(jù)遍歷序列確定二叉樹(shù) 178
7.4.3 遍歷算法應(yīng)用 179
7.5 線索二叉樹(shù) 182
7.5.1 線索二叉樹(shù)的概念 182
7.5.2 線索二叉樹(shù)的構(gòu)造和遍歷 184
7.6 樹(shù)和森林 186
7.6.1 樹(shù)的存儲(chǔ)結(jié)構(gòu) 186
7.6.2 樹(shù)、森林與二叉樹(shù)的相互轉(zhuǎn)換 189
7.6.3 樹(shù)與森林的遍歷 191
7.7 引例的解決 193
7.7.1 哈夫曼樹(shù)用于編碼的原理和方法 193
7.7.2 引例中字符編碼和譯碼問(wèn)題的解決 196
7.7.3 引例中報(bào)文編碼和譯碼問(wèn)題的解決 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ù)語(yǔ) 211
8.2.3 圖的抽象數(shù)據(jù)類(lèi)型定義 215
8.3 圖的存儲(chǔ)結(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 最小生成樹(shù) 231
8.5.1 最小生成樹(shù)和通信網(wǎng)絡(luò)建立 231
8.5.2 普里姆算法 231
8.5.3 克魯斯卡爾算法 236
8.5.4 引例中通信網(wǎng)絡(luò)建立問(wèn)題的解決 240
8.6 最短路徑 241
8.6.1 兩類(lèi)最短路徑問(wèn)題及應(yīng)用 241
8.6.2 迪杰斯特拉算法 242
8.6.3 引例中按距離、飛行時(shí)間、票價(jià)查詢最優(yōu)航線的解決 246
8.6.4 弗洛伊德算法 248
8.6.5 引例中醫(yī)院選址問(wèn)題的解決 253
8.7 拓?fù)渑判?254
8.7.1 拓?fù)渑判蚝驼n程計(jì)劃制定 254
8.7.2 拓?fù)渑判蛩惴?255
8.7.3 引例中課程計(jì)劃制定問(wèn)題的解決 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ì)算問(wèn)題的解決 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 樹(shù)表的查找 282
9.4.1 二叉排序樹(shù) 283
9.4.2 平衡二叉樹(shù) 292
9.4.3 B-樹(shù) 296
9.4.4 B+樹(shù) 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)問(wèn)題的解決 312
9.6.2 火車(chē)票信息查詢中查找相關(guān)問(wèn)題的解決 314
9.6.3 學(xué)生課程成績(jī)管理中查找相關(guān)問(wè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 簡(jiǎn)單選擇排序 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)問(wèn)題的解決 354
10.9.2 火車(chē)票信息查詢中排序相關(guān)問(wèn)題的解決 355
10.9.3 學(xué)生課程成績(jī)管理中排序相關(guān)問(wèn)題的解決 357
小結(jié) 360
習(xí)題 360
上機(jī)實(shí)驗(yàn)題 363
參考文獻(xiàn) 364
索引 365