數據結構與算法（C語言版）第2版

《數據結構與算法（C語言版）第2版》是2014年清華大學出版社出版的圖書。

基本介紹

• 書名：數據結構與算法（C語言版）第2版 
• ISBN：9787302220626
• 定價：36元
• 出版社：清華大學出版社
• 出版時間：2014年
• 裝幀：平裝

出版信息

數據結構與算法（C語言版）第2版

作者：郭龍源、胡虛懷、何光明、戴仕明
定價：36元
印次：2-3
ISBN：9787302220626
出版日期：2010.03.01
印刷日期：2014.07.28

圖書簡介

“數據結構與算法”是計算機學科研究的主題之一。本書採用類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 算法概述 6

1.4.2 算法與數據結構之間的關係 7

1.4.3 算法的度量 8

1.5 算法分析 9

1.5.1 數學基礎 9

1.5.2 所需分析的問題 10

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佇列實現方法比較 74

3.4佇列的套用 75

3.4.1排列問題 75

3.4.2非排列問題 76

小結 77

自測題答案 78

編程項目 79

第4章串 80

4.1串的定義 80

4.1.1串 80

4.1.2串的抽象數據類型 81

4.2串的存儲實現 82

4.2.1串的順序存儲結構 82

4.2.2串的鏈式存儲結構 85

4.3串的模式匹配 86

4.3.1簡單模式匹配算法 86

4.3.2KMP算法 88

4.3.3其他模式匹配算法 92

小結 94

自測題答案 95

編程項目 96

第5章數組及廣義表 97

5.1數組的定義 97

5.1.1數組的基本概念 97

5.1.2數組的抽象數據類型 98

5.2數組的順序存儲 99

5.2.1數組的順序存儲方式 99

5.2.2數組的順序存儲的基本操作 100

5.3矩陣的壓縮存儲 102

5.3.1特殊矩陣 102

5.3.2稀疏矩陣 105

5.4廣義表 113

5.4.1廣義表的定義 113

5.4.2廣義表的存儲 114

5.4.3廣義表的基本操作 116

小結 120

自測題答案 121

編程項目 123

第6章樹和二叉樹 124

6.1樹的定義與基本操作 124

6.1.1樹的定義與相關術語 124

6.1.2樹的抽象數據類型 126

6.2二叉樹 127

6.2.1二叉樹的定義與基本操作 127

6.2.2二叉樹的性質 129

6.2.3二叉樹的存儲結構 131

6.2.4二叉樹的遍歷 133

6.2.5線索化二叉樹 138

6.3樹和森林 142

6.3.1樹的存儲結構 142

6.3.2森林、樹、二叉樹的

相互轉化 145

6.3.3樹和森林的遍歷 146

6.4哈夫曼樹與哈夫曼編碼 147

6.4.1哈夫曼樹 148

6.4.2哈夫曼編碼 151

小結 154

自測題答案 156

編程項目 158

第7章圖 159

7.1圖的定義 159

7.1.1圖的定義和相關術語 159

7.1.2圖的抽象數據類型 163

7.2圖的存儲方式 164

7.2.1數組表示法 165

7.2.2鄰接表法 167

7.2.3十字鍊表法 169

7.2.4鄰接多重表 171

7.3圖的遍歷 173

7.3.1深度優先遍歷 173

7.3.2廣度優先遍歷 175

7.4圖的連通性 178

7.4.1無向圖的連通性 178

7.4.2有向圖的連通性 181

7.5最小生成樹 182

7.5.1基本概念 182

7.5.2Prim算法 183

7.5.3Kruskal算法 185

7.6最短路徑 187

7.6.1從某個頂點到其餘各頂點的

最短路徑 187

7.6.2所有點對最短路徑 190

7.7有向無環圖的套用 193

7.7.1拓撲排序 193

7.7.2求解關鍵路徑 197

小結 202

自測題答案 203

編程項目 207

第8章查找 208

8.1線性表上的查找 208

8.1.1順序表上的查找 208

8.1.2有序表上的查找 209

8.1.3索引順序表上的查找 213

8.1.4線性表上的查找算法比較 215

8.2樹上的查找 216

8.2.1二叉排序樹 216

8.2.2平衡二叉樹 224

8.2.3B-樹 231

8.3哈希表 239

8.3.1哈希表概述 239

8.3.2哈希函式的構造 240

8.3.3衝突的解決方法 243

8.3.4哈希表的查找分析 249

小結 250

自測題答案 252

編程項目 255

第9章排序 256

9.1插入排序 256

9.1.1直接插入排序 257

9.1.2折半插入排序 258

9.1.32路插入排序 259

9.1.4希爾排序 261

9.2交換排序 264

9.2.1冒泡排序 264

9.2.2快速排序 265

9.3選擇排序 269

9.3.1直接選擇排序 269

9.3.2樹形選擇排序 271

9.3.3堆排序 272

9.4歸併排序 276

9.5基數排序 279

9.6各種內部排序方法比較 281

9.7外部排序 284

9.7.1選擇外部排序的理由 284

9.7.2簡單外部排序算法 285

9.7.3多路合併排序 287

9.7.4替換-選擇排序 287

小結 290

自測題答案 291

編程項目 294

附錄各章編程項目參考答案 295

參考文獻 388