數(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ù)語(yǔ)4
1.1.3數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容6
1.2數(shù)據(jù)類(lèi)型與抽象數(shù)據(jù)類(lèi)型7
1.2.1數(shù)據(jù)類(lèi)型7
1.2.2抽象數(shù)據(jù)類(lèi)型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線性表的順序存儲(chǔ)及運(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)酱鎯?chǔ)和運(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棧的存儲(chǔ)實(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ì)列的存儲(chǔ)實(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串的定長(zhǎng)度順序存儲(chǔ)及基本運(yùn)算62
4.2.1串的定長(zhǎng)順序存儲(chǔ)62
4.2.2定長(zhǎng)順序串的基本運(yùn)算63
4.2.3模式匹配64
4.3串的堆存儲(chǔ)結(jié)構(gòu)69
4.3.1串名的存儲(chǔ)映像69
4.3.2堆存儲(chǔ)結(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特殊矩陣的壓縮存儲(chǔ)77
5.2.1對(duì)稱(chēng)矩陣77
5.2.2三角矩陣78
5.2.3帶狀矩陣79
5.3稀疏矩陣80
5.3.1稀疏矩陣的三元組表存儲(chǔ)80
5.3.2稀疏矩陣的十字鏈表存儲(chǔ)86
5.4廣義表92
5.4.1廣義表的定義和基本運(yùn)算92
5.4.2廣義表的存儲(chǔ)93
5.4.3廣義表的基本操作的實(shí)現(xiàn)95
習(xí)題99
第6章二叉樹(shù)101
6.1定義與性質(zhì)101
6.1.1二叉樹(shù)的基本概念101
6.1.2二叉樹(shù)的主要性質(zhì)103
6.2基本操作與存儲(chǔ)實(shí)現(xiàn)104
6.2.1二叉樹(shù)的存儲(chǔ)104
6.2.2二叉樹(shù)的基本操作及實(shí)現(xiàn)107
6.3二叉樹(shù)的遍歷110
6.3.1二叉樹(shù)的遍歷方法及遞歸實(shí)現(xiàn)110
6.3.2二叉樹(shù)遍歷的非遞歸實(shí)現(xiàn)112
6.3.3由遍歷序列恢復(fù)二叉樹(shù)116
6.3.4不用棧的二叉樹(shù)遍歷的非遞歸方法118
6.4線索二叉樹(shù)118
6.4.1線索二叉樹(shù)的定義及結(jié)構(gòu)118
6.4.2線索二叉樹(shù)的基本操作實(shí)現(xiàn)120
6.5二叉樹(shù)的運(yùn)用126
6.5.1二叉樹(shù)遍歷的運(yùn)用126
6.5.2最優(yōu)二叉樹(shù)——哈夫曼樹(shù)129
習(xí)題135
第7章樹(shù)137
7.1樹(shù)的概念與表示137
7.1.1樹(shù)的定義及相關(guān)術(shù)語(yǔ)137
7.1.2樹(shù)的表示138
7.2樹(shù)的基本操作與存儲(chǔ)139
7.2.1樹(shù)的基本操作139
7.2.2樹(shù)的存儲(chǔ)結(jié)構(gòu)140
7.3樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換143
7.3.1樹(shù)轉(zhuǎn)換為二叉樹(shù)143
7.3.2森林轉(zhuǎn)化為二叉樹(shù)144
7.3.3二叉樹(shù)轉(zhuǎn)換為樹(shù)和森林145
7.4樹(shù)和森林的遍歷146
7.4.1樹(shù)的遍歷146
7.4.2森林的遍歷147
7.5樹(shù)的應(yīng)用147
7.5.1判定樹(shù)147
7.5.2集合的表示149
7.5.3關(guān)系等價(jià)求等價(jià)類(lèi)問(wèn)題151
習(xí)題152
第8章圖153
8.1圖的定義和術(shù)語(yǔ)153
8.1.1圖的定義153
8.1.2圖的相關(guān)術(shù)語(yǔ)153
8.1.3圖的基本操作156
8.2圖的存儲(chǔ)表示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無(wú)向圖的連通性169
8.4.2有向圖的連通性169
8.4.3生成樹(shù)和生成森林170
8.4.4關(guān)結(jié)點(diǎn)和重連通分量172
8.5最小生成樹(shù)175
8.5.1最小生成樹(shù)的基本概念175
8.5.2構(gòu)造最小生成樹(shù)的Prim算法176
8.5.3構(gòu)造最小生成樹(shù)的Kruskal算法178
8.6最短路徑181
8.6.1從一個(gè)源點(diǎn)到其他各點(diǎn)的最短路徑181
8.6.2每一對(duì)頂點(diǎn)之間的最短路徑183
8.7有向無(wú)環(huán)圖及其應(yīng)用186
8.7.1有向無(wú)環(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ù)語(yǔ)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動(dòng)態(tài)查找表205
9.3.1二叉排序樹(shù)205
9.3.2平衡二叉樹(shù)210
9.3.3B-樹(shù)和B+樹(shù)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簡(jiǎn)單選擇排序242
10.4.2樹(shù)型選擇排序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