《數據結構與算法（C語言版）（第3版）》是2015年7月清華大學出版社出版的圖書，作者是陳琳琳、李建林、孫啟虎、李橙、郭龍源。
基本介紹
- 書名：數據結構與算法（C語言版）（第3版）
- 作者：陳琳琳、李建林、孫啟虎、李橙、郭龍源
- ISBN：9787302402534
- 定價：42元
- 出版社：清華大學出版社
- 出版時間：2015年7月
內容簡介,圖書目錄,
內容簡介
“數據結構與算法”是計算機學科研究的主題之一。本書採用類C語言描述，系統地介紹了各種數據結構和排序、查找算法。全書共分為9章，主要內容包括數據結構與算法簡介、線性表、棧和佇列、串、數組及廣義表、樹和二叉樹、圖、查找和排序等。對於各種數據結構，本書給出了基本概念、抽象數據類型以及相關的操作，並且對各種算法的運行時間進行了分析。
本書對數據結構中的重點和難點內容進行了深入的剖析，著重培養學生的動手能力，對經典算法、重點算法及套用算法進行了詳細的講解，以使學生更好地掌握數據結構的套用。
本書可作為計算機及相關專業的大學本科教材，也可作為套用型專業以及成人教育、工程技術人員的培訓教材。
圖書目錄
第1章 緒論 1
1.1 學習數據結構與算法的意義 1
1.1.1 學習數據結構的意義 1
1.1.2 學習算法的意義 2
1.2 數據結構 3
1.2.1 數據結構概述 3
1.2.2 基本概念 3
1.3 抽象數據類型 5
1.4 算法 6
1.4.1 算法概述 7
1.4.2 算法與數據結構之間的關係 8
1.4.3 算法的度量 8
1.5 算法分析 9
1.5.1 數學基礎 9
1.5.2 所需分析的問題 11
1.5.3 運行時間的計算 11
1.5.4 檢驗你的分析 13
小結 15
自測題答案 16
編程項目 17
第2章 線性表 18
2.1 線性表的定義 18
2.1.1 線性表概述 18
2.1.2 線性表的抽象數據類型 19
2.1.3 線性表的相關操作 20
2.2 線性表的順序存儲結構 22
2.2.1 線性表的順序存儲結構 22
2.2.2 相關操作的實現 23
2.2.3 順序存儲結構的分析 29
2.3 線性表的鏈式存儲結構 29
2.3.1 線性鍊表與相關操作實現 29
2.3.2 雙向鍊表與相關操作實現 38
2.3.3 循環鍊表及其相關操作的
實現 41
2.3.4 鏈式存儲結構分析 42
2.4 線性表的套用 43
2.4.1 一元多項式的抽象數據類型 43
2.4.2 多項式的順序表實現 43
小結 46
自測題答案 47
編程項目 48
第3章 棧和佇列 49
3.1 棧 49
3.1.1 棧概述 49
3.1.2 棧的實現 50
3.1.3 棧的實現方式比較 54
3.2 棧的套用 55
3.2.1 平衡符號 55
3.2.2 表達式求值 57
3.2.3 函式調用 61
3.2.4 遞歸與棧 62
3.3 佇列 67
3.3.1 佇列概述 67
3.3.2 佇列的實現 69
3.3.3 佇列實現方法比較 76
3.4 佇列的套用 76
3.4.1 排列問題 76
3.4.2 非排列問題 77
小結 79
自測題答案 79
編程項目 81
第4章 串 82
4.1 串的定義 82
4.1.1 串 82
4.1.2 串的抽象數據類型 83
4.2 串的存儲實現 84
4.2.1 串的順序存儲結構 84
4.2.2 串的鏈式存儲結構 87
4.3 串的模式匹配 88
4.3.1 簡單模式匹配算法 88
4.3.2 KMP算法 90
4.3.3 其他模式匹配算法 94
小結 96
自測題答案 97
編程項目 98
第5章 數組及廣義表 99
5.1 數組的定義 99
5.1.1 數組的基本概念 99
5.1.2 數組的抽象數據類型 100
5.2 數組的順序存儲 101
5.2.1 數組的順序存儲方式 101
5.2.2 數組的順序存儲的
基本操作 102
5.3 矩陣的壓縮存儲 104
5.3.1 特殊矩陣 104
5.3.2 稀疏矩陣 107
5.4 廣義表 115
5.4.1 廣義表的定義 115
5.4.2 廣義表的存儲 117
5.4.3 廣義表的基本操作 118
小結 122
自測題答案 123
編程項目 125
第6章 樹和二叉樹 126
6.1 樹的定義與基本操作 126
6.1.1 樹的定義與相關術語 126
6.1.2 樹的抽象數據類型 128
6.2 二叉樹 129
6.2.1 二叉樹的定義與基本操作 129
6.2.2 二叉樹的性質 131
6.2.3 二叉樹的存儲結構 133
6.2.4 二叉樹的遍歷 135
6.2.5 線索化二叉樹 140
6.3 樹和森林 144
6.3.1 樹的存儲結構 144
6.3.2 森林、樹、二叉樹的
相互轉化 147
6.3.3 樹和森林的遍歷 148
6.4 哈夫曼樹與哈夫曼編碼 149
6.4.1 哈夫曼樹 150
6.4.2 哈夫曼編碼 153
小結 157
自測題答案 158
編程項目 160
第7章 圖 161
7.1 圖的定義 161
7.1.1 圖的定義和相關術語 161
7.1.2 圖的抽象數據類型 165
7.2 圖的存儲方式 166
7.2.1 數組表示法 167
7.2.2 鄰接表法 169
7.2.3 十字鍊表法 171
7.2.4 鄰接多重表 173
7.3 圖的遍歷 175
7.3.1 深度優先遍歷 175
7.3.2 廣度優先遍歷 177
7.4 圖的連通性 180
7.4.1 無向圖的連通性 180
7.4.2 有向圖的連通性 183
7.5 最小生成樹 184
7.5.1 基本概念 184
7.5.2 Prim算法 185
7.5.3 Kruskal算法 187
7.6 最短路徑 189
7.6.1 從某個頂點到其餘各頂點的
最短路徑 189
7.6.2 所有點對的最短路徑 192
7.7 有向無環圖的套用 195
7.7.1 拓撲排序 195
7.7.2 求解關鍵路徑 199
小結 204
自測題答案 205
編程項目 209
第8章 查找 210
8.1 線性表上的查找 210
8.1.1 順序表上的查找 210
8.1.2 有序表上的查找 211
8.1.3 索引順序表上的查找 215
8.1.4 線性表上的查找算法比較 217
8.2 樹上的查找 218
8.2.1 二叉排序樹 218
8.2.2 平衡二叉樹 226
8.2.3 B-樹 233
8.3 哈希表 241
8.3.1 哈希表概述 241
8.3.2 哈希函式的構造 242
8.3.3 衝突的解決方法 245
8.3.4 哈希表的查找分析 251
小結 252
自測題答案 254
編程項目 257
第9章 排序 258
9.1 插入排序 258
9.1.1 直接插入排序 259
9.1.2 折半插入排序 260
9.1.3 2路插入排序 261
9.1.4 希爾排序 263
9.2 交換排序 266
9.2.1 冒泡排序 266
9.2.2 快速排序 267
9.3 選擇排序 271
9.3.1 直接選擇排序 271
9.3.2 樹形選擇排序 273
9.3.3 堆排序 274
9.4 歸併排序 278
9.5 基數排序 281
9.6 各種內部排序方法比較 283
9.7 外部排序 286
9.7.1 選擇外部排序的理由 286
9.7.2 簡單外部排序算法 287
9.7.3 多路合併排序 289
9.7.4 替換-選擇排序 289
小結 292
自測題答案 293
編程項目 296
附錄 各章編程項目參考答案 297
參考文獻 391
