在編排上，本書內(nèi)容符合“數(shù)據(jù)結(jié)構(gòu)”本科教學(xué)大綱及最新研究生考試大綱的要求；另外，本書還加強(qiáng)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)等實(shí)踐應(yīng)用環(huán)節(jié)。

本書編者結(jié)合自己的教學(xué)和編程實(shí)踐經(jīng)驗(yàn)，精選基礎(chǔ)理論內(nèi)容，降低了概念的抽象性和理論的難度，突出實(shí)用性，便于讀者理解和掌握。

本書條理清晰，概念清楚，邏輯推理嚴(yán)謹(jǐn)，內(nèi)容詳實(shí)，既注重?cái)?shù)據(jù)結(jié)構(gòu)和算法原理，又十分強(qiáng)調(diào)程序設(shè)計(jì)訓(xùn)練。

本書力圖用生動(dòng)、通俗易懂的語言，并結(jié)合編程實(shí)例來講解各個(gè)知識(shí)點(diǎn)；書中算法均配有完整的C語言程序，結(jié)構(gòu)清晰，構(gòu)思精巧。

本書配套有中國水利水電出版社出版的《數(shù)據(jù)結(jié)構(gòu)習(xí)題解答及上機(jī)指導(dǎo)》。

數(shù)據(jù)結(jié)構(gòu)是普通高等院校計(jì)算機(jī)和信息技術(shù)等相關(guān)專業(yè)的一門主要的專業(yè)基礎(chǔ)課，也是一門必修的核心課程。它不僅是計(jì)算機(jī)程序設(shè)計(jì)的理論基礎(chǔ)，還是學(xué)習(xí)計(jì)算機(jī)操作系統(tǒng)原理、編譯原理、數(shù)據(jù)庫原理等課程的重要基礎(chǔ)。

數(shù)據(jù)結(jié)構(gòu)課程的主要任務(wù)是討論數(shù)據(jù)的各種邏輯結(jié)構(gòu)和數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)表示，以及各種非數(shù)值運(yùn)算的算法實(shí)現(xiàn)，其內(nèi)容豐富、涉及面廣，并且隨著各種基于計(jì)算機(jī)的應(yīng)用技術(shù)的發(fā)展而不斷增加新的內(nèi)容。通過學(xué)習(xí)，學(xué)生可以較全面地理解算法和數(shù)據(jù)結(jié)構(gòu)概念，掌握各種數(shù)據(jù)結(jié)構(gòu)和算法的實(shí)現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法特點(diǎn)，能夠使用數(shù)據(jù)結(jié)構(gòu)的基本分析方法來提高編寫程序的能力和應(yīng)用計(jì)算機(jī)解決實(shí)際問題的能力。

數(shù)據(jù)結(jié)構(gòu)內(nèi)容多、理論深、概念抽象。因此，在本書的編寫中，編者結(jié)合自己的教學(xué)和編程實(shí)踐經(jīng)驗(yàn)，精選了基礎(chǔ)理論內(nèi)容，降低了概念的抽象性和理論難度。一方面力圖用生動(dòng)、通俗易懂的語言并結(jié)合編程實(shí)例來講解各個(gè)知識(shí)點(diǎn)，便于讀者理解和掌握；另一方面加強(qiáng)了數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)、算法設(shè)計(jì)等實(shí)踐應(yīng)用環(huán)節(jié)。全書共9章，第1章主要講述數(shù)據(jù)結(jié)構(gòu)和算法的基本概念；第2～7章分別講述線性表、棧和隊(duì)列、多維數(shù)組和廣義表、樹和圖這幾種基本數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)、存儲(chǔ)方法和基本運(yùn)算，作為本書的重點(diǎn)，書中使用大量的篇幅來介紹這些基本數(shù)據(jù)結(jié)構(gòu)的實(shí)際應(yīng)用；第8章和第9章講述查找和排序的基本原理與方法。另外，書中所涉及的有關(guān)概念及背景知識(shí)皆做出詳細(xì)交代；對(duì)相關(guān)的定理和性質(zhì)給出簡單證明；對(duì)所有算法，都詳細(xì)討論其設(shè)計(jì)思想和實(shí)現(xiàn)方法，最后給出完整的C語言代碼；書中所有算法和程序代碼均在Dev-C++5.0環(huán)境下調(diào)試通過。

本書配套有《數(shù)據(jù)結(jié)構(gòu)習(xí)題解答及上機(jī)指導(dǎo)》，內(nèi)含與主教材各章內(nèi)容相配合的習(xí)題解答參考和7套模擬考試試題和10個(gè)精心設(shè)計(jì)的實(shí)驗(yàn)，每個(gè)實(shí)驗(yàn)均包括實(shí)驗(yàn)?zāi)康摹��?shí)驗(yàn)內(nèi)容、實(shí)驗(yàn)說明、實(shí)驗(yàn)指導(dǎo)等，兩本書配套使用可以更為全面地掌握數(shù)據(jù)結(jié)構(gòu)這門課程。

本書第1～5章由李素若編寫，第6、8、9章由陳萬華編寫，第7章由游明坤編寫；全書由李素若負(fù)責(zé)審核和統(tǒng)稿；參加本書編寫大綱討論的教師還有嚴(yán)永松、胡玉榮、任正云、武永成、張牧等。

由于編者水平有限，加之時(shí)間倉促，書中難免有疏漏之處，敬請(qǐng)廣大讀者批評(píng)指正，以使本書質(zhì)量得到進(jìn)一步提高。

編 者

2014年4月

前言

第1章 緒論 1
1.1 數(shù)據(jù)結(jié)構(gòu)的概述 1
1.2 基本概念和常用術(shù)語 2
1.3 數(shù)據(jù)抽象和抽象數(shù)據(jù)類型 6
1.3.1 數(shù)據(jù)抽象 6
1.3.2 抽象數(shù)據(jù)類型 7
1.3.3 抽象數(shù)據(jù)類型的描述和實(shí)現(xiàn) 8
1.4 算法和算法分析 10
1.4.1 算法及性能標(biāo)準(zhǔn) 10
1.4.2 算法時(shí)間復(fù)雜度和漸近時(shí)間復(fù)雜度 11
1.4.3 算法的空間復(fù)雜度 13
習(xí)題1 13
第2章 線性表 17
2.1 線性表的邏輯結(jié)構(gòu) 17
2.1.1 線性表的定義 17
2.1.2 線性表的ADT定義 18
2.2 線性表的順序存儲(chǔ)和實(shí)現(xiàn) 19
2.2.1 線性表順序存儲(chǔ)結(jié)構(gòu) 19
2.2.2 線性表在順序存儲(chǔ)結(jié)構(gòu)下的運(yùn)算 20
2.3 線性表的鏈?zhǔn)酱鎯?chǔ)和實(shí)現(xiàn) 23
2.3.1 線性鏈表 23
2.3.2 循環(huán)鏈表 30
2.3.3 雙向循環(huán)鏈表 32
2.3.4 循環(huán)鏈表 34
2.4 一元多項(xiàng)式的表示及相加 35
習(xí)題2 38
第3章 棧和隊(duì)列 42
3.1 棧 42
3.1.1 棧的定義 42
3.1.2 棧的ADT定義 42
3.1.3 順序棧 44
3.1.4 多棧共享鄰接空間 46
3.1.5 鏈棧 48
3.1.6 棧的應(yīng)用舉例 50
3.1.7 棧與遞歸的實(shí)現(xiàn) 56
3.2 隊(duì)列 60
3.2.1 隊(duì)列的定義 60
3.2.2 隊(duì)列的ADT定義 60
3.2.3 順序隊(duì)列 61
3.2.4 鏈隊(duì)列 65
3.2.5 隊(duì)列應(yīng)用舉例 66
習(xí)題3 69
第4章 串 73
4.1 串 73
4.1.1 串的定義與相關(guān)概念 73
4.1.2 串的ADT定義 74
4.2 串的定長順序存儲(chǔ) 77
4.2.1 串的定長順序存儲(chǔ)結(jié)構(gòu) 77
4.2.2 定長順序存儲(chǔ)的基本運(yùn)算 77
4.3 串的堆存儲(chǔ)結(jié)構(gòu) 80
4.3.1 串名存儲(chǔ)映像 81
4.3.2 堆存儲(chǔ)結(jié)構(gòu) 82
4.3.3 基于堆存儲(chǔ)結(jié)構(gòu)的基本運(yùn)算 82
4.4 串的塊鏈存儲(chǔ)結(jié)構(gòu) 85
4.5 串的模式匹配 87
習(xí)題4 92
第5章 數(shù)組和廣義表 96
5.1 數(shù)組類型的定義 96
5.1.1 數(shù)組的定義 96
5.1.2 數(shù)組的ADT定義 98
5.2 數(shù)組的順序存儲(chǔ)和實(shí)現(xiàn) 99
5.3 矩陣壓縮存儲(chǔ) 101
5.3.1 對(duì)稱矩陣 101
5.3.2 三角矩陣 102
5.3.3 帶狀矩陣 103
5.4 稀疏矩陣 104
5.4.1 稀疏矩陣三元組表存儲(chǔ) 104
5.4.2 稀疏矩陣十字鏈表存儲(chǔ) 113
5.5 廣義表 117
5.5.1 廣義表的定義和基本運(yùn)算 117
5.5.2 廣義表的存儲(chǔ) 119
5.5.3 廣義表基本操作的實(shí)現(xiàn) 121
習(xí)題5 124
第6章 樹 128
6.1 樹的基本概念 128
6.1.1 樹的定義 128
6.1.2 樹的邏輯表示方法 129
6.1.3 樹的基本術(shù)語 130
6.1.4 樹的ADT定義 131
6.2 二叉樹的概念和性質(zhì) 132
6.2.1 二叉樹的概念 132
6.2.2 二叉樹的性質(zhì) 133
6.3 二叉樹的存儲(chǔ)結(jié)構(gòu) 135
6.3.1 二叉樹的順序存儲(chǔ)結(jié)構(gòu) 135
6.3.2 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 136
6.4 二叉樹的遍歷及其他操作 137
6.4.1 二叉樹遍歷的概念 137
6.4.2 二叉樹遍歷的遞歸算法 138
6.4.3 二叉樹遍歷的非遞歸算法 140
6.4.4 二叉樹的其他操作 143
6.5 線索二叉樹 145
6.5.1 線索二叉樹的概念 145
6.5.2 線索化二叉樹 146
6.5.3 遍歷線索二叉樹 148
6.6 樹和森林 149
6.6.1 樹的存儲(chǔ)結(jié)構(gòu) 149
6.6.2 二叉樹與樹、森林之間的轉(zhuǎn)換 152
6.6.3 樹和森林的遍歷 154
6.7 哈夫曼樹 155
6.7.1 哈夫曼樹的概述 155
6.7.2 哈夫曼樹的構(gòu)造 156
6.7.3 哈夫曼編碼 157
6.7.4 相關(guān)算法 158
習(xí)題6 161
第7章 圖 165
7.1 圖的概述 165
7.1.1 圖的定義 165
7.1.2 圖的相關(guān)術(shù)語 166
7.1.3 圖的ADT描述 169
7.2 圖的存儲(chǔ)結(jié)構(gòu) 170
7.2.1 鄰接矩陣存儲(chǔ)結(jié)構(gòu) 170
7.2.2 鄰接表存儲(chǔ)結(jié)構(gòu) 173
7.3 圖的遍歷 176
7.3.1 深度優(yōu)先遍歷 177
7.3.2 廣度優(yōu)先遍歷 179
7.3.3 非連通圖的遍歷 181
7.4 最小生成樹 182
7.4.1 生成樹和最小生成樹的概念 182
7.4.2 普里姆算法 183
7.4.3 克魯斯卡爾算法 185
7.5 拓?fù)渑判蚺c關(guān)鍵路徑 187
7.5.1 拓?fù)渑判?187
7.5.2 關(guān)鍵路徑 191
7.6 最短路徑 195
7.6.1 單源最短路徑 196
7.6.2 任意兩個(gè)頂點(diǎn)間的最短路徑 199
習(xí)題7 202
第8章 查找 208
8.1 基本概念 208
8.1.1 相關(guān)術(shù)語 208
8.1.2 查找表結(jié)構(gòu) 209
8.2 靜態(tài)查找表 209
8.2.1 順序查找 210
8.2.2 二分查找 210
8.2.3 分塊查找 213
8.3 動(dòng)態(tài)查找表 214
8.3.1 二叉排序樹 214
8.3.2 平衡二叉樹 220
8.3.3 B-樹 227
8.3.4 B+樹 232
8.4 哈希表查找 233
8.4.1 哈希表的基本概念 233
8.4.2 哈希函數(shù)構(gòu)造方法 234
8.4.3 哈希沖突解決方法 236
8.4.4 哈希表的查找過程 240
8.4.5 哈希表的性能分析 240
習(xí)題8 241
第9章 排序 246
9.1 排序的相關(guān)術(shù)語與概念 246
9.2 插入排序 247
9.2.1 直接插入排序 247
9.2.2 希爾排序 249
9.3 交換排序 251
9.3.1 冒泡排序 251
9.3.2 快速排序 253
9.4 選擇排序 256
9.4.1 直接選擇排序 256
9.4.2 堆排序 257
9.5 歸并排序 261
9.6 基數(shù)排序 264
9.7 各種排序方法比較 267
習(xí)題9 268
參考文獻(xiàn) 272

1. 高等數(shù)學(xué)導(dǎo)學(xué)篇（下冊） [主編 李文婧 胡雷 尹金生]
2. 高等數(shù)學(xué)導(dǎo)學(xué)篇（上冊） [主編 李文婧 胡雷 尹金生]
3. 高等數(shù)學(xué)（下冊） [主編 李愛芹 胡雷 尹金生]
4. 高等數(shù)學(xué)（上冊） [主編 李愛芹 胡雷 尹金生]
5. 中華水文化（慕課版）（第二版） [畢雪燕 楊華軻 羅玲誼 等編著]
6. 電路與電子技術(shù)Ⅱ——電路分析基礎(chǔ) [主編 陳曉 金哲]
7. Spark大數(shù)據(jù)處理技術(shù) [主編　劉仁山　周洪翠　莊新妍]
8. C語言同步案例習(xí)題精解 [主編 肖朝暉]
9. 人工智能算法與實(shí)踐 [主編　梁琨　張翼英]
10. 數(shù)據(jù)清洗 [黃源　劉智楊　孫大松]
11. 電路設(shè)計(jì)與PCB制作實(shí)操教程 [主編 周永宏]
12. 電路與電子技術(shù)Ⅰ—數(shù)字電子技術(shù) [主編 鄭玉珍 王淑琴]
13. Java編程基礎(chǔ)案例式教程 [主編 陳艷華 唐春蘭]
14. Python語言同步案例習(xí)題精解 [主編 肖朝暉]
15. Web用戶界面設(shè)計(jì)與制作 [主編 趙娟]
16. Unity應(yīng)用開發(fā)與實(shí)戰(zhàn)（微課版） [主 編 程永恒]
17. 文學(xué)基礎(chǔ)與影視欣賞 [楊華軻 朱偉利 畢雪燕 羅玲誼]
18. 大學(xué)計(jì)算機(jī)基礎(chǔ)與計(jì)算思維 [主編 閔笛 汪瑩]
19. 大學(xué)計(jì)算機(jī)信息素養(yǎng)（第二版） [主編 盧山]
20. 大學(xué)計(jì)算機(jī)基礎(chǔ)實(shí)驗(yàn)指導(dǎo)及習(xí)題解析 [主編 閔笛 李明]
21. 大學(xué)計(jì)算機(jī)信息素養(yǎng)實(shí)驗(yàn)指導(dǎo)（第二版） [主編 盧山]
22. 計(jì)算機(jī)應(yīng)用基礎(chǔ)教程（Windows 10+Office 2019） [主編 聶長浪 賀秋芳 李久仲]
23. 計(jì)算機(jī)應(yīng)用基礎(chǔ)（Windows 7+Office 2016） [主編 王洪平 楊華]
24. 計(jì)算機(jī)信息素養(yǎng)基礎(chǔ) [主編 陳艷 秦凱 黃海玉]
25. 計(jì)算機(jī)基礎(chǔ)與應(yīng)用 [主編 秦凱 梁寧玉 王毅]
26. 大學(xué)計(jì)算機(jī)基礎(chǔ)上機(jī)實(shí)踐教程（第六版） [主編 何振林 羅奕]
27. C語言程序設(shè)計(jì)（微課版） [主編　夏啟壽]
28. C語言程序設(shè)計(jì)實(shí)踐教程 [夏啟壽]
29. 單片機(jī)應(yīng)用技術(shù)項(xiàng)目教程（C語言版）（第三版） [主編　郭志勇]
30. 大學(xué)計(jì)算機(jī)基礎(chǔ)教程實(shí)驗(yàn)指導(dǎo)與測試題集 [主編 饒拱維 吳華光 巫滿秀]