數據結構

第1章 緒論1
1.1 數據結構課程的地位1
1.2 數據結構的定義和基本術語2
1.2.1 數據結構研究的內容及定義2
1.2.2 基本術語4
1.3 數據的邏輯結構和存儲結構5
1.3.1 邏輯結構5
1.3.2 存儲結構5
1.4 算法和算法分析7
1.4.1 算法7
1.4.2 算法分析8
本章小結9
綜合訓練10

第2章 線性表17
2.1 線性表的定義及邏輯結構17
2.2 順序存儲結構19
2.2.1 順序表19
2.2.2 順序表中基本操作的實現20
2.3 鏈式存儲結構26
2.3.1 單鏈表27
2.3.2 單鏈表中基本操作的實現28
2.3.3 循環鏈表34
2.3.4 雙向鏈表35
2.4 應用: 一元多項式的表示和相加37
實驗一線性表的順序存儲39
實驗二單鏈表的基本操作43
實驗三鏈表綜合操作51
本章小結54
綜合訓練55

第3章 棧和隊列65
3.1 棧65
3.1.1 棧的定義65
3.1.2 順序棧的存儲結構和操作的實現66
3.1.3 鏈棧的存儲結構和操作的實現68
3.2 棧的應用69
3.3 隊列73
3.3.1 隊列的定義73
3.3.2 鏈隊列的存儲結構和操作的實現74
3.3.3 順序隊列的存儲結構和操作的實現76
3.4 隊列的應用79
實驗四棧和隊列的表示與實現79
實驗五棧和隊列的應用82
本章小結84
綜合訓練84

第4章 串91
4.1 串的定義91
4.1.1 基本術語91
4.1.2 基本運算92
4.2 串的存儲結構93
4.2.1 定長順序存儲93
4.2.2 堆分配存儲94
4.2.3 塊鏈存儲94
4.3 串的基本操作的實現95
本章小結96
綜合訓練96

第5章 數組98
5.1 數組的定義98
5.2 數組的順序存儲結構99
5.3 矩陣的壓縮存儲100
5.3.1 對稱矩陣100
5.3.2 三角矩陣101
5.3.3 對角矩陣102
5.3.4 稀疏矩陣102
本章小結105
綜合訓練106

第6章 樹和二叉樹110
6.1 樹的定義和基本術語110
6.2 二叉樹111
6.2.1 二叉樹的定義和相關概念111
6.2.2 二叉樹的性質112
6.2.3 二叉樹的存儲結構113
6.3 遍歷二叉樹和線索二叉樹115
6.3.1 遍歷二叉樹115
6.3.2 線索二叉樹118
6.4 樹和森林120
6.4.1 樹的存儲結構120
6.4.2 森林與二叉樹的轉換122
6.4.3 樹和森林的遍歷123
6.5 哈夫曼樹及其應用124
6.5.1 最優二叉樹124
6.5.2 哈夫曼編碼125
實驗六樹與二叉樹127
本章小結128
綜合訓練129

第7章 圖133
7.1 圖的定義和基本術語133
7.2 圖的存儲結構135
7.2.1 鄰接矩陣表示法（數組表示法）135
7.2.2 鄰接表表示法137
7.3 圖的遍歷139
7.3.1 深度優先搜索139
7.3.2 廣度優先搜索139
7.4 圖的應用140
7.4.1 最小生成樹140
7.4.2 拓撲排序142
7.4.3 關鍵路徑143
7.4.4 最短路徑146
實驗七圖的操作148
本章小結148
綜合訓練149

第8章 查找153
8.1 查找的基本概念153
8.2 基於線性表的查找155
8.2.1 順序查找155
8.2.2 折半查找157
8.2.3 索引查找161
8.3 基於樹的查找162
8.3.1 二叉排序樹162
8.3.2 平衡二叉樹168
8.3.3 B?樹171
實驗八查找172
8.4 哈希表174
8.4.1 哈希表的定義174
8.4.2 哈希函數的構造方法175
8.4.3 處理沖突的方法176
8.4.4 哈希表的查找分析177
實驗九哈希表的查找179
本章小結180
綜合訓練180

第9章 內部排序184
9.1 概述184
9.1.1 排序的定義184
9.1.2 內部排序和外部排序184
9.2 插入排序185
9.2.1 直接插入排序185
9.2.2 希爾排序187
9.3 交換排序188
9.3.1 冒泡排序189
9.3.2 快速排序191
9.4 選擇排序193
9.4.1 簡單選擇排序194
9.4.2 堆排序196
9.5 歸並排序200
9.6 基數排序202
9.6.1 多關鍵字排序202
9.6.2 鏈式基數排序202
9.7 各種排序方法的比較205
實驗十內部排序206
本章小結208
綜合訓練209

第10章 課程設計214
10.1 目的和題目214
10.2 考核方式及報告要求214
附錄A 課程設計報告模板216
附錄B 模擬試題237參考文獻240