C++與數(shù)據(jù)結(jié)構(gòu)（第4版）

目 錄

第1章 數(shù)據(jù)結(jié)構(gòu)的基本概念 1
1.1 數(shù)據(jù)結(jié)構(gòu)的概念和術(shù)語 1
1.2 抽象數(shù)據(jù)類型 3
1.2.1 數(shù)據(jù)類型 3
1.2.2 數(shù)據(jù)抽象與抽象數(shù)據(jù)類型 4
1.3 算法和算法分析 5
1.3.1 算法 5
1.3.2 算法設(shè)計(jì)的要求 5
1.3.3 算法效率的度量 6
1.4 面向?qū)ο蟾攀?8
1.4.1 面向?qū)ο蟮乃枷?9
1.4.2 面向?qū)ο蟪绦蛟O(shè)計(jì) 9
1.4.3 面向?qū)ο蟮恼Z言 9
1.4.4 面向?qū)ο蟮幕靖拍?10
1.4.5 面向?qū)ο蟮幕咎匦?11
1.5 本章小結(jié) 13
習(xí)題1 13
第2章 C 初步知識 14
2.1 C 語言 14
2.2 數(shù)組 14
2.2.1 一維數(shù)組 15
2.2.2 二維數(shù)組 17
2.2.3 字符數(shù)組和字符串 20
2.3 指針 24
2.3.1 指針的概念 24
2.3.2 指針的定義 24
2.3.3 指針的運(yùn)算 25
2.4 指針和數(shù)組 27
2.4.1 指針與數(shù)組名 27
2.4.2 指向數(shù)組的指針 28
2.4.3 存儲指針的數(shù)組 31
2.4.4 動態(tài)存儲 32
2.5 結(jié)構(gòu) 34
2.5.1 結(jié)構(gòu)類型的定義 34
2.5.2 結(jié)構(gòu)變量的說明 35
2.5.3 結(jié)構(gòu)成員的引用 36
2.5.4 結(jié)構(gòu)數(shù)組和結(jié)構(gòu)指針 37
2.6 函數(shù) 39
2.6.1 函數(shù)的聲明、定義和調(diào)用 40
2.6.2 函數(shù)的參數(shù)傳遞 41
2.6.3 帶默認(rèn)參數(shù)的函數(shù) 42
2.6.4 內(nèi)置函數(shù) 43
2.6.5 函數(shù)的重載 44
2.7 本章小結(jié) 45
習(xí)題2 45
實(shí)驗(yàn)訓(xùn)練2 45
第3章 C 類及其對象的封裝性 48
3.1 類的聲明和對象的定義 48
3.1.1 聲明類類型 48
3.1.2 定義對象的方法 50
3.1.3 對象成員的引用 51
3.2 類的成員函數(shù) 52
3.2.1 成員函數(shù)的訪問屬性 52
3.2.2 在類外定義成員函數(shù) 52
3.2.3 內(nèi)置成員函數(shù) 53
3.2.4 成員函數(shù)的存儲方式 54
3.3 構(gòu)造函數(shù)和析構(gòu)函數(shù) 55
3.3.1 對象的初始化 55
3.3.2 構(gòu)造函數(shù)的作用 55
3.3.3 帶參數(shù)的構(gòu)造函數(shù) 57
3.3.4 構(gòu)造函數(shù)的重載 58
3.3.5 拷貝構(gòu)造函數(shù) 58
3.3.6 析構(gòu)函數(shù) 59
3.4 相關(guān)特性 61
3.4.1 引用 61
3.4.2 友元 67
3.4.3 運(yùn)算符重載 70
3.5 本章小結(jié) 77
習(xí)題3 77
實(shí)驗(yàn)訓(xùn)練3 78
第4章 繼承性和多態(tài)性 81
4.1 繼承與派生的概念 81
4.1.1 派生類的聲明與構(gòu)成 81
4.1.2 派生類成員的訪問 83
4.2 派生類的構(gòu)造函數(shù)和析構(gòu)函數(shù) 87
4.2.1 簡單的派生類的構(gòu)造函數(shù) 87
4.2.2 有子對象的派生類的構(gòu)造函數(shù) 88
4.2.3 多級派生時(shí)的構(gòu)造函數(shù) 90
4.2.4 派生類的析構(gòu)函數(shù) 91
4.3 多繼承 92
4.3.1 多繼承的聲明與使用 92
4.3.2 多繼承引起的二義性問題 94
4.3.3 虛基類的概念與使用 96
4.4 多態(tài)性與虛函數(shù) 99
4.4.1 多態(tài)的概念 99
4.4.2 虛函數(shù)的定義與使用 99
4.4.3 虛析構(gòu)函數(shù) 103
4.4.4 純虛函數(shù)與抽象類 104
4.5 本章小結(jié) 107
習(xí)題4 107
實(shí)驗(yàn)訓(xùn)練4 107
第5章 模板與標(biāo)準(zhǔn)模板庫 112
5.1 模板 112
5.1.1 模板的概念 112
5.1.2 函數(shù)模板 112
5.1.3 類模板 117
5.2 標(biāo)準(zhǔn)模板庫 120
5.3 序列式容器 121
5.3.1 vector容器 121
5.3.2 使用迭代器 123
5.3.3 list容器 124
5.4 關(guān)聯(lián)式容器 125
5.4.1 pair類型 126
5.4.2 map容器 127
5.4.3 set容器 128
5.5 本章小結(jié) 130
習(xí)題5 131
實(shí)驗(yàn)訓(xùn)練5 131
第6章 線性表 133
6.1 線性表的定義 133
6.1.1 線性表的邏輯結(jié)構(gòu) 133
6.1.2 線性表的抽象類定義 134
6.2 線性表的順序表示和實(shí)現(xiàn) 135
6.2.1 線性表的順序表示 135
6.2.2 順序表類的定義 135
6.2.3 順序表類的實(shí)現(xiàn) 136
6.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 140
6.3.1 線性表的鏈?zhǔn)奖硎?140
6.3.2 抽象鏈表類的定義 140
6.3.3 抽象鏈表類各成員函數(shù)的實(shí)現(xiàn) 142
6.4 單鏈表 143
6.4.1 單鏈表的定義 143
6.4.2 單鏈表類的定義 144
6.4.3 單鏈表的常用成員函數(shù)的實(shí)現(xiàn) 144
6.4.4 單鏈表舉例——一元多項(xiàng)式加法 147
6.5 循環(huán)鏈表 150
6.5.1 循環(huán)鏈表的定義 150
6.5.2 循環(huán)鏈表類的定義 150
6.5.3 循環(huán)鏈表常用函數(shù)的實(shí)現(xiàn) 151
6.5.4 循環(huán)鏈表舉例——約瑟夫問題 155
6.6 雙向鏈表 155
6.6.1 雙向鏈表的定義 155
6.6.2 雙向鏈表類的定義 156
6.6.3 雙向鏈表的常用成員函數(shù)的實(shí)現(xiàn) 157
6.7 本章小結(jié) 161
習(xí)題6 161
實(shí)驗(yàn)訓(xùn)練6 162
第7章 堆棧、隊(duì)列和遞歸 169
7.1 堆棧的概念及其運(yùn)算 169
7.2 抽象堆棧類的定義 170
7.3 堆棧的定義及其實(shí)現(xiàn) 170
7.3.1 順序棧的定義 170
7.3.2 順序棧類的定義及典型成員函數(shù)
的實(shí)現(xiàn) 171
7.3.3 多棧共享空間問題 174
7.3.4 鏈棧的定義 175
7.3.5 鏈?zhǔn)綏ｎ惖亩x及典型成員函數(shù)
的實(shí)現(xiàn) 176
7.4 堆棧的應(yīng)用舉例 179
7.4.1 數(shù)制轉(zhuǎn)換 179
7.4.2 迷宮問題 180
7.5 隊(duì)列的概念及其運(yùn)算 183
7.6 抽象隊(duì)列類的定義 184
7.7 隊(duì)列的定義及其實(shí)現(xiàn) 184
7.7.1 隊(duì)列的順序存儲結(jié)構(gòu) 184
7.7.2 循環(huán)隊(duì)列的定義 186
7.7.3 順序循環(huán)隊(duì)列類的定義及常用
成員函數(shù)的實(shí)現(xiàn) 187
7.7.4 鏈?zhǔn)疥?duì)列的定義 189
7.7.5 鏈?zhǔn)疥?duì)列類的定義及常用成員
函數(shù)的實(shí)現(xiàn) 190
7.7.6 鏈?zhǔn)疥?duì)列的應(yīng)用舉例 193
7.7.7 優(yōu)先級隊(duì)列的定義 194
7.7.8 優(yōu)先級隊(duì)列類的定義及常用
成員函數(shù)的實(shí)現(xiàn) 194
7.8 遞歸 197
7.8.1 遞歸的概念 197
7.8.2 遞歸的應(yīng)用 198
7.8.3 遞歸在計(jì)算機(jī)中的實(shí)現(xiàn) 199
7.8.4 遞歸問題的非遞歸算法 201
7.9 本章小結(jié) 204
習(xí)題7 204
實(shí)驗(yàn)訓(xùn)練7 205
第8章 樹與二叉樹 212
8.1 樹、二叉樹和森林的基本概念 212
8.1.1 樹 212
8.1.2 二叉樹 213
8.1.3 樹與森林的存儲結(jié)構(gòu) 218
8.2 二叉樹的抽象類和樹的類 222
8.2.1 二叉樹的抽象類 222
8.2.2 樹的類 227
8.3 二叉樹的遍歷和樹的遍歷 233
8.3.1 二叉樹的遍歷 233
8.3.2 樹的遍歷 236
8.4 二叉排序樹 239
8.5 二叉樹的計(jì)數(shù) 244
8.6 哈夫曼樹及其應(yīng)用 244
8.6.1 *二叉樹 244
8.6.2 哈夫曼編碼 246
8.7 本章小結(jié) 247
習(xí)題8 247
實(shí)驗(yàn)訓(xùn)練8 248
第9章 圖 253
9.1 圖的基本概念 253
9.1.1 圖的定義 253
9.1.2 圖的術(shù)語 254
9.1.3 圖的基本操作 256
9.1.4 圖的存儲表示 256
9.2 圖的抽象類 260
9.2.1 圖的鄰接矩陣類 261
9.2.2 圖的鄰接表類 265
9.3 圖的遍歷 271
9.3.1 深度優(yōu)先搜索 272
9.3.2 廣度優(yōu)先搜索 273
9.4 圖的連通性與*小生成樹 274
9.4.1 無向圖的連通分量和生成樹 274
9.4.2 *小生成樹 274
9.4.3 關(guān)節(jié)點(diǎn)和重連通分量 279
9.5 *短路徑 281
9.5.1 圖結(jié)點(diǎn)的可達(dá)性 281
9.5.2 從某個(gè)源點(diǎn)到其余各頂點(diǎn)的
*短路徑 282
9.5.3 每一對頂點(diǎn)之間的*短路徑 284
9.6 活動網(wǎng)絡(luò) 286
9.6.1 AOV網(wǎng)絡(luò) 286
9.6.2 AOE網(wǎng)絡(luò) 287
9.7 本章小結(jié) 288
習(xí)題9 289
實(shí)驗(yàn)訓(xùn)練9 290
第10章 查找與散列結(jié)構(gòu) 300
10.1 基本概念 300
10.2 靜態(tài)查找表 301
10.2.1 順序表的查找 301
10.2.2 有序表的查找 303
10.2.3 索引順序表的查找 305
10.3 動態(tài)查找表 306
10.4 Hash表及其查找 307
10.4.1 Hash表 307
10.4.2 Hash函數(shù)的構(gòu)造方法 309
10.4.3 處理沖突的方法 312
10.4.4 Hash表的查找及其分析 313
10.5 本章小結(jié) 315
習(xí)題10 315
實(shí)驗(yàn)訓(xùn)練10 316
第11章 排序 324
11.1 排序的基本概念 324
11.2 插入排序 326
11.2.1 直接插入排序 326

11.2.2 其他插入排序 327
11.2.3 希爾排序 330
11.3 快速排序 331
11.4 選擇排序 334
11.4.1 簡單選擇排序 334
11.4.2 錦標(biāo)賽排序 335
11.4.3 堆排序 338
11.5 歸并排序 343
11.5.1 歸并 343
11.5.2 迭代的歸并排序算法 344
11.6 基數(shù)排序 346
11.6.1 多關(guān)鍵字排序 346
11.6.2 鏈?zhǔn)交鶖?shù)排序 346
11.7 本章小結(jié) 348
習(xí)題11 349
實(shí)驗(yàn)訓(xùn)練11 349
參考文獻(xiàn) 354