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