數據結構（C語言版)

第1章 緒論 1

1.1 數據結構的概念及分類 2

1.1.1 數據與數據結構 2

思政要點 2

1.1.2 數據結構的分類 3

思政要點 4

1.2 抽象數據類型 5

1.2.1 數據類型 5

1.2.2 數據抽象與抽象數據類型 5

1.2.3 用於描述數據結構的語言 7

思政要點 7

1.3 算法定義 7

思政要點 9

1.4 算法性能分析與度量 9

1.4.1 算法的性能標準 9

思政要點 10

1.4.2 算法的後期測試 10

1.4.3 算法的事前估計 11

思政要點 15

1.4.4 漸進的時間覆雜度 15

思政要點 18

1.4.5 漸進的空間覆雜度 18

思政要點 19

1.5 上機實驗 19

思政要點 21

本章小結 21

習題1 22

第2章 線性表 24

2.1 線性表實例及概念 25

思政要點 26

2.2 線性表的存儲方式 26

2.2.1 線性表的順序存儲結構 26

2.2.2 線性表的鏈式存儲結構 27

思政要點 30

2.3 線性表的有關操作 30

2.3.1 順序表的操作實現 30

思政要點 35

2.3.2 單鏈表的操作實現 35

思政要點 40

2.3.3 雙向循環鏈表的操作實現 41

思政要點 43

2.4 線性表的ADT定義 44

思政要點 45

2.5 線性表的應用—多項式相加問題 45

2.5.1 存儲結構的選取 45

2.5.2 一元多項加法運算的實現 45

思政要點 47

2.6 上機實驗 47

思政要點 50

本章小結 50

習題2 53

第3章 棧 56

3.1 棧的應用實例及概念 57

思政要點 58

3.2 棧的存儲方式 58

3.2.1 棧的順序存儲結構 58

思政要點 59

3.2.2 棧的鏈式存儲結構 59

思政要點 60

3.3 棧的有關操作 60

3.3.1 順序棧的操作實現 60

3.3.2 鏈棧的操作實現 62

思政要點 64

3.4 棧的ADT定義 64

思政要點 65

3.5 棧的應用實例——算術表達式的求值 65

3.5.1 表達式的構成 65

3.5.2 運算符的優先關系 65

3.5.3 算法思路 66

思政要點 67

3.6 上機實驗 67

思政要點 70

本章小結 70

習題3 71

第4章 隊列 74

4.1 隊列的應用實例及概念 75

思政要點 76

4.2 隊列的存儲方式 76

4.2.1 隊列的鏈式存儲結構 76

思政要點 78

4.2.2 隊列的順序存儲結構 78

思政要點 80

4.3 隊列的有關操作 81

4.3.1 循環隊列的操作實現 81

思政要點 83

4.3.2 鏈隊列的操作實現 83

4.4 隊列的ADT定義 87

思政要點 87

4.5 順序循環隊列的應用 88

思政要點 89

4.6 上機實驗 89

思政要點 93

本章小結 93

習題4 94

第5章 串 97

5.1 串的應用實例及基本概念 98

思政要點 98

5.2 串的存儲結構 99

5.2.1 串的順序存儲 99

思政要點 100

5.2.2 串的鏈式存儲 100

思政要點 101

5.3 串運算的實現 101

思政要點 109

5.4 串的ADT定義 109

思政要點 110

5.5 上機實驗 110

思政要點 113

本章小結 113

習題5 115

第6章 數組 116

6.1 二維數組應用實例及概念 117

思政要點 118

6.2 數組的順序存儲和實現 118

6.2.1 數組的順序存儲 118

6.2.2 數組的實現 119

思政要點 121

6.3 特殊矩陣的壓縮存儲 122

6.3.1 三角矩陣 122

6.3.2 稀疏矩陣 124

思政要點 129

6.4 數組應用實例 129

思政要點 131

6.5 上機實驗 132

思政要點 134

本章小結 134

習題6 135

第7章 樹 137

7.1 樹的實例和基本概念 138

7.1.1 樹的實例 138

7.1.2 樹的基本概念 138

7.1.3 樹的常用術語 139

7.1.4 樹的表示方法 140

思政要點 140

7.2 二叉樹 141

7.2.1 二叉樹的定義 141

7.2.2 二叉樹的重要性質 141

思政要點 143

7.2.3 二叉樹的存儲結構 143

7.2.4 二叉樹二叉鏈表的一個

生成算法 144

思政要點 145

7.3 二叉樹的遍歷 145

7.3.1 二叉樹遍歷的定義 145

7.3.2 遍歷的遞歸方法 146

7.3.3 二叉樹遍歷的非遞歸實現 147

思政要點 151

7.4 二叉樹其他運算的實現 151

思政要點 153

7.5 線索二叉樹 154

7.5.1 線索二叉樹的基本概念 154

7.5.2 線索二叉樹的邏輯表示圖 155

7.5.3 中序次序線索化算法 155

7.5.4 在中序線索樹上檢索某結點的

前驅或後繼 157

7.5.5 在中序線索樹上遍歷二叉樹 158

思政要點 158

7.6 樹與森林 158

7.6.1 樹的存儲結構 158

7.6.2 樹、森林和二叉樹的轉換 161

7.6.3 一般樹或森林的遍歷 163

思政要點 164

7.7 哈夫曼樹及其應用 164

7.7.1 哈夫曼樹的基本概念 164

7.7.2 哈夫曼樹的構造及其算法 165

7.7.3 哈夫曼樹的應用 167

思政要點 169

7.8 二叉樹的ADT定義 169

思政要點 170

7.9 上機實驗 170

思政要點 173

本章小結 173

習題7 175

第8章 圖 178

8.1 圖的實例及概念 179

8.1.1 實例 179

8.1.2 圖的定義和基本概念 179

思政要點 182

8.2 圖的存儲結構及實現 182

8.2.1 鄰接矩陣 183

8.2.2 鄰接鏈表 190

8.2.3 圖的ADT定義 199

8.3 遍歷圖 199

8.3.1 深度優先搜索法 200

8.3.2 廣度優先搜索法 201

思政要點 203

8.4 最小生成樹 204

8.4.1 最小生成樹的基本概念 204

思政要點 205

8.4.2 普里姆算法 205

思政要點 208

8.4.3 克魯斯卡爾算法 208

思政要點 209

8.5 最短路徑 210

8.5.1 從某個源點到其他各頂點的

最短路徑 210

思政要點 213

8.5.2 求每一對頂點之間的最短路徑 213

思政要點 216

8.6 上機實驗 216

思政要點 221

本章小結 221

習題8 224

第9章 排序 227

9.1 排序的基本概念 228

思政要點 229

9.2 插入排序 229

9.2.1 直接插入排序 229

思政要點 231

9.2.2 希爾排序 231

思政要點 233

9.3 交換排序 233

9.3.1 冒泡排序 233

思政要點 234

9.3.2 快速排序 234

思政要點 237

9.4 選擇排序 237

9.4.1 直接選擇排序 237

思政要點 238

9.4.2 堆排序 238

思政要點 244

9.5 上機實驗 244

思政要點 245

本章小結 246

習題9 246

第10章 查找 248

10.1 靜態查找表 249

10.1.1 無序順序表的查找 249

思政要點 250

10.1.2 有序順序表的查找 251

思政要點 252

10.1.3 索引順序表的查找 252

思政要點 255

10.2 動態查找表 255

10.2.1 二叉排序樹 255

思政要點 259

10.2.2 平衡二叉樹 260

思政要點 261

10.3 哈希表及其查找 261

10.3.1 哈希表與哈希函數 261

思政要點 262

10.3.2 構造哈希函數的常用方法 263

思政要點 264

10.3.3 解決沖突的主要方法 264

思政要點 266

10.4 上機實驗 266

思政要點 269

本章小結 269

習題10 269

參考文獻 271