零基礎(chǔ)學(xué)數(shù)據(jù)結(jié)構(gòu)（第2版）

目　　錄  　　
前言
第一篇  基礎(chǔ)知識(shí)
第1章  數(shù)據(jù)結(jié)構(gòu)概述 1
1.1  為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 1
1.2  基本概念和術(shù)語 2
1.3  數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu) 4
1.3.1  邏輯結(jié)構(gòu) 4
1.3.2  存儲(chǔ)結(jié)構(gòu) 4
1.4  抽象數(shù)據(jù)類型及其描述 5
1.4.1  什么是抽象數(shù)據(jù)類型 5
1.4.2  抽象數(shù)據(jù)類型的描述 6
1.5  算法 8
1.5.1  數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系 8
1.5.2  什么是算法 8
1.5.3  算法的五大特性 9
1.5.4  算法的描述 9
1.6  算法分析 10
1.6.1  算法設(shè)計(jì)的4個(gè)目標(biāo) 11
1.6.2  算法效率評(píng)價(jià) 11
1.6.3  算法的時(shí)間復(fù)雜度 12
1.6.4  算法的空間復(fù)雜度 14
1.7  學(xué)好數(shù)據(jù)結(jié)構(gòu)的秘訣 14
1.8  習(xí)題 15
第2章  C語言基礎(chǔ) 17
2.1  C語言開發(fā)環(huán)境 17
2.1.1  Turbo C 2.0開發(fā)環(huán)境 17
2.1.2  Visual C++ 6.0開發(fā)環(huán)境 19
2.2  遞歸與非遞歸 22
2.2.1  函數(shù)的遞歸調(diào)用 22
2.2.2  遞歸應(yīng)用舉例 23
2.2.3  迭代與遞歸 26
2.3  指針 27
2.3.1  什么是指針 27
2.3.2  指針變量的間接引用 28
2.3.3  指針與數(shù)組 29
2.3.4  指針函數(shù)與函數(shù)指針 34
2.4  參數(shù)傳遞 40
2.4.1  傳值調(diào)用 40
2.4.2  傳地址調(diào)用 42
2.5  結(jié)構(gòu)體與聯(lián)合體 44
2.5.1  結(jié)構(gòu)體的定義 45
2.5.2  指向結(jié)構(gòu)體的指針 47
2.5.3  用typedef定義數(shù)據(jù)類型 48
2.5.4  聯(lián)合體 49
2.6  鏈表 54
2.6.1  內(nèi)存的動(dòng)態(tài)分配與釋放 54
2.6.2  什么是鏈表 55
2.6.3  創(chuàng)建鏈表 55
2.6.4  鏈表的輸出操作 58
2.6.5  鏈表的插入操作 60
2.6.6  鏈表的刪除操作 64
2.6.7  鏈表的綜合操作 66
2.6.8  鏈表應(yīng)用舉例：一元多項(xiàng)式的相加 67
2.7  小結(jié) 73
2.8  習(xí)題 74
第二篇  線性數(shù)據(jù)結(jié)構(gòu)
第3章  線性表 77
3.1  線性表的定義及抽象數(shù)據(jù)類型 77
3.1.1  線性表的邏輯結(jié)構(gòu) 77
3.1.2  線性表的抽象數(shù)據(jù)類型 78
3.2  線性表的順序表示與實(shí)現(xiàn) 79
3.2.1  線性表的順序存儲(chǔ)結(jié)構(gòu) 79
3.2.2  順序表的基本運(yùn)算 80
3.2.3  順序表的實(shí)現(xiàn)算法分析 83
3.2.4  順序表的優(yōu)缺點(diǎn) 83
3.2.5  順序表應(yīng)用舉例 84
3.3  線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 89
3.3.1  單鏈表的存儲(chǔ)結(jié)構(gòu) 90
3.3.2  單鏈表上的基本運(yùn)算 91
3.3.3  單鏈表存儲(chǔ)結(jié)構(gòu)與順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn) 96
3.3.4  單鏈表應(yīng)用舉例 97
3.4  循環(huán)單鏈表 104
3.4.1  循環(huán)鏈表的鏈?zhǔn)酱鎯?chǔ) 104
3.4.2  循環(huán)單鏈表應(yīng)用舉例 106
3.5  雙向鏈表 108
3.5.1  雙向鏈表的存儲(chǔ)結(jié)構(gòu) 108
3.5.2  雙向鏈表的插入和刪除操作 109
3.5.3  雙向鏈表應(yīng)用舉例 111
3.6  靜態(tài)鏈表 113
3.6.1  靜態(tài)鏈表的存儲(chǔ)結(jié)構(gòu) 114
3.6.2  靜態(tài)鏈表的基本運(yùn)算 114
3.6.3  靜態(tài)鏈表應(yīng)用舉例 117
3.7  綜合案例：一元多項(xiàng)式的表示與相乘 118
3.7.1  一元多項(xiàng)式的表示 118
3.7.2  一元多項(xiàng)式相乘 119
3.8  小結(jié) 123
3.9  習(xí)題 123
第4章  棧 127
4.1  棧的定義與抽象數(shù)據(jù)類型 127
4.1.1  什么是棧 127
4.1.2  棧的抽象數(shù)據(jù)類型 128
4.2  棧的順序表示與實(shí)現(xiàn) 128
4.2.1  棧的順序存儲(chǔ)結(jié)構(gòu) 128
4.2.2  順序棧的基本運(yùn)算 129
4.2.3  順序棧應(yīng)用舉例 131
4.3  棧的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 136
4.3.1  棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 137
4.3.2  鏈棧的基本運(yùn)算 137
4.3.3  鏈棧應(yīng)用舉例 140
4.4  棧的典型應(yīng)用 141
4.4.1  括號(hào)匹配 141
4.4.2  求算術(shù)表達(dá)式的值 144
4.4.3  迷宮求解 151
4.5  棧與遞歸 156
4.5.1  遞歸 156
4.5.2  消除遞歸 160
4.6  小結(jié) 162
4.7  習(xí)題 163
第5章  隊(duì)列 165
5.1  隊(duì)列的定義與抽象數(shù)據(jù)類型 165
5.1.1  什么是隊(duì)列 165
5.1.2  隊(duì)列的抽象數(shù)據(jù)類型 165
5.2  隊(duì)列的順序存儲(chǔ)及實(shí)現(xiàn) 166
5.2.1  順序隊(duì)列的表示 166
5.2.2  順序隊(duì)列的“假溢出” 167
5.2.3  順序循環(huán)隊(duì)列的表示 167
5.2.4  順序循環(huán)隊(duì)列的基本運(yùn)算 169
5.2.5  順序循環(huán)隊(duì)列舉例 170
5.3  隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn) 172
5.3.1  鏈?zhǔn)疥?duì)列的表示 172
5.3.2  鏈?zhǔn)疥?duì)列的基本運(yùn)算 173
5.3.3  鏈?zhǔn)疥?duì)列舉例 175
5.4  雙端隊(duì)列 179
5.4.1  什么是雙端隊(duì)列 179
5.4.2  雙端隊(duì)列的應(yīng)用 179
5.5  綜合案例：動(dòng)畫模擬停車場(chǎng)管理系統(tǒng) 181
5.6  小結(jié) 194
5.7  習(xí)題 194
第6章  串 197
6.1  串的定義及抽象數(shù)據(jù)類型 197
6.1.1  什么是串 197
6.1.2  串的抽象數(shù)據(jù)類型 198
6.2  串的順序表示與實(shí)現(xiàn) 199
6.2.1  串的順序存儲(chǔ)結(jié)構(gòu) 199
6.2.2  順序串的基本運(yùn)算 200
6.2.3  順序串應(yīng)用舉例 203
6.3  串的堆分配表示與實(shí)現(xiàn) 205
6.3.1  堆分配的存儲(chǔ)結(jié)構(gòu) 205
6.3.2  堆串的基本運(yùn)算 205
6.4  串的塊鏈?zhǔn)酱鎯?chǔ)表示與實(shí)現(xiàn) 208
6.4.1  串的塊鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 208
6.4.2  塊鏈串的基本運(yùn)算 209
6.5  串的模式匹配 212
6.5.1  樸素模式匹配算法——Brute-Force 212
6.5.2  KMP算法 214
6.5.3  模式匹配應(yīng)用舉例 219
6.6  小結(jié) 223
6.7  習(xí)題 224
第7章  數(shù)組 226
7.1  數(shù)組的定義及抽象數(shù)據(jù)類型 226
7.1.1  重新認(rèn)識(shí)數(shù)組 226
7.1.2  數(shù)組的抽象數(shù)據(jù)類型 227
7.2  數(shù)組的順序表示與實(shí)現(xiàn) 227
7.2.1  數(shù)組的順序存儲(chǔ)結(jié)構(gòu) 227
7.2.2  數(shù)組的基本運(yùn)算 229
7.2.3  數(shù)組應(yīng)用舉例 231
7.3  特殊矩陣的壓縮存儲(chǔ) 233
7.3.1  對(duì)稱矩陣的壓縮存儲(chǔ) 233
7.3.2  三角矩陣的壓縮存儲(chǔ) 233
7.3.3  對(duì)角矩陣的壓縮存儲(chǔ) 235
7.4  稀疏矩陣的壓縮存儲(chǔ) 236
7.4.1  什么是稀疏矩陣 236
7.4.2  稀疏矩陣抽象數(shù)據(jù)類型 236
7.4.3  稀疏矩陣的三元組表示 236
7.4.4  稀疏矩陣的三元組實(shí)現(xiàn) 237
7.5  稀疏矩陣應(yīng)用舉例 241
7.5.1  三元組表示的稀疏矩陣相加 241
7.5.2  三元組表示的稀疏矩陣相乘 244
7.6  稀疏矩陣的十字鏈表表示與實(shí)現(xiàn) 249
7.6.1  稀疏矩陣的十字鏈表表示 249
7.6.2  十字鏈表的基本運(yùn)算 250
7.7  小結(jié) 252
7.8  習(xí)題 252
第8章  廣義表 254
8.1  廣義表的定義及抽象數(shù)據(jù)類型 254
8.1.1  什么是廣義表 254
8.1.2  廣義表的抽象數(shù)據(jù)類型 255
8.2  廣義表的頭尾鏈表表示與實(shí)現(xiàn) 255
8.2.1  廣義表的頭尾鏈表存儲(chǔ)結(jié)構(gòu) 255
8.2.2  廣義表的基本運(yùn)算 256
8.2.3  廣義表應(yīng)用舉例（采用頭尾鏈表存儲(chǔ)結(jié)構(gòu)） 259
8.3  廣義表的擴(kuò)展線性鏈表表示與實(shí)現(xiàn) 263
8.3.1  廣義表的擴(kuò)展線性鏈表存儲(chǔ)結(jié)構(gòu) 263
8.3.2  廣義表的基本運(yùn)算 264
8.3.3  廣義表應(yīng)用舉例（擴(kuò)展線性鏈表存儲(chǔ)結(jié)構(gòu)） 266
8.4  小結(jié) 269
8.5  習(xí)題 269
第三篇  非線性數(shù)據(jù)結(jié)構(gòu)
第9章  樹 271
9.1  樹的相關(guān)概念及抽象數(shù)據(jù)類型 271
9.1.1  什么是樹 271
9.1.2  樹的相關(guān)概念 272
9.1.3  樹的邏輯表示 272
9.1.4  樹的抽象數(shù)據(jù)類型 273
9.1.5  樹的存儲(chǔ)結(jié)構(gòu) 274
9.2  二叉樹的相關(guān)概念及抽象數(shù)據(jù)類型 277
9.2.1  什么是二叉樹 277
9.2.2  二叉樹的性質(zhì) 277
9.2.3  二叉樹的抽象數(shù)據(jù)類型 280
9.3  二叉樹的存儲(chǔ)表示與實(shí)現(xiàn) 281
9.3.1  二叉樹的順序存儲(chǔ) 281
9.3.2  二叉樹的鏈?zhǔn)酱鎯?chǔ) 282
9.3.3  二叉樹的基本運(yùn)算 282
9.4  遍歷二叉樹 285
9.4.1  什么是遍歷二叉樹 285
9.4.2  遍歷二叉樹 286
9.4.3  非遞歸遍歷二叉樹——基于棧的遞歸消除 288
9.5  遍歷二叉樹的應(yīng)用 290
9.5.1  按層次輸出二叉樹 290
9.5.2  二叉樹的計(jì)數(shù) 291
9.5.3  求葉子結(jié)點(diǎn)的最大最小枝長(zhǎng) 293
9.5.4  判斷兩棵二叉樹是否相似 294
9.5.5  交換二叉樹的左右子樹 294
9.5.6  求根結(jié)點(diǎn)到r結(jié)點(diǎn)之間的路徑 294
9.6  線索二叉樹 296
9.6.1  什么是線索化二叉樹 296
9.6.2  線索二叉樹 297
9.6.3  遍歷線索二叉樹 298
9.6.4  線索二叉樹應(yīng)用舉例 300
9.7  樹、森林與二叉樹 304
9.7.1  樹轉(zhuǎn)換為二叉樹 304
9.7.2  森林轉(zhuǎn)換為二叉樹 305
9.7.3  二叉樹轉(zhuǎn)換為樹和森林 306
9.7.4  樹和森林的遍歷 306
9.7.5  樹與二叉樹應(yīng)用舉例 307
9.8  綜合案例：哈夫曼樹 320
9.8.1  什么是哈夫曼樹 320
9.8.2  哈夫曼編碼 322
9.8.3  哈夫曼編碼算法的實(shí)現(xiàn) 322
9.9  小結(jié) 326
9.10  習(xí)題 327
第10章  圖 330
10.1  圖的定義與相關(guān)概念 330
10.1.1  什么是圖 330
10.1.2  圖的相關(guān)概念 331
10.1.3  圖的抽象數(shù)據(jù)類型 333
10.2  圖的存儲(chǔ)結(jié)構(gòu) 334
10.2.1  鄰接矩陣（數(shù)組表示法） 334
10.2.2  鄰接表 338
10.2.3  十字鏈表 343
10.2.4  鄰接多重鏈表 344
10.3  圖的遍歷 345
10.3.1  圖的深度優(yōu)先搜索 345
10.3.2  圖的廣度優(yōu)先搜索 348
10.4  圖的連通性問題 349
10.4.1  無向圖的連通分量與最小生成樹 349
10.4.2  最小生成樹 351
10.5  有向無環(huán)圖 359
10.5.1  AOV網(wǎng)與拓?fù)渑判?360
10.5.2  AOE網(wǎng)與關(guān)鍵路徑 362
10.6  最短路徑 367
10.6.1  從某個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑 367
10.6.2  每一對(duì)頂點(diǎn)之間的最短路徑 372
10.6.3  最短路徑應(yīng)用舉例 374
10.7  圖的應(yīng)用舉例 375
10.8  小結(jié) 383
10.9  習(xí)題 383
第四篇  查找與排序
第11章  查找 387
11.1  基本概念 387
11.2  靜態(tài)查找 388
11.2.1  順序表的查找 388
11.2.2  有序順序表的查找 389
11.2.3  索引順序表的查找 391
11.2.4  靜態(tài)查找應(yīng)用舉例 393
11.3  動(dòng)態(tài)查找 395
11.3.1  二叉排序樹 395
11.3.2  平衡二叉樹 402
11.4  B-樹與B+樹 408
11.4.1  B-樹 408
11.4.2  B+樹 415
11.5  哈希表 415
11.5.1  什么是哈希表 416
11.5.2  哈希函數(shù)的構(gòu)造方法 416
11.5.3  處理沖突的方法 417
11.5.4  哈希表應(yīng)用舉例 419
11.6  小結(jié) 422
11.7  習(xí)題 423
第12章  內(nèi)排序 425
12.1  基本概念 425
12.2  插入排序 426
12.2.1  直接插入排序 426
12.2.2  折半插入排序 428
12.2.3  希爾排序 430
12.2.4  插入排序應(yīng)用舉例 431
12.3  交換排序 434
12.3.1  冒泡排序 434
12.3.2  快速排序 437
12.3.3  交換排序應(yīng)用舉例 439
12.4  選擇排序 442
12.4.1  簡(jiǎn)單選擇排序 443
12.4.2  堆排序 444
12.4.3  選擇排序應(yīng)用舉例 448
12.5  歸并排序 451
12.5.1  2路歸并排序算法 452
12.5.2  歸并排序應(yīng)用舉例 453
12.6  基數(shù)排序 455
12.6.1  基數(shù)排序算法 455
12.6.2  基數(shù)排序應(yīng)用舉例 458
12.7  小結(jié) 462
12.8  習(xí)題 462
第13章  外排序 464
13.1  外存的存取特性 464
13.2  磁盤排序 465
13.2.1  歸并排序的基本方法 466
13.2.2  多路歸并排序 467
13.3  磁帶排序 468
13.3.1  2路歸并排序 468
13.3.2  多路非平衡歸并排序 469
13.4  小結(jié) 470
參考文獻(xiàn) 471