2020版數據結構高分筆記(第8版)（簡體書）

新版使用說明:
*為穩妥的複習辦法是，準備一本知識點講解更為豐富的“資料結構”科目書籍，例如嚴蔚敏老師的《資料結構》，把它當做“知識點字典”，複習的時候先看本輔導書，等把本書中涉及的知識點全部熟練掌握之後，如時間有富餘，再去嚴老師的書中進行知識點擴展，查缺補漏。本書是根據現有多本資料結構權威書籍，以往年多份考研大綱為參考系，對知識點進行提純，並結合通俗易懂的講解方式而編寫而成的，雖精簡實用卻難面面俱到，因此需要結合考生自己複習時間的多少，合理規劃在本書以及其他書籍上所花的時間。相信按照這種方法，可以大大提高考生的複習效率。*近考研形勢又有了新的變化，具體如何變考生可以自己去詳細瞭解，但是不論怎麼變上邊提到的方法都是適用的，因為這種方法針對的是資料結構這門課的掌握程度而不僅僅是應付某一次考試。
注意：本書中所出現的所有大綱字樣，均不特指任一版本的資料結構考研大綱，這裡的大綱是根據往年所有大綱以及考研真題所總結出來的一個大綱。

天勤論壇，取名自古訓“天道酬勤”，意為考研路上，困苦實多，然而天自有道，勤懇付出者，必有應得之酬勞。天勤論壇由浙大、北航等多所計算機專業名校的研究生創辦，團隊所有成員皆親身經歷過計算機專業考研的磨煉，於是本著為考生服務的熱情，共同搭建了此交流平臺。
由天勤論壇組編的高分筆記系列計算機考研輔導書，融入了論壇答疑的精華內容，論壇組織了高分考生進行勘誤，不斷完善此套書籍。考生在書中遇到疑問，也可在線與作者進行交流。
為提高考生算法設計能力，團隊搭建了專門針對計算機考研學子的在線算法測試平臺——ACM俱樂部（acmclub.com），希望能借此幫助考生提高複習效率。

本書針對近幾年全國計算機學科專業綜合考試大綱的“資料結構”部分進行了深入解讀，以一種獨創的方式對考試大綱知識點進行了講解，即從考生的視角剖析知識難點；以通俗易懂的語言取代晦澀難懂的專業術語；以成功考生的親身經歷指引複習方向；以風趣幽默的筆觸緩解考研壓力。讀者對書中的知識點講解有任何疑問都可與作者進行在線互動，為考生解決複習中的疑難點，提高考生的複習效率。
根據計算機專業研究生入學考試形勢的變化，書中對大量非統考知識點進行了講解，使本書所包含的知識點除覆蓋統考大綱的所有內容外，還包括了各自主命題高校所要求的知識點。

序
輔導專欄簡介
前言
第1章 緒論 1
本章概略 1
1.1 針對考研資料結構的代碼書寫規範以及C與C 語言基礎 1
1.1.1 考研綜合應用題中算法設計部分的代碼書寫規範 1
1.1.2 考研中的C與C 語言基礎 3
1.2 算法的時間複雜度與空間複雜度分析基礎 12
1.2.1 考研中的算法時間複雜度分析 12
1.2.2 例題選講 12
1.2.3 考研中的算法空間複雜度分析 14
1.3 資料結構和算法的基本概念 14
1.3.1 資料結構的基本概念 14
1.3.2 算法的基本概念 15
習題 16
習題答案 17
第2章 線性表 20
大綱要求 20
考點與要點分析 20
核心考點 20
基礎要點 20
知識點講解 20
2.1 線性表的基本概念與實現 20
2.2 線性表的結構體定義和基本操作 24
2.2.1 線性表的結構體定義 24
2.2.2 順序表的操作 26
2.2.3 單鏈表的操作 29
2.2.4 雙鏈表的操作 33
2.2.5 迴圈鏈表的操作 35
▲真題仿造 35
真題仿造答案與解析 36
習題 真題精選 37
習題答案 真題精選答案 41
第3章 棧和佇列 55
大綱要求 55
考點與要點分析 55
核心考點 55
基礎要點 55
知識點講解 55
3.1 棧和佇列的基本概念 55
3.1.1 棧的基本概念 55
3.1.2 佇列的基本概念 56
3.2 棧和佇列的存儲結構、算法與應用 56
3.2.1 本章所涉及的結構體定義 56
3.2.2 順序棧 57
3.2.3 鏈棧 59
3.2.4 棧的應用 60
3.2.5 順序隊 64
3.2.6 鏈隊 66
3.3 抽象資料類型 69
▲真題仿造 71
真題仿造答案與解析 71
習題 真題精選 74
習題答案 真題精選答案 79
第4章 串 91
知識點講解 91
4.1 串資料類型的定義 91
4.1.1 串的定義 91
4.1.2 串的存儲結構 91
4.1.3 串的基本操作 92
4.2 串的模式匹配算法 95
4.2.1 簡單模式匹配算法 95
4.2.2 KMP算法 96
4.2.3 KMP算法的改進 99
習題 102
習題答案 103
第5章 陣列、矩陣與廣義表 113
知識點講解 113
5.1 陣列 113
5.2 矩陣的壓縮存儲 114
5.2.1 矩陣 114
5.2.2 特殊矩陣和疏鬆陣列 115
5.3 廣義表 121
習題 122
習題答案 123
第6章 樹與二叉樹 132
大綱要求 132
考點與要點分析 132
核心考點 132
基礎要點 132
知識點講解 132
6.1 樹的基本概念 132
6.1.1 樹的定義 132
6.1.2 樹的基本術語 132
6.1.3 樹的存儲結構 133
6.2 二叉樹 134
6.2.1 二叉樹的定義 134
6.2.2 二叉樹的主要性質 135
6.2.3 二叉樹的存儲結構 137
6.2.4 二叉樹的遍歷算法 137
6.2.5 二叉樹遍歷算法的改進 146
6.3 樹和森林與二叉樹的互相轉換 155
6.3.1 樹轉換為二叉樹 155
6.3.2 二叉樹轉換為樹 156
6.3.3 森林轉換為二叉樹 156
6.3.4 二叉樹轉換為森林 157
6.3.5 樹和森林的遍歷 157
6.4 樹與二叉樹的應用 158
6.4.1 二叉排序樹與平衡二叉樹 158
6.4.2 赫夫曼樹和赫夫曼編碼 159
▲真題仿造 162
真題仿造答案與解析 162
習題 真題精選 163
習題答案 真題精選答案 168
第7章 圖 183
大綱要求 183
考點與要點分析 183
核心考點 183
基礎要點 183
知識點講解 183
7.1 圖的基本概念 183
7.2 圖的存儲結構 184
7.2.1 鄰接矩陣 185
7.2.2 鄰接表 186
7.2.3 鄰接多重表 187
7.3 圖的遍歷算法操作 188
7.3.1 深度優先搜索遍歷 188
7.3.2 廣度優先搜索遍歷 189
7.3.3 例題選講 190
7.4 最小（代價）生成樹 193
7.4.1 普裡姆算法和克魯斯卡爾算法 193
7.4.2 例題選講 197
7.5 最短路徑 198
7.5.1 迪傑斯特拉算法 198
7.5.2 佛洛德算法 204
7.6 拓撲排序 207
7.6.1 AOV網 207
7.6.2 拓撲排序核心算法 207
7.6.3 例題選講 209
7.7 關鍵路徑 209
7.7.1 AOE網 209
7.7.2 關鍵路徑核心算法 210
▲真題仿造 213
真題仿造答案與解析 213
習題 真題精選 215
習題答案 真題精選答案 221
第8章 排序 234
大綱要求 234
考點與要點分析 234
核心考點 234
基礎要點 234
知識點講解 235
8.1 排序的基本概念 235
8.1.1 排序 235
8.1.2 穩定性 235
8.1.3 排序算法的分類 235
8.2 插入類排序 236
8.2.1 直接插入排序 236
8.2.2 折半插入排序 237
8.2.3 希爾排序 238
8.3 交換類排序 240
8.3.1 起泡排序 240
8.3.2 快速排序 241
8.4 選擇類排序 243
8.4.1 簡單選擇排序 243
8.4.2 堆排序 244
8.5 二路歸併排序 247
8.6 基數排序 248
8.7 外部排序 252
8.7.1 概念與流程 252
8.7.2 置換-選擇排序 253
8.7.3 最佳歸併樹 254
8.7.4 敗者樹 255
8.7.5 時間與空間複雜度相關問題 257
8.8 排序知識點小結 258
▲真題仿造 259
真題仿造答案與解析 259
習題 真題精選 260
習題答案 真題精選答案 265
第9章 查找 275
大綱要求 275
考點與要點分析 275
核心考點 275
基礎要點 275
知識點講解 275
9.1 查找的基本概念、順序查找法、折半查找法 275
9.1.1 查找的基本概念 275
9.1.2 順序查找法 276
9.1.3 折半查找法 277
9.1.4 分塊查找 279
9.2 二叉排序樹與平衡二叉樹 280
9.2.1 二叉排序樹 280
9.2.2 平衡二叉樹 283
9.3 B-樹的基本概念及其基本操作、B 樹的基本概念 286
9.3.1 B-樹（B樹）的基本概念 286
9.3.2 B-樹的基本操作 288
9.3.3 B 樹的基本概念 292
9.4 散列表 293
9.4.1 散列表的概念 293
9.4.2 散列表的建立方法以及衝突解決方法 293
9.4.3 散清單的性能分析 297
▲真題仿造 298
真題仿造答案與解析 298
習題 真題精選 299
習題答案 真題精選答案 304
第10章 考研中某些算法的分治法解釋 318
參考文獻 322