編輯推薦
內容全麵:介紹瞭數據結構的基本理論與方法,包括綫性錶、棧和隊列、串、數組和廣義錶、樹和二叉樹、圖、查找、內部排序等,內容全麵,循序漸進。
案例豐富:從應用齣發,結閤大量實際案例,對概念與算法進行詳盡描述,加深學生對數據結構基本概念、原理和方法的理解。
插圖易懂:在闡述基本概念、基本理論和算法原理時,配有豐富的插圖,以直觀的方式清晰解釋復雜的算法程序,易於理解。
代碼詳盡:基於C++語言,提供瞭詳盡的算法代碼,且所有算法和實例程序都在VC++6.0環境下編譯通過並運行正確。
習題完備:在每一章末尾都配有圍繞知識點和難點的習題,且習題題型多樣,難度適中,便於鞏固理論知識。
應用突齣:倡導從實用性和實踐性角度學習數據結構,強化算法的實踐與應用,解決學生中普遍存在的“隻懂概念,不會編程”的問題。
內容簡介
本書共分10章,主要包括第1章緒論,第2章綫性錶,第3章棧和隊列,第4章串,第5章數組和廣義錶,第6章 樹和二叉樹,第7章圖,第8章查找,第9章內部排序,第10章算法分析。其內容模塊涵蓋瞭課堂教學、習題課教學、實驗教學、自學輔導、綜閤訓練等。立體化教材的使用在提高教學效率、增強教學效果、加大教學信息量、培養學生的應用與實踐能力。
作者簡介
張 琨,於2003年博士畢業並參加工作,2013年5月獲評為教授,2011年獲評為博士生導師,現任計算機科學與工程學院軟件工程係主任。本人的主要教學經曆如下:數據結構、2005年至今、本科生、周學時4;軟件方法學、2004年至2005年、研究生、周學時4;信息安全理論與技術、2004年至2005年、研究生、周學時4。
目錄
第1章 緒論 1
1.1 數據結構的概念 1
1.1.1 數據結構的發展 1
1.1.2 什麼是數據結構 2
1.1.3 數據結構的研究對象 4
1.1.4 數據結構相關概念及術語 6
1.2 數據類型和抽象數據類型 8
1.2.1 數據類型 8
1.2.2 抽象數據類型 9
1.3 算法和算法分析 11
1.3.1 算法特性 11
1.3.2 算法設計的要求 12
1.3.3 算法的性能分析與度量 12
習題一 17
第2章 綫性錶 21
2.1 綫性錶的基本概念 21
2.1.1 綫性錶的概念 21
2.1.2 綫性錶的抽象數據類型 22
2.2 綫性錶的順序存儲結構 25
2.2.1 綫性錶的順序存儲錶示 26
2.2.2 順序錶的類定義和基本操作 26
2.2.3 順序錶的應用 33
2.2.4 順序錶的特點 35
2.3 綫性錶的鏈式存儲結構 36
2.3.1 單鏈錶 36
2.3.2 靜態鏈錶 43
2.3.3 循環鏈錶 47
2.3.4 雙嚮鏈錶 48
2.4 綫性錶的應用:一元多項式的錶示及
運算 50
2.4.1 一元多項式的錶示 50
2.4.2 一元多項式的實現 51
習題二 56
第3章 棧和隊列 59
3.1 棧的基本概念 59
3.1.1 棧的概念 59
3.1.2 棧的抽象數據類型 60
3.2 棧的順序存儲結構及實現 61
3.2.1 順序棧的概念 61
3.2.2 順序棧的類定義和基本操作 62
3.2.3 順序棧的應用 63
3.3 棧的鏈式存儲結構及實現 68
3.3.1 鏈棧的概念 69
3.3.2 鏈棧的類定義和基本操作 69
3.4 隊列的基本概念 71
3.4.1 隊列的概念 71
3.4.2 隊列的抽象數據類型 71
3.5 隊列的順序存儲 72
3.5.1 循環隊列 73
3.5.2 循環隊列的類定義和基本
操作 74
3.6 隊列的鏈式存儲 76
3.6.1 鏈隊列的概念 76
3.6.2 鏈隊列的類定義和基本操作 76
3.6.3 鏈隊列的應用 78
習題三 83
第4章 串 86
4.1 串的基本概念 86
4.2 串的錶示與實現 88
4.2.1 定長順序存儲錶示 88
4.2.2 堆分配存儲錶示 91
4.2.3 鏈式存儲錶示 92
4.3 串的模式匹配 93
4.3.1 模式匹配方法BF 93
4.3.2 模式匹配方法KMP 94
習題四 96
第5章 數組和廣義錶 101
5.1 數組的基本概念 101
5.1.1 數組的概念 101
5.1.2 數組的抽象數據類型 102
5.2 數組的存儲結構 103
5.3 矩陣的壓縮存儲 105
5.3.1 特殊矩陣的壓縮存儲 106
5.3.2 稀疏矩陣的壓縮存儲 107
5.4 廣義錶的基本概念 115
5.4.1 廣義錶的概念 116
5.4.2 廣義錶的抽象數據類型 116
5.4.3 廣義錶的存儲結構 117
5.4.4 廣義錶的遞歸算法 119
習題五 120
第6章 樹和二叉樹 123
6.1 樹 123
6.1.1 樹的概念 123
6.1.2 基本術語 124
6.1.3 樹的抽象數據類型 125
6.1.4 樹的性質 127
6.1.5 樹的存儲結構 127
6.1.6 樹的遍曆 130
6.1.7 樹的應用 131
6.2 森林 133
6.2.1 森林的存儲結構 134
6.2.2 森林的遍曆 135
6.3 二叉樹 135
6.3.1 二叉樹的概念 135
6.3.2 二叉樹的性質 136
6.3.3 二叉樹的抽象數據類型 140
6.3.4 二叉樹的存儲結構 142
6.3.5 遍曆二叉樹 145
6.3.6 綫索二叉樹 156
6.4 樹、森林與二叉樹的轉換 163
6.4.1 樹與二叉樹的轉換 163
6.4.2 森林與二叉樹的轉換 164
6.5 堆 166
6.6 哈夫曼樹和哈夫曼編碼 167
6.6.1 哈夫曼樹的概念 167
6.6.2 哈夫曼樹的構造 168
6.6.3 哈夫曼編碼 170
習題六 173
第7章 圖 176
7.1 圖的基本概念 176
7.1.1 圖的概念 176
7.1.2 圖的基本術語 177
7.1.3 圖的抽象數據類型 179
7.2 圖的存儲結構 181
7.2.1 圖的順序存儲結構-鄰接
矩陣 181
7.2.2 圖的鏈式存儲結構 184
7.3 圖的遍曆 189
7.3.1 深度優先搜索 189
7.3.2 廣度優先搜索 190
7.3.3 連通分量和重連通分量 191
7.4 最小生成樹 194
7.4.1 最小生成樹的定義 194
7.4.2 最小生成樹的構造算法 195
7.5 有嚮無環圖及其應用 198
7.5.1 AOV網與拓撲排序 199
7.5.2 AOE網與關鍵路徑 202
7.6 最短路徑 206
7.6.1 單源最短路徑 207
7.6.2 每對頂點間的最短路徑 210
習題七 211
第8章 查找 214
8.1 查找的基本概念 214
8.2 靜態查找錶 216
8.2.1 順序查找 216
8.2.2 有序錶的查找 218
8.2.3 分塊查找 219
8.2.4 二叉排序樹 221
8.2.5 B_樹 226
8.3 哈希錶 232
8.3.1 哈希錶的概念 232
8.3.2 哈希函數 233
8.3.3 處理衝突的方法 235
8.3.4 哈希查找算法及分析 237
習題八 239
第9章 內部排序 242
9.1 排序的基本概念 242
9.2 插入排序 244
9.2.1 直接插入排序 244
9.2.2 摺半插入排序 246
9.2.3 錶插入排序 248
9.2.4 希爾排序 251
9.3 交換排序 253
9.3.1 冒泡排序 253
9.3.2 快速排序 255
9.4 選擇排序 258
9.4.1 簡單選擇排序 258
9.4.2 樹形選擇排序 261
9.4.3 堆排序 262
9.5 歸並排序 265
9.6 基數排序 268
9.6.1 多關鍵字的排序 268
9.6.2 鏈式基數排序 269
9.7 各種內部排序方法的比較討論 272
習題九 273
第10章 算法設計與分析 276
10.1 分治法 276
10.2 迴溯法 278
10.3 貪心算法 283
10.4 動態規劃法 285
10.5 分支限界法 288
習題十 294
附錄A 詞匯索引 296
前言/序言
數據結構與算法分析(C++語言版) 下載 mobi epub pdf txt 電子書 格式