本書把數(shù)據(jù)結構的原理和算法分析技術有機地結合在一起,系統(tǒng)地介紹各種數(shù)據(jù)結構及各種數(shù)據(jù)結構的相關算法,使用C語言作為算法描述語言,通過C語言實現(xiàn)了具體算法,能夠更好地讓學生理解各種數(shù)據(jù)結構的基本描述方法,借助抽象數(shù)據(jù)類型,從邏輯結構的角度系統(tǒng)地介紹線性表、棧、隊列、串、數(shù)組、矩陣、廣義表、二叉樹、樹和圖等各種基本數(shù)據(jù)結構;從算法的角度討論查找方法和排序算法;從應用的角度介紹了一些具體的應用在C語言下的代碼實現(xiàn)。
全書共分三部分:第1部分(第1章)為基本概念介紹部分,介紹數(shù)據(jù)結構、抽象數(shù)據(jù)類型以及算法的基本概念;第2部分(第2~8章)為基本數(shù)據(jù)結構部分,重點介紹線性表、棧、隊列、串、數(shù)組、矩陣、廣義表、二叉樹、樹和圖等各種基本數(shù)據(jù)結構,并且附帶有具體的算法實現(xiàn)的代碼;第3部分(第9章和第10章)為算法應用設計,重點介紹順序查找、折半查找、插值查找、斐波那契查找、分塊查找等靜態(tài)查找的具體算法,介紹在二叉排序樹、平衡二叉樹上的動態(tài)查找算法以及哈希表查找算法等。全書提供了大量應用實例,每章后均附有習題。
1、使用大量的示例和圖表闡明各種概念及理論。
2、本書以傳統(tǒng)的數(shù)據(jù)結構的主要內容為主線,在充分討論結構的邏輯特征與存儲表示的基礎上,突出算法重點。
3、注重算法實現(xiàn)的源碼設計,在學習算法的同時,了解算法的設計實現(xiàn)過程,用C++語言完成數(shù)據(jù)結構的描述和實現(xiàn)。
4、本書更加強調數(shù)據(jù)結構的應用,對不同的數(shù)據(jù)結構類型設計多個應用實例,每一算法或程序的編寫力求高效、易讀,并遵循程序設計的規(guī)范,從而幫助讀者將數(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