《算法與數據結構（C 語言版）》是2018年出版的圖書，作者是馮廣慧等。本書主要介紹各種常用的經典數據結構（如線性表、棧、佇列、串、數組、樹、圖、集合等）和算法。
基本介紹
- 書名：算法與數據結構（C 語言版）
- 作者：馮廣慧 等
- ISBN：9787121350719
- 頁數：344
- 出版時間：2018年10月
- 開本：16開
內容簡介,目錄,
內容簡介
本書按照“全國碩士研究生招生考試計算機科學與技術學科聯考計算機學科專業基礎綜合考試大綱”的要求編寫，基本涵蓋所有知識點，並加入部分高校及全國統一考試真題作為自測題，同時給出參考答案和題目解析。本書主要介紹各種常用的經典數據結構（如線性表、棧、佇列、串、數組、樹、圖、集合等）和算法，並在時間複雜度和空間複雜度之間進行平衡與取捨。 本書將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
