目錄
第一章 緒論1
1．1 什麼是數據結構1
1．2 基本概念和術語3
1．3 數據結構的發展簡史及它在計算機科學中所處的地位12
1．4 算法的描述和算法分析13
1．4．1 算法的描述13
1．4．2 算法設計的要求15
1．4．3 算法效率的度量16
1．4．4 算法的存儲空間需求18
第二章 線性表19
2．1 線性表的邏輯結構19
2．2 線性表的順序存儲結構22
2．3 線性表的鏈式存儲結構27
2．3．1 線性鍊表27
2．3．2 循環鍊表35
2．3，3 雙向鍊表35
2．4 一元多項式的表示及相加37
第三章 棧和佇列41
3．1 棧41
3．1．1 抽象數據類型棧的定義41
3．1．2 棧的表示和實現43
3．2 表達式求值45
**3．3 棧與遞歸過程47
3．3．1 遞歸過程及其實現47
3．3．2 遞歸過程的模擬52
3．4 佇列59
3．4．1 抽象數據類型佇列的定義59
3．4．2 鏈佇列——佇列的鏈式存儲結構61
3．4．3 循環佇列——佇列的順序存儲結構63
3．5 離散事件模擬66
第四章 串71
4．1 串及其操作71
4．1．1 串的邏輯結構定義71
4．1．2 串的基本操作72
4．2 串的存儲結構73
4．2．1 靜態存儲結構74
4．2．2 動態存儲結構74
4．3 串基本操作的實現77
4．3．1 靜態結構存儲串時的操作77
4．3．2 模式匹配的一種改進算法80
4．3．3 堆結構存儲串時的操作84
4．4 串操作套用舉例86
4．4．1 文本編輯86
**4．4．2 建立詞索引表87
第五章 數組和廣義表93
5．1 數組的定義和運算93
5．2 數組的順序存儲結構95
5．3 矩陣的壓縮存儲96
5．3．1 特殊矩陣97
5．3．2 稀疏矩陣97
5．4 廣義表的定義107
5．5 廣義表的存儲結構109
**5．6 m元多項式的表示110
**5．7 廣義表的遞歸算法112
5．7．1 求廣義表的深度113
5．7．2 複製廣義表114
5．7．3 建立廣義表的存儲結構115
第六章 樹和二叉樹118
6．1 樹的結構定義和基本操作118
6．2 二叉樹120
6．2．1 定義與基本操作120
6．2．2 二叉樹的性質122
6．2．3 二叉樹的存儲結構124
6．3 遍歷二叉樹和線索二叉樹125
6．3．1 遍歷二叉樹125
5．3．2 線索二叉樹128
6．4 樹和森林134
6．4．1 樹的存儲結構134
6．4．2 森林與二叉樹的轉換135
6．4．3 樹的遍歷137
**6．5 樹與等價問題138
6．6 哈夫曼樹及其套用142
6．6．1 最優二叉樹（哈夫曼樹）142
6．6．2 哈夫曼編碼144
**6．7 回溯法與樹的遍歷148
**6．8 樹的計數150
第七章 圖155
7．1 圖的定義和術語155
7．2 圖的存儲結構159
7．2．1 數組表示法159
7．2．2 鄰接表161
7．2．3 十字鍊表162
7．2．4 鄰接多重表164
7．3 圖的遍歷165
7．3．1 深度優先搜尋166
7．3．2 廣度優先搜尋167
7．4 圖的連通性問題168
7．4．1 無向圖的連通分量和生成樹168
**7．4．2 有向圖的強連通分量171
7．4．3 最小生成樹171
**7．4．4 關節點和重連通分量174
7．5 有向無環圖及其套用177
7．5．1 拓撲排序179
7．5．2 關鍵路徑184
7．6 最短路徑188
7．6．1 從某個源點到其餘各頂點的最短路徑189
7．6．2 每一對頂點之間的最短路徑191
**7．7 二部圖與圖匹配193
第八章 動態存儲管理198
8．1 概述198
8．2 可利用空間表及分配方法200
8．3 邊界標識法203
8．3．1 可利用空間表的結構203
8．3．2 分配算法204
8．3．3 回收算法206
8．4 夥伴系統208
8．4．1 可利用空間表的結構208
8．4．2 分配算法209
8．4．3 回收算法210
8．5 無用單元收集211
8．6 存儲緊縮216
第九章 查找219
9．1 靜態查找表220
9．1．1 順序表的查找220
9．1．2 有序表的查找223
9．1．3 靜態樹表的查找226
9．1．4 索引順序表的查找230
9．2 動態查找表231
9．2．1 二叉排序樹和平衡二叉樹231
9．2．2 B_樹和B+樹241
9．2．3 鍵樹249
9．3 哈希表253
9．3．1 什麼是哈希表253
9．3．2 哈希函式的構造方法255
9．3．3 處理衝突的方法258
9．3．4 哈希表的查找及其分析260
第十章 內部排序264
10．1 概述264
10．2 插入排序265
10．2．1 直接插入排序265
10．2．2 其它插入排序268
10．2．3 希爾排序272
10．3 快速排序274
10．4 選擇排序278
10．4．1 簡單選擇排序278
10．4．2 樹形選擇排序280
10．4．3 堆排序281
10．5 歸併排序284
10．6 基數排序285
10．6．1 多關鍵字的排序286
10．6．2 鏈式基數排序287
10．7 各種內部排序方法的比較討論289
第十一章 外部排序294
11．1 外存信息的存取294
11．2 外部排序的方法296
11．3 多路平衡歸併的實現298
11．4 置換-選擇排序300
**11．5 緩衝區的並行操作處理305
11．6 最佳歸併樹307
**11．7 磁帶歸併排序308
11．7．1 平衡歸併308
11．7．2 多步歸併308
第十二章 檔案311
12．1 有關檔案的基本概念311
12．2 順序檔案313
12．3 索引檔案316
12．4 ISAM檔案和VSAM檔案318
12．4．1 ISAM檔案318
12．4．2 VSAM檔案321
12．5 直接存取檔案(散列檔案）322
12．6 多關鍵字檔案324
12．6．1 多重表檔案324
12．6．2 倒排檔案325
附錄一 類PASCAL語言擴充部分的語法圖327
附錄二 名詞索引329
附錄三 過程和函式索引336
參考書目340
