數(shù)據(jù)結構與算法

Contents第1章緒論1
1.1數(shù)據(jù)結構的概念1
1.1.1為什么要學習數(shù)據(jù)結構1
1.1.2有關概念和術語4
1.1.3數(shù)據(jù)結構課程的內容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線性表的邏輯結構11
2.1.1線性表的定義11
2.1.2線性表的基本操作11
2.2線性表的順序存儲及運算實現(xiàn)12
2.2.1順序表12
2.2.2順序表上基本運算的實現(xiàn)14
2.2.3順序表應用舉例18
2.3線性表的鏈式存儲和運算實現(xiàn)20
2.3.1單鏈表20
2.3.2單鏈表上基本運算的實現(xiàn)22
2.3.3循環(huán)鏈表28
2.3.4雙向鏈表29
2.3.5靜態(tài)鏈表302.3.6單鏈表應用舉例32
2.4順序表和鏈表的比較34
◆數(shù)據(jù)結構與算法目錄第3章棧和隊列36
3.1棧36
3.1.1棧的定義及基本操作36
3.1.2棧的存儲實現(xiàn)和操作實現(xiàn)37
3.2棧的應用舉例40
3.3隊列50
3.3.1隊列的定義及基本運算50
3.3.2隊列的存儲實現(xiàn)及運算實現(xiàn)50
3.4隊列應用舉例56
習題59
第4章串60
4.1串及基本運算60
4.1.1串的基本概念60
4.1.2串的基本運算60
4.2串的定長度順序存儲及基本運算62
4.2.1串的定長順序存儲62
4.2.2定長順序串的基本運算63
4.2.3模式匹配64
4.3串的堆存儲結構69
4.3.1串名的存儲映像69
4.3.2堆存儲結構71
4.3.3基于堆結構的基本運算71
習題73
第5章數(shù)組、特殊矩陣和廣義表74
5.1多維數(shù)組74
5.1.1數(shù)組的邏輯結構74
5.1.2數(shù)組的內存映像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廣義表的定義和基本運算92
5.4.2廣義表的存儲93
5.4.3廣義表的基本操作的實現(xiàn)95
習題99
第6章二叉樹101
6.1定義與性質101
6.1.1二叉樹的基本概念101
6.1.2二叉樹的主要性質103
6.2基本操作與存儲實現(xiàn)104
6.2.1二叉樹的存儲104
6.2.2二叉樹的基本操作及實現(xiàn)107
6.3二叉樹的遍歷110
6.3.1二叉樹的遍歷方法及遞歸實現(xiàn)110
6.3.2二叉樹遍歷的非遞歸實現(xiàn)112
6.3.3由遍歷序列恢復二叉樹116
6.3.4不用棧的二叉樹遍歷的非遞歸方法118
6.4線索二叉樹118
6.4.1線索二叉樹的定義及結構118
6.4.2線索二叉樹的基本操作實現(xiàn)120
6.5二叉樹的運用126
6.5.1二叉樹遍歷的運用126
6.5.2最優(yōu)二叉樹——哈夫曼樹129
習題135
第7章樹137
7.1樹的概念與表示137
7.1.1樹的定義及相關術語137
7.1.2樹的表示138
7.2樹的基本操作與存儲139
7.2.1樹的基本操作139
7.2.2樹的存儲結構140
7.3樹、森林與二叉樹的轉換143
7.3.1樹轉換為二叉樹143
7.3.2森林轉化為二叉樹144
7.3.3二叉樹轉換為樹和森林145
7.4樹和森林的遍歷146
7.4.1樹的遍歷146
7.4.2森林的遍歷147
7.5樹的應用147
7.5.1判定樹147
7.5.2集合的表示149
7.5.3關系等價求等價類問題151
習題152
第8章圖153
8.1圖的定義和術語153
8.1.1圖的定義153
8.1.2圖的相關術語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關結點和重連通分量172
8.5最小生成樹175
8.5.1最小生成樹的基本概念175
8.5.2構造最小生成樹的Prim算法176
8.5.3構造最小生成樹的Kruskal算法178
8.6最短路徑181
8.6.1從一個源點到其他各點的最短路徑181
8.6.2每一對頂點之間的最短路徑183
8.7有向無環(huán)圖及其應用186
8.7.1有向無環(huán)圖的概念186
8.7.2AOV網(wǎng)與拓撲排序187
8.7.3AOE網(wǎng)與關鍵路徑192
習題196
第9章查找197
9.1基本概念與術語197
9.2靜態(tài)查找表199
9.2.1靜態(tài)查找表結構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
習題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多關鍵碼排序248
10.6.2鏈式基數(shù)排序248
10.7外部排序251
10.7.1外部排序的方法251
10.7.2多路平衡歸并的實現(xiàn)253
習題255