第 1 章 概論 ............................................... 1
1.1　數(shù)據(jù)結(jié)構(gòu)的基本概念與術(shù)語 ..................................　1
1.1.1　數(shù)據(jù)結(jié)構(gòu)的基本概念..................................................1
1.1.2　數(shù)據(jù)的邏輯結(jié)構(gòu).........................................................2
1.1.3　數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu).........................................................3
1.1.4　數(shù)據(jù)的運(yùn)算集合.........................................................5
1.2　數(shù)據(jù)類型和抽象數(shù)據(jù)類型.....................................　5
1.2.1　數(shù)據(jù)類型....................................................................6
1.2.2　抽象數(shù)據(jù)類型.............................................................6
1.2.3　抽象數(shù)據(jù)類型的描述和實(shí)現(xiàn)........................................7
1.3　算法和算法分析 ................................................　8
1.3.1　算法的基本概念和基本特征........................................8
1.3.2　算法的時(shí)間復(fù)雜度和空間復(fù)雜度.................................8
本章小結(jié)　................................................................　9
習(xí)題.....................................................................10
第　2 章 線性表及其順序存儲(chǔ)..........................　12
2.1　線性表...........................................................12
2.2　順序表 ..........................................................12
2.2.1　順序表的基本概念及描述 .........................................12
2.2.2　順序表的實(shí)現(xiàn)...........................................................13
2.3　棧 ................................................................17
2.3.1　棧的基本概念及描述 ................................................17
2.3.2　順序棧及其實(shí)現(xiàn) .......................................................18
2.3.3　棧的應(yīng)用之一括號(hào)匹配......................................20
2.3.4　棧的應(yīng)用之二算術(shù)表達(dá)式求值 ...........................22
2.4　隊(duì)列 .............................................................26
2.4.1　隊(duì)列的基本概念及描述.............................................26
2.4.2　順序隊(duì)列及其實(shí)現(xiàn)....................................................27
2.4.3　順序循環(huán)隊(duì)列及其實(shí)現(xiàn).............................................30
2.4.4　隊(duì)列的應(yīng)用..............................................................31
本章小結(jié)　...............................................................32
習(xí)題.....................................................................32
第　3 章 線性表的鏈?zhǔn)酱鎯?chǔ) ............................　34
3.1　鏈?zhǔn)酱鎯?chǔ)........................................................34
3.2　單鏈表 ..........................................................35
3.2.1　單鏈表的基本概念及描述 .........................................35
3.2.2　單鏈表的實(shí)現(xiàn)...........................................................36
3.3　帶頭節(jié)點(diǎn)的單鏈表 ...........................................　39
3.3.1　帶頭節(jié)點(diǎn)的單鏈表的基本概念及描述........................39
3.3.2　帶頭節(jié)點(diǎn)的單鏈表的實(shí)現(xiàn) .........................................40
3.4　循環(huán)單鏈表.....................................................43
3.4.1　循環(huán)單鏈表的基本概念及描述..................................43
3.4.2　循環(huán)單鏈表的實(shí)現(xiàn)....................................................44
3.5　雙鏈表 .........................................................　49
3.5.1　雙鏈表的基本概念及描述.........................................49
3.5.2　雙鏈表的實(shí)現(xiàn)...........................................................49
3.6　鏈?zhǔn)綏?.........................................................　54
3.6.1　鏈?zhǔn)綏５幕�本概念及描�?........................................54
3.6.2　鏈?zhǔn)綏５膶?shí)現(xiàn)...........................................................54
3.7　鏈?zhǔn)疥?duì)列........................................................57
3.7.1　鏈?zhǔn)疥?duì)列的基本概念及描述......................................57
3.7.2　鏈?zhǔn)疥?duì)列的實(shí)現(xiàn) .......................................................57
本章小結(jié)　..............................................................　60
習(xí)題.....................................................................61
第　4 章 字符串、集合和特殊數(shù)組....................　63
4.1　字符串...........................................................63
4.1.1　字符串的基本概念....................................................63
4.1.2　字符串類的定義.......................................................64
4.1.3　字符串的存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)......................................65
4.2　字符串的模式匹配 ............................................71
4.2.1　樸素模式匹配算法....................................................71
4.2.2　快速模式匹配算法....................................................72
4.3　集合 .............................................................75
4.3.1　集合的定義和性質(zhì)....................................................75
4.3.2　集合類的定義...........................................................76
4.3.3　集合的存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn).........................................76
4.4　數(shù)組 ............................................................　84
4.4.1　數(shù)組和數(shù)組元素.......................................................84
4.4.2　數(shù)組類的定義...........................................................85
4.4.3　數(shù)組的順序存儲(chǔ)及其實(shí)現(xiàn).........................................86
4.5　特殊矩陣.......................................................　89
4.5.1　對(duì)稱矩陣的壓縮存儲(chǔ)................................................89
2
4.5.2　三角矩陣的壓縮存儲(chǔ)................................................90
4.5.3　帶狀矩陣的壓縮存儲(chǔ)................................................92
4.6　稀疏矩陣.......................................................　93
4.6.1　稀疏矩陣類的定義....................................................93
4.6.2　稀疏矩陣的順序存儲(chǔ)及其實(shí)現(xiàn)..................................94
4.6.3　稀疏矩陣的鏈?zhǔn)酱鎯?chǔ)及其實(shí)現(xiàn)..................................96
本章小結(jié)　.............................................................100
習(xí)題...................................................................100
第　5 章 遞歸 ...........................................　102
5.1　遞歸的基本概念與遞歸程序設(shè)計(jì) .........................102
5.2　遞歸程序執(zhí)行過程的分析..................................104
5.3　遞歸程序到非遞歸程序的轉(zhuǎn)換 ............................106
5.3.1　簡單遞歸程序到非遞歸程序的轉(zhuǎn)換.........................107
5.3.2　復(fù)雜遞歸程序到非遞歸程序的轉(zhuǎn)換 .........................109
5.4　遞歸程序設(shè)計(jì)的應(yīng)用實(shí)例..................................　114
本章小結(jié)　.............................................................　116
習(xí)題...................................................................116
第　6 章 樹狀結(jié)構(gòu)......................................　118
6.1　樹的基本概念 ................................................　118
6.2　樹類的定義...................................................120
6.3　樹的存儲(chǔ)結(jié)構(gòu)................................................120
6.3.1　雙親表示法............................................................120
6.3.2　孩子表示法............................................................121
6.3.3　孩子兄弟表示法.....................................................124
6.4　樹的遍歷......................................................125
6.5　樹的線性表示................................................128
6.5.1　樹的括號(hào)表示.........................................................128
6.5.2　樹的層號(hào)表示.........................................................130
6.6　并查集 ........................................................　131
6.6.1　并查集的定義.........................................................131
6.6.2　并查集的構(gòu)建.........................................................132
6.6.3　基于樹狀結(jié)構(gòu)的并查集實(shí)現(xiàn)....................................132
本章小結(jié)　.............................................................137
習(xí)題...................................................................138
3
第　7 章 二叉樹 ........................................　139
7.1　二叉樹的基本概念 ..........................................139
7.2　二叉樹的基本操作 ..........................................　141
7.3　二叉樹的存儲(chǔ)結(jié)構(gòu) ..........................................　141
7.3.1　順序存儲(chǔ)結(jié)構(gòu).........................................................142
7.3.2　鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu).........................................................143
7.4　二叉樹的遍歷................................................145
7.4.1　二叉樹遍歷的定義..................................................145
7.4.2　二叉樹遍歷的遞歸實(shí)現(xiàn)...........................................145
7.4.3　二叉樹遍歷的非遞歸實(shí)現(xiàn).......................................147
7.5　二叉樹其他運(yùn)算的實(shí)現(xiàn).....................................150
7.6　線索二叉樹...................................................152
7.6.1　線索二叉樹的定義..................................................152
7.6.2　中序線索二叉樹的基本操作....................................153
7.6.3　中序線索二叉樹的存儲(chǔ)結(jié)構(gòu)及其實(shí)現(xiàn)......................154
7.7　樹、森林和二叉樹的轉(zhuǎn)換..................................156
7.7.1　樹、森林到二叉樹的轉(zhuǎn)換.......................................156
7.7.2　二叉樹到樹、森林的轉(zhuǎn)換 .......................................157
本章小結(jié)　.............................................................158
習(xí)題...................................................................158
第　8 章 圖 ..............................................　160
8.1　圖的基本概念 ................................................160
8.2　圖的基本操作................................................163
8.3　圖的基本存儲(chǔ)結(jié)構(gòu) ..........................................164
8.3.1　鄰接矩陣及其實(shí)現(xiàn)..................................................164
8.3.2　鄰接表及其實(shí)現(xiàn).....................................................167
8.3.3　鄰接多重表............................................................169
8.4　圖的遍歷......................................................170
8.4.1　深度優(yōu)先遍歷 ........................................................170
8.4.2　廣度優(yōu)先遍歷.........................................................172
8.5　生成樹與最小生成樹 .......................................173
8.5.1　最小生成樹的定義 .................................................175
8.5.2　最小生成樹的 Prim 算法 ........................................176
8.5.3　最小生成樹的 Kruskal 算法 ...................................179
8.6　最短路徑......................................................182
8.6.1　單源最短路徑 ........................................................182
4
8.6.2　所有頂點(diǎn)對(duì)的最短路徑...........................................185
8.7　拓?fù)渑判?.....................................................188
8.8　關(guān)鍵路徑......................................................　191
本章小結(jié)　.............................................................196
習(xí)題...................................................................196
第　9 章 查找 ...........................................　200
9.1　查找的基本概念 .............................................200
9.2　線性表的查找................................................201
9.2.1　順序查找................................................................201
9.2.2　二分查找................................................................203
9.2.3　分塊查找................................................................205
9.3　二叉排序樹...................................................207
9.4　豐滿樹和平衡樹 .............................................213
9.4.1　豐滿樹...................................................................214
9.4.2　平衡二叉排序樹.....................................................215
9.4.3　擴(kuò)充二叉樹............................................................222
9.5　紅黑樹 ........................................................223
9.5.1　紅黑樹的定義.........................................................224
9.5.2　紅黑樹的插入.........................................................224
9.5.3　紅黑樹的刪除.........................................................227
9.6　最佳二叉排序樹和 Huffman 樹 .........................230
9.6.1　最佳二叉排序樹.....................................................230
9.6.2　Huffman 樹...........................................................235
9.7　B 樹 ...........................................................238
9.7.1　B-樹的定義 ...........................................................238
9.7.2　B-樹的基本操作 ....................................................239
9.7.3　B 樹 .....................................................................243
9.8　散列表查找...................................................245
9.8.1　散列存儲(chǔ) ...............................................................245
9.8.2　散列函數(shù)的構(gòu)造.....................................................246
9.8.3　沖突處理 ...............................................................247
本章小結(jié)　.............................................................251
習(xí)題...................................................................251
第　10 章 排序..........................................　255
10.1　排序的基本概念 ...........................................255
5
10.2　插入排序....................................................256
10.2.1　直接插入排序 ......................................................256
10.2.2　二分法插入排序...................................................259
10.2.3　表插入排序..........................................................260
10.2.4　Shell 插入排序 ....................................................262
10.3　選擇排序....................................................263
10.3.1　直接選擇排序 ......................................................263
10.3.2　樹狀選擇排序 ......................................................265
10.3.3　堆排序.................................................................267
10.4　交換排序....................................................271
10.4.1　冒泡排序 .............................................................271
10.4.2　快速排序 .............................................................272
10.5　歸并排序....................................................274
10.6　基數(shù)排序....................................................278
10.6.1　多排序碼的排序...................................................278
10.6.2　靜態(tài)鏈?zhǔn)交鶖?shù)排序 ...............................................278
10.7　外部排序....................................................281
10.7.1　磁盤排序 .............................................................282
10.7.2　多路平衡歸并 ......................................................283
10.7.3　置換-選擇排序.....................................................285
10.7.4　最佳歸并樹..........................................................288
本章小結(jié)　.............................................................290
習(xí)題...................................................................291
附錄　1 基礎(chǔ)實(shí)驗(yàn) ......................................　294
實(shí)驗(yàn)　1 線性表的順序存儲(chǔ)實(shí)現(xiàn) .................................294
實(shí)驗(yàn)　2 不帶頭節(jié)點(diǎn)的單鏈表....................................297
實(shí)驗(yàn)　3 帶頭節(jié)點(diǎn)的單鏈表.......................................301
實(shí)驗(yàn)　4 棧與字符串 ...............................................303
實(shí)驗(yàn)　5 遞歸........................................................306
實(shí)驗(yàn)　6 樹...........................................................310
實(shí)驗(yàn)　7 二叉樹.....................................................312
實(shí)驗(yàn)　8 圖...........................................................315
實(shí)驗(yàn)　9 查找........................................................317
實(shí)驗(yàn)　10 排序 ......................................................318
附錄　2 綜合實(shí)驗(yàn)