數(shù)據(jù)結構：從概念到算法（C語言 微課版）

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