數(shù)據(jù)結(jié)構(gòu)與算法（第4版）

前言
第1章 緒論1
1.1 引言1
1.1.1 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1
1.1.2 “數(shù)據(jù)結(jié)構(gòu)”課程的內(nèi)容4
1.2 數(shù)據(jù)結(jié)構(gòu)的概念5
1.2.1 基本概念和術(shù)語(yǔ)5
1.2.2 抽象數(shù)據(jù)類型7
1.3 算法8
1.3.1 算法及其特征8
1.3.2 算法的描述9
1.3.3 算法的性能分析9
1.4 遞歸12
1.4.1 遞歸的概念12
1.4.2 遞歸調(diào)用的實(shí)現(xiàn)原理13
1.4.3 遞歸轉(zhuǎn)換為非遞歸15
1.4.4 遞歸應(yīng)用舉例16
1.5 本章知識(shí)點(diǎn)小結(jié)17
練習(xí)題18
實(shí)驗(yàn)題20
題目1 比較算法復(fù)雜性描述函數(shù)的
增長(zhǎng)20
題目2 全排列的遞歸實(shí)現(xiàn)21
題目3 皇后問(wèn)題21
第2章 基本線性結(jié)構(gòu)22
2.1 線性表22
2.1.1 問(wèn)題提出22
2.1.2 線性表的定義23
2.1.3 線性表的基本運(yùn)算23
2.2 線性表的順序存儲(chǔ)24
2.2.1 順序表24
2.2.2 順序表上基本運(yùn)算的實(shí)現(xiàn)26
2.2.3 順序表應(yīng)用舉例29
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)31
2.3.1 單鏈表31
2.3.2 單鏈表上基本運(yùn)算的實(shí)現(xiàn)33
2.3.3 循環(huán)鏈表39
2.3.4 雙向鏈表39
2.3.5 鏈表應(yīng)用舉例41
2.4 順序表和鏈表的比較44
2.5 堆棧45
2.5.1 堆棧的定義45
2.5.2 堆棧的存儲(chǔ)及基本運(yùn)算的
實(shí)現(xiàn)46
2.5.3 堆棧應(yīng)用舉例49
2.6 隊(duì)列58
2.6.1 隊(duì)列的定義58
2.6.2 隊(duì)列的存儲(chǔ)及基本運(yùn)算的
實(shí)現(xiàn)59
2.6.3 隊(duì)列應(yīng)用舉例64
2.7 本章知識(shí)點(diǎn)小結(jié)67
練習(xí)題68
實(shí)驗(yàn)題72
題目1 Josephus環(huán)問(wèn)題72
題目2 模擬停車場(chǎng)管理73
第3章 線性結(jié)構(gòu)的擴(kuò)展75
3.1 字符串75
3.1.1 字符串的基本概念75
3.1.2 順序串76
3.1.3 模式匹配79
3.2 多維數(shù)組與特殊矩陣84
3.2.1 多維數(shù)組84
3.2.2 特殊矩陣86
3.2.3 稀疏矩陣90
3.3 廣義表99
3.3.1 廣義表的基本概念99
3.3.2 廣義表的存儲(chǔ)101
3.4 本章知識(shí)點(diǎn)小結(jié)103
練習(xí)題104
實(shí)驗(yàn)題107
題目 格式化文本107
第4章 樹(shù)結(jié)構(gòu)110
4.1 引言110
4.1.1 問(wèn)題提出110
4.1.2 相關(guān)概念111
4.2 二叉樹(shù)113
4.2.1 二叉樹(shù)的概念113
4.2.2 二叉樹(shù)的主要性質(zhì)114
4.2.3 二叉樹(shù)的存儲(chǔ)116
4.2.4 二叉樹(shù)基本運(yùn)算的實(shí)現(xiàn)119
4.3 二叉樹(shù)的遍歷121
4.3.1 遞歸方法實(shí)現(xiàn)二叉樹(shù)的遍歷121
4.3.2 非遞歸方法實(shí)現(xiàn)二叉樹(shù)的遍歷123
4.3.3 隊(duì)列方法實(shí)現(xiàn)二叉樹(shù)的層次遍歷126
4.4 二叉樹(shù)遍歷的應(yīng)用127
4.4.1 構(gòu)造二叉樹(shù)的二叉鏈表存儲(chǔ)127
4.4.2 在二叉樹(shù)中查找值為x的數(shù)據(jù)元素128
4.4.3 統(tǒng)計(jì)給定二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目128
4.4.4 由遍歷序列恢復(fù)二叉樹(shù)129
4.5 線索二叉樹(shù)130
4.5.1 線索二叉樹(shù)的定義及結(jié)構(gòu)130
4.5.2 線索二叉樹(shù)的構(gòu)建132
4.5.3 線索二叉樹(shù)的遍歷133
4.6 最優(yōu)二叉樹(shù)136
4.6.1 最優(yōu)二叉樹(shù)的概念136
4.6.2 最優(yōu)二叉樹(shù)的構(gòu)造138
4.6.3 最優(yōu)二叉樹(shù)的應(yīng)用——哈夫曼編碼141
4.7 樹(shù)和森林143
4.7.1 樹(shù)的基本操作與表示143
4.7.2 樹(shù)的存儲(chǔ)144
4.7.3 樹(shù)和森林與二叉樹(shù)之間的轉(zhuǎn)換148
4.7.4 樹(shù)或森林的遍歷150
4.7.5 樹(shù)的應(yīng)用151
4.8 本章知識(shí)點(diǎn)小結(jié)153
練習(xí)題155
實(shí)驗(yàn)題159
題目 哈夫曼編碼/譯碼器159
第5章 圖結(jié)構(gòu)161
5.1 引言161
5.1.1 問(wèn)題提出161
5.1.2 相關(guān)概念162
5.1.3 圖的基本操作165
5.2 圖的存儲(chǔ)方法165
5.2.1 鄰接矩陣165
5.2.2 鄰接表167
*5.2.3 十字鏈表169
*5.2.4 鄰接多重表171
5.3 圖的遍歷173
5.3.1 深度優(yōu)先搜索173
5.3.2 廣度優(yōu)先搜索175
5.3.3 應(yīng)用圖的遍歷判定圖的連通性177
5.4 生成樹(shù)與最小生成樹(shù)178
5.4.1 生成樹(shù)和生成森林178
5.4.2 最小生成樹(shù)179
5.4.3 構(gòu)造最小生成樹(shù)的Prim
算法180
5.4.4 構(gòu)造最小生成樹(shù)的Kruskal
算法183
5.5 最短路徑186
5.5.1 從一個(gè)源點(diǎn)到其他各點(diǎn)的最短路徑186
*5.5.2 每一對(duì)頂點(diǎn)之間的最短路徑——弗洛伊德算法189
5.6 拓?fù)渑判?93
5.6.1 有向無(wú)環(huán)圖的概念193
5.6.2 AOV網(wǎng)與拓?fù)渑判?94
5.7 關(guān)鍵路徑198
5.7.1 AOE網(wǎng)與關(guān)鍵路徑198
5.7.2 關(guān)鍵路徑的確定199
5.8 本章知識(shí)點(diǎn)小結(jié)203
練習(xí)題206
實(shí)驗(yàn)題208
題目 校園導(dǎo)游程序208
第6章 查找210
6.1 引言210
6.1.1 問(wèn)題提出210
6.1.2 相關(guān)概念210
6.2 線性表查找212
6.2.1 順序查找212
6.2.2 在順序存儲(chǔ)的有序表上查找214
6.3 樹(shù)表查找218
6.3.1 二叉排序樹(shù)218
6.3.2 平衡二叉樹(shù)224
*6.3.3 B樹(shù)和B+樹(shù)230
6.4 散列表查找236
6.4.1 散列表236
6.4.2 常用的散列函數(shù)237
6.4.3 處理沖突的方法及散列表的構(gòu)造238
6.4.4 散列表上的查找242
6.4.5 散列表上的插入244
6.4.6 散列表上的刪除245
6.5 本章知識(shí)點(diǎn)小結(jié)245
練習(xí)題246
實(shí)驗(yàn)題249
題目1 職工信息檢索系統(tǒng)249
題目2 個(gè)人圖書(shū)管理系統(tǒng)250
第7章 排序252
7.1 引言252
7.1.1 問(wèn)題提出252
7.1.2 相關(guān)概念252
7.2 插入排序254
7.2.1 直接插入排序254
7.2.2 折半插入排序256
7.2.3 希爾排序256
7.3 交換排序258
7.3.1 冒泡排序258
7.3.2 快速排序259
7.4 選擇排序261
7.4.1 簡(jiǎn)單選擇排序261
7.4.2 樹(shù)型選擇排序262
7.4.3 堆排序263
7.5 歸并排序266
7.5.1 兩個(gè)有序表的合并266
7.5.2 二路歸并排序的迭代算法267
7.5.3 二路歸并排序的遞歸算法268
*7.6 基數(shù)排序268
7.6.1 多關(guān)鍵碼排序268
7.6.2 鏈?zhǔn)交鶖?shù)排序269
7.7 排序方法比較272
7.8 本章知識(shí)點(diǎn)小結(jié)274
練習(xí)題275
實(shí)驗(yàn)題278
題目 各種內(nèi)部排序的性能比較278
第8章 擴(kuò)展應(yīng)用舉例279
8.1 求最大子段和279
8.1.1 問(wèn)題描述279
8.1.2 問(wèn)題分析與解決279
8.2 表達(dá)式樹(shù)的構(gòu)造283
8.2.1 問(wèn)題描述283
8.2.2 問(wèn)題分析與解決283
8.3 由等價(jià)關(guān)系求劃分287
8.3.1 問(wèn)題描述287
8.3.2 問(wèn)題分析與解決287
8.4 本章知識(shí)點(diǎn)小結(jié)289
練習(xí)題290
實(shí)驗(yàn)題290
題目1 模擬銀行排隊(duì)辦理業(yè)務(wù)290
題目2 0-1背包問(wèn)題291
附錄292
附錄A 實(shí)驗(yàn)要求292
實(shí)驗(yàn)題目294
附錄B 模擬試卷295
模擬試卷一295
模擬試卷二296
模擬試卷三299
模擬試卷四301
參考文獻(xiàn)304