《數據結構、算法及套用（第2版）》是科學出版社出版的圖書。
基本介紹
- 中文名：數據結構、算法及套用（第2版）
- 作者：張憲超
- 出版社：科學出版社
- 出版時間：2021年10月1日
- 頁數：366 頁
- 開本：16 開
- 裝幀：平裝
- ISBN：9787030629586
- 正文字數：602000 字
內容簡介,圖書目錄,
內容簡介
本書依據ACM/IEEE計算課程體系規範CC2020，在常用數據結構與算法基礎上，適當補充算法設計方法、計算複雜性理論和若干高級算法，幫助學生系統地學習數據結構與算法的理論知識和實踐技能。全書共7章：第1章概述數據結構與算法的基本知識；第2章講述線性表、棧與佇列等線性結構；第3章講述樹、二叉樹、二叉搜尋樹等；第4章講述圖的基本概念、存儲和最短路徑、最小生成樹等算法；第5章講述查找問題，包括靜態查找、動態查找和散列等；第6章講述排序算法，包括插入排序等基本算法和快速排序等高級算法；第7章講述算法專題，包括算法設計策略、最最佳化問題、計算複雜性理論、隨機算法和近似算法等。
圖書目錄
前言
第1章 緒論 1
1.1 數據結構的概念 1
1.1.1 數據的邏輯結構 2
1.1.2 數據的存儲結構 3
1.2 算法與算法設計 5
1.2.1 算法的概念 5
1.2.2 算法設計 6
1.3 算法分析 8
1.3.1 算法的漸進分析 8
1.3.2 最好、最壞和平均情況 12
1.3.3 時間和空間資源開銷 14
1.4 計算複雜性理論 15
1.5 最最佳化問題 15
1.6 隨機算法和近似算法 16
1.6.1 隨機算法 16
1.6.2 近似算法 17
1.7 數據結構與算法中的唯物辯證法 17
1.8 本書的內容及組織形式 19
習題 20
科學家小傳——高德納 21
第2章 線性表 22
2.1 線性表的概念 22
2.1.1 線性表的定義 22
2.1.2 線性表的抽象數據類型 23
2.1.3 線性表的主要操作 23
2.1.4 線性表的存儲結構 24
2.2 順序表 25
2.2.1 順序表的實現 25
2.2.2 多維數組 30
2.2.3* 矩陣運算 32
2.2.4 順序表的套用 37
2.3 鍊表 40
2.3.1 單鍊表 40
2.3.2 雙向鍊表 47
2.3.3 循環鍊表 49
2.3.4 鍊表的套用 54
2.4 棧 59
2.4.1 順序棧 59
2.4.2 鏈式棧 62
2.4.3 棧與遞歸 63
2.4.4 遞歸的套用 66
2.4.5 棧的套用 69
2.5 佇列 81
2.5.1 順序佇列 81
2.5.2 鏈式佇列 84
2.5.3 佇列的套用 85
2.6 字元串 87
2.6.1 基本概念 87
2.6.2 存儲結構和實現 88
2.6.3 字元串運算的算法實現 92
2.6.4 字元串的模式匹配 96
習題 103
科學家小傳——姚期智 104
第3章 樹 106
3.1 樹的基本概念 106
3.1.1 樹的定義 106
3.1.2 樹的基本性質 107
3.2 二叉樹的概念 108
3.2.1 二叉樹的定義 108
3.2.2 幾種特殊的二叉樹 108
3.2.3 二叉樹的性質 110
3.2.4 二叉樹的存儲結構 111
3.2.5 二叉樹的抽象數據類型 113
3.2.6 二叉樹的遍歷 115
3.2.7 線索二叉樹 120
3.3 二叉樹的套用 123
3.3.1 二叉搜尋樹 123
3.3.2 平衡二叉樹 128
3.3.3* 紅黑樹 138
3.3.4* 基於決策樹的分類方法 144
3.3.5 堆與優先佇列 151
3.3.6 Huffman編碼樹 157
3.4 樹與森林 160
3.4.1 二叉樹、樹、森林之間的轉換 160
3.4.2 樹和森林的遍歷 162
3.4.3 樹的存儲 163
3.5* 樹的套用 165
3.5.1 並查集 165
3.5.2 頻繁模式樹 167
習題 171
科學家小傳——約翰·霍普克羅夫特 173
第4章 圖 175
4.1 圖的基本概念 175
4.1.1 圖的定義和概念 175
4.1.2 圖的抽象數據類型 178
4.2 圖的存儲及基本操作 180
4.2.1 圖的鄰接矩陣表示法 181
4.2.2 圖的鄰接表表示法 183
4.2.3 圖的十字鍊表和鄰接多重表表示法 186
4.3 圖的遍歷 187
4.3.1 深度優先搜尋 187
4.3.2 廣度優先搜尋 189
4.4 最小生成樹 190
4.4.1 Prim算法 191
4.4.2 Kruskal算法 193
4.5 最短路徑 196
4.5.1 單源最短路徑 196
4.5.2 頂點對之間的最短路徑 199
4.6 拓撲排序 200
4.7 關鍵路徑 203
4.8* 最大流 207
4.8.1 流網路 207
4.8.2 最大流最小割定理 208
4.8.3 Ford-Fulkerson方法 209
4.8.4 推送-重貼標籤算法 212
4.9* 圖的社區發現 216
4.9.1 圖劃分方法 216
4.9.2 基於模組度的方法 218
習題 220
科學家小傳——艾茲格·迪傑斯特拉 221
第5章 查找 223
5.1 靜態查找 224
5.1.1 順序查找法 224
5.1.2 折半查找法 225
5.1.3 分塊查找法 228
5.2 動態查找 229
5.2.1 B-樹 230
5.2.2 B+樹 239
5.3 散列 243
5.3.1 散列的概念 243
5.3.2 散列函式 244
5.3.3 衝突解決方法 246
5.3.4 散列算法設計與分析 251
5.3.5* 散列的套用 254
習題 257
科學家小傳——羅伯特·塔揚 258
第6章 排序 259
6.1 排序的基本概念 259
6.2 插入排序 260
6.2.1 直接插入排序 260
6.2.2 折半插入排序 261
6.2.3 希爾排序 263
6.3 交換排序 266
6.3.1 冒泡排序 266
6.3.2 快速排序 268
6.3.3 快速排序算法改進 275
6.4 選擇排序 278
6.4.1 簡單選擇排序 279
6.4.2 堆排序 280
6.5 歸併排序 283
6.5.1 有序數組歸併的方法 283
6.5.2 自頂向下的歸併排序 285
6.5.3 自底向上的歸併排序 286
6.6 比較排序算法的時間複雜度下界 287
6.7 基數排序 288
6.8 各種內部排序算法的比較和選擇 292
6.9 排序的套用 294
習題 295
科學家小傳——查爾斯·霍爾 296
第7章* 算法專題 298
7.1 算法設計基本策略 298
7.1.1 貪心策略 298
7.1.2 分治策略 302
7.1.3 動態規劃 308
7.1.4 回溯 312
7.1.5 分支限界法 317
7.2 最最佳化問題 324
7.2.1 線性規劃 324
7.2.2 整數規劃 334
7.2.3 組合最佳化 336
7.2.4 非線性規劃 338
7.3 計算複雜性理論 340
7.3.1 計算模型 341
7.3.2 P問題與NP問題 342
7.3.3 NP完備理論 342
7.3.4 典型NP完全問題 345
7.4 隨機算法 346
7.4.1 隨機數的產生 346
7.4.2 隨機變數 349
7.4.3 蒙特卡羅算法 350
7.4.4 拉斯維加斯算法 354
7.5 近似算法 359
習題 363
科學家小傳——史蒂芬·庫克 365
參考文獻 366
