數據結構及套用算法教程（修訂版）

《數據結構及套用算法教程（修訂版）》是2014年清華大學出版社出版的圖書。

基本介紹

• 書名：數據結構及套用算法教程（修訂版）
• ISBN：9787302243908
• 定價：45元
• 出版社：清華大學出版社
• 出版時間：2014-8-4
• 裝幀：平裝

圖書簡介

本書從數據類型的角度，分別討論了四大類型的數據結構的邏輯特性、存儲表示及其套用。此外，還專辟一章，以若干實例闡述以抽象數據類型為中心的程式設計方法。書中每一章後都配有適量的習題，以供讀者複習提高之用。第1～9章還專門設有“解題指導與示例”一節內容，不僅給出答案，對大部分題目提供了詳盡的解答注釋；其中的一些算法題還給出了多種解法。書中主要算法和最後一章的實例中的全部程式代碼均收錄在與本書配套的光碟之中。

本書內容豐富，概念闡述細緻清楚，可作為高等院校計算機類專業和信息類相關專業“數據結構”或“軟體基礎”課程的本科教材。另外，對於準備參加計算機類研究生專業課統考的考生，本書也可作為應試的解題指導。

目錄

第1章緒論1

1.1數據結構討論的範疇1

1.2與數據結構相關的概念2

1.2.1基本概念和術語3

1.2.2數據結構(datastructures)4

1.2.3數據類型和抽象數據類型5

1.3算法及其描述和分析6

1.3.1算法6

1.3.2算法的描述6

1.3.3算法效率的衡量方法和準則9

1.3.4算法的存儲空間需求10

解題指導與示例11

習題16

第2章線性表18

2.1線性表的類型定義18

2.1.1線性表的定義18

2.1.2線性表的基本操作19

2.2線性表的順序表示和實現22

2.2.1順序表--線性表的順序存儲表示22

2.2.2順序表中基本操作的實現23

2.2.3順序表其他算法舉例28

2.3線性表的鏈式表示和實現31

2.3.1單鍊表和指針31

2.3.2單鍊表的基本操作32

2.3.3單鍊表的其他操作舉例36

2.3.4循環鍊表39

2.3.5雙向鍊表40

2.4有序表42

2.5順序表和鍊表的綜合比較47

解題指導與示例47

習題57

第3章排序60

3.1排序的基本概念60

3.2簡單排序方法63

3.2.1插入排序63

3.2.2起泡排序65

3.3先進排序方法67

3.3.1快速排序67

3.3.2歸併排序69

3.3.3堆排序71

3.4基數排序72

3.5各種排序方法的綜合比較76

解題指導與示例78

習題84

第4章棧和佇列86

4.1棧86

4.1.1棧的結構特點和操作86

4.1.2棧的表示和操作的實現87

4.2棧的套用舉例90

4.3佇列98

4.3.1佇列的結構特點和操作98

4.3.2佇列的表示和操作的實現100

4.4佇列套用舉例104

解題指導與示例109

習題113

第5章串和數組115

5.1串的定義和操作115

5.2串的表示和實現118

5.2.1定長順序存儲表示118

5.2.2堆分配存儲表示119

5.2.3塊鏈存儲表示120

5.3正文模式匹配121

5.4正文編輯--串操作套用舉例123

5.5數組124

5.5.1數組的定義和操作124

5.5.2數組的順序表示和實現125

5.5.3數組的套用127

5.6矩陣的壓縮存儲130

5.6.1特殊形狀矩陣的存儲表示130

5.6.2隨機稀疏矩陣的存儲壓縮131

解題指導與示例137

習題142

第6章二叉樹和樹144

6.1二叉樹144

6.1.1二叉樹的定義和基本術語144

6.1.2二叉樹的幾個基本性質147

6.1.3二叉樹的存儲結構148

6.2二叉樹遍歷150

6.2.1問題的提出150

6.2.2遍歷算法描述152

6.2.3二叉樹遍歷套用舉例153

6.2.4線索二叉樹157

6.3樹和森林159

6.3.1樹和森林的定義159

6.3.2樹和森林的存儲結構161

6.3.3樹和森林的遍歷164

6.4樹的套用168

6.4.1堆排序的實現168

6.4.2二叉排序樹171

6.4.3赫夫曼樹及其套用173

解題指導與示例179

習題198

第7章圖和廣義表201

7.1圖的定義和術語201

7.2圖的存儲結構204

7.2.1圖的數組（鄰接矩陣）存儲表示204

7.2.2圖的鄰接表存儲表示205

7.3圖的遍歷207

7.3.1深度優先搜尋遍歷圖208

7.3.2廣度優先搜尋遍歷圖210

7.4連通網的最小生成樹215

7.5單源最短路徑217

7.6拓撲排序221

7.7關鍵路徑223

7.8廣義表225

7.8.1廣義表的定義225

7.8.2廣義表的存儲結構226

7.8.3廣義表的遍歷227

解題指導與示例228

習題246

第8章查找表248

8.1靜態查找表249

8.1.1順序查找250

8.1.2折半查找251

8.1.3分塊查找254

8.2動態查找表255

8.2.1二叉查找樹256

8.2.2鍵樹260

8.3哈希表及其查找265

8.3.1什麼是哈希表265

8.3.2構造哈希函式的幾種方法267

8.3.3處理衝突的方法和建表示例268

8.3.4哈希表的查找及其性能分析269

8.3.5哈希表的套用舉例272

解題指導與示例274

習題285

第9章檔案287

9.1基本概念287

9.1.1外存儲器簡介287

9.1.2有關檔案的基本概念288

9.2順序檔案289

9.2.1存儲在順序存儲器上的檔案289

9.2.2存儲在直接存儲器上的檔案291

9.3索引檔案291

9.3.1B樹291

9.3.2B+樹和索引順序檔案293

9.4哈希檔案295

9.4.1檔案組織方式295

9.4.2檔案的操作296

9.5多關鍵碼檔案296

9.5.1倒排檔案297

9.5.2索引連結檔案297

解題指導與示例299

習題300

第10章數據結構程式設計示例301

10.1抽象數據類型301

10.2從問題到程式的求解過程304

10.2.1建立數據結構模型設計抽象數據類型305

10.2.2算法設計306

10.2.3實現抽象數據類型307

10.2.4編製程序代碼並進行靜態測試和動態調試308

10.3程式的規範說明309

10.4套用示例分析311

10.4.1含並、交和差運算的集合類型312

10.4.2最佳任務分配方案求解322

10.4.3排隊問題的系統仿真330

10.4.4十進制四則運算計算器339

10.4.5腳踏車零部件庫的庫存模型345

10.4.6教務課程計畫的輔助制定353

10.4.7一個小型全文檢索模型360

10.4.8汽車牌照的快速查找369

實習題377

實習一鍊表的維護與檔案形式的保存378

實習二用回溯法求解“穩定婚配”問題378

實習三以佇列實現的仿真技術預測理髮館的經營狀況379

實習四利用樹形結構的搜尋算法模擬網際網路域名的查詢380

實習五管道鋪設施工的最佳方案選擇381

實習六使用哈希表技術判別兩個源程式的相似性381

附錄算法一覽表384

參考文獻391