數(shù)據(jù)結(jié)構(gòu)：從概念到算法（C語(yǔ)言 微課版）

目錄
第 1章 緒論1
1.1 程序設(shè)計(jì)的問(wèn)題背景1
1.2 程序設(shè)計(jì)的一般過(guò)程2
1.3 數(shù)據(jù)結(jié)構(gòu)概述3
1.4 數(shù)據(jù)結(jié)構(gòu)基本概念6
1.5 算法設(shè)計(jì)的一般步驟9
1.5.1 算法定義及性質(zhì)9
1.5.2 算法設(shè)計(jì)步驟12
1.6 算法復(fù)雜度分析12
1.6.1 算法時(shí)間復(fù)雜度分析12
1.6.2 算法空間復(fù)雜度分析15
1.7 算法分析實(shí)例17
1.8 本章小結(jié)22
計(jì)算機(jī)領(lǐng)域名人堂23
本章習(xí)題23
第 2章 線性表27
2.1 線性表的基本概念27
2.1.1 線性表定義28
2.2.2 抽象數(shù)據(jù)類型定義29
2.2 線性表順序存儲(chǔ)結(jié)構(gòu)定義及實(shí)現(xiàn)32
2.2.1 順序表存儲(chǔ)結(jié)構(gòu)定義32
2.2.2 順序表的基本操作實(shí)現(xiàn)35
2.3 線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義及實(shí)現(xiàn)39
2.3.1 單鏈表存儲(chǔ)結(jié)構(gòu)定義40
2.3.2 單鏈表的實(shí)現(xiàn)40
2.3.3 循環(huán)單鏈表44
2.3.4 雙向鏈表46
2.4 順序表與鏈表的比較48
2.5 線性表應(yīng)用實(shí)例49
2.5.1 遞增有序單鏈表生成算法49
2.5.2 單鏈表插入刪除算法53
2.5.3 單鏈表合并算法55
2.5.4 單鏈表的逆置57
2.6 本章小結(jié)60
計(jì)算機(jī)領(lǐng)域名人堂61
本章習(xí)題62
第3章 棧與隊(duì)列66
3.1 棧67
3.1.1 棧的基本概念67
3.1.2 棧的抽象數(shù)據(jù)類型68
3.1.3 棧的操作特性68
3.1.4 棧的順序存儲(chǔ)結(jié)構(gòu)70
3.1.5 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)76
3.1.6 棧的應(yīng)用78
3.2 隊(duì)列86
3.2.1 隊(duì)列的基本概念87
3.2.2 隊(duì)列的抽象數(shù)據(jù)類型87
3.2.3 鏈?zhǔn)疥?duì)列的基本運(yùn)算及實(shí)現(xiàn)88
3.2.4 順序隊(duì)列的基本運(yùn)算及實(shí)現(xiàn)91
3.3 應(yīng)用實(shí)例96
3.3.1 棧的應(yīng)用實(shí)例96
3.3.2 隊(duì)列的應(yīng)用實(shí)例99
3.4 本章小結(jié)102
計(jì)算機(jī)領(lǐng)域名人堂103
本章習(xí)題103
第4章 字符串、多維數(shù)組與廣義表108
4.1 字符串108
4.1.1 字符串的定義109
4.1.2 字符串的存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)111
4.1.3 字符串的模式匹配算法116
4.2 多維數(shù)組122
4.2.1 多維數(shù)組概念的引入122
4.2.2 多維數(shù)組的順序存儲(chǔ)124
4.2.3 矩陣的壓縮存儲(chǔ)128
4.3 廣義表137
4.3.1 廣義表的定義137
4.3.2 廣義表的存儲(chǔ)139
4.4 應(yīng)用實(shí)例143
4.4.1最大匹配分詞算法143
4.4.2正數(shù)值三角形的最優(yōu)路徑147
4.5 本章小結(jié)149
計(jì)算機(jī)領(lǐng)域名人堂149
本章習(xí)題150
第5章 樹(shù)與二叉樹(shù)153
5.1 實(shí)際應(yīng)用中的樹(shù)153
5.2樹(shù)的邏輯結(jié)構(gòu)155
5.2.1 樹(shù)的定義與基本術(shù)語(yǔ)155
5.2.2 樹(shù)的抽象數(shù)據(jù)類型定義157
5.3 樹(shù)的存儲(chǔ)結(jié)構(gòu)158
5.3.1 雙親表示法159
5.3.2 孩子表示法159
5.3.3 孩子兄弟表示法161
5.4 二叉樹(shù)的邏輯結(jié)構(gòu)162
5.4.1 二叉樹(shù)的定義163
5.4.2 二叉樹(shù)的性質(zhì)163
5.4.3 二叉樹(shù)的操作與抽象數(shù)據(jù)類型定義166
5.5 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)168
5.5.1 二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)168
5.5.2 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)169
5.5.3 基于二叉鏈表的二叉樹(shù)遍歷170
5.5.4 線索鏈表與線索二叉樹(shù)179
5.6 樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換185
5.6.1 樹(shù)與二叉樹(shù)的轉(zhuǎn)換185
5.6.2 森林與二叉樹(shù)的轉(zhuǎn)換186
5.6.3 樹(shù)與森林的遍歷187
5.7 哈夫曼樹(shù)189
5.7.1 哈夫曼樹(shù)與哈夫曼算法189
5.7.2 哈夫曼編碼192
5.8 應(yīng)用實(shí)例：表達(dá)式二叉樹(shù)193
5.8.1 表達(dá)式二叉樹(shù)的概念194
5.8.2 表達(dá)式二叉樹(shù)的實(shí)現(xiàn)194
5.9本章小結(jié)197
計(jì)算機(jī)領(lǐng)域名人堂197
本章習(xí)題198
第6章 圖203
6.1 實(shí)際應(yīng)用中的圖203
6.2 圖的基本概念204
6.2.1 圖的定義和基本術(shù)語(yǔ)204
6.2.2 圖的操作定義207
6.3 圖的存儲(chǔ)結(jié)構(gòu)208
6.3.1 鄰接矩陣208
6.3.2 鄰接表211
6.3.3 十字鏈表213
6.3.4 鄰接多重表214
6.4 圖的遍歷215
6.4.1 圖的深度優(yōu)先搜索遍歷215
6.4.2 圖的廣度優(yōu)先搜索遍歷217
6.4.3 圖的連通性218
6.5 圖的生成樹(shù)問(wèn)題219
6.5.1 生成樹(shù)與最小生成樹(shù)219
6.5.2 最小生成樹(shù)Prim算法220
6.5.3 最小生成樹(shù)Kruskal算法223
6.6 圖的最短路徑問(wèn)題226
6.6.1 單源最短路徑Dijkstra算法226
6.6.2 各頂點(diǎn)間最短路徑Floyd算法230
6.7 有向無(wú)環(huán)圖的應(yīng)用233
6.7.1 拓?fù)渑判?33
6.7.2 關(guān)鍵路徑236
6.8 應(yīng)用實(shí)例241
6.8.1 并查集241
6.8.2 地鐵換乘問(wèn)題245
6.9 本章小結(jié)258
計(jì)算機(jī)領(lǐng)域名人堂258
本章習(xí)題259
第7章 排序263
7.1 實(shí)際應(yīng)用中的排序263
7.2 排序的概述264
7.2.1 排序算法的穩(wěn)定性265
7.2.2 排序算法的分類266
7.2.3 排序算法的性能266
7.3 插入排序266
7.3.1 直接插入排序266
7.3.2 折半插入排序269
7.3.3 希爾排序271
7.4 交換排序274
7.4.1 冒泡排序274
7.4.2 快速排序277
7.5 選擇排序281
7.5.1 簡(jiǎn)單選擇排序281
7.5.2 樹(shù)形選擇排序284
7.6 歸并排序291
7.7 分配排序295
7.7.1 桶排序295
7.7.2 基數(shù)排序296
7.8 各種排序技術(shù)比較299
7.9 本章小結(jié)300
計(jì)算機(jī)領(lǐng)域名人堂301
本章習(xí)題302
第8章 查找308
8.1 查找概述308
8.1.1 查找基本概念308
8.1.2 查找操作性能分析309
8.2 線性表的查找技術(shù)309
8.2.1 順序查找309
8.2.2 折半查找312
8.2.3 索引查找315
8.3 樹(shù)表的查找技術(shù)316
8.3.1 二叉排序樹(shù)316
8.3.2 平衡二叉樹(shù)325
8.3.3 紅黑樹(shù)331
8.3.4 B樹(shù)346
8.4 散列表的查找技術(shù)350
8.4.1 散列表概述350
8.4.2 散列函數(shù)設(shè)計(jì)351
8.4.3 處理沖突的方法352
8.4.4 散列查找性能分析355
8.5 本章小結(jié)357
計(jì)算機(jī)領(lǐng)域名人堂358
本章習(xí)題359
第9章 大數(shù)據(jù)存儲(chǔ)與檢索364
9.1 大數(shù)據(jù)的定義與特征364
9.1.1 大數(shù)據(jù)定義365
9.1.2 大數(shù)據(jù)特征365
9.1.3 大數(shù)據(jù)的行業(yè)發(fā)展趨勢(shì)367
9.2 大數(shù)據(jù)存儲(chǔ)367
9.2.1 數(shù)據(jù)存儲(chǔ)管理368
9.2.2 分布式文件系統(tǒng)368
9.2.3 NoSQL數(shù)據(jù)庫(kù)371
9.2.4 HBase數(shù)據(jù)庫(kù)372
9.3 大數(shù)據(jù)檢索375
9.3.1 大數(shù)據(jù)索引375
9.3.2 大數(shù)據(jù)高效檢索377
9.4 應(yīng)用實(shí)例378
9.5 本章小結(jié)382
計(jì)算機(jī)領(lǐng)域名人堂383
本章習(xí)題383