算法與數據結構

“算法與數據結構”是計算機及相關專業的核心基礎課程，旨在培養學生採用相應的數據結構與算法進行算法設計、算法應用和實際應用軟件的開發，提高複雜應用軟件的開發能力。 全書共9章，第1章介紹數據結構的基本概念，第2～5章介紹數據結構中的線性結構，包括線性表、棧、隊列和數組，第6章介紹樹狀結構，包括樹和二叉樹，第7章介紹圖狀結構，第8章介紹查找，第9章介紹排序。 本書注重可讀性和實用性，提供許多例題和應用實例。每章後均附有習題，應用實例都提供源碼且已經通過調試，可供讀者學習時參考。 本書可作為高等院校計算機及相關專業的本科教材，也適合從事算法設計和軟件開發的人員參考。 ^[1] 

第1章緒論1

1.1數據結構的概念1

1.1.1基本概念和術語1

1.1.2邏輯結構2

1.1.3存儲結構5

1.1.4抽象數據類型6

1.2算法8

1.2.1算法的描述8

1.2.2算法設計的要求8

1.2.3算法分析8

1.3本章小結12

習題112

第2章線性表15

2.1線性表的抽象數據類型15

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

2.2.1順序表的類型定義18

2.2.2線性表基本運算在順序表上的實現18

2.2.3順序表的應用舉例21

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

2.3.1單鏈表的類型定義23

2.3.2線性表基本運算在單鏈表上的實現25

2.3.3單鏈表的應用舉例29

2.3.4單循環鏈表31

2.3.5雙向鏈表32

2.4本章小結34

習題234算法與數據結構目錄第3章棧37

3.1棧的抽象數據類型37

3.2棧的順序存儲結構39

3.2.1順序棧的類型定義39

3.2.2棧基本運算在順序棧上的實現40

3.2.3順序棧的應用舉例41

3.3棧的鏈式存儲結構43

3.3.1鏈棧的類型定義43

3.3.2棧基本運算在鏈棧上的實現44

3.3.3鏈棧的應用舉例45

3.4棧與遞歸的實現46

3.5本章小結49

習題349

第4章隊列51

4.1隊列的抽象數據類型51

4.2隊列的順序存儲結構52

4.2.1循環隊列的類型定義54

4.2.2隊列基本運算在循環隊列上的實現54

4.2.3循環隊列的應用舉例55

4.3隊列的鏈式存儲結構56

4.3.1鏈隊列的類型定義57

4.3.2隊列基本運算在鏈隊列上的實現57

4.3.3鏈隊列的應用舉例59

4.4本章小結61

習題461

第5章數組和稀疏矩陣63

5.1數組的概念與表示63

5.1.1數組的概念63

5.1.2數組的順序表示65

5.1.3特殊矩陣的壓縮存儲67

5.2稀疏矩陣68

5.2.1稀疏矩陣的三元組表示69

5.2.2稀疏矩陣的十字鏈表表示77

5.3本章小結79

習題579

第6章樹和二叉樹83

6.1樹83

6.1.1樹的抽象數據類型83

6.1.2樹的基本術語86

6.1.3樹的存儲結構87

6.2二叉樹90

6.2.1二叉樹的抽象數據類型90

6.2.2二叉樹的性質93

6.2.3二叉樹的存儲結構95

6.3二叉樹的遍歷97

6.3.1常用的二叉樹遍歷算法97

6.3.2遍歷算法的應用舉例105

6.4森林與二叉樹的轉換111

6.4.1森林轉換為二叉樹111

6.4.2二叉樹轉換為森林113

6.4.3樹的遍歷113

6.5哈夫曼樹及其應用115

6.5.1哈夫曼樹115

6.5.2哈夫曼算法115

6.5.3哈夫曼編碼118

6.6本章小結120

習題6120

第7章圖123

7.1圖的基本概念123

7.1.1圖的抽象數據類型123

7.1.2圖的基本術語125

7.2圖的存儲結構127

7.2.1鄰接矩陣127

7.2.2鄰接表129

7.2.3應用舉例131

7.3圖的遍歷133

7.3.1深度優先搜索134

7.3.2廣度優先搜索135

7.3.3應用舉例137

7.4最小生成樹139

7.4.1Prim算法140

7.4.2Kruskal算法143

7.5拓撲排序145

7.6關鍵路徑149

7.7最短路徑154

7.7.1單源點最短路徑154

7.7.2每對頂點之間的最短路徑156

7.8本章小結158

習題7158

第8章查找161

8.1查找表161

8.2靜態查找表162

8.2.1順序查找162

8.2.2折半查找163

8.2.3分塊查找165

8.3動態查找表165

8.3.1二叉排序樹166

8.3.2平衡二叉樹170

8.4散列表173

8.4.1散列函數的構造方法174

8.4.2散列衝突的解決方法175

8.5本章小結179

習題8179

第9章排序181

9.1排序的基本概念181

9.2插入排序182

9.2.1直接插入排序182

9.2.2希爾排序183

9.3交換排序185

9.3.1冒泡排序185

9.3.2快速排序186

9.4選擇排序188

9.4.1直接選擇排序188

9.4.2堆排序189

9.5歸併排序191

9.6基數排序192

9.7本章小結195

習題9195

附錄中英名詞對照表197

參考文獻201 ^[2]