前言
第1章 緒論1
1.1 數(shù)據(jù)結(jié)構(gòu)的基本概念1
1.2 抽象數(shù)據(jù)類型3
1.2.1 抽象數(shù)據(jù)類型的定義3
1.2.2 抽象數(shù)據(jù)類型的描述3
1.3 數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)4
1.3.1 邏輯結(jié)構(gòu)4
1.3.2 存儲結(jié)構(gòu)5
1.4 算法的特性與算法的描述6
1.4.1 算法的定義6
1.4.2 算法的特性6
1.4.3 算法的描述6
1.5 算法分析7
1.5.1 算法設(shè)計的要求8
1.5.2 算法時間復(fù)雜度8
1.5.3 算法空間復(fù)雜度13
1.6 關(guān)于數(shù)據(jù)結(jié)構(gòu)課程的地位及
學(xué)習(xí)方法13
習(xí)題14
第2章 線性表17
2.1 線性表的概念及運算17
2.1.1 線性表的邏輯結(jié)構(gòu)17
2.1.2 線性表的抽象數(shù)據(jù)類型18
2.2 線性表的順序表示與實現(xiàn)19
2.2.1 線性表的順序存儲19
2.2.2 順序表的基本運算20
2.2.3 基本操作算法分析23
2.2.4 順序表應(yīng)用舉例23
2.3 線性表的鏈?zhǔn)奖硎九c實現(xiàn)27
2.3.1 單鏈表的存儲結(jié)構(gòu)27
2.3.2 單鏈表上的基本運算28
2.3.3 單鏈表應(yīng)用舉例33
2.3.4 循環(huán)單鏈表38
2.3.5 雙向鏈表41
2.4* 靜態(tài)鏈表43
2.4.1 靜態(tài)鏈表的存儲結(jié)構(gòu)44
2.4.2 靜態(tài)鏈表的實現(xiàn)44
2.4.3 靜態(tài)鏈表應(yīng)用舉例46
2.5 線性表應(yīng)用舉例：一元多項式的
表示與相乘48
2.5.1 一元多項式的表示48
2.5.2 一元多項式的相乘49
2.6 小結(jié)53
習(xí)題54
第3章 棧與隊列59
3.1 棧的表示與實現(xiàn)59
3.1.1 棧的定義59
3.1.2 棧的抽象數(shù)據(jù)類型60
3.1.3 順序棧61
3.1.4 鏈棧65
3.2 棧的應(yīng)用68
3.2.1 數(shù)制轉(zhuǎn)換68
3.2.2 行編輯程序68
3.2.3 算術(shù)表達(dá)式求值70
3.3 遞歸76
3.3.1 遞歸的定義76
3.3.2 消除遞歸79
3.4 隊列的表示與實現(xiàn)82
3.4.1 隊列的定義82
3.4.2 隊列的抽象數(shù)據(jù)類型82
3.4.3 順序隊列83
3.4.4 順序循環(huán)隊列85
3.4.5* 雙端隊列88
3.4.6 鏈?zhǔn)疥犃?8
3.4.7 鏈?zhǔn)疥犃械膶崿F(xiàn)90
3.5 隊列的應(yīng)用92
3.5.1 隊列在楊輝三角中的應(yīng)用92
3.5.2 隊列在回文中的應(yīng)用94
3.6 綜合案例：停車場管理97
3.7 小結(jié)105
習(xí)題105
第4章 串109
4.1 串109
4.1.1 串的定義109
4.1.2 串的抽象數(shù)據(jù)類型109
4.2 串的表示與實現(xiàn)111
4.2.1 定長順序存儲表示與實現(xiàn)111
4.2.2* 堆串的存儲分配表示與實現(xiàn)117
4.2.3* 塊鏈存儲表示與實現(xiàn)123
4.3 串的模式匹配128
4.3.1 Brute-Force經(jīng)典算法128
4.3.2 KMP算法130
4.3.3 模式匹配應(yīng)用舉例134
4.4 小結(jié)138
習(xí)題138
第5章 數(shù)組與廣義表141
5.1 數(shù)組的定義與運算141
5.1.1 數(shù)組的定義141
5.1.2 數(shù)組的抽象數(shù)據(jù)類型142
5.1.3 數(shù)組的順序表示與實現(xiàn)142
5.2 特殊矩陣的壓縮存儲146
5.2.1 對稱矩陣的壓縮存儲147
5.2.2 三角矩陣的壓縮存儲147
5.2.3 對角矩陣的壓縮存儲148
5.3 稀疏矩陣的壓縮存儲149
5.3.1 稀疏矩陣的定義149
5.3.2 稀疏矩陣的抽象數(shù)據(jù)類型149
5.3.3 稀疏矩陣的三元組表示與實現(xiàn)150
5.3.4 稀疏矩陣應(yīng)用舉例156
5.3.5 稀疏矩陣的十字鏈表表示與實現(xiàn)160
5.4 廣義表164
5.4.1 廣義表的定義164
5.4.2 廣義表的抽象數(shù)據(jù)類型165
5.5 廣義表的頭尾鏈表表示與實現(xiàn)165
5.5.1 廣義表的頭尾鏈表存儲結(jié)構(gòu)166
5.5.2 廣義表的基本運算166
5.5.3 廣義表應(yīng)用舉例169
5.6 廣義表的擴(kuò)展線性鏈表表示與
實現(xiàn)172
5.6.1 廣義表的擴(kuò)展線性鏈表存儲172
5.6.2 廣義表的基本運算173
5.6.3 采用擴(kuò)展線性鏈表存儲結(jié)構(gòu)的
廣義表應(yīng)用舉例175
5.7 廣義表應(yīng)用舉例：導(dǎo)師-本科生
制管理178
5.8 小結(jié)183
習(xí)題184
第6章 樹188
6.1 樹188
6.1.1 樹的定義188
6.1.2 樹的邏輯表示189
6.1.3 樹的抽象數(shù)據(jù)類型190
6.2 二叉樹191
6.2.1 二叉樹的定義191
6.2.2 二叉樹的性質(zhì)193
6.2.3 二叉樹的抽象數(shù)據(jù)類型195
6.2.4 二叉樹的存儲表示與實現(xiàn)196
6.3 二叉樹的遍歷201
6.3.1 二叉樹遍歷的定義202
6.3.2 二叉樹的先序遍歷202
6.3.3 二叉樹的中序遍歷203
6.3.4 二叉樹的后序遍歷205
6.4 二叉樹的線索化207
6.4.1 二叉樹的線索化定義207
6.4.2 二叉樹的線索化實現(xiàn)209
6.4.3 線索二叉樹的遍歷210
6.4.4 線索二叉樹應(yīng)用舉例212
6.5 樹、森林與二叉樹215
6.5.1 樹的存儲結(jié)構(gòu)215
6.5.2 樹轉(zhuǎn)換為二叉樹217
6.5.3 森林轉(zhuǎn)換為二叉樹219
6.5.4 二叉樹轉(zhuǎn)換為樹和森林219
6.5.5 樹和森林的遍歷220
6.6 綜合應(yīng)用舉例：哈夫曼樹221
6.6.1 哈夫曼樹的定義221
6.6.2 哈夫曼編碼222
6.6.3 哈夫曼編碼算法的實現(xiàn)223
6.7 小結(jié)226
習(xí)題227
第7章 圖232
7.1 圖的定義與相關(guān)概念232
7.1.1 圖的定義232
7.1.2 圖的相關(guān)概念233
7.1.3 圖的抽象數(shù)據(jù)類型235
7.2 圖的存儲結(jié)構(gòu)236
7.2.1 鄰接矩陣表示法236
7.2.2 鄰接表表示法240
7.2.3 十字鏈表表示法244
7.2.4 多重表表示法245
7.3 圖的遍歷246
7.3.1 圖的深度優(yōu)先遍歷246
7.3.2 圖的廣度優(yōu)先遍歷249
7.4 圖的連通性問題251
7.4.1 無向圖的連通分量與生成樹251
7.4.2 最小生成樹252
7.5 有向無環(huán)圖257
7.5.1 AOV網(wǎng)與拓?fù)渑判?57
7.5.2 AOE網(wǎng)與關(guān)鍵路徑260
7.6 最短路徑264
7.6.1 從某個頂點到其余各頂點的
最短路徑264
7.6.2 每一對頂點之間的最短路徑271
7.7 圖的應(yīng)用舉例275
7.7.1 距離某個頂點的最短路徑長度為
k的所有頂點275
7.7.2 求圖中頂點u到頂點v的簡單
路徑277
7.8 圖的綜合應(yīng)用：鐵路交通線路
規(guī)劃279
7.9 小結(jié)286
習(xí)題287
第8章 查找291
8.1 查找的基本概念291
8.2 靜態(tài)查找292
8.2.1 順序表的查找292
8.2.2 有序順序表的查找293
8.2.3 索引順序表的查找295
8.3 動態(tài)查找296
8.3.1 二叉排序樹296
8.3.2* 平衡二叉樹303
8.4* B-樹與B+樹311
8.4.1 B-樹311
8.4.2 B+樹319
8.5 哈希表320
8.5.1 哈希表的定義320
8.5.2 哈希函數(shù)的構(gòu)造方法321
8.5.3 處理沖突的方法322
8.5.4 哈希表查找與分析324
8.5.5 哈希表應(yīng)用舉例324
8.6 小結(jié)328
習(xí)題329
第9章 排序332
9.1 排序的基本概念332
9.2 插入排序333
9.2.1 直接插入排序333
9.2.2 折半插入排序335
9.2.3 希爾排序336
9.2.4 插入排序應(yīng)用舉例338
9.3 選擇排序339
9.3.1 簡單選擇排序339
9.3.2 堆排序340
9.4 交換排序346
9.4.1 冒泡排序346
9.4.2 快速排序347
9.4.3 交換排序應(yīng)用舉例350
9.5 歸并排序353
9.6 基數(shù)排序354
9.6.1 基數(shù)排序算法355
9.6.2 基數(shù)排序應(yīng)用舉例357
9.7 小結(jié)360
習(xí)題361
參考文獻(xiàn)364