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

目　　錄  　　
前言
第一篇  基礎(chǔ)知識
第1章  數(shù)據(jù)結(jié)構(gòu)概述 1
1.1  為什么要學習數(shù)據(jù)結(jié)構(gòu) 1
1.2  基本概念和術(shù)語 2
1.3  數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu) 4
1.3.1  邏輯結(jié)構(gòu) 4
1.3.2  存儲結(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è)計的4個目標 11
1.6.2  算法效率評價 11
1.6.3  算法的時間復雜度 12
1.6.4  算法的空間復雜度 14
1.7  學好數(shù)據(jù)結(jié)構(gòu)的秘訣 14
1.8  習題 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  遞歸應用舉例 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)存的動態(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  鏈表應用舉例：一元多項式的相加 67
2.7  小結(jié) 73
2.8  習題 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  線性表的順序表示與實現(xiàn) 79
3.2.1  線性表的順序存儲結(jié)構(gòu) 79
3.2.2  順序表的基本運算 80
3.2.3  順序表的實現(xiàn)算法分析 83
3.2.4  順序表的優(yōu)缺點 83
3.2.5  順序表應用舉例 84
3.3  線性表的鏈式表示與實現(xiàn) 89
3.3.1  單鏈表的存儲結(jié)構(gòu) 90
3.3.2  單鏈表上的基本運算 91
3.3.3  單鏈表存儲結(jié)構(gòu)與順序存儲結(jié)構(gòu)的優(yōu)缺點 96
3.3.4  單鏈表應用舉例 97
3.4  循環(huán)單鏈表 104
3.4.1  循環(huán)鏈表的鏈式存儲 104
3.4.2  循環(huán)單鏈表應用舉例 106
3.5  雙向鏈表 108
3.5.1  雙向鏈表的存儲結(jié)構(gòu) 108
3.5.2  雙向鏈表的插入和刪除操作 109
3.5.3  雙向鏈表應用舉例 111
3.6  靜態(tài)鏈表 113
3.6.1  靜態(tài)鏈表的存儲結(jié)構(gòu) 114
3.6.2  靜態(tài)鏈表的基本運算 114
3.6.3  靜態(tài)鏈表應用舉例 117
3.7  綜合案例：一元多項式的表示與相乘 118
3.7.1  一元多項式的表示 118
3.7.2  一元多項式相乘 119
3.8  小結(jié) 123
3.9  習題 123
第4章  棧 127
4.1  棧的定義與抽象數(shù)據(jù)類型 127
4.1.1  什么是棧 127
4.1.2  棧的抽象數(shù)據(jù)類型 128
4.2  棧的順序表示與實現(xiàn) 128
4.2.1  棧的順序存儲結(jié)構(gòu) 128
4.2.2  順序棧的基本運算 129
4.2.3  順序棧應用舉例 131
4.3  棧的鏈式表示與實現(xiàn) 136
4.3.1  棧的鏈式存儲結(jié)構(gòu) 137
4.3.2  鏈棧的基本運算 137
4.3.3  鏈棧應用舉例 140
4.4  棧的典型應用 141
4.4.1  括號匹配 141
4.4.2  求算術(shù)表達式的值 144
4.4.3  迷宮求解 151
4.5  棧與遞歸 156
4.5.1  遞歸 156
4.5.2  消除遞歸 160
4.6  小結(jié) 162
4.7  習題 163
第5章  隊列 165
5.1  隊列的定義與抽象數(shù)據(jù)類型 165
5.1.1  什么是隊列 165
5.1.2  隊列的抽象數(shù)據(jù)類型 165
5.2  隊列的順序存儲及實現(xiàn) 166
5.2.1  順序隊列的表示 166
5.2.2  順序隊列的“假溢出” 167
5.2.3  順序循環(huán)隊列的表示 167
5.2.4  順序循環(huán)隊列的基本運算 169
5.2.5  順序循環(huán)隊列舉例 170
5.3  隊列的鏈式存儲及實現(xiàn) 172
5.3.1  鏈式隊列的表示 172
5.3.2  鏈式隊列的基本運算 173
5.3.3  鏈式隊列舉例 175
5.4  雙端隊列 179
5.4.1  什么是雙端隊列 179
5.4.2  雙端隊列的應用 179
5.5  綜合案例：動畫模擬停車場管理系統(tǒng) 181
5.6  小結(jié) 194
5.7  習題 194
第6章  串 197
6.1  串的定義及抽象數(shù)據(jù)類型 197
6.1.1  什么是串 197
6.1.2  串的抽象數(shù)據(jù)類型 198
6.2  串的順序表示與實現(xiàn) 199
6.2.1  串的順序存儲結(jié)構(gòu) 199
6.2.2  順序串的基本運算 200
6.2.3  順序串應用舉例 203
6.3  串的堆分配表示與實現(xiàn) 205
6.3.1  堆分配的存儲結(jié)構(gòu) 205
6.3.2  堆串的基本運算 205
6.4  串的塊鏈式存儲表示與實現(xiàn) 208
6.4.1  串的塊鏈式存儲結(jié)構(gòu) 208
6.4.2  塊鏈串的基本運算 209
6.5  串的模式匹配 212
6.5.1  樸素模式匹配算法——Brute-Force 212
6.5.2  KMP算法 214
6.5.3  模式匹配應用舉例 219
6.6  小結(jié) 223
6.7  習題 224
第7章  數(shù)組 226
7.1  數(shù)組的定義及抽象數(shù)據(jù)類型 226
7.1.1  重新認識數(shù)組 226
7.1.2  數(shù)組的抽象數(shù)據(jù)類型 227
7.2  數(shù)組的順序表示與實現(xiàn) 227
7.2.1  數(shù)組的順序存儲結(jié)構(gòu) 227
7.2.2  數(shù)組的基本運算 229
7.2.3  數(shù)組應用舉例 231
7.3  特殊矩陣的壓縮存儲 233
7.3.1  對稱矩陣的壓縮存儲 233
7.3.2  三角矩陣的壓縮存儲 233
7.3.3  對角矩陣的壓縮存儲 235
7.4  稀疏矩陣的壓縮存儲 236
7.4.1  什么是稀疏矩陣 236
7.4.2  稀疏矩陣抽象數(shù)據(jù)類型 236
7.4.3  稀疏矩陣的三元組表示 236
7.4.4  稀疏矩陣的三元組實現(xiàn) 237
7.5  稀疏矩陣應用舉例 241
7.5.1  三元組表示的稀疏矩陣相加 241
7.5.2  三元組表示的稀疏矩陣相乘 244
7.6  稀疏矩陣的十字鏈表表示與實現(xiàn) 249
7.6.1  稀疏矩陣的十字鏈表表示 249
7.6.2  十字鏈表的基本運算 250
7.7  小結(jié) 252
7.8  習題 252
第8章  廣義表 254
8.1  廣義表的定義及抽象數(shù)據(jù)類型 254
8.1.1  什么是廣義表 254
8.1.2  廣義表的抽象數(shù)據(jù)類型 255
8.2  廣義表的頭尾鏈表表示與實現(xiàn) 255
8.2.1  廣義表的頭尾鏈表存儲結(jié)構(gòu) 255
8.2.2  廣義表的基本運算 256
8.2.3  廣義表應用舉例（采用頭尾鏈表存儲結(jié)構(gòu)） 259
8.3  廣義表的擴展線性鏈表表示與實現(xiàn) 263
8.3.1  廣義表的擴展線性鏈表存儲結(jié)構(gòu) 263
8.3.2  廣義表的基本運算 264
8.3.3  廣義表應用舉例（擴展線性鏈表存儲結(jié)構(gòu)） 266
8.4  小結(jié) 269
8.5  習題 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  樹的存儲結(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  二叉樹的存儲表示與實現(xiàn) 281
9.3.1  二叉樹的順序存儲 281
9.3.2  二叉樹的鏈式存儲 282
9.3.3  二叉樹的基本運算 282
9.4  遍歷二叉樹 285
9.4.1  什么是遍歷二叉樹 285
9.4.2  遍歷二叉樹 286
9.4.3  非遞歸遍歷二叉樹——基于棧的遞歸消除 288
9.5  遍歷二叉樹的應用 290
9.5.1  按層次輸出二叉樹 290
9.5.2  二叉樹的計數(shù) 291
9.5.3  求葉子結(jié)點的最大最小枝長 293
9.5.4  判斷兩棵二叉樹是否相似 294
9.5.5  交換二叉樹的左右子樹 294
9.5.6  求根結(jié)點到r結(jié)點之間的路徑 294
9.6  線索二叉樹 296
9.6.1  什么是線索化二叉樹 296
9.6.2  線索二叉樹 297
9.6.3  遍歷線索二叉樹 298
9.6.4  線索二叉樹應用舉例 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  樹與二叉樹應用舉例 307
9.8  綜合案例：哈夫曼樹 320
9.8.1  什么是哈夫曼樹 320
9.8.2  哈夫曼編碼 322
9.8.3  哈夫曼編碼算法的實現(xiàn) 322
9.9  小結(jié) 326
9.10  習題 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  圖的存儲結(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)與拓撲排序 360
10.5.2  AOE網(wǎng)與關(guān)鍵路徑 362
10.6  最短路徑 367
10.6.1  從某個頂點到其余各頂點的最短路徑 367
10.6.2  每一對頂點之間的最短路徑 372
10.6.3  最短路徑應用舉例 374
10.7  圖的應用舉例 375
10.8  小結(jié) 383
10.9  習題 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)查找應用舉例 393
11.3  動態(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  哈希表應用舉例 419
11.6  小結(jié) 422
11.7  習題 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  插入排序應用舉例 431
12.3  交換排序 434
12.3.1  冒泡排序 434
12.3.2  快速排序 437
12.3.3  交換排序應用舉例 439
12.4  選擇排序 442
12.4.1  簡單選擇排序 443
12.4.2  堆排序 444
12.4.3  選擇排序應用舉例 448
12.5  歸并排序 451
12.5.1  2路歸并排序算法 452
12.5.2  歸并排序應用舉例 453
12.6  基數(shù)排序 455
12.6.1  基數(shù)排序算法 455
12.6.2  基數(shù)排序應用舉例 458
12.7  小結(jié) 462
12.8  習題 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
參考文獻 471