數據結構

作者：路瑩、劉娜、姚春龍

定價：33元

印次：1-1

ISBN：9787302320050

出版日期：2013.07.01

印刷日期：2013.06.24

“數據結構”課程是計算機程序設計的重要理論基礎，它不僅是計算機專業重要的專業基礎課程與核心課程，同時也是信息管理專業以及數學統計專業的主要課程。全書共分為9章。第1章緒論，以非數值計算的程序設計解決實際問題為例，說明什麼是數據結構，數據結構的研究內容以及相關概念，最後討論了演演算法分析；第2～7章分別論述了線性表、棧和隊列、串及模式匹配、數組和廣義表、樹與二叉樹、圖等基本數據類型以及相關的數據操作。對於典型操作，書中給出了詳盡的演演算法分析過程和演演算法描述；第8章和第9章討論了程序設計中常見的查找和排序問題，並就典型方法進行詳盡的演演算法分析和描述。

第1章緒論1

1.1什麼是數據結構1

1.2基本術語4

1.3演演算法和演演算法分析6

1.3.1演演算法7

1.3.2演演算法設計的要求7

1.3.3演演算法效率的度量7

小結9

習題9

第2章線性表11

2.1線性表的定義和基本操作11

2.1.1線性表的定義11

2.1.2線性表的抽象數據類型12

2.2線性表的順序存儲結構12

2.2.1順序表的結構13

2.2.2順序表基本操作的實現14

2.2.3順序表的一個簡單應用19

2.3線性表的鏈式存儲結構22

2.3.1線性鏈表23

2.3.2線性鏈表的一個應用實例29

2.3.3循環鏈表和雙向鏈表34

2.3.4循環鏈表的一個應用實例37

小結40

習題41

第3章棧和隊列45

3.1棧45

3.1.1棧的定義45

3.1.2棧的抽象數據類型45

3.1.3棧的表示和實現46

3.2棧的應用舉例513.2.1數制轉換51

3.2.2括弧匹配檢測53

3.2.3表達式求值54

3.2.4迷宮求解60

3.3棧與遞歸66

3.3.1函數的嵌套調用66

3.3.2遞歸調用66

3.4隊列71

3.4.1隊列的定義71

3.4.2隊列的抽象數據類型71

3.4.3鏈隊列——隊列的鏈式表示和實現72

3.4.4循環隊列——隊列的順序表示和實現75

3.4.5一個隊列的應用實例78

小結83

習題83

第4章串及模式匹配86

4.1串類型的定義86

4.2串的存儲結構及其運算87

4.2.1串的定長順序存儲87

4.2.2堆的分配存儲結構89

4.2.3串...

4.3串的模式匹配91

4.3.1簡單的模式匹配演演算法92

4.3.2改進后的模式匹配演演算法94

4.4串操作應用舉例100

小結107

習題107

第5章數組和廣義表108

5.1數組的定義和運算108

5.2數組的順序存儲結構109

5.3矩陣的壓縮存儲110

5.3.1特殊矩陣110

5.3.2稀疏矩陣114

5.4廣義表118

5.4.1廣義表的定義118

5.4.2廣義表的運算119

5.5廣義表的存儲結構119

小結121

習題121

第6章樹與二叉樹122

6.1樹的基本概念122

6.2二叉樹124

6.2.1二叉樹的定義124

6.2.2二叉樹的性質125

6.2.3二叉樹的存儲結構126

6.3遍歷二叉樹和線索二叉樹129

6.3.1二叉樹的遍歷方法與演演算法實現129

6.3.2二叉樹的非遞歸演演算法實現131

6.3.3由遍歷序列恢復二叉樹135

6.3.4線索二叉樹137

6.4樹和森林138

6.4.1樹的存儲表示138

6.4.2森林與二叉樹的轉換140

6.4.3樹和森林的遍歷142

6.5哈夫曼樹及其應用144

6.5.1最優二叉樹144

6.5.2哈夫曼編碼146

6.6回溯法與樹的遍歷149

小結150

習題150

第7章圖152

7.1圖的基本概念152

7.2圖的存儲結構及基本操作155

7.2.1鄰接矩陣155

7.2.2鄰接表158

7.2.3有向圖的十字鏈表162

7.2.4鄰接多重表166

7.3圖的遍歷167

7.3.1深度優先搜索（Depth_FirstSearch）168

7.3.2廣度優先搜索（Breadth_FirstSearch）170

7.4圖的連通性問題174

7.4.1無向圖的連通性174

7.4.2有向圖的連通性174

7.4.3生成樹和生成森林175

7.5有向無環圖及其應用185

7.5.1拓撲排序186

7.5.2關鍵路徑192

7.6最短路徑195

7.6.1從一個源點到其餘各頂點的最短路徑195

7.6.2每一對頂點間的最短路徑197

小結199

習題199

第8章查找200

8.1基本概念200

8.2靜態查找表201

8.2.1順序查找201

8.2.2有序表的查找203

8.2.3索引順序表的查找207

8.3動態查找表210

8.3.1二叉排序樹210

8.3.2平衡二叉樹221

8.3.3B-樹和B+樹230

8.4哈希表236

8.4.1哈希表和哈希查找237

8.4.2常用的哈希函數238

8.4.3處理衝突的方法241

8.4.4哈希表的查找及其分析244

小結245

習題245

第9章內部排序247

9.1排序的基本概念247

9.2插入排序248

9.2.1直接插入排序248

9.2.2希爾排序251

9.3交換排序253

9.3.1冒泡排序253

9.3.2快速排序255

9.4選擇排序259

9.4.1簡單選擇排序259

9.4.2堆排序261

9.5歸併排序265

9.6基數排序267

9.6.1多關鍵字排序的演演算法思想267

9.6.2鏈式基數排序268

9.7各種內部排序演演算法的比較270

9.7.1選擇排序演演算法的依據270

9.7.2選擇排序演演算法的結論270

小結271

習題271