“數據結構”是學習計算機軟件的一門重要基礎課程。計算機科學各領域及相關的應用軟件都要用到各種數據結構。“數據結構”課程的目的是使學生學會分析各種數據結構及其內在的邏輯關系，掌握它們在計算機中的存儲表示及其相應的算法，并初步掌握算法執行的時間和空間分析技術。由于它在計算機學科的各門課程中具有承前啟后的作用，因此學好數據結構這門課程至關重要。

數據結構的原理及算法較為抽象，而該課程一般在本科低年級開設，我們在多年的教學過程中深深感到，對于只具有計算機程序設計基礎知識的學生，要很好地理解和掌握其中的原理比較困難，特別是理解數據的存儲結構、相關的算法，以及將算法轉化成對應的應用程序，這些都是學習的難點。這本《數據結構》教材是作者在多年教授“數據結構”課程并指導學生上機實踐所積累的知識與經驗的基礎之上編寫而成的，希望能夠幫助學生在盡可能短的時間內對數據結構的知識與應用有一個比較全面、深入和系統的認識。本書給出的絕大多數算法都特別突出了算法設計思想、完整的算法描述及算法分析三個部分，既便于學生將算法轉換成C或C++ 程序，也能為培養學生在實際應用中分析問題和解決問題的能力打下良好的基礎。

本書主要采用C語言作為數據結構和算法的描述語言，考慮到算法描述的簡潔性和知識的延續性，我們在算法描述中適當地引進了部分C++ 的基本概念。例如，C++ 語言的引用調用、參數傳遞方式等，使得算法描述更為簡明清晰。讀者只需通過本書的附錄，對C++ 的引用調用的參數傳遞方式作一個了解，就能讀懂書中的所有算法。

全書共分10章及一個附錄。第1章介紹數據結構的基本概念、抽象數據類型及算法分析方法；第2章至第4章介紹線性結構的相關概念及算法，包括線性表、棧、隊列和串；第5章介紹較為復雜的數據結構，包括多維數組、稀疏矩陣和廣義表；第6章、第7章分別介紹了非線性結構樹及圖；第8章至第10章介紹常用的查找、排序算法及文件結構。附錄中給出了本書所涉及的有關C和C++ 相關知識的對照，有助于前期學過C或C++ 語言的學生順利閱讀本書。

本書編寫力求概念準確、文字流暢、算法精湛、突出重點、注重應用。其中各章都給出了難易適中的不同類型的習題，供學生課后練習使用。本書適合作為計算機類專業的本科或專科教材，也可作為信息類相關專業的選修教材。本書授課的總學時可定為108學時，其中講授72學時，上機實踐36學時。

本書由阮宏一主編，并負責全書的總體策劃與統稿、定稿工作，唐宏亮、楊鶴、張緒輝任副主編。各章主要編寫人員分工如下：第1、2、5、7章由阮宏一、張緒輝、賀睿編寫，第3、4、6章由唐宏亮、王芳、朱勤童編寫，第8章至第10章由楊鶴、李紅玲、杜超編寫。參加本書編寫的還有文忠林、強士端、趙晶、王大雷、李玲、黃朝援、江濤、劉平、張偉、劉舒、陳燦等。

本書在編寫過程中還得到了雷建軍老師、羅忠老師的大力支持和幫助，并提出了很好的意見和建議，在此謹向他們表示衷心感謝。

本書為授課教師免費提供電子教案，此教案采用PowerPoint制作，可以任意修改。需要者可從中國水利水電出版社網站免費下載，網址為：http://www.waterpub.com.cn/ softdown/。

由于時間倉促及作者水平有限，書中難免存在欠妥和疏漏之處，敬請廣大讀者批評指正。作者的E-mail地址為：hyruan@hubce.edu.cn、hyyh001@126.com。

編 者

2006年11月

前言
第1章 緒論 1
1.1 數據結構的概念 1
1.1.1 什么是數據結構 1
1.1.2 為什么要學習數據結構 2
1.1.3 基本概念和術語 5
1.2 抽象數據類型 9
1.2.1 數據類型 10
1.2.2 抽象數據類型 10
1.2.3 抽象數據類型的表示和實現 11
1.3 算法和算法分析 12
1.3.1 算法的特性 13
1.3.2 算法描述 13
1.3.3 算法性能分析與度量 14
習題1 16
第2章 線性表 19
2.1 線性表的類型定義 19
2.1.1 抽象數據類型線性表的定義 19
2.1.2 基于ADT線性表的算法設計 20
2.2 線性表的順序存儲及實現 22
2.2.1 順序表的定義及存儲 22
2.2.2 順序表基本運算的實現 24
2.2.3 順序表應用舉例 28
2.3 線性表的鏈式存儲及實現 29
2.3.1 單鏈表的定義及存儲 30
2.3.2 單鏈表基本運算的實現 31
2.3.3 循環鏈表 36
2.3.4 雙向鏈表 38
2.3.5 靜態鏈表 40
2.4 線性表應用舉例 42
2.4.1 一元多項式的表示 42
2.4.2 一元多項式相加 43
習題2 46
第3章 棧和隊列 48
3.1 棧 48
3.1.1 棧的定義及基本運算 48
3.1.2 棧的順序表示與實現 49
3.1.3 棧的鏈式表示與實現 51
3.2 棧的應用舉例 53
3.2.1 括號匹配的檢驗 53
3.2.2 行編輯程序 55
3.2.3 表達式求值 56
3.3 棧與遞歸 58
3.3.1 遞歸的實現 59
3.3.2 遞歸設計 60
3.4 隊列 62
3.4.1 隊列的定義及基本運算 62
3.4.2 隊列的順序表示和實現 63
3.4.3 隊列的鏈式表示和實現 66
3.4.4 隊列的應用舉例 67
習題3 69
第4章 串 72
4.1 串的定義 72
4.2 串的存儲及基本運算 74
4.2.1 串的定長順序存儲表示 74
4.2.2 串的堆分配存儲表示 78
4.2.3 串的塊鏈存儲表示 81
4.3 串的模式匹配算法 82
4.3.1 簡單的模式匹配算法 82
4.3.2 無回溯的模式匹配算法 84
4.4 串的應用 87
習題4 89
第5章 多維數組、矩陣和廣義表 90
5.1 多維數組 90
5.1.1 數組的定義 90
5.1.2 數組的存儲表示 91
5.1.3 數組基本運算的實現 93
5.2 特殊矩陣 96
5.2.1 對稱矩陣 96
5.2.2 三角矩陣 97
5.2.3 對角矩陣 98
5.3 稀疏矩陣 98
5.3.1 稀疏矩陣的定義 99
5.3.2 三元組順序表 100
5.3.3 十字鏈表 103
5.4 廣義表 108
5.4.1 廣義表的定義和基本運算 109
5.4.2 廣義表的存儲結構 110
5.4.3 廣義表基本運算的實現 113
習題5 117
第6章 樹和二叉樹 120
6.1 樹的定義及其存儲結構 120
6.1.1 樹的定義及基本術語 120
6.1.2 樹的存儲結構 123
6.2 二叉樹 126
6.2.1 二叉樹的定義 126
6.2.2 二叉樹的性質 128
6.2.3 二叉樹的存儲結構 129
6.3 遍歷二叉樹和線索化二叉樹 131
6.3.1 遍歷二叉樹 131
6.3.2 線索化二叉樹 135
6.4 樹、森林和二叉樹的關系 139
6.4.1 樹、森林與二叉樹的轉換 139
6.4.2 樹和森林的遍歷 141
6.5 哈夫曼樹及其應用 142
6.5.1 哈夫曼樹 142
6.5.2 哈夫曼樹的應用 144
6.5.3 哈夫曼算法的實現 146
習題6 149
第7章 圖 151
7.1 圖的基本概念 151
7.1.1 圖的定義 151
7.1.2 圖的基本術語 153
7.2 圖的存儲結構 157
7.2.1 鄰接矩陣 157
7.2.2 鄰接表 159
7.2.3 十字鏈表 161
7.3 圖的遍歷及圖的連通分量 163
7.3.1 深度優先搜索 163
7.3.2 廣度優先搜索 165
7.3.3 圖的連通分量 167
7.4 生成樹和最小生成樹 168
7.4.1 生成樹和生成森林 168
7.4.2 最小生成樹 170
7.4.3 關節點和重連通分量 175
7.5 最短路徑 178
7.5.1 從某個源點到其余各頂點的最短路徑 178
7.5.2 每一對頂點之間的最短路徑 181
7.6 拓撲排序與關鍵路徑 183
7.6.1 拓撲排序 184
7.6.2 關鍵路徑 186
習題7 191
第8章 查找 194
8.1 基本概念 194
8.2 靜態查找 195
8.2.1 順序查找 195
8.2.2 折半查找 197
8.2.3 分塊查找 200
8.3 動態查找 201
8.3.1 二叉排序樹 202
8.3.2 平衡二叉樹 207
8.3.3 B_樹和B+樹 216
8.4 哈希查找 223
8.4.1 哈希表的基本概念 223
8.4.2 哈希函數的構造方法 224
8.4.3 處理沖突的方法 226
8.4.4 哈希表的查找與分析 228
8.4.5 哈希算法舉例 229
習題8 232
第9章 內排序 234
9.1 基本概念 234
9.2 插入排序 235
9.2.1 直接插入排序 235
9.2.2 折半插入排序 237
9.2.3 希爾排序 238
9.3 選擇排序 240
9.3.1 直接選擇排序 240
9.3.2 堆排序 242
9.4 交換排序 247
9.4.1 冒泡排序 247
9.4.2 快速排序 249
9.5 歸并排序 252
9.6 基數排序 255
9.7 各種內排序方法比較 260
習題9 261
第10章 文件與外排序 263
10.1 文件 263
10.1.1 外存信息的存取 263
10.1.2 文件的基本概念 264
10.1.3 順序文件 266
10.1.4 索引文件 267
10.1.5 索引順序文件 268
10.1.6 直接存取文件（散列文件） 272
10.1.7 多關鍵字文件 273
10.2 外排序 276
10.2.1 外排序的方法 276
10.2.2 多路平衡歸并及實現 277
10.2.3 置換—選擇排序 282
10.2.4 最佳歸并樹 287
習題10 289
附錄 291
參考文獻 296

1. 數據結構（Python語言描述） [曹岳輝　劉衛國　康松林　編著]
2. 數據結構——C語言（微課版） [主編 梁海英]
3. 數據結構（C語言版）習題解答及實訓指導 [李根強 謝月娥]
4. 數據結構（C語言版） [主編 李根強 劉浩 謝月娥]
5. 數據結構（Java版） [主編 李云平]
6. 數據結構 [主編 韓利凱 朱浩悅]
7. 數據結構（C語言版）（第三版） [主編 庫波 曹靜]
8. 數據結構（Java版） [孫琳 張宇]
9. 數據結構 [許繪香 段明義]
10. 數據結構（C語言描述） [李素若 陳萬華 游明坤 編著]
11. 數據結構習題解答及上機指導 [李素若 琚輝 嚴永松 編著]
12. 數據結構（C++描述）習題解答及實習指導 [李根強 謝月娥 主編]
13. 數據結構（C語言版）學習指導與習題解答 [趙堅 姜梅 主編]
14. 數據結構 [陸勤 主編 ]
15. 數據結構（C++描述） [李根強 主 編]
16. 數據結構（C++版）--習題解答及實習指導 [李根強 主編]
17. 數據結構算法--Visual C++ 6.0程序集 [侯識忠 等編著]
18. 數據結構算法--C++ Builder 6.0程序集 [侯識忠 等編著]
19. 數據結構（C語言版）學習指導與習題解答 [趙堅 姜梅 主編]
20. 數據結構（C語言版） [趙堅 姜梅 主編]
21. 數據結構（C語言描述） [斯慶巴拉 主編]
22. 數據結構（C++版）（第二版） [李根強]
23. 數據結構（C++版）（第二版）習題解答及實訓指導 [李根強]
24. 數據結構——用C語言描述 [蔡明志 編著]
25. 數據結構（C++版） [李根強 主編]
26. 數據結構--用C語言描述（第二版） [寧正元 易金聰 編著]
27. 數據結構（C語言描述） [馬秋菊 主編]
28. 數據結構--C語言描述（第二版） [王路群 主編]
29. 數據結構、算法與應用（Java語言描述） [[美]Sartaj Sahni（薩爾塔杰.薩]
30. 數據結構實驗程序 [智東杰 主 編]