數據結構課程學習與應考指導

《數據結構課程學習與應考指導》是2011年清華大學出版社出版的圖書，作者是徐塞虹、顧懋柟。

基本介紹

• 中文名：數據結構課程學習與應考指導
• 作者：徐塞虹、顧懋柟
• 類別：作業系統
• 出版社：清華大學出版社
• 出版時間：2011年12月30日
• 定價：25 元
• 裝幀：平裝
• ISBN：9787302272267

圖書簡介

本書面向各類數據結構課程的在學者和應考者，也特別適合作為高等學校計算機專業碩士研究生入學考試的備考用書。讀者既可以將此書用於考前的全面複習，同時還可以在課程學習過程中作為參考書使用。

書中內容涵蓋了數據結構課程教學大綱的要求，並且可滿足計算機學科碩士研究生入學統考的需求。全書共分9章，每章按照“知識點”、“內容精要”和“典型例題解析”三個部分精心組織。“知識點”列出應該掌握的知識重點；“內容精要”基於各個知識點上需要掌握的內容，將其歸納組織在明確的小標題下，提煉和濃縮知識，便於讀者查閱和複習基本概念、基本原理和基本方法以及相關的重點與難點；“典型例題解析”選用不同題型，力求覆蓋所需掌握的知識，達到舉一反三、靈活運用知識的目的，是應考者鞏固和檢測學習效果的極好素材。

本書依照高等學校數據結構課程的教學內容編寫，並且參照了近幾年全國碩士研究生計算機學科專業基礎綜合考試大綱和考題。旨在幫助各類數據結構課程的應考者和在學者。

目錄

第1章概論1

1.1知識點1

1.2內容精要1

1.2.1概念和術語1

1.2.2數據結構的研究目的和研究內容1

1.2.3數據邏輯結構的四種基本形態2

1.2.4數據存儲結構的基本組織方式2

1.2.5數據邏輯結構上定義的基本運算3

1.2.6在數據結構中引入抽象數據類型概念的好處4

1.2.7什麼是算法4

1.2.8算法的五個重要特性4

1.2.9評價算法優劣的基本標準4

1.2.10算法分析的目的5

1.2.11算法的時間複雜度的含義5

1.2.12算法的空間複雜度的含義5

1.3典型例題解析5

第2章線性表11

2.1知識點11

2.2內容精要11

2.2.1概念和術語11

2.2.2線性表的特點11

2.2.3通常線上性表上定義的基本運算11

2.2.4線性表的順序存儲結構（順序表）12

2.2.5C語言中線性表順序存儲空間的兩種分配方法12

2.2.6靜態分配空間和動態分配空間時，構造一個順序表算法之比較13

2.2.7線性表的順序存儲結構的優缺點14

2.2.8線性表的鏈式存儲結構（鍊表）14

2.2.9幾種常用的鏈式存儲結構14

2.2.10線性表的鏈式存儲結構的優缺點15

2.2.11單鍊表設定頭結點的好處15

2.2.12單鍊表不帶頭結點和帶頭結點兩種結構下，刪除第i個元素的

算法之比較15

2.2.13循環鍊表設立尾指針而不設頭指針的好處17

2.2.14靜態鍊表的用途和構造方法17

2.2.15線性表的索引存儲結構及其優點17

2.3典型例題解析17

第3章棧和佇列27

3.1知識點27

3.2內容精要27

3.2.1棧的定義和術語27

3.2.2棧的特性27

3.2.3棧的基本運算定義27

3.2.4順序棧（棧的順序存儲結構）28

3.2.5在順序棧上運算的實現28

3.2.6鏈棧（棧的鏈式存儲結構）30

3.2.7棧空間共享問題30

3.2.8棧和遞歸的關係31

3.2.9哪些類型的問題適合於用遞歸方法求解31

3.2.10遞歸模型及遞歸執行過程31

3.2.11遞歸算法的設計步驟32

3.2.12遞歸過程的實現32

3.2.13遞歸算法的優缺點33

3.2.14遞歸算法轉換為非遞歸算法的方法33

3.2.15佇列的定義和術語35

3.2.16佇列的特性36

3.2.17佇列的基本運算定義36

3.2.18順序佇列（佇列的順序存儲結構）36

3.2.19循環佇列的好處36

3.2.20在循環佇列上運算的實現37

3.2.21鏈佇列（佇列的鏈式存儲結構）38

3.2.22在鏈佇列上運算的實現38

3.3典型例題解析39

第4章串54

4.1知識點54

4.2內容精要54

4.2.1概念和術語54

4.2.2串與線性表的關係54

4.2.3兩個串相等的充分必要條件54

4.2.4通常在串上定義的基本運算54

4.2.5順序串（串的順序存儲結構）55

4.2.6鏈串/塊鏈結構（串的鏈式存儲結構）56

4.2.7在塊鏈中結點大小（CHUNKSIZE值）的選擇56

4.2.8兩種典型的串的模式匹配算法56

4.2.9求next數組值的方法58

4.2.10next數組的缺陷和改進58

4.3典型例題解析58

第5章多維數組67

5.1知識點67

5.2內容精要67

5.2.1多維數組的定義67

5.2.2多維數組和線性表的關係67

5.2.3數組的特點68

5.2.4數組的基本運算的定義68

5.2.5數組的順序存儲結構68

5.2.6特殊矩陣壓縮存儲的意義69

5.2.7對稱矩陣壓縮存儲的方法69

5.2.8三角矩陣壓縮存儲的方法69

5.2.9對角矩陣壓縮存儲的方法70

5.2.10稀疏矩陣及其壓縮存儲的特點70

5.2.11稀疏矩陣壓縮存儲的順序存儲方式70

5.2.12稀疏矩陣壓縮存儲的鏈式存儲方式--十字鍊表

（或稱正交鍊表）72

5.3典型例題解析73

第6章樹和二叉樹81

6.1知識點81

6.2內容精要81

6.2.1樹的概念和定義81

6.2.2樹的特點82

6.2.3樹的表示方法82

6.2.4樹的相關術語82

6.2.5二叉樹的定義和它的五種形態83

6.2.6一棵度為2的有序樹與二叉樹的區別83

6.2.7滿二叉樹和完全二叉樹83

6.2.8二叉樹的基本運算84

6.2.9二叉樹的性質85

6.2.10二叉樹的存儲結構85

6.2.11遍歷二叉樹86

6.2.12線索二叉樹的概念87

6.2.13線索二叉樹的存儲結構87

6.2.14二叉樹的線索化87

6.2.15遍歷線索二叉樹88

6.2.16最優二叉樹（也稱哈夫曼樹）的概念89

6.2.17哈夫曼樹的構造方法89

6.2.18哈夫曼樹的套用89

6.2.19樹的存儲結構90

6.2.20樹與二叉樹的轉換91

6.2.21森林轉換為二叉樹92

6.2.22樹和森林的遍歷92

6.3典型例題解析93

第7章圖122

7.1知識點122

7.2內容精要122

7.2.1概念和術語122

7.2.2圖的基本運算的定義123

7.2.3圖的存儲結構124

7.2.4鄰接矩陣和鄰接表兩種圖的存儲結構的比較125

7.2.5圖的遍歷算法126

7.2.6圖的生成樹和最小生成樹的概念126

7.2.7如何得到圖的生成樹126

7.2.8最小生成樹(MST)的性質129

7.2.9Prim算法構造最小生成樹129

7.2.10Kruskal算法構造最小生成樹130

7.2.11拓撲排序和AOV(ActivityonVertex)網131

7.2.12無前趨的頂點優先的拓撲排序算法131

7.2.13無後繼的頂點優先的拓撲排序算法133

7.2.14關鍵路徑問題和AOE(ActivityOnEdge)網133

7.2.15確定關鍵路徑的主要步驟134

7.2.16採用鄰接表作為圖的存儲結構時，求事件的最早發生時間和

最晚發生時間為何採用不同的策略134

7.2.17求關鍵路徑的算法135

7.2.18單源最短路徑--迪傑斯特拉(Dijkstra)算法136

7.2.19每對頂點間的最短路徑--弗洛伊德(Floyd)算法137

7.2.20Floyd算法使用時的限制138

7.3典型例題解析138第8章查找154

8.1知識點154

8.2內容精要154

8.2.1查找在數據處理中的重要性154

8.2.2基本概念和術語154

8.2.3查找表的典型存儲結構155

8.2.4靜態查找表的順序表存儲結構155

8.2.5順序表上的順序查找156

8.2.6有序順序表上的折半查找（也稱二分查找）156

8.2.7索引順序表的分塊查找158

8.2.8二叉排序樹（也稱二叉查找樹）的概念和性質159

8.2.9二叉排序樹的存儲結構定義159

8.2.10二叉排序樹上的查找160

8.2.11二叉排序樹上結點的插入161

8.2.12二叉排序樹的生成162

8.2.13二叉排序樹上結點的刪除162

8.2.14平衡二叉樹（也稱AVL樹）的概念163

8.2.15平衡二叉樹上插入結點的操作163

8.2.16平衡二叉樹的生成164

8.2.17平衡二叉樹上結點的刪除操作165

8.2.18平衡二叉樹的特點165

8.2.19B-樹的概念165

8.2.20B-樹的高度定理166

8.2.21B-樹的用途166

8.2.22B-樹的存儲結構定義166

8.2.23B-樹上的查找操作166

8.2.24B-樹上的插入操作167

8.2.25B-樹上的刪除操作168

8.2.26B+樹的概念168

8.2.27B-樹和B+樹的主要差異169

8.2.28B+樹上的基本運算169

8.2.29鍵樹（又稱數字查找樹或字元樹）的概念169

8.2.30鍵樹的存儲結構170

8.2.31鍵樹上的運算和性能要點171

8.2.32哈希表（也稱散列表或雜湊表）的概念和相關術語171

8.2.33哈希表的設計過程171

8.2.34哈希函式的基本構造方法172

8.2.35哈希表中處理衝突的常用方法172

8.2.36哈希表的平均查找長度ASL與裝填因子α的關係173

8.3典型例題解析173

第9章排序187

9.1知識點187

9.2內容精要187

9.2.1排序的概念187

9.2.2排序的分類187

9.2.3評價排序算法的主要標準188

9.2.4直接插入排序188

9.2.5希爾排序（也稱縮小增量排序）190

9.2.6冒泡排序191

9.2.7快速排序（也稱分劃交換排序）192

9.2.8簡單選擇排序193

9.2.9堆的定義194

9.2.10堆與完全二叉樹的關係194

9.2.11調整堆的操作和建堆的操作194

9.2.12堆排序195

9.2.13歸併排序196

9.2.14基數排序與前述排序方法不同的實質是什麼197

9.2.15多關鍵字排序的兩種方法197

9.2.16基數排序198

9.2.17各種內部排序方法的比較200

9.2.18選擇內部排序方法時所應考慮的主要因素200

9.2.19外部排序的概念200

9.2.20外部排序的基本方法201

9.2.21影響外部排序時間開銷的因素201

9.2.22提高外部排序效率的途徑201

9.2.23利用敗者樹實現k路平衡歸併的方法201

9.2.24勝者樹較之敗者樹的缺陷202

9.2.25置換-選擇排序生成初始歸併段的方法202

9.2.26引入最佳歸併樹的必要性203

9.2.27最佳歸併樹的構造方法203

9.3典型例題解析204

附錄A類C語言說明220

參考文獻227