第1章 緒論 1
1.1 從編程說(shuō)起 1
1.1.1 計(jì)算機(jī)解題的一般步驟 1
1.1.2 從程序設(shè)計(jì)角度看數(shù)據(jù)與數(shù)據(jù)的處理 2
1.1.3 程序設(shè)計(jì)方法 3
1.1.4 程序開(kāi)發(fā)過(guò)程 3
1.2 程序要處理的數(shù)據(jù) 4
1.2.1 數(shù)值計(jì)算與非數(shù)值計(jì)算的概念 5
1.2.2 數(shù)值計(jì)算實(shí)例 5
1.2.3 非數(shù)值計(jì)算實(shí)例—表 6
1.2.4 非數(shù)值計(jì)算實(shí)例—圖 9
1.2.5 非數(shù)值計(jì)算實(shí)例—樹(shù) 10
1.3 數(shù)據(jù)結(jié)構(gòu)的引入 11
1.4 數(shù)據(jù)結(jié)構(gòu)的基本概念 12
1.4.1 數(shù)據(jù)結(jié)構(gòu)的基本術(shù)語(yǔ) 12
1.4.2 數(shù)據(jù)結(jié)構(gòu)的三個(gè)要素 12
1.5 如何設(shè)計(jì)算法 15
1.5.1 算法的定義與表示方法 15
1.5.2 算法設(shè)計(jì)與函數(shù)設(shè)計(jì)的關(guān)系 16
1.5.3 軟件設(shè)計(jì)方法 17
1.5.4 算法設(shè)計(jì)的一般步驟 18
1.6 如何評(píng)價(jià)算法的優(yōu)劣 21
1.6.1 算法的設(shè)計(jì)要求 21
1.6.2 算法效率的度量方法 22
1.7 算法性能的事前分析方法 23
1.7.1 問(wèn)題的規(guī)模與算法的策略 24
1.7.2 算法效率的上限與下限 25
1.7.3 上下限問(wèn)題的數(shù)學(xué)描述 26
1.7.4 漸近的上限—算法的時(shí)間復(fù)雜度 29
1.7.5 算法時(shí)間復(fù)雜度的綜合討論 30
1.7.6 算法的空間效率分析方法 34
1.7.7 算法效率分析的綜合例子 37
1.8 算法性能綜合考量 39
1.9 本章小結(jié) 40
習(xí)題 40
第2章 結(jié)點(diǎn)邏輯關(guān)系為線性的結(jié)構(gòu)—線性表 43
2.1 從邏輯結(jié)構(gòu)角度看線性表 43
2.1.1 實(shí)際問(wèn)題中的線性關(guān)系 43
2.1.2 線性表的邏輯結(jié)構(gòu) 44
2.2 線性表的存儲(chǔ)結(jié)構(gòu)方法之一—順序表 45
2.2.1 順序表的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì) 45
2.2.2 關(guān)于結(jié)構(gòu)類(lèi)型應(yīng)用的思考與討論 47
2.2.3 順序表的運(yùn)算 49
2.2.4 順序存儲(chǔ)結(jié)構(gòu)的討論 56
2.3 線性表的存儲(chǔ)結(jié)構(gòu)方法之二—鏈表 56
2.3.1 問(wèn)題的引入 56
2.3.2 單鏈表的存儲(chǔ) 59
2.3.3 單鏈表的運(yùn)算 65
2.3.4 單鏈表的討論 78
2.3.5 循環(huán)鏈表 79
2.3.6 雙向鏈表 82
2.3.7 靜態(tài)鏈表 83
2.3.8 鏈表小結(jié) 83
2.4 線性表應(yīng)用舉例 84
2.4.1 逆序輸出單鏈表結(jié)點(diǎn)值 84
2.4.2 一元多項(xiàng)式的相加 85
2.5 順序表和鏈表的比較 92
2.6 本章小結(jié) 93
習(xí)題 93
第3章 運(yùn)算受限的線性表—棧和隊(duì)列 97
3.1 棧—按先進(jìn)后出方式管理的線性表 97
3.1.1 棧處理模式的引入 97
3.1.2 棧的邏輯結(jié)構(gòu) 100
3.1.3 棧的存儲(chǔ)結(jié)構(gòu)設(shè)計(jì) 102
3.1.4 順序棧的操作 103
3.1.5 鏈棧的基本操作 114
3.1.6 各種棧結(jié)構(gòu)的比較 119
3.1.7 棧的應(yīng)用舉例 119
3.2 隊(duì)列—按先進(jìn)先出方式管理的線性表 127
3.2.1 隊(duì)列處理模式的引入 127
3.2.2 隊(duì)列的邏輯結(jié)構(gòu) 130
3.2.3 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 131
3.2.4 順序隊(duì)列的基本操作 143
3.2.5 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 147
3.2.6 鏈隊(duì)列的基本操作 148
3.2.7 各種隊(duì)列結(jié)構(gòu)的比較 156
3.2.8 優(yōu)先隊(duì)列 156
3.2.9 隊(duì)列的應(yīng)用舉例 156
3.3 本章小結(jié) 168
習(xí)題 169
第4章 內(nèi)容特殊的線性表—多維數(shù)組與字符串 171
4.1 多維數(shù)組 171
4.1.1 數(shù)組的概念 171
4.1.2 數(shù)組的存儲(chǔ)結(jié)構(gòu) 172
4.2 矩陣的壓縮存儲(chǔ) 175
4.2.1 對(duì)稱(chēng)矩陣的壓縮存儲(chǔ) 176
4.2.2 三角矩陣的壓縮存儲(chǔ) 177
4.2.3 對(duì)角矩陣的壓縮存儲(chǔ) 178
4.2.4 稀疏矩陣的壓縮存儲(chǔ) 179
4.3 字符串 183
4.3.1 字符串的概念 184
4.3.2 字符串的存儲(chǔ)結(jié)構(gòu) 185
4.3.3 字符串的查找—模式匹配 189
4.3.4 BF算法 190
4.3.5 KMP算法 196
4.4 本章小結(jié) 204
習(xí)題 205
第5章 結(jié)點(diǎn)邏輯關(guān)系分層次的非線性結(jié)構(gòu)—樹(shù) 208
5.1 實(shí)際問(wèn)題中的樹(shù)形結(jié)構(gòu) 208
5.1.1　日常生活中的樹(shù)形結(jié)構(gòu) 208
5.1.2　計(jì)算機(jī)中的目錄結(jié)構(gòu) 209
5.1.3　網(wǎng)站的樹(shù)形結(jié)構(gòu) 209
5.1.4 表達(dá)式樹(shù) 210
5.2 樹(shù)的邏輯結(jié)構(gòu) 210
5.2.1 樹(shù)的定義和基本術(shù)語(yǔ) 210
5.2.2 樹(shù)的操作定義 213
5.3 樹(shù)的存儲(chǔ)結(jié)構(gòu) 213
5.3.1 樹(shù)的連續(xù)存儲(chǔ)方式 214
5.3.2 樹(shù)的鏈?zhǔn)酱鎯?chǔ)方式 215
5.4 二叉樹(shù)的邏輯結(jié)構(gòu) 218
5.4.1　二叉樹(shù)與普通樹(shù)的轉(zhuǎn)換 218
5.4.2 二叉樹(shù)的概念 220
5.4.3 二叉樹(shù)的基本性質(zhì) 222
5.4.4 二叉樹(shù)的操作定義 222
5.5 二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 223
5.5.1 二叉樹(shù)的順序結(jié)構(gòu) 223
5.5.2 二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 224
5.5.3 建立動(dòng)態(tài)二叉鏈表 226
5.6 二叉樹(shù)結(jié)點(diǎn)的查找問(wèn)題—樹(shù)的遍歷 230
5.6.1　問(wèn)題引例 230
5.6.2 樹(shù)的廣度優(yōu)先遍歷 233
5.6.3 樹(shù)的深度優(yōu)先遍歷 235
5.6.4 樹(shù)的遍歷的應(yīng)用 243
5.7 樹(shù)的應(yīng)用 248
5.7.1 表達(dá)式樹(shù) 248
5.7.2 線索二叉樹(shù) 249
5.7.3 哈夫曼樹(shù)及哈夫曼編碼 254
5.8 線性與非線性結(jié)構(gòu)的集合—廣義表 268
5.8.1 廣義表的定義 269
5.8.2 廣義表的存儲(chǔ) 271
5.8.3 廣義表的基本運(yùn)算 277
5.9 本章小結(jié) 280
習(xí)題 281
第6章 結(jié)點(diǎn)邏輯關(guān)系任意的非線性結(jié)構(gòu)—圖 285
6.1 實(shí)際問(wèn)題中的圖及抽象 285
6.2 圖的邏輯結(jié)構(gòu) 289
6.2.1 圖的定義和基本術(shù)語(yǔ) 289
6.2.2　圖的基本術(shù)語(yǔ) 290
6.2.3 圖的操作定義 292
6.3 圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn) 292
6.3.1 圖的數(shù)組表示法1—鄰接矩陣 293
6.3.2 圖的數(shù)組表示法2—邊集數(shù)組 295
6.3.3 圖的鏈表表示法1—鄰接表 296
6.3.4 圖的鏈表表示法2—十字鏈表 301
6.3.5 圖的鏈表表示法3—鄰接多重表 302
6.3.6 圖各種存儲(chǔ)結(jié)構(gòu)的歸結(jié)比較 304
6.4 圖的基本操作 305
6.4.1 鄰接矩陣的操作 305
6.4.2 鄰接表的操作 307
6.4.3　圖的運(yùn)算實(shí)例 309
6.5 圖的頂點(diǎn)查找問(wèn)題—圖的遍歷 313
6.5.1　問(wèn)題的引入 313
6.5.2 圖的廣度優(yōu)先遍歷—BFS 314
6.5.3 圖的深度優(yōu)先遍歷—DFS 318
6.6 圖的經(jīng)典應(yīng)用—圖中的樹(shù)問(wèn)題 324
6.6.1　引例 324
6.6.2 生成樹(shù) 326
6.6.3 最小生成樹(shù) 327
6.6.4 求最小生成樹(shù)算法1—Prim算法 328
6.6.5 求最小生成樹(shù)算法2—Kruskal算法 334
6.6.6 生成樹(shù)算法小結(jié) 341
6.7 圖的經(jīng)典應(yīng)用—最短路徑問(wèn)題 341
6.7.1 最短路徑問(wèn)題的引入 341
6.7.2 單源最短路徑算法—Dijkstra算法 343
6.7.3 各頂點(diǎn)對(duì)間最短路徑算法—Floyd算法 348
6.7.4 最短路徑問(wèn)題小結(jié) 353
6.8 圖的經(jīng)典應(yīng)用—活動(dòng)頂點(diǎn)與活動(dòng)邊的問(wèn)題 354
6.8.1 圖的活動(dòng)頂點(diǎn)排序問(wèn)題的引入 354
6.8.2 AOV網(wǎng)與拓?fù)渑判颉�活�?dòng)頂點(diǎn)排序問(wèn)題 356
6.8.3 AOE網(wǎng)與關(guān)鍵路徑—活動(dòng)邊最長(zhǎng)問(wèn)題 362
6.8.4 活動(dòng)頂點(diǎn)與活動(dòng)邊問(wèn)題小結(jié) 373
6.9 本章小結(jié) 373
習(xí)題 374
第7章 數(shù)據(jù)的處理方法—排序技術(shù) 380
7.1 概述 380
7.1.1 排序的基本概念 380
7.1.2 排序算法的分類(lèi) 382
7.2 插入排序 382
7.2.1 直接插入排序 382
7.2.2 希爾排序 385
7.3 交換排序 387
7.3.1 冒泡排序 387
7.3.2 快速排序 389
7.4 選擇排序 393
7.4.1 簡(jiǎn)單選擇排序 393
7.4.2 堆排序 394
7.5 歸并排序 398
7.6 分配排序 402
7.6.1 桶排序 402
7.6.2 基數(shù)排序 405
7.7 各種排序算法的比較 408
7.8 本章小結(jié) 411
習(xí)題 411

第8章 數(shù)據(jù)的處理方法—索引與查找技術(shù) 414
8.1 索引的基本概念 415
8.1.1 索引的定義 416
8.1.2 表示索引的邏輯結(jié)構(gòu) 416
8.1.3 索引的主要操作 417
8.2 線性索引技術(shù) 417
8.2.1 稠密索引 417
8.2.2 分塊索引 418
8.2.3 分級(jí)索引 419
8.2.4 多重表 420
8.2.5 倒排表 422
8.3 樹(shù)形索引 424
8.3.1 二叉排序樹(shù) 424
8.3.2 B樹(shù) 428
8.4 查找概述 430
8.4.1 查找的基本概念 431
8.4.2 查找算法的性能 431
8.5 線性表的查找技術(shù) 432
8.5.1 順序查找 432
8.5.2 有序表查找 433
8.5.3 索引查找 437
8.6 樹(shù)表的查找技術(shù) 439
8.6.1 二叉排序樹(shù)的查找 439
8.6.2 B樹(shù)的查找 439
8.6.3 在非數(shù)值有序表上的查找—字典樹(shù) 440
8.7 散列表存儲(chǔ)及其查找技術(shù) 442
8.7.1 問(wèn)題引入 442
8.7.2 散列概述 443
8.7.3 散列函數(shù)的設(shè)計(jì) 446
8.7.4 處理沖突的方法 447
8.7.5 散列查找的性能分析 452
8.8 本章小結(jié) 454
習(xí)題 455
第9章 經(jīng)典算法 457
9.1 遞歸—有去有回的過(guò)程 457
9.1.1 “先進(jìn)后出”的遞歸 457
9.1.2 遞歸的計(jì)算機(jī)實(shí)現(xiàn) 458
9.1.3 遞歸方法特點(diǎn)分析 460
9.1.4 遞歸算法實(shí)例 462
9.1.5 遞歸小結(jié) 464
9.2 分治法—分而治之策略 464
9.2.1 分治法 464
9.2.2 分治法的適用條件 465
9.2.3 分治問(wèn)題的類(lèi)型 465
9.2.4 分治法小結(jié) 468
9.3 動(dòng)態(tài)規(guī)劃—多段決策法 468
9.3.1 動(dòng)態(tài)規(guī)劃 468
9.3.2 動(dòng)態(tài)規(guī)劃的解題方法 470
9.3.3 動(dòng)態(tài)規(guī)劃解題實(shí)例 473
9.3.4 動(dòng)態(tài)規(guī)劃小結(jié) 478
9.4 貪心算法—局部最優(yōu)解法 478
9.4.1 貪心算法 478
9.4.2 貪心算法經(jīng)典問(wèn)題 480
9.4.3 貪心算法小結(jié) 482
9.5 回溯法—深度優(yōu)先搜索解空間 483
9.5.1 回溯法 483
9.5.2 回溯法實(shí)例 484
9.5.3 回溯法小結(jié) 488
9.6 分支限界法—廣度優(yōu)先搜索解空間 488
9.6.1 分支限界法簡(jiǎn)介 488
9.6.2 分支限界法的求解思想 490
9.6.3 分支限界法經(jīng)典問(wèn)題 491
9.6.4 分支限界法小結(jié) 493
9.7 本章小結(jié) 494
習(xí)題 494
附錄A 數(shù)據(jù)的聯(lián)系 496