圖書信息
出版社: 人民郵電出版社; 第1版 (2008年11月1日)
叢書名: 高等院校計算機教材系列
平裝: 354頁
正文語種: 簡體中文
開本: 16
ISBN: 9787115186430, 711518643X
條形碼: 9787115186430
尺寸: 25.7 x 18.3 x 1.5 cm
重量: 544 g
作者簡介
余臘生，中南大學副教授。主講計算機專業本科“數據結構”和“計算機系統結構”課程以及研究生“軟體構件技術”課程多年，其中“數據結構”課程被評為“中南大學精品課程”。主持和參加了包括國家863套用示範工程和湖南省自然科學基金項目在內的10多個科研項目，在國內外專業核心刊物發表論文30多篇，EI檢索多篇。主要研究方向為Agerlt理論及其計算技術、結構與算法、網路資料庫技術等。
內容簡介
《數據結構基於C++模板類的實現》採用能夠自然體現抽象數據類型概念的C++ 語言作為算法描述語言，把數據結構的原理和算法分析技術有機地結合在一起。全書內容包括線性表、棧、佇列、遞歸、廣義表、字元串、數組、樹、圖、查找以及各種排序算法，並給出了相關的實驗指導。書中還引入了一些比較高級的數據結構和相關的算法分析技術。
《數據結構基於C++模板類的實現》可作為高等院校計算機或相關專業的教材，也可以作為其他程式類課程的輔導教材，同時也適用準備參加研究生入學考試、自學考試和各類程式設計競賽的人員閱讀。
目錄
第1章 緒論 1
1.1 數據結構的概念 1
1.1.1 為什麼要學習數據結構 2
1.1.2 相關概念和術語 4
1.2 抽象數據類型 6
1.2.1 數據類型 6
1.2.2 抽象數據類型 7
1.3 算法和算法分析 10
1.3.1 問題求解概述 10
1.3.2 算法特性 10
1.3.3 常見的算法類型 11
1.3.4 算法描述 12
1.3.5 算法性能分析與度量 12
習題 15
實習題 16
第2章 線性表 17
2.1 線性表的邏輯結構 17
2.1.1 線性表的定義 17
2.1.2 線性表的基本操作 17
2.2 線性表的順序存儲及操作實現 20
2.2.1 順序表 20
2.2.2 順序表上基本操作的實現 22
2.2.3 順序表套用舉例 25
2.2.4 小結 25
2.3 線性表的鏈式存儲及操作實現 26
2.3.1 單向鍊表 26
2.3.2 單向鍊表上基本操作的實現 28
2.3.3 循環鍊表 34
2.3.4 雙向鍊表 37
2.3.5 靜態鍊表 41
2.3.6 單向鍊表套用舉例 44
2.4 順序表和鍊表的選取 47
習題 47
實習題 49
第3章 棧和佇列 50
3.1 棧 50
3.1.1 棧的定義及基本操作 50
3.1.2 棧的存儲及操作實現 51
3.1.3 棧套用舉例 56
3.2 佇列 66
3.2.1 佇列的定義及基本操作 66
3.2.2 佇列的存儲及操作實現 66
3.2.3 優先佇列 72
3.2.4 雙端佇列 74
3.2.5 佇列套用舉例 74
習題 79
實習題 80
第4章 遞歸和廣義表 82
4.1 何謂遞歸 82
4.2 遞歸的執行過程 84
4.3 尾部遞歸函式 88
4.4 遞歸的套用 89
4.4.1 漢諾塔問題 89
4.4.2 迷宮問題 90
4.4.3 n皇后問題 92
4.5 遞歸程式到非遞歸程式的轉換 94
4.5.1 簡單轉換 95
4.5.2 複雜轉換 95
4.5.3 轉化的形式化步驟 97
4.6 廣義表 101
4.6.1 廣義表的定義及基本操作 101
4.6.2 廣義表的存儲 103
4.6.3 廣義表有關操作的實現 105
習題 107
實習題 108
第5章 字元串 110
5.1 字元串及其基本操作 110
5.1.1 字元串的基本概念 110
5.1.2 字元串的基本操作 111
5.2 字元串的定長順序存儲及基本操作 112
5.2.1 字元串的定長順序存儲 112
5.2.2 定長順序串的基本操作 114
5.2.3 模式匹配 114
5.3 字元串的堆存儲 123
5.3.1 字元串名的存儲映像 123
5.3.2 堆存儲結構 124
5.3.3 基於堆存儲結構的基本操作 125
5.4 字元串的鏈式存儲 128
5.5 字元串的套用 128
5.5.1 中文分詞 128
5.5.2 遺傳算法 130
習題 131
實習題 133
第6章 數組與矩陣 134
6.1 數組 134
6.1.1 數組的邏輯結構 134
6.1.2 數組的記憶體映像 137
6.2 特殊矩陣的壓縮存儲 139
6.2.1 對角矩陣 139
6.2.2 三對角矩陣 140
6.2.3 三角矩陣 141
6.2.4 對稱矩陣 142
6.3 稀疏矩陣 143
6.3.1 稀疏矩陣的三元組表存儲 143
6.3.2 稀疏矩陣的鏈式存儲 149
6.3.3 稀疏矩陣的十字鍊表存儲 149
習題 155
實習題 156
第7章 樹與二叉樹 157
7.1 樹的定義及表示 157
7.1.1 樹的定義 157
7.1.2 樹的表示 158
7.1.3 樹的特點 159
7.1.4 與樹相關的基本術語 159
7.1.5 樹形結構的邏輯特徵 160
7.1.6 樹的存儲 161
7.2 二叉樹 165
7.2.1 二叉樹的定義及相關概念 165
7.2.2 二叉樹的主要性質 167
7.2.3 二叉樹的存儲 168
7.2.4 二叉樹的基本操作及實現 171
7.3 二叉樹的遍歷 171
7.3.1 二叉樹的遍歷方法及遞歸實現 171
7.3.2 二叉樹遍歷的非遞歸實現 173
7.3.3 遍歷算法套用舉例 176
7.3.4 由遍歷序列恢復二叉樹 178
7.3.5 不用棧的二叉樹遍歷非遞歸方法 179
7.4 線索二叉樹 179
7.4.1 線索二叉樹的定義及結構 179
7.4.2 線索二叉樹的基本操作及實現 181
7.5 最優二叉樹——赫夫曼樹 187
7.5.1 赫夫曼樹的基本概念 187
7.5.2 赫夫曼樹的構造算法 189
7.5.3 赫夫曼樹的套用 190
7.6 樹、森林與二叉樹的轉換 193
7.6.1 樹、森林到二叉樹的轉換 193
7.6.2 二叉樹到樹和森林的轉換 194
7.7 樹和森林的遍歷 195
7.7.1 樹的遍歷 195
7.7.2 森林的遍歷 196
7.7.3 樹和森林的層次次序遍歷 197
7.8 樹的套用 197
7.8.1 判定樹 197
7.8.2 集合的表示 198
習題 200
實習題 202
第8章 圖 203
8.1 基本概念 203
8.1.1 圖的定義和術語 203
8.1.2 圖的抽象數據類型 207
8.2 圖的存儲結構 208
8.2.1 鄰接矩陣 208
8.2.2 鄰接表 212
8.2.3 鄰接矩陣和鄰接表的比較 215
8.2.4 十字鍊表 216
8.2.5 鄰接多重表 217
8.2.6 索引表 218
8.3 圖的遍歷 218
8.3.1 深度優先搜尋 219
8.3.2 廣度優先搜尋 220
8.4 圖的連通性 221
8.4.1 無向圖的連通性 221
8.4.2 有向圖的連通性 222
8.4.3 生成樹和生成森林 223
8.4.4 關節點和雙連通分量 224
8.5 最小生成樹 226
8.5.1 最小生成樹的基本概念 226
8.5.2 Prim算法 227
8.5.3 kruskal算法 230
8.6 最短路徑 231
8.6.1 無權最短路徑問題 232
8.6.2 從一個源點到其他各頂點的最短路徑 233
8.6.3* 邊上權值為任意值的單源最短路徑問題 236
8.6.4* 負權最短路徑問題 237
8.6.5 每對頂點之間的最短路徑 239
8.7 DAG及其套用 240
8.7.1 DAG的概念 240
8.7.2 AOV網與拓撲排序 241
8.7.3 AOE圖與關鍵路徑 246
習題 250
實習題 253
第9章 查找 254
9.1 基本概念 254
9.2 靜態查找表 255
9.2.1 靜態查找表結構 255
9.2.2 順序查找 256
9.2.3 有序表的二分查找 257
9.2.4 有序表的斐波那契查找和插值查找 260
9.2.5 分塊查找 261
9.3 動態查找表 262
9.3.1 二叉排序樹 263
9.3.2 平衡二叉樹 267
9.3.3* 紅黑樹 280
9.3.4 B樹 289
9.3.5 B+樹 298
9.4 散列表查找 299
9.4.1 散列表與散列方法 299
9.4.2 常用的散列函式 300
9.4.3 處理衝突的方法 302
9.4.4 散列表的查找分析 306
9.4.5 散列表的操作 308
習題 310
實習題 311
第10章 排序 312
10.1 基本概念 312
10.2 插入排序 314
10.2.1 直接插入排序 314
10.2.2 二分插入排序 316
10.2.3 表插入排序 317
10.2.4 謝爾排序 319
10.3 交換排序 321
10.3.1 冒泡排序 321
10.3.2 快速排序 323
10.4 選擇排序 326
10.4.1 線性選擇排序 326
10.4.2 交換線性選擇排序 328
10.4.3 樹形選擇排序 329
10.4.4 堆排序 331
10.4.5 用堆實現的優先佇列 336
10.5 兩路歸併排序 337
10.6 分配排序 339
10.6.1 多鍵排序 339
10.6.2 桶排序 340
10.6.3 鏈式基數排序 340
10.7 其他排序方法 342
10.7.1 二叉樹排序法 342
10.7.2 計數排序法 342
10.8 各種內排序方法的比較 344
10.9* 外排序 346
10.9.1 外排序的方法 346
10.9.2 自然歸併排序法 347
10.9.3 k路歸併法 347
10.9.4 多段歸併法 349
習題 352
實習題 354
參考文獻 355
附錄 實驗指導(圖靈網站下載)
