數(shù)據(jù)結(jié)構(gòu)與算法

Contents第1章緒論1
1.1數(shù)據(jù)結(jié)構(gòu)的概念1
1.1.1為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)1
1.1.2有關(guān)概念和術(shù)語4
1.1.3數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容6
1.2數(shù)據(jù)類型與抽象數(shù)據(jù)類型7
1.2.1數(shù)據(jù)類型7
1.2.2抽象數(shù)據(jù)類型7
1.3算法和算法分析8
1.3.1算法特性8
1.3.2算法描述9
1.3.3算法性能分析與度量9
第2章線性表11
2.1線性表的邏輯結(jié)構(gòu)11
2.1.1線性表的定義11
2.1.2線性表的基本操作11
2.2線性表的順序存儲及運(yùn)算實(shí)現(xiàn)12
2.2.1順序表12
2.2.2順序表上基本運(yùn)算的實(shí)現(xiàn)14
2.2.3順序表應(yīng)用舉例18
2.3線性表的鏈?zhǔn)酱鎯瓦\(yùn)算實(shí)現(xiàn)20
2.3.1單鏈表20
2.3.2單鏈表上基本運(yùn)算的實(shí)現(xiàn)22
2.3.3循環(huán)鏈表28
2.3.4雙向鏈表29
2.3.5靜態(tài)鏈表302.3.6單鏈表應(yīng)用舉例32
2.4順序表和鏈表的比較34
◆數(shù)據(jù)結(jié)構(gòu)與算法目錄第3章棧和隊(duì)列36
3.1棧36
3.1.1棧的定義及基本操作36
3.1.2棧的存儲實(shí)現(xiàn)和操作實(shí)現(xiàn)37
3.2棧的應(yīng)用舉例40
3.3隊(duì)列50
3.3.1隊(duì)列的定義及基本運(yùn)算50
3.3.2隊(duì)列的存儲實(shí)現(xiàn)及運(yùn)算實(shí)現(xiàn)50
3.4隊(duì)列應(yīng)用舉例56
習(xí)題59
第4章串60
4.1串及基本運(yùn)算60
4.1.1串的基本概念60
4.1.2串的基本運(yùn)算60
4.2串的定長度順序存儲及基本運(yùn)算62
4.2.1串的定長順序存儲62
4.2.2定長順序串的基本運(yùn)算63
4.2.3模式匹配64
4.3串的堆存儲結(jié)構(gòu)69
4.3.1串名的存儲映像69
4.3.2堆存儲結(jié)構(gòu)71
4.3.3基于堆結(jié)構(gòu)的基本運(yùn)算71
習(xí)題73
第5章數(shù)組、特殊矩陣和廣義表74
5.1多維數(shù)組74
5.1.1數(shù)組的邏輯結(jié)構(gòu)74
5.1.2數(shù)組的內(nèi)存映像74
5.2特殊矩陣的壓縮存儲77
5.2.1對稱矩陣77
5.2.2三角矩陣78
5.2.3帶狀矩陣79
5.3稀疏矩陣80
5.3.1稀疏矩陣的三元組表存儲80
5.3.2稀疏矩陣的十字鏈表存儲86
5.4廣義表92
5.4.1廣義表的定義和基本運(yùn)算92
5.4.2廣義表的存儲93
5.4.3廣義表的基本操作的實(shí)現(xiàn)95
習(xí)題99
第6章二叉樹101
6.1定義與性質(zhì)101
6.1.1二叉樹的基本概念101
6.1.2二叉樹的主要性質(zhì)103
6.2基本操作與存儲實(shí)現(xiàn)104
6.2.1二叉樹的存儲104
6.2.2二叉樹的基本操作及實(shí)現(xiàn)107
6.3二叉樹的遍歷110
6.3.1二叉樹的遍歷方法及遞歸實(shí)現(xiàn)110
6.3.2二叉樹遍歷的非遞歸實(shí)現(xiàn)112
6.3.3由遍歷序列恢復(fù)二叉樹116
6.3.4不用棧的二叉樹遍歷的非遞歸方法118
6.4線索二叉樹118
6.4.1線索二叉樹的定義及結(jié)構(gòu)118
6.4.2線索二叉樹的基本操作實(shí)現(xiàn)120
6.5二叉樹的運(yùn)用126
6.5.1二叉樹遍歷的運(yùn)用126
6.5.2最優(yōu)二叉樹——哈夫曼樹129
習(xí)題135
第7章樹137
7.1樹的概念與表示137
7.1.1樹的定義及相關(guān)術(shù)語137
7.1.2樹的表示138
7.2樹的基本操作與存儲139
7.2.1樹的基本操作139
7.2.2樹的存儲結(jié)構(gòu)140
7.3樹、森林與二叉樹的轉(zhuǎn)換143
7.3.1樹轉(zhuǎn)換為二叉樹143
7.3.2森林轉(zhuǎn)化為二叉樹144
7.3.3二叉樹轉(zhuǎn)換為樹和森林145
7.4樹和森林的遍歷146
7.4.1樹的遍歷146
7.4.2森林的遍歷147
7.5樹的應(yīng)用147
7.5.1判定樹147
7.5.2集合的表示149
7.5.3關(guān)系等價(jià)求等價(jià)類問題151
習(xí)題152
第8章圖153
8.1圖的定義和術(shù)語153
8.1.1圖的定義153
8.1.2圖的相關(guān)術(shù)語153
8.1.3圖的基本操作156
8.2圖的存儲表示157
8.2.1鄰接矩陣157
8.2.2鄰接表159
8.2.3十字鏈表161
8.2.4鄰接多重表163
8.3圖的遍歷165
8.3.1深度優(yōu)先搜索165
8.3.2廣度優(yōu)先搜索167
8.4圖的連通性169
8.4.1無向圖的連通性169
8.4.2有向圖的連通性169
8.4.3生成樹和生成森林170
8.4.4關(guān)結(jié)點(diǎn)和重連通分量172
8.5最小生成樹175
8.5.1最小生成樹的基本概念175
8.5.2構(gòu)造最小生成樹的Prim算法176
8.5.3構(gòu)造最小生成樹的Kruskal算法178
8.6最短路徑181
8.6.1從一個源點(diǎn)到其他各點(diǎn)的最短路徑181
8.6.2每一對頂點(diǎn)之間的最短路徑183
8.7有向無環(huán)圖及其應(yīng)用186
8.7.1有向無環(huán)圖的概念186
8.7.2AOV網(wǎng)與拓?fù)渑判?87
8.7.3AOE網(wǎng)與關(guān)鍵路徑192
習(xí)題196
第9章查找197
9.1基本概念與術(shù)語197
9.2靜態(tài)查找表199
9.2.1靜態(tài)查找表結(jié)構(gòu)199
9.2.2順序查找200
9.2.3有序表的折半查找201
9.2.4有序表的插值查找和斐波那契查找203
9.2.5分塊查找205
9.3動態(tài)查找表205
9.3.1二叉排序樹205
9.3.2平衡二叉樹210
9.3.3B-樹和B+樹216
9.4哈希表查找(雜湊法)223
9.4.1哈希表與哈希方法223
9.4.2常用的哈希函數(shù)224
9.4.3處理沖突的方法225
9.4.4哈希表的查找分析229
習(xí)題230
第10章排序231
10.1基本概念231
10.2插入排序231
10.2.1直接插入排序231
10.2.2折半插入排序233
10.2.3表插入排序234
10.2.4希爾排序236
10.3交換排序238
10.3.1冒泡排序238
10.3.2快速排序239
10.4選擇排序241
10.4.1簡單選擇排序242
10.4.2樹型選擇排序242
10.4.3堆排序243
10.5二路歸并排序246
10.6基數(shù)排序248
10.6.1多關(guān)鍵碼排序248
10.6.2鏈?zhǔn)交鶖?shù)排序248
10.7外部排序251
10.7.1外部排序的方法251
10.7.2多路平衡歸并的實(shí)現(xiàn)253
習(xí)題255