數據結構C語言版

本書的前半部分從抽象數據類型的角度討論各種基本類型的數據結構及其應用；後半部分主要討論查找和排序的各種實現方法及綜合分析比較。

第1章緒論1

1.1什麼是數據結構1

1.2基本概念和

術語4

1.3抽象數據類型的表示與實現9

1.4演演算法和演演算法分析13

1.4.1演演算法13

1.4.2演演算法設計的要求13

1.4.3演演算法效率的度量14

1.4.4演演算法的存儲空間需求17

第2章線性表18

2.1線性表的類型定義18

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

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

2.3.1線性鏈表27

2.3.2循環鏈表35

2.3.3雙向鏈表35

2.4一元多項式的表示及相加39

第3章棧和隊列44

3.1棧44

3.1.1抽象數據類型棧的定義44

3.1.2棧的表示和實現45

3.2棧的應用舉例48

3?2?1數制轉換48

3?2?2括弧匹配的檢驗49

3?2?3行編輯程序49

3?2?4迷宮求解50

3?2?5表達式求值52

**3.3棧與遞歸的實現54

3.4隊列58

3.4.1抽象數據類型隊列的定義58

3.4.2鏈隊列——隊列的鏈式表示和實現60

3.4.3循環隊列——隊列的順序表示和實現63

**3.5離散事件模擬65

第4章串70

4.1串類型的定義70

4.2串的表示和實現72

4.2.1定長順序存儲表示73

4.2.2堆分配存儲表示75

4?2?3串的塊鏈存儲表示78

**4?3串的模式匹配演演算法79

4.3.1求子串位置的定位函數Index(S,T,pos)79

4.3.2模式匹配的一種改進演演算法80

4.4串操作應用舉例84

4.4.1文本編輯84

4.4.2建立詞索引表86

第5章數組和廣義表90

5.1數組的定義90

5.2數組的順序表示和實現91

5.3矩陣的壓縮存儲95

5.3.1特殊矩陣95

5.3.2稀疏矩陣96

5.4廣義表的定義106

5.5廣義表的存儲結構109

**5.6m元多項式的表示110

**5.7廣義表的遞歸演演算法112

5.7.1求廣義表的深度113

5.7.2複製廣義表115.7.3建立廣義表的存儲結構115

第6章樹和二叉樹118

6.1樹的定義和基本術語118

6.2二叉樹121

6.2.1二叉樹的定義121

6.2.2二叉樹的性質123

6.2.3二叉樹的存儲結構126

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

6.3.1遍歷二叉樹128

6.3.2線索二叉樹132

6.4樹和森林135

6.4.1樹的存儲結構135

6.4.2森林與二叉樹的轉換137

6.4.3樹和森林的遍歷138

**6.5樹與等價問題139

6.6赫夫曼樹及其應用144

6.6.1最優二叉樹(赫夫曼樹)144