數(shù)據(jù)結構與算法：理論與實踐

第1章 數(shù)據(jù)結構與算法概述 1
1．1 引言 1
1．1．1 《數(shù)據(jù)結構與算法》課程到底研究什么 1
1．1．2 《數(shù)據(jù)結構與算法》課程介紹 1
1．1．3 為什么要學習《數(shù)據(jù)結構與算法》課程 2
1．2 基本概念和術語 3
1．2．1 數(shù)據(jù) 3
1．2．2 數(shù)據(jù)項 3
1．2．3 數(shù)據(jù)元素 4
1．2．4 數(shù)據(jù)對象 4
1．2．5 數(shù)據(jù)結構 4
1．2．6 數(shù)據(jù)結構的形式化描述 6
1．2．7 數(shù)據(jù)的邏輯結構、存儲結構與物理結構 7
1．2．8 數(shù)據(jù)結構實例 7
1．3 算法 9
1．3．1 什么是算法 9
1．3．2 算法的性質 11
1．3．3 算法和程序 12
1．4 算法的表示（描述） 14
1．4．1 自然語言 14
1．4．2 計算機語言 15
1．4．3 圖形化工具 16
1．4．4 偽代碼 17
1．5 算法設計的準則 19
1．5．1 正確性 19
1．5．2 可讀性 20
1．5．3 健壯性 20
1．5．4 效率 21
1．6 算法效率分析 24
1．6．1 事后統(tǒng)計的方法 25
1．6．2 事前分析估算的方法 25
1．6．3 算法的空間復雜度 28
1．7 抽象數(shù)據(jù)類型 30
閱讀材料 32
習題1 35
第2章 順序存儲結構的線性表 39
2．1 基本概念和操作 39
2．1．1 什么是線性表 39
2．1．2 線性表的邏輯結構 40
2．1．3 線性表的基本操作 40
2．1．4 線性表的順序存儲結構 41
2．1．5 線性表的插入與刪除操作（算法） 42
2．1．6 順序表應用舉例 45
2．2 堆棧 47
2．2．1 堆棧的定義 47
2．2．2 棧的順序存儲結構與操作（算法） 48
2．2．3 堆棧在算法設計中的應用 51
2．3 隊列 63
2．3．1 隊列的定義 64
2．3．2 隊列的順序存儲結構與操作（算法） 64
2．3．3 循環(huán)隊列 66
2．3．4 隊列應用舉例 68
2．4 集合及其運算 71
2．4．1 集合的定義 71
2．4．2 集合運算 72
2．4．3 集合的順序存儲結構和操作實現(xiàn) 72
小結 75
習題2 75
第3章 鏈式存儲結構的線性表 79
3．1 什么是鏈式存儲結構的線性表 79
3．2 線性鏈表的操作（算法） 82
3．2．1 線性鏈表的構造 83
3．2．2 求表長 86
3．2．3 查找操作 86
3．2．4 線性鏈表的插入 87
3．2．5 線性鏈表的刪除 89
3．3 棧的鏈式存儲結構 90
3．4 隊列的鏈式存儲結構 92
3．5 循環(huán)鏈表 93
3．6 雙向鏈表 94
3．7 靜態(tài)鏈表 95
3．8 鏈表應用 97
3．9 一元多項式的存儲和相加 100
3．10 集合的鏈式存儲結構與操作 103
3．11 順序表和鏈表的比較 106
習題3 107
第4章 串 110
4．1 基本概念 111
4．2 串的存儲結構 112
4．2．1 順序存儲結構 112
4．2．2 鏈式存儲結構 113
4．3 串的基本操作 113
4．3．1 串復制 114
4．3．2 求字符串的長度 115
4．3．3 字符串連接 115
4．3．4 取子串 115
4．3．5 判斷兩個字符串是否相等 116
4．3．6 插入字符串 117
4．3．7 刪除子串 117
4．3．8 字符串清空 118
4．3．9 判斷字符串是否為空 118
4．3．10 字符串比較 118
4．4 串的模式匹配算法 119
4．4．1 模式匹配及其BF算法 119
4．4．2 模式匹配的一種改進算法――KMP算法 120
4．4．3 其他模式匹配算法 124
4．5 串操作應用舉例 132
習題4 133
第5章 數(shù)組、特殊矩陣與廣義表 136
5．1 數(shù)組的定義和運算 136
5．1．1 數(shù)組的基本概念 136
5．1．2 數(shù)組的特點 137
5．2 數(shù)組的順序存儲結構 137
5．2．1 一維數(shù)組 137
5．2．2 二維數(shù)組 138
5．2．3 三維數(shù)組 138
5．2．4 n維數(shù)組 139
5．3 特殊矩陣的壓縮存儲與處理 141
5．3．1 基本原則 141
5．3．2 對稱矩陣的壓縮存儲 141
5．3．3 三角矩陣的壓縮存儲 142
5．3．4 對角矩陣（帶狀矩陣）的壓縮存儲 143
5．4 稀疏矩陣 144
5．4．1 稀疏矩陣的三元組表存儲 145
5．4．2 稀疏矩陣的轉置 145
5．4．3 稀疏矩陣的快速轉置算法 147
5．5．4 稀疏矩陣的乘積 148
5．4．5 稀疏矩陣的十字鏈表存儲 151
5．5 廣義表 155
5．5．1 廣義表的定義 155
5．5．2 廣義表的特性 156
5．5．3 廣義表的基本操作 156
5．5．4 廣義表的存儲 157
5．5．5 廣義表的基本操作 159
習題5 162
第6章 樹與二叉樹 166
6．1 基本概念 166
6．1．1 什么是樹 166
6．1．2 基本概念和術語 167
6．1．3 樹的表示方法 167
6．1．4 樹的基本操作 168
6．1．5 樹的存儲結構 168
6．2 二叉樹 173
6．2．1 二叉樹的定義 173
6．2．2 二叉樹的基本形態(tài) 173
6．2．3 兩種特殊的二叉樹 174
6．2．4 二叉樹具有的重要性質 175
6．2．5 二叉樹的存儲結構 176
6．2．6 二叉樹的基本操作 179
6．3 二叉樹的遍歷 179
6．3．1 二叉樹的遍歷 179
6．3．2 先序遍歷算法 180
6．3．3 中序遍歷 181
6．3．4 后序遍歷 182
6．3．5 按層次順序遍歷二叉樹 183
6．3．6 遍歷算法的應用 184
6．4 二叉樹其他運算 185
6．4．1 建造二叉樹算法 185
6．4．2 求二叉樹高度（深度） 186
6．4．3 求二叉樹寬度 186
6．4．4 二叉樹查找 187
6．4．5 輸出一棵二叉樹 188
6．4．6 清除一棵二叉樹 188
6．5 線索二叉樹 189
6．5．1 建立線索樹 189
6．5．2 檢索結點 191
6．5．3 在線索二叉樹上插入一個結點 192
6．6 樹與森林 193
6．6．1 樹與二叉樹的轉換 193
6．6．2 森林與二叉樹的轉換 194
6．6．3 樹和森林的遍歷 194
6．7 樹的應用 197
6．7．1 判定樹 197
6．7．2 集合的表示 198
6．7．3 關系等價求等價類問題 199
6．8 二叉排序樹 200
6．8．1 二叉排序樹的定義 200
6．8．2 二叉排序樹的構造 201
6．8．3 二叉排序樹的查找 203
6．8．4 二叉排序樹的更新 205
6．8．5 二叉排序樹的刪除 205
6．9 哈夫曼樹及其應用 207
6．9．1 基本概念 207
6．9．2 哈夫曼樹的構造 208
6．9．3 哈夫曼編碼 210
6．9．4 最佳判定過程 211
6．10 平衡二叉樹 212
6．10．1 平衡二叉樹的引入 212
6．10．2 平衡二叉樹的定義 212
6．10．3 最小不平衡二叉樹 213
6．10．4 不平衡二叉樹的調整方法 214
6．10．5 建立平衡二叉樹舉例 218
6．10．6 平衡二叉樹與二叉排序樹比較 219
習題6 220
第7章 圖及其應用 223
7．1 基本概念和術語 225
7．1．1 圖的定義 225
7．1．2 完全圖、稠密圖、稀疏圖 226
7．1．3 頂點的度 227
7．1．4 子圖 227
7．1．5 路徑和回路 227
7．1．6 連通和連通分量 227
7．1．7 強連通圖和強連通分量 227
7．1．8 權和網(wǎng) 228
7．2 圖的存儲結構 229
7．2．1 鄰接矩陣 229
7．2．2 鄰接表 231
7．2．3 十字鏈表 234
7．2．4 鄰接多重表 236
7．2．5 圖的邊集數(shù)組 237
7．3 圖的遍歷 237
7．3．1 深度優(yōu)先搜索 237
7．3．2 廣度優(yōu)先搜索 239
7．3．3 搜索算法在搜索引擎中的應用 242
7．4 圖的連通性 243
7．4．1 向圖的連通性 243
7．4．2 有向圖的連通性 244
7．4．3 生成樹和生成森林 245
7．4．4 關結點和重連通分量 245
7．5 最小生成樹 248
7．5．1 什么是生成樹 248
7．5．2 構造最小生成樹的普里姆（Prim）算法 248
7．5．3 構造最小生成樹的Kruskal算法 252
7．6 最短路徑 255
7．6．1 求某一個源點到其他頂點的最短路徑 256
7．6．2 Bellman-Ford算法 259
7．6．3 每對頂點之間的最短路徑 262
7．7 有向環(huán)圖及其應用 267
7．7．1 有向環(huán)圖的概念 267
7．7．2 AOV網(wǎng)與拓撲排序 268
7．7．3 AOE網(wǎng)與關鍵路徑 272
習題7 277
第8章 查找與搜索引擎 281
8．1 基本概念與術語 281
8．2 順序查找 283
8．3 二分查找（折半查找） 285
8．3．1 二分查找的定義 285
8．3．2 二分查找算法 286
8．3．3 二分查找判定樹 287
8．3．4 二分查找性能分析 287
8．4 有序表的插值查找和斐波那契查找 288
8．4．1 插值查找 288
8．4．2 斐波那契查找 288
8．5 分塊查找 289
8．6 B-樹和B+樹上的查找 291
8．6．1 B-樹及其查找 291
8．6．2 B+樹 293
8．7 哈希表與散列查找 294
8．7．1 散列的概念 295
8．7．2 哈希函數(shù) 295
8．7．3 散列存儲的沖突 298
8．7．4 裝填因子 298
8．7．5 沖突解決方法 298
8．7．6 散列存儲的平均查找長度 302
8．7．7 散列存儲的優(yōu)缺點 303
8．8 搜索引擎及其相關技術 303
8．8．1 網(wǎng)頁的自動下載與存儲 304
8．8．2 網(wǎng)頁索引技術 306
8．8．3 網(wǎng)頁排名技術 310
習題8 323
第9章 排序 326
9．1 基本概念 327
9．2 插入排序 327
9．2．1 直接插入排序 327
9．2．2 折半插入排序 329
9．2．3 表插入排序 330
9．2．4 希爾排序 332
9．3 交換排序 336
9．3．1 冒泡排序 336
9．3．2 快速排序 337
9．4 選擇排序 343
9．4．1 簡單選擇排序 343
9．4．2 樹形選擇排序 346
9．4．3 堆排序 350
9．5 歸并排序 356
9．6 分配排序 359
9．6．1 箱排序 359
9．6．2 基數(shù)排序 360
9．6．3 多關鍵字排序 363
9．7 外排序 364
9．7．1 外部排序的方法 364
9．7．2 多路歸并的實現(xiàn) 365
9．8 排序方法之比較 368
習題9 369