基本介紹
內容提要,圖書目錄,
內容提要
本書的前半部分從抽象數據類型的角度討論各種基本類型的數據結構及其套用;後半部分主要討論查找和排序的各種實現方法及綜合分析比較。
圖書目錄
第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
