《算法與數據結構（C++語言版）》是2018年10月電子工業出版社出版的圖書，作者是馮廣慧。
基本介紹
- 中文名：算法與數據結構（C++語言版）
- 作者：馮廣慧
- 出版社：電子工業出版社
- 出版時間：2018年10月
- 頁數：344 頁
- 定價：56 元
- 開本：16 開
- ISBN：9787121350719
內容簡介,圖書目錄,
內容簡介
本書按照“全國碩士研究生招生考試計算機科學與技術學科聯考計算機學科專業基礎綜合考試大綱”的要求編寫，基本涵蓋所有知識點，並加入部分高校及全國統一考試真題作為自測題，同時給出參考答案和題目解析。本書主要介紹各種常用的經典數據結構（如線性表、棧、佇列、串、數組、樹、圖、集合等）和算法，並在時間複雜度和空間複雜度之間進行平衡與取捨。
本書將C++語言作為數據結構的算法描述語言，將數據結構與面向對象技術有機結合。書中的算法講解都有完整的C++代碼實現，並在Visual Studio 2010環境下編譯通過。
圖書目錄
第1章 概論 1
1.1 什麼是數據結構 1
1.2 基本概念和術語 4
1.3 算法和算法分析 7
1.3.1 算法的定義及特性 7
1.3.2 算法的設計要求 8
1.3.3 算法效率的衡量方法 9
1.3.4 算法的時間複雜度 10
1.3.5 算法的空間複雜度 15
1.4 抽象數據類型 16
習題 18
第2章 線性表 20
2.1 線性表的類型定義 20
2.1.1 線性表的概念 20
2.1.2 線性表的抽象數據類型 21
2.2 線性表的順序表示和實現 22
2.2.1 線性表的順序表示 22
2.2.2 順序表基本運算的實現 23
2.3 線性表的鏈式表示和實現 28
2.3.1 線性表的鏈式表示 29
2.3.2 單鍊表上基本運算的實現 32
2.4 雙鍊表 40
2.5 循環鍊表 44
2.6 線性表實現方法的比較 46
2.7 算法設計舉例 47
習題 52
第3章 棧和佇列 55
3.1 棧 55
3.1.1 棧的類型定義 55
3.1.2 順序棧的表示和實現 57
3.1.3 鏈棧的表示和實現 60
3.2 棧的套用舉例 62
3.2.1 十進制數轉換為其他進制數 62
3.2.2 表達式中括弧的匹配檢查 63
3.2.3 表達式求值 64
3.2.4 利用棧消除遞歸 72
3.3 佇列 77
3.3.1 佇列的類型定義 77
3.3.2 循環佇列—佇列的順序表示和
實現 78
3.3.3 鏈佇列—佇列的鏈式表示和
實現 82
3.4 算法設計舉例 83
習題 87
第4章 串 90
4.1 串的基本概念 90
4.2 串的表示和實現 91
4.2.1 串的順序存儲結構 91
4.2.2 串的鏈式存儲結構 94
4.3 串的模式匹配 95
4.3.1 樸素的模式匹配算法 95
4.3.2 KMP算法 96
習題 101
第5章 數組 104
5.1 數組的基本概念 104
5.2 矩陣的壓縮存儲 107
5.2.1 特殊矩陣 107
5.2.2 稀疏矩陣 110
5.3 算法設計舉例 117
習題 121
第6章 樹和二叉樹 124
6.1 樹的概念 124
6.2 二叉樹的概念和性質 126
6.2.1 二叉樹的概念和抽象數據
類型 126
6.2.2 二叉樹的性質 129
6.3 二叉樹的表示和實現 131
6.3.1 二叉樹的存儲結構 131
6.3.2 二叉樹的遍歷運算 133
6.3.3 二叉樹的其他基本運算 140
6.4 樹和森林 142
6.4.1 樹的存儲結構 143
6.4.2 樹、森林和二叉樹的相互
轉換 146
6.4.3 樹和森林的遍歷運算 148
6.4.4 樹和森林的其他基本運算 151
*6.5 線索二叉樹 154
6.5.1 線索二叉樹的概念 154
6.5.2 線索二叉樹的基本運算 157
6.6 算法設計舉例 161
習題 162
第7章 樹和二叉樹的套用 166
*7.1 表達式樹 166
7.2 哈夫曼樹和哈夫曼編碼 171
7.2.1 哈夫曼樹 171
7.2.2 哈夫曼編碼 175
7.3 堆和優先權佇列 178
7.3.1 堆 178
7.3.2 優先權佇列 179
*7.4 並查集 184
7.5 算法設計舉例 187
習題 189
第8章 圖 191
8.1 圖的概念 191
8.2 圖的存儲結構 196
8.2.1 鄰接矩陣 196
8.2.2 鄰接表 200
*8.2.3 十字鍊表 205
*8.2.4 鄰接多重表 205
8.3 圖的遍歷 206
8.3.1 深度優先遍歷 207
8.3.2 廣度優先遍歷 209
8.3.3 圖的連通分量和生成樹 212
習題 213
第9章 圖的套用 217
9.1 最小生成樹 217
9.1.1 最小生成樹的概念 217
9.1.2 Prim算法 218
9.1.3 Kruskal算法 222
9.2 有向無環圖及其套用 225
9.2.1 拓撲排序 225
9.2.2 關鍵路徑 230
9.3 最短路徑 236
9.3.1 單源點最短路徑 236
9.3.2 每對頂點之間的最短路徑 240
習題 243
第10章 集合與查找 247
10.1 基本概念 247
10.2 靜態查找表上的查找 248
10.2.1 順序查找 248
10.2.2 折半查找 250
10.2.3 分塊查找 254
10.3 動態查找表上的查找 256
10.3.1 二叉查找樹 256
10.3.2 平衡二叉樹 263
*10.3.3 B樹 275
*10.3.4 B+樹 280
*10.3.5 字典樹 281
10.4 算法設計舉例 282
習題 285
第11章 散列表 288
11.1 散列表的概念 288
11.2 構造散列函式的方法 289
11.2.1 直接定址法 289
11.2.2 摺疊法 289
11.2.3 數字分析法 289
11.2.4 平方取中法 290
11.2.5 除留餘數法 290
11.3 解決衝突的方法 291
11.3.1 閉散列法 291
11.3.2 開散列法 293
11.4 散列表的實現 294
11.4.1 閉散列表的表示和實現 294
11.4.2 開散列表的表示和實現 298
11.4.3 閉散列表與開散列表的
比較 302
11.5 散列表的查找性能分析 302
習題 303
第12章 排序 306
12.1 排序的基本概念 306
12.2 插入排序 307
12.2.1 直接插入排序 307
12.2.2 折半插入排序 308
12.2.3 希爾排序 309
12.3 交換排序 310
12.3.1 冒泡排序 310
12.3.2 快速排序 311
12.4 選擇排序 315
12.4.1 直接選擇排序 315
12.4.2 堆排序 316
*12.4.3 錦標賽排序 320
12.5 歸併排序 320
*12.6 基數排序 322
12.7 各種內部排序方法的比較 324
*12.8 外部排序 327
12.8.1 置換選擇排序 328
12.8.2 多路歸併排序 330
習題 331
附錄A 上機實驗參考題目 334
參考文獻 336
