數(shù)據(jù)結(jié)構(gòu)（C語言版）

目錄
第1章緒論1
1.1數(shù)據(jù)結(jié)構(gòu)概述1
1.2常用術(shù)語和基本概念3
1.3數(shù)據(jù)類型6
1.3.1數(shù)據(jù)類型概述6
1.3.2抽象數(shù)據(jù)類型7
1.4算法和算法復(fù)雜度8
1.4.1算法的重要性9
1.4.2時(shí)間復(fù)雜度10
1.4.3空間復(fù)雜度12
1.5本章實(shí)戰(zhàn)練習(xí)13
1.6本章小結(jié)15
1.7習(xí)題116
第2章線性表19
2.1線性表概述19
2.1.1線性表的定義及特點(diǎn)19
2.1.2線性表的抽象數(shù)據(jù)類型的
定義20
2.2線性表的順序存儲(chǔ)及運(yùn)算的
實(shí)現(xiàn)21
2.2.1線性表的順序存儲(chǔ)21
2.2.2順序表的基本操作22
2.3線性表的鏈?zhǔn)酱鎯?chǔ)及運(yùn)算的
實(shí)現(xiàn)28
2.3.1單鏈表28
2.3.2循環(huán)鏈表37
2.3.3雙向鏈表38
2.4本章實(shí)戰(zhàn)練習(xí)41
2.4.1順序表的常用操作41
2.4.2單鏈表的常用操作45
2.4.3通訊錄管理47
2.5本章小結(jié)53
2.6習(xí)題254
第3章棧和隊(duì)列59
3.1棧59
3.1.1棧的定義59
3.1.2棧的順序存儲(chǔ)與操作61
3.1.3棧的鏈?zhǔn)酱鎯?chǔ)與操作65
3.2隊(duì)列66
3.2.1隊(duì)列的定義67
3.2.2隊(duì)列的順序存儲(chǔ)與操作68
3.2.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)與操作71
3.3本章實(shí)戰(zhàn)練習(xí)73
3.3.1top為指針且指向棧頂
元素的下一個(gè)位置73
3.3.2top為整數(shù)且指向棧頂
元素的下一個(gè)位置75
3.3.3棧的應(yīng)用——數(shù)制轉(zhuǎn)換77
3.3.4順序隊(duì)列的基本操作79
3.3.5循環(huán)隊(duì)列設(shè)置不同隊(duì)空與
隊(duì)滿條件的解決方案82
3.3.6鏈隊(duì)列的基本操作85
3.4本章小結(jié)88
3.5習(xí)題389
第4章串、數(shù)組、矩陣和廣義表94
4.1串的定義95
4.1.1串的基本概念95
4.1.2串的抽象數(shù)據(jù)類型的定義96
4.2串的存儲(chǔ)與操作97
4.2.1串的順序存儲(chǔ)與操作97
4.2.2串的鏈?zhǔn)酱鎯?chǔ)與操作99
4.3數(shù)組100
4.3.1數(shù)組的定義100
4.3.2數(shù)組的順序存儲(chǔ)101
4.4矩陣的壓縮存儲(chǔ)102
4.4.1特殊矩陣的壓縮存儲(chǔ)102
4.4.2稀疏矩陣及其壓縮存儲(chǔ)105
4.5廣義表111
4.5.1廣義表的定義111
4.5.2廣義表的存儲(chǔ)結(jié)構(gòu)及
實(shí)現(xiàn)112
4.6本章實(shí)戰(zhàn)練習(xí)114
4.6.1串的常見操作114
4.6.2串的基本操作及應(yīng)用117
4.6.3數(shù)組應(yīng)用——方陣126
4.6.4數(shù)組應(yīng)用——稀疏矩陣126
4.7本章小結(jié)130
4.8習(xí)題4131
第5章樹134
5.1樹的概念134
5.1.1樹的定義134
5.1.2樹的基本術(shù)語135
5.2二叉樹137
5.2.1二叉樹的定義137
5.2.2二叉樹的性質(zhì)139
5.3二叉樹的存儲(chǔ)結(jié)構(gòu)141
5.3.1二叉樹的順序存儲(chǔ)141
5.3.2二叉樹的鏈?zhǔn)酱鎯?chǔ)與
操作142
5.4二叉樹的遍歷145
5.4.1遍歷算法145
5.4.2線索二叉樹148
5.4.3遍歷算法的應(yīng)用舉例152
5.5樹與森林153
5.5.1樹和森林的存儲(chǔ)154
5.5.2二叉樹、樹和森林的
轉(zhuǎn)換157
5.5.3樹和森林的遍歷158
5.6哈夫曼樹159
5.6.1哈夫曼樹的定義159
5.6.2哈夫曼樹的構(gòu)造算法159
5.6.3哈夫曼編碼161
5.7本章實(shí)戰(zhàn)練習(xí)162
5.7.1二叉樹的基本操作162
5.7.2線索二叉樹的操作167
5.7.3樹的應(yīng)用——模擬資源
管理器171
5.7.4哈夫曼樹構(gòu)造178
5.8本章小結(jié)180
5.9習(xí)題5180
第6章圖189
6.1圖的定義和基本術(shù)語189
6.1.1圖的定義189
6.1.2圖的基本術(shù)語190
6.2圖的存儲(chǔ)與操作194
6.2.1鄰接矩陣194
6.2.2鄰接表197
6.2.3十字鏈表200
6.3圖的遍歷201
6.3.1深度優(yōu)先遍歷算法202
6.3.2廣度優(yōu)先遍歷算法204
6.4圖與最小生成樹206
6.4.1生成樹和森林的算法206
6.4.2最小生成樹208
6.5最短路徑212
6.5.1單源點(diǎn)到其余各頂點(diǎn)的
最短路徑212
6.5.2任意源點(diǎn)之間的最短
路徑217
6.6AOV網(wǎng)與拓?fù)渑判?18
6.6.1AOV網(wǎng)219
6.6.2拓?fù)渑判?20
6.7AOE網(wǎng)與關(guān)鍵路徑222
6.7.1AOE網(wǎng)222
6.7.2關(guān)鍵路徑223
6.8本章實(shí)戰(zhàn)練習(xí)226
6.8.1圖的鄰接矩陣操作226
6.8.2圖的鄰接表操作230
6.8.3利用鄰接矩陣實(shí)現(xiàn)連通圖
的深度優(yōu)先遍歷234
6.8.4利用鄰接表實(shí)現(xiàn)連通圖
的深度優(yōu)先遍歷237
6.8.5利用鄰接矩陣實(shí)現(xiàn)連通圖
的廣度優(yōu)先遍歷239
6.8.6利用鄰接表實(shí)現(xiàn)連通圖
的廣度優(yōu)先遍歷242
6.8.7普里姆最小生成樹算法245
6.8.8迪杰斯特拉最短路徑
算法248
6.9本章小結(jié)251
6.10習(xí)題6251
第7章查找260
7.1查找的定義260
7.2靜態(tài)查找算法262
7.2.1順序查找262
7.2.2折半查找265
7.2.3分塊查找268
7.3動(dòng)態(tài)查找算法270
7.3.1二叉排序樹270
7.3.2平衡二叉樹275
7.4哈希表279
7.4.1哈希表的定義279
7.4.2哈希函數(shù)的構(gòu)造280
7.4.3處理沖突的方法283
7.4.4哈希表的查找和性能285
7.5本章實(shí)戰(zhàn)練習(xí)286
7.5.1順序查找算法286
7.5.2折半查找算法287
7.5.3二叉排序樹查找算法289
7.6本章小結(jié)291
7.7習(xí)題7292
第8章排序296
8.1排序的定義296
8.2插入排序算法297
8.2.1直接插入排序298
8.2.2折半插入排序299
8.2.3二路插入排序301
8.2.4表插入排序303
8.2.5希爾排序304
8.3交換排序算法305
8.3.1冒泡排序305
8.3.2快速排序306
8.4選擇排序算法309
8.4.1直接選擇排序309
8.4.2堆排序310
8.5歸并排序算法314
8.6排序算法的比較316
8.7本章實(shí)戰(zhàn)練習(xí)317
8.8本章小結(jié)322
8.9習(xí)題8323
參考文獻(xiàn)327