數(shù)據(jù)結(jié)構(gòu)與算法：理論與實(shí)踐

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