第1章  緒論 1
1.1  知識點 1
1.2  內容精要 1
1.2.1  數據結構的基本概念 1
1.2.2  數據的邏輯結構與存儲結構 2
1.2.3  算法的特性與算法的描述 3
1.3  典型試題精選與解析 8
1.3.1  典型試題 8
1.3.2  答案解析 11
第2章  線性表 14
2.1  知識點 14
2.2  線性表的內容精要（1）─線性表的順序表示 14
2.2.1  線性表的定義 14
2.2.2  線性表的順序表示與實現 15
2.2.3  典型例題解析 20
2.3  順序表的典型試題精選與解析 25
2.3.1  典型試題 25
2.3.2  答案解析 27
2.4  線性表的內容精要（2）─線性表的鏈式表示 33
2.4.1  單鏈表的存儲結構 33
2.4.2  單鏈表上的基本運算 35
2.5  循環單鏈表 40
2.5.1  循環鏈表的鏈式存儲 40
2.5.2  循環鏈表的合並操作 41
2.6  雙向鏈表 42
2.6.1  雙向鏈表的存儲結構 42
2.6.2  雙向鏈表的插入和刪除操作 43
2.6.3  鏈式存儲結構與順序存儲結構的優缺點 45
2.6.4  典型例題解析 45
2.7  線性表的典型試題精選與解析 51
2.7.1  典型試題 51
2.7.2  答案解析 57
2.8  歸納總結 69
第3章  棧與隊列 70
3.1  知識點 70
3.2  棧的內容精要 70
3.2.1  棧的定義和術語 70
3.2.2  棧的特性 71
3.2.3  棧的存儲結構 71
3.2.4  棧與遞歸 74
3.2.5  典型例題解析 77
3.3  棧的典型試題精選與解析 84
3.3.1  典型試題 84
3.3.2  答案解析 87
3.4  隊列的內容精要 103
3.4.1  隊列的定義和術語 103
3.4.2  隊列的順序存儲 104
3.4.3  隊列的鏈式存儲 107
3.4.4  鏈式隊列的基本運算 109
3.4.5  雙端隊列 110
3.4.6  典型例題解析 112
3.5  隊列的典型試題精選與解析 114
3.5.1  典型試題 114
3.5.2  答案解析 117
3.6  歸納總結 130
第4章  串、數組與廣義表 131
4.1  知識點 131
4.2  串的內容精要 131
4.2.1  串的定義 131
4.2.2  串的表示與實現 132
4.2.3  串的模式匹配 135
4.2.4  典型例題解析 141
4.3  串的典型試題精選與解析 145
4.3.1  典型試題 145
4.3.2  答案解析 148
4.4  數組的內容精要 151
4.4.1  數組的定義 151
4.4.2  數組的順序表示與實現 152
4.4.3  特殊矩陣的壓縮存儲 153
4.4.4  稀疏矩陣的壓縮存儲 155
4.4.5  典型例題解析 157
4.5  數組的典型試題精選與解析 161
4.5.1  典型試題 161
4.5.2  答案解析 165
4.6  廣義表的內容精要 171
4.6.1  廣義表的定義 171
4.6.2  廣義表的頭尾鏈表存儲結構及基本運算 172
4.6.3  廣義表的擴展線性鏈表存儲 176
4.6.4  典型例題解析 179
4.7  廣義表的典型試題精選與解析 186
4.7.1  典型試題 186
4.7.2  答案解析 187
4.8  歸納總結 189
第5章  樹 191
5.1  知識點 191
5.2  樹的內容精要（1）─樹和二叉樹的定義及性質 191
5.2.1  樹的定義和基本概念 191
5.2.2  樹的邏輯表示 193
5.2.3  二叉樹的定義 193
5.2.4  二叉樹的性質 195
5.2.5  二叉樹的存儲表示與實現 196
5.3  樹的典型試題精選與解析（1） 198
5.3.1  典型試題 198
5.3.2  答案解析 199
5.4  樹的內容精要（2）─二叉樹的遍歷和線索化 200
5.4.1  二叉樹的遍歷 200
5.4.2  線索二叉樹 207
5.4.3  典型例題解析 211
5.5  樹的典型試題精選與解析（2） 213
5.5.1  典型試題 213
5.5.2  答案解析 219
5.6  樹的內容精要（3）─樹的存儲結構和樹、森林的轉換 233
5.6.1  樹的存儲結構 233
5.6.2  樹、森林與二叉樹的轉換 235
5.6.3  樹和森林的遍歷 238
5.6.4  哈夫曼樹 239
5.6.5  典型例題解析 241
5.7  樹的典型試題精選與解析（3） 249
5.7.1  典型試題 249
5.7.2  答案解析 251
5.8  歸納總結 257
第6章  圖 258
6.1  知識點 258
6.2  圖的內容精要（1）─圖的定義及相關概念 258
6.2.1  圖的定義和基本概念 258
6.2.2  圖的存儲結構 261
6.3  圖的典型試題精選與解析（1） 266
6.3.1  典型試題 266
6.3.2  答案解析 268
6.4  圖的內容精要（2）─圖的遍歷 270
6.4.1  圖的深度優先搜索 270
6.4.2  圖的廣度優先搜索 272
6.4.3  典型例題解析 273
6.5  圖的典型試題精選與解析（2） 279
6.5.1  典型試題 279
6.5.2  答案解析 281
6.6  圖的內容精要（3）─圖的應用 293
6.6.1  小生成樹 293
6.6.2  AOV網與拓撲排序 298
6.6.3  AOE網與關鍵路徑 301
6.6.4  短路徑 303
6.6.5  典型例題解析 309
6.7  圖的典型試題精選與解析（3） 313
6.7.1  典型試題 313
6.7.2  答案解析 316
6.8  歸納總結 322
第7章  查找 323
7.1  知識點 323
7.2  查找的內容精要（1）─查找的定義及相關概念 323
7.2.1  查找的基本概念 323
7.2.2  順序表的查找 324
7.2.3  有序順序表的查找 325
7.2.4  索引順序表的查找 327
7.3  查找的典型試題精選與解析（1） 329
7.3.1  典型試題 329
7.3.2  答案解析 331
7.4  查找的內容精要（2）─動態查找 334
7.4.1  二叉排序樹 334
7.4.2  平衡二叉樹 339
7.4.3  B-樹與B 樹 343
7.5  查找的典型試題精選與解析（2） 347
7.5.1  典型試題 347
7.5.2  答案解析 349
7.6  查找的內容精要（3）─哈希表 354
7.6.1  哈希表的定義 354
7.6.2  哈希函數的構造方法 355
7.6.3  處理衝突的方法 356
7.6.4  哈希表應用舉例 358
7.7  查找的典型試題精選與解析（3） 362
7.7.1  典型試題 362
7.7.2  試題分析 363
7.8  歸納總結 366

第8章  排序 367
8.1  知識點 367
8.2  排序的內容精要 367
8.2.1  插入排序 367
8.2.2  選擇排序 372
8.2.3  交換排序 379
8.2.4  歸並排序 383
8.2.5  基數排序 384
8.3  排序的典型試題精選與解析 387
8.3.1  典型試題 387
8.3.2  答案解析 389
8.4  歸納總結 398
參考文獻 400

本書的組織分為兩部分：數據結構重點知識的總結和典型習題及分析解答。書中首先對數據結構主要內容進行梳理，然後通過篩選歷年計算機專業考研試題、各種競賽試題、軟考試題等具有典型的試題鞏固所學知識。本書重視數據結構核心思想的講解，同時兼顧算法實踐的理解和掌握，每章都提供了相關典型案例及其完整代碼，方便讀者學習數據結構算法思想。希望本書能給正在學習數據結構和打算考研的讀者朋友有所幫助和啟發。
本書的部分習題答案是針對經典數據結構教材進行分析和解答的，此外，還精選了歷年全國計算機專業考研試題和部分名校試題。編寫本書和教學的過程也是作者重新學習的過程，一個深切的感受就是無論是打算考研，還是參加各種競賽，數據結構知識是計算機相關專業學習和軟件開發的基礎，要想學好它，除了認真閱讀教材、認真思考外，還需要多動手、多上機、調試程序，隻有這樣，纔能把數據結構真正學好。
本書的課後習題解答均花費大量時間認真分析、嚴密求解得到。為了求解某個題目，可能需要認真研讀算法，例如在求解短路徑、關鍵路徑時，就需要真正理解算法思想和算法代碼的描述，隻有真正理解了，纔能知道求解問題時每一個變量和每一個修正過程的含義。本書所提供的算法均經過精心調試運行，雖然在調試程序上花費不少時間，但是感覺每一次都有很大收獲，因為在調試程序的過程中總會出現一些新的錯誤，在解決這些問題之後，對算法纔會有更深入的理解，同時也提高了程序調試技術。調試程序是一件花費時間的事情，但是隻有自己親自動手調試，纔能深刻理解算法思想，發現錯誤和不足，在調試程序的過程中，自身水平纔能得到提高。
本書的許多案例選自歷年全國考研試題、競賽試題和清華大學、華中科技大學、西北大學、西安電子科技大學、南京航空航天大學、南京理工大學、哈爾濱工業大學等著名高校考研試題，這些題目非常具有代表性，題目的設計涵蓋數據結構的各個方面，同時考查了數據結構的基礎知識和算法設計思想。本書內容及學習方法
本書內容包括數據線性表、棧、隊列、串、數組和廣義表、樹、圖、查找和排序等，涵蓋數據結構的主要知識、典型例題、算法實現和習題解析，是一本計算機專業人士學習數據結構與算法的參考用書，適合作為計算機考研和數據結構學習輔導用書。
對於初學者來說，數據結構這門課有許多抽像的概念，不是太容易掌握。萬事開頭難，隻要掌握了學習方法和技巧，學習任何東西都會變得很容易，學習數據結構也是如此。要想學好數據結構，首先應該有信心，要有戰勝困難的決心，不要有畏懼心理，一開始每個人都會遇到困難，重要的是堅持，不放棄。“路雖遠，行則將至；事雖難，做則必成。”任何事情都是這樣，學習亦如此。其次就是要掌握好C語言，C語言是基礎，因為本書中的算法都是用C語言描述的，即使之前沒有掌握好C語言也沒有關繫，讀者可以邊學數據結構，邊鞏固C語言知識。
不少讀者朋友在學習數據結構時，由於缺乏對高級程序設計語言的理解和掌握，造成在學習數據結構課程時存在很多疑惑和不解，這個是很多讀者遇到的問題。目前大多數數據結構采用C語言描述，很多同學對指針和結構體的用法不甚清楚，因此在學習數據結構時，對算法的理解往往一知半解，弄不清楚為什麼使用要一級指針和二級指針，這些疑惑在開始學習數據結構時就產生了，嚴重影響後續學習的積極性和效果。因此，建議讀者朋友在遇到這些困難時，一定要復習一下C語言基礎，尤其是指針和結構體的相關知識。另外，通過多上機調試程序，對學習和理解算法十分有幫助。
在閱讀本書過程中，可以邊看書，邊聽視頻講解，視頻講解主要針對本書中的難點和重點，每學完一部分內容，可通過調試本書配套的代碼，認真領會算法的思想，並思考為什麼要這樣實現，從而加深對數據結構概念和算法的理解。
源碼、教學視頻下載
本書配套的源碼與教學視頻，需用微信掃描右邊二維碼獲取，可按提示把鏈接轉發到自己的郵箱中下載。如果有疑問，請聯繫booksaga@163.com，郵件主題為“數據結構習題精解”。
致  謝
參加本書編寫的有陳銳、張建偉、馬軍霞、馬歡、谷培培、張亞洲、範艷煥和朱少林。其中，張建偉編寫第1章，張亞洲編寫第2章，朱少林編寫第3章，谷培培編寫第4章，馬軍霞編寫第5章，陳銳編寫第6章，馬歡編寫第7章，範艷煥編寫第8章。
由於時間倉促，加上作者水平有限，書中難免存在一些不足，懇請讀者批評指正。讀者朋友可通過下載資源中提供的電子郵箱與我們聯繫。祝願各位在閱讀本書的過程中有一個愉快的旅程。
在本書的寫作過程中，參閱了大量相關著作、教材，書後已給出參考文獻供讀者參考，在此向各位原作者致敬！在本書出版過程中，得到了清華大學出版社和鄭州輕工業大學的大力支持和幫助，在此表示衷心感謝。

作  者
2021年5月