在編排上，本書內容符合“數據結構”本科教學大綱及最新研究生考試大綱的要求；另外，本書還加強數據結構設計、算法設計等實踐應用環節。

本書編者結合自己的教學和編程實踐經驗，精選基礎理論內容，降低了概念的抽象性和理論的難度，突出實用性，便于讀者理解和掌握。

本書條理清晰，概念清楚，邏輯推理嚴謹，內容詳實，既注重數據結構和算法原理，又十分強調程序設計訓練。

本書力圖用生動、通俗易懂的語言，并結合編程實例來講解各個知識點；書中算法均配有完整的C語言程序，結構清晰，構思精巧。

本書配套有中國水利水電出版社出版的《數據結構習題解答及上機指導》。

數據結構是普通高等院校計算機和信息技術等相關專業的一門主要的專業基礎課，也是一門必修的核心課程。它不僅是計算機程序設計的理論基礎，還是學習計算機操作系統原理、編譯原理、數據庫原理等課程的重要基礎。

數據結構課程的主要任務是討論數據的各種邏輯結構和數據在計算機中的存儲表示，以及各種非數值運算的算法實現，其內容豐富、涉及面廣，并且隨著各種基于計算機的應用技術的發展而不斷增加新的內容。通過學習，學生可以較全面地理解算法和數據結構概念，掌握各種數據結構和算法的實現方式，比較不同數據結構和算法特點，能夠使用數據結構的基本分析方法來提高編寫程序的能力和應用計算機解決實際問題的能力。

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

本書配套有《數據結構習題解答及上機指導》，內含與主教材各章內容相配合的習題解答參考和7套模擬考試試題和10個精心設計的實驗，每個實驗均包括實驗目的、實驗內容、實驗說明、實驗指導等，兩本書配套使用可以更為全面地掌握數據結構這門課程。

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

由于編者水平有限，加之時間倉促，書中難免有疏漏之處，敬請廣大讀者批評指正，以使本書質量得到進一步提高。

編 者

2014年4月

前言

第1章 緒論 1
1.1 數據結構的概述 1
1.2 基本概念和常用術語 2
1.3 數據抽象和抽象數據類型 6
1.3.1 數據抽象 6
1.3.2 抽象數據類型 7
1.3.3 抽象數據類型的描述和實現 8
1.4 算法和算法分析 10
1.4.1 算法及性能標準 10
1.4.2 算法時間復雜度和漸近時間復雜度 11
1.4.3 算法的空間復雜度 13
習題1 13
第2章 線性表 17
2.1 線性表的邏輯結構 17
2.1.1 線性表的定義 17
2.1.2 線性表的ADT定義 18
2.2 線性表的順序存儲和實現 19
2.2.1 線性表順序存儲結構 19
2.2.2 線性表在順序存儲結構下的運算 20
2.3 線性表的鏈式存儲和實現 23
2.3.1 線性鏈表 23
2.3.2 循環鏈表 30
2.3.3 雙向循環鏈表 32
2.3.4 循環鏈表 34
2.4 一元多項式的表示及相加 35
習題2 38
第3章 棧和隊列 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 棧的應用舉例 50
3.1.7 棧與遞歸的實現 56
3.2 隊列 60
3.2.1 隊列的定義 60
3.2.2 隊列的ADT定義 60
3.2.3 順序隊列 61
3.2.4 鏈隊列 65
3.2.5 隊列應用舉例 66
習題3 69
第4章 串 73
4.1 串 73
4.1.1 串的定義與相關概念 73
4.1.2 串的ADT定義 74
4.2 串的定長順序存儲 77
4.2.1 串的定長順序存儲結構 77
4.2.2 定長順序存儲的基本運算 77
4.3 串的堆存儲結構 80
4.3.1 串名存儲映像 81
4.3.2 堆存儲結構 82
4.3.3 基于堆存儲結構的基本運算 82
4.4 串的塊鏈存儲結構 85
4.5 串的模式匹配 87
習題4 92
第5章 數組和廣義表 96
5.1 數組類型的定義 96
5.1.1 數組的定義 96
5.1.2 數組的ADT定義 98
5.2 數組的順序存儲和實現 99
5.3 矩陣壓縮存儲 101
5.3.1 對稱矩陣 101
5.3.2 三角矩陣 102
5.3.3 帶狀矩陣 103
5.4 稀疏矩陣 104
5.4.1 稀疏矩陣三元組表存儲 104
5.4.2 稀疏矩陣十字鏈表存儲 113
5.5 廣義表 117
5.5.1 廣義表的定義和基本運算 117
5.5.2 廣義表的存儲 119
5.5.3 廣義表基本操作的實現 121
習題5 124
第6章 樹 128
6.1 樹的基本概念 128
6.1.1 樹的定義 128
6.1.2 樹的邏輯表示方法 129
6.1.3 樹的基本術語 130
6.1.4 樹的ADT定義 131
6.2 二叉樹的概念和性質 132
6.2.1 二叉樹的概念 132
6.2.2 二叉樹的性質 133
6.3 二叉樹的存儲結構 135
6.3.1 二叉樹的順序存儲結構 135
6.3.2 二叉樹的鏈式存儲結構 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 樹的存儲結構 149
6.6.2 二叉樹與樹、森林之間的轉換 152
6.6.3 樹和森林的遍歷 154
6.7 哈夫曼樹 155
6.7.1 哈夫曼樹的概述 155
6.7.2 哈夫曼樹的構造 156
6.7.3 哈夫曼編碼 157
6.7.4 相關算法 158
習題6 161
第7章 圖 165
7.1 圖的概述 165
7.1.1 圖的定義 165
7.1.2 圖的相關術語 166
7.1.3 圖的ADT描述 169
7.2 圖的存儲結構 170
7.2.1 鄰接矩陣存儲結構 170
7.2.2 鄰接表存儲結構 173
7.3 圖的遍歷 176
7.3.1 深度優先遍歷 177
7.3.2 廣度優先遍歷 179
7.3.3 非連通圖的遍歷 181
7.4 最小生成樹 182
7.4.1 生成樹和最小生成樹的概念 182
7.4.2 普里姆算法 183
7.4.3 克魯斯卡爾算法 185
7.5 拓撲排序與關鍵路徑 187
7.5.1 拓撲排序 187
7.5.2 關鍵路徑 191
7.6 最短路徑 195
7.6.1 單源最短路徑 196
7.6.2 任意兩個頂點間的最短路徑 199
習題7 202
第8章 查找 208
8.1 基本概念 208
8.1.1 相關術語 208
8.1.2 查找表結構 209
8.2 靜態查找表 209
8.2.1 順序查找 210
8.2.2 二分查找 210
8.2.3 分塊查找 213
8.3 動態查找表 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 哈希函數構造方法 234
8.4.3 哈希沖突解決方法 236
8.4.4 哈希表的查找過程 240
8.4.5 哈希表的性能分析 240
習題8 241
第9章 排序 246
9.1 排序的相關術語與概念 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 基數排序 264
9.7 各種排序方法比較 267
習題9 268
參考文獻 272

1. 實用運籌學 [主編　邢育紅　于晉臣]
2. 電子技術（第二版） [主編 覃愛娜 李飛]
3. 勞動爭議處理實務 [主編 王秀卿 羅靜]
4. 語音識別理論與實踐 [主編　莫宏偉]
5. 武術基礎教程 [主編 李代勇 謝志民]
6. 畫法幾何與機械制圖習題集（多學時） [主編 趙軍]
7. 機械設計基礎（第二版） [主編 田亞平 李愛姣]
8. 畫法幾何與機械制圖 [主編 趙軍]
9. C語言程序設計習題與實驗指導（第二版） [主編 甄增榮 張賓]
10. C語言程序設計（第二版） [主編 甄增榮 田云霞]
11. Unity3D虛擬現實應用開發實踐 [主 編 劉龍]
12. C語言程序設計實踐教程（活頁式） [主編 鄭茵 陳巍 滕泓虬]
13. 面向對象程序設計 [主編 張勇 張平華 趙小龍]
14. 數據結構（Python語言描述） [曹岳輝　劉衛國　康松林　編著]
15. 網絡營銷 [主編 夏薇薇 劉婷 尚潔]
16. C語言程序設計 [姜雪]
17. 數據庫技術與應用實踐教程（SQL Server 2019） [主 編 嚴暉 周肆清]
18. C語言程序設計項目化教程（活頁式） [主編 張利華 潘曉利]
19. 功能材料制備與表征實驗指導書 [龔偉平 趙軍峰 梅海娟 等編著]
20. 信號與系統（第二版） [主編 張宇]
21. Python 語言程序設計實踐指導 [主編　張雙獅]
22. 體育舞蹈教程 [主編 劉偉 陳志明 曾明]
23. 線性代數導學篇 [主編 史昱]
24. 信息技術基礎實訓與習題指導（Windows7+Office2016） [主編 周金容 唐天國]
25. 高等數學導學篇（下冊） [主編 李文婧 胡雷 尹金生]
26. 高等數學導學篇（上冊） [主編 李文婧 胡雷 尹金生]
27. 高等數學（下冊） [主編 李愛芹 胡雷 尹金生]
28. 高等數學（上冊） [主編 李愛芹 胡雷 尹金生]
29. 中華水文化（慕課版）（第二版） [畢雪燕 楊華軻 羅玲誼 等編著]
30. 電路與電子技術Ⅱ——電路分析基礎 [主編 陳曉 金哲]