前言
第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ù)語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)用的實現(xiàn)原理13
1.4.3 遞歸轉(zhuǎn)換為非遞歸15
1.4.4 遞歸應(yīng)用舉例16
1.5 本章知識點小結(jié)17
練習(xí)題18
實驗題20
題目1 比較算法復(fù)雜性描述函數(shù)的
增長20
題目2 全排列的遞歸實現(xiàn)21
題目3 皇后問題21
第2章 基本線性結(jié)構(gòu)22
2.1 線性表22
2.1.1 問題提出22
2.1.2 線性表的定義23
2.1.3 線性表的基本運(yùn)算23
2.2 線性表的順序存儲24
2.2.1 順序表24
2.2.2 順序表上基本運(yùn)算的實現(xiàn)26
2.2.3 順序表應(yīng)用舉例29
2.3 線性表的鏈?zhǔn)酱鎯?1
2.3.1 單鏈表31
2.3.2 單鏈表上基本運(yùn)算的實現(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 堆棧的存儲及基本運(yùn)算的
實現(xiàn)46
2.5.3 堆棧應(yīng)用舉例49
2.6 隊列58
2.6.1 隊列的定義58
2.6.2 隊列的存儲及基本運(yùn)算的
實現(xiàn)59
2.6.3 隊列應(yīng)用舉例64
2.7 本章知識點小結(jié)67
練習(xí)題68
實驗題72
題目1 Josephus環(huán)問題72
題目2 模擬停車場管理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 廣義表的存儲101
3.4 本章知識點小結(jié)103
練習(xí)題104
實驗題107
題目 格式化文本107
第4章 樹結(jié)構(gòu)110
4.1 引言110
4.1.1 問題提出110
4.1.2 相關(guān)概念111
4.2 二叉樹113
4.2.1 二叉樹的概念113
4.2.2 二叉樹的主要性質(zhì)114
4.2.3 二叉樹的存儲116
4.2.4 二叉樹基本運(yùn)算的實現(xiàn)119
4.3 二叉樹的遍歷121
4.3.1 遞歸方法實現(xiàn)二叉樹的遍歷121
4.3.2 非遞歸方法實現(xiàn)二叉樹的遍歷123
4.3.3 隊列方法實現(xiàn)二叉樹的層次遍歷126
4.4 二叉樹遍歷的應(yīng)用127
4.4.1 構(gòu)造二叉樹的二叉鏈表存儲127
4.4.2 在二叉樹中查找值為x的數(shù)據(jù)元素128
4.4.3 統(tǒng)計給定二叉樹中葉子結(jié)點的數(shù)目128
4.4.4 由遍歷序列恢復(fù)二叉樹129
4.5 線索二叉樹130
4.5.1 線索二叉樹的定義及結(jié)構(gòu)130
4.5.2 線索二叉樹的構(gòu)建132
4.5.3 線索二叉樹的遍歷133
4.6 最優(yōu)二叉樹136
4.6.1 最優(yōu)二叉樹的概念136
4.6.2 最優(yōu)二叉樹的構(gòu)造138
4.6.3 最優(yōu)二叉樹的應(yīng)用哈夫曼編碼141
4.7 樹和森林143
4.7.1 樹的基本操作與表示143
4.7.2 樹的存儲144
4.7.3 樹和森林與二叉樹之間的轉(zhuǎn)換148
4.7.4 樹或森林的遍歷150
4.7.5 樹的應(yīng)用151
4.8 本章知識點小結(jié)153
練習(xí)題155
實驗題159
題目 哈夫曼編碼/譯碼器159
第5章 圖結(jié)構(gòu)161
5.1 引言161
5.1.1 問題提出161
5.1.2 相關(guān)概念162
5.1.3 圖的基本操作165
5.2 圖的存儲方法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 生成樹與最小生成樹178
5.4.1 生成樹和生成森林178
5.4.2 最小生成樹179
5.4.3 構(gòu)造最小生成樹的Prim
算法180
5.4.4 構(gòu)造最小生成樹的Kruskal
算法183
5.5 最短路徑186
5.5.1 從一個源點到其他各點的最短路徑186
*5.5.2 每一對頂點之間的最短路徑弗洛伊德算法189
5.6 拓?fù)渑判?93
5.6.1 有向無環(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 本章知識點小結(jié)203
練習(xí)題206
實驗題208
題目 校園導(dǎo)游程序208
第6章 查找210
6.1 引言210
6.1.1 問題提出210
6.1.2 相關(guān)概念210
6.2 線性表查找212
6.2.1 順序查找212
6.2.2 在順序存儲的有序表上查找214
6.3 樹表查找218
6.3.1 二叉排序樹218
6.3.2 平衡二叉樹224
*6.3.3 B樹和B 樹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 本章知識點小結(jié)245
練習(xí)題246
實驗題249
題目1 職工信息檢索系統(tǒng)249
題目2 個人圖書管理系統(tǒng)250
第7章 排序252
7.1 引言252
7.1.1 問題提出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 簡單選擇排序261
7.4.2 樹型選擇排序262
7.4.3 堆排序263
7.5 歸并排序266
7.5.1 兩個有序表的合并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 本章知識點小結(jié)274
練習(xí)題275
實驗題278
題目 各種內(nèi)部排序的性能比較278
第8章 擴(kuò)展應(yīng)用舉例279
8.1 求最大子段和279
8.1.1 問題描述279
8.1.2 問題分析與解決279
8.2 表達(dá)式樹的構(gòu)造283
8.2.1 問題描述283
8.2.2 問題分析與解決283
8.3 由等價關(guān)系求劃分287
8.3.1 問題描述287
8.3.2 問題分析與解決287
8.4 本章知識點小結(jié)289
練習(xí)題290
實驗題290
題目1 模擬銀行排隊辦理業(yè)務(wù)290
題目2 0-1背包問題291
附錄292
附錄A 實驗要求292
實驗題目294
附錄B 模擬試卷295
模擬試卷一295
模擬試卷二296
模擬試卷三299
模擬試卷四301
參考文獻(xiàn)304