數(shù)據(jù)結(jié)構(gòu)（C/C++描述）

“數(shù)據(jù)結(jié)構(gòu)”是學(xué)習(xí)計(jì)算機(jī)軟件的一門重要基礎(chǔ)課程。計(jì)算機(jī)科學(xué)各領(lǐng)域及相關(guān)的應(yīng)用軟件都要用到各種數(shù)據(jù)結(jié)構(gòu)。“數(shù)據(jù)結(jié)構(gòu)”課程的目的是使學(xué)生學(xué)會分析各種數(shù)據(jù)結(jié)構(gòu)及其內(nèi)在的邏輯關(guān)系，掌握它們在計(jì)算機(jī)中的存儲表示及其相應(yīng)的算法，并初步掌握算法執(zhí)行的時間和空間分析技術(shù)。由于它在計(jì)算機(jī)學(xué)科的各門課程中具有承前啟后的作用，因此學(xué)好數(shù)據(jù)結(jié)構(gòu)這門課程至關(guān)重要。

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

本書主要采用C語言作為數(shù)據(jù)結(jié)構(gòu)和算法的描述語言，考慮到算法描述的簡潔性和知識的延續(xù)性，我們在算法描述中適當(dāng)?shù)匾�進(jìn)了部分C++ 的基本概念。例如，C++ 語言的引用調(diào)用、參數(shù)傳遞方式等，使得算法描述更為簡明清晰。讀者只需通過本書的附錄，對C++ 的引用調(diào)用的參數(shù)傳遞方式作一個了解，就能讀懂書中的所有算法。

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

本書編寫力求概念準(zhǔn)確、文字流暢、算法精湛、突出重點(diǎn)、注重應(yīng)用。其中各章都給出了難易適中的不同類型的習(xí)題，供學(xué)生課后練習(xí)使用。本書適合作為計(jì)算機(jī)類專業(yè)的本科或?qū)？平滩模�也可作為信息類相關(guān)專業(yè)的選修教材。本書授課的總學(xué)時可定為108學(xué)時，其中講授72學(xué)時，上機(jī)實(shí)踐36學(xué)時。

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

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

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

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

編 者

2006年11月

前言
第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)的概念 1
1.1.1 什么是數(shù)據(jù)結(jié)構(gòu) 1
1.1.2 為什么要學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu) 2
1.1.3 基本概念和術(shù)語 5
1.2 抽象數(shù)據(jù)類型 9
1.2.1 數(shù)據(jù)類型 10
1.2.2 抽象數(shù)據(jù)類型 10
1.2.3 抽象數(shù)據(jù)類型的表示和實(shí)現(xiàn) 11
1.3 算法和算法分析 12
1.3.1 算法的特性 13
1.3.2 算法描述 13
1.3.3 算法性能分析與度量 14
習(xí)題1 16
第2章 線性表 19
2.1 線性表的類型定義 19
2.1.1 抽象數(shù)據(jù)類型線性表的定義 19
2.1.2 基于ADT線性表的算法設(shè)計(jì) 20
2.2 線性表的順序存儲及實(shí)現(xiàn) 22
2.2.1 順序表的定義及存儲 22
2.2.2 順序表基本運(yùn)算的實(shí)現(xiàn) 24
2.2.3 順序表應(yīng)用舉例 28
2.3 線性表的鏈?zhǔn)酱鎯�及�?shí)現(xiàn) 29
2.3.1 單鏈表的定義及存儲 30
2.3.2 單鏈表基本運(yùn)算的實(shí)現(xiàn) 31
2.3.3 循環(huán)鏈表 36
2.3.4 雙向鏈表 38
2.3.5 靜態(tài)鏈表 40
2.4 線性表應(yīng)用舉例 42
2.4.1 一元多項(xiàng)式的表示 42
2.4.2 一元多項(xiàng)式相加 43
習(xí)題2 46
第3章 棧和隊(duì)列 48
3.1 棧 48
3.1.1 棧的定義及基本運(yùn)算 48
3.1.2 棧的順序表示與實(shí)現(xiàn) 49
3.1.3 棧的鏈?zhǔn)奖硎九c實(shí)現(xiàn) 51
3.2 棧的應(yīng)用舉例 53
3.2.1 括號匹配的檢驗(yàn) 53
3.2.2 行編輯程序 55
3.2.3 表達(dá)式求值 56
3.3 棧與遞歸 58
3.3.1 遞歸的實(shí)現(xiàn) 59
3.3.2 遞歸設(shè)計(jì) 60
3.4 隊(duì)列 62
3.4.1 隊(duì)列的定義及基本運(yùn)算 62
3.4.2 隊(duì)列的順序表示和實(shí)現(xiàn) 63
3.4.3 隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn) 66
3.4.4 隊(duì)列的應(yīng)用舉例 67
習(xí)題3 69
第4章 串 72
4.1 串的定義 72
4.2 串的存儲及基本運(yùn)算 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 串的應(yīng)用 87
習(xí)題4 89
第5章 多維數(shù)組、矩陣和廣義表 90
5.1 多維數(shù)組 90
5.1.1 數(shù)組的定義 90
5.1.2 數(shù)組的存儲表示 91
5.1.3 數(shù)組基本運(yùn)算的實(shí)現(xiàn) 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 廣義表的定義和基本運(yùn)算 109
5.4.2 廣義表的存儲結(jié)構(gòu) 110
5.4.3 廣義表基本運(yùn)算的實(shí)現(xiàn) 113
習(xí)題5 117
第6章 樹和二叉樹 120
6.1 樹的定義及其存儲結(jié)構(gòu) 120
6.1.1 樹的定義及基本術(shù)語 120
6.1.2 樹的存儲結(jié)構(gòu) 123
6.2 二叉樹 126
6.2.1 二叉樹的定義 126
6.2.2 二叉樹的性質(zhì) 128
6.2.3 二叉樹的存儲結(jié)構(gòu) 129
6.3 遍歷二叉樹和線索化二叉樹 131
6.3.1 遍歷二叉樹 131
6.3.2 線索化二叉樹 135
6.4 樹、森林和二叉樹的關(guān)系 139
6.4.1 樹、森林與二叉樹的轉(zhuǎn)換 139
6.4.2 樹和森林的遍歷 141
6.5 哈夫曼樹及其應(yīng)用 142
6.5.1 哈夫曼樹 142
6.5.2 哈夫曼樹的應(yīng)用 144
6.5.3 哈夫曼算法的實(shí)現(xiàn) 146
習(xí)題6 149
第7章 圖 151
7.1 圖的基本概念 151
7.1.1 圖的定義 151
7.1.2 圖的基本術(shù)語 153
7.2 圖的存儲結(jié)構(gòu) 157
7.2.1 鄰接矩陣 157
7.2.2 鄰接表 159
7.2.3 十字鏈表 161
7.3 圖的遍歷及圖的連通分量 163
7.3.1 深度優(yōu)先搜索 163
7.3.2 廣度優(yōu)先搜索 165
7.3.3 圖的連通分量 167
7.4 生成樹和最小生成樹 168
7.4.1 生成樹和生成森林 168
7.4.2 最小生成樹 170
7.4.3 關(guān)節(jié)點(diǎn)和重連通分量 175
7.5 最短路徑 178
7.5.1 從某個源點(diǎn)到其余各頂點(diǎn)的最短路徑 178
7.5.2 每一對頂點(diǎn)之間的最短路徑 181
7.6 拓?fù)渑判蚺c關(guān)鍵路徑 183
7.6.1 拓?fù)渑判?184
7.6.2 關(guān)鍵路徑 186
習(xí)題7 191
第8章 查找 194
8.1 基本概念 194
8.2 靜態(tài)查找 195
8.2.1 順序查找 195
8.2.2 折半查找 197
8.2.3 分塊查找 200
8.3 動態(tài)查找 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 哈希函數(shù)的構(gòu)造方法 224
8.4.3 處理沖突的方法 226
8.4.4 哈希表的查找與分析 228
8.4.5 哈希算法舉例 229
習(xí)題8 232
第9章 內(nèi)排序 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 基數(shù)排序 255
9.7 各種內(nèi)排序方法比較 260
習(xí)題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 多關(guān)鍵字文件 273
10.2 外排序 276
10.2.1 外排序的方法 276
10.2.2 多路平衡歸并及實(shí)現(xiàn) 277
10.2.3 置換—選擇排序 282
10.2.4 最佳歸并樹 287
習(xí)題10 289
附錄 291
參考文獻(xiàn) 296

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