2015版數(shù)據(jù)結(jié)構(gòu)高分筆記（第3版）

序
新版更新簡介及互動服務(wù)
新版使用說明
前言
口袋題庫考研版
第1章 緒論 1
本章概略 1
1.1 針對考研數(shù)據(jù)結(jié)構(gòu)的代碼書寫規(guī)范以及C&C++語言基礎(chǔ) 1
1.1.1 考研綜合應(yīng)用題中算法設(shè)計部分的代碼書寫規(guī)范 1
1.1.2 考研中的C&C++語言基礎(chǔ) 3
1.2 算法的時間復(fù)雜度與空間復(fù)雜度分析基礎(chǔ) 10
1.2.1 考研中的算法時間復(fù)雜度分析 10
1.2.2 例題選講 11
1.2.3 考研中的算法空間復(fù)雜度分析 12
1.3 數(shù)據(jù)結(jié)構(gòu)和算法的基本概念 12
1.3.1 數(shù)據(jù)結(jié)構(gòu)的基本概念 12
1.3.2 算法的基本概念 14
習(xí)題 15
習(xí)題答案 16
第2章 線性表 19
大綱要求 19
考點與要點分析 19
核心考點 19
基礎(chǔ)要點 19
本章知識體系框架圖 19
知識點講解 20
2.1 線性表的基本概念與實現(xiàn) 20
2.2 線性表的基本操作 23
2.2.1 線性表的定義 23
2.2.2 線性表的結(jié)構(gòu)定義 23
2.2.3 順序表的算法操作 24
2.2.4 單鏈表的算法操作 27
2.2.5 雙鏈表的算法操作 32
2.2.6 循環(huán)鏈表的算法操作 33
▲真題仿造 34
真題仿造答案與講解 34
上機實戰(zhàn) 35
習(xí)題+歷年真題 36
習(xí)題答案+歷年真題答案 40
第3章 棧、隊列和數(shù)組 53
大綱要求 53
考點與要點分析 53
核心考點 53
基礎(chǔ)要點 53
本章知識體系框架圖 53
知識點講解 54
3.1 棧和隊列的基本概念 54
3.1.1 棧的基本概念 54
3.1.2 隊列的基本概念 54
3.2 棧和隊列的存儲結(jié)構(gòu)、算法與應(yīng)用 54
3.2.1 本章所涉及的數(shù)據(jù)結(jié)構(gòu)定義 54
3.2.2 順序棧的基本算法操作 56
3.2.3 鏈棧的基本算法操作 57
3.2.4 棧的應(yīng)用 59
3.2.5 順序隊的算法操作 62
3.2.6 鏈隊的算法操作 64
3.3 特殊矩陣的壓縮存儲 66
▲真題仿造 68
真題仿造答案與講解 69
上機實戰(zhàn) 72
習(xí)題+歷年真題 72
習(xí)題答案+歷年真題答案 77
第4章 串（非統(tǒng)考補充內(nèi)容） 89
知識點講解 89
4.1 串?dāng)?shù)據(jù)類型的定義 89
4.1.1 串的定義 89
4.1.2 串的結(jié)構(gòu)定義 89
4.1.3 串的基本操作 90
4.2 串的模式匹配算法 93
4.2.1 一種簡單的模式匹配算法 93
4.2.2 KMP算法 94
習(xí)題 99
習(xí)題答案 100
上機實戰(zhàn) 109
第5章 數(shù)組和稀疏矩陣（非統(tǒng)考補充內(nèi)容） 110
知識點講解 110
5.1 數(shù)組 110
5.2 稀疏矩陣 111
習(xí)題 116
習(xí)題答案 117
上機實戰(zhàn) 125
第6章 樹與二叉樹 126
大綱要求 126
考點與要點分析 126
核心考點 126
基礎(chǔ)要點 126
本章知識體系框架圖 126
知識點講解 127
6.1 樹的基本概念 127
6.1.1 樹的定義 127
6.1.2 樹的基本術(shù)語 127
6.1.3 樹的存儲結(jié)構(gòu) 128
6.2 二叉樹 128
6.2.1 二叉樹的定義 128
6.2.2 二叉樹的主要性質(zhì) 129
6.2.3 二叉樹的存儲結(jié)構(gòu) 130
6.2.4 二叉樹的遍歷算法 131
6.2.5 線索二叉樹的基本概念和構(gòu)造 140
6.3 樹和森林 142
6.3.1 孩子兄弟存儲結(jié)構(gòu) 142
6.3.2 森林與二叉樹的轉(zhuǎn)換 143
6.3.3 樹和森林的遍歷 143
6.4 樹與二叉樹的應(yīng)用 144
6.4.1 二叉排序樹與平衡二叉樹 144
6.4.2 赫夫曼樹和赫夫曼編碼 144
▲真題仿造 146
真題仿造答案與解析 147
上機實戰(zhàn) 148
習(xí)題+歷年真題 149
習(xí)題答案+歷年真題答案 154
第7章 圖 170
大綱要求 170
考點與要點分析 170
核心考點 170
基礎(chǔ)要點 170
本章知識體系框架圖 170
知識點講解 171
7.1 圖的基本概念 171
7.2 圖的存儲結(jié)構(gòu) 172
7.2.1 鄰接矩陣 172
7.2.2 鄰接表 173
7.2.3 鄰接多重表 174
7.3 圖的遍歷算法操作 175
7.3.1 深度優(yōu)先搜索遍歷 175
7.3.2 廣度優(yōu)先搜索遍歷 176
7.3.3 例題選講 178
7.4 最小（代價）生成樹 180
7.4.1 普里姆算法和克魯斯卡爾算法 180
7.4.2 例題選講 184
7.5 最短路徑 185
7.5.1 迪杰斯特拉算法 185
7.5.2 弗洛伊德算法 191
7.6 拓?fù)渑判?194
7.6.1 AOV網(wǎng) 194
7.6.2 拓?fù)渑判?194
7.6.3 例題選講 196
7.7 關(guān)鍵路徑 197
7.7.1 AOE網(wǎng) 197
7.7.2 關(guān)鍵路徑 197
▲真題仿造 200
真題仿造答案解析 200
上機實戰(zhàn) 202
習(xí)題+歷年真題 203
習(xí)題答案+歷年真題答案 209
第8章 排序 221
大綱要求 221
考點與要點分析 221
核心考點 221
基礎(chǔ)要點 221
本章知識體系框架圖 222
知識點講解 222
8.1 排序的基本概念 222
8.1.1 排序 222
8.1.2 穩(wěn)定性 222
8.1.3 排序算法的分類 222
8.2 插入類排序 223
8.2.1 直接插入排序 223
8.2.2 折半插入排序 224
8.2.3 希爾排序 225
8.3 交換類排序 227
8.3.1 起泡排序 227
8.3.2 快速排序 228
8.4 選擇類排序 230
8.4.1 簡單選擇排序 230
8.4.2 堆排序 231
8.5 二路歸并排序 234
8.6 基數(shù)排序 235
8.7 外部排序 238
8.7.1 基本概念 238
8.7.2 歸并排序法 238
8.7.3 敗者樹 240
▲真題仿造 242
真題仿造答案與解析 243
上機實戰(zhàn) 244
習(xí)題+歷年真題 244
習(xí)題答案+歷年真題答案 249
第9章 查找 259
大綱要求 259
考點與要點分析 259
核心考點 259
基礎(chǔ)要點 259
本章知識體系框架圖 259
知識點講解 260
9.1 查找的基本概念、順序查找法、折半查找法 260
9.1.1 查找的基本概念 260
9.1.2 順序查找法 261
9.1.3 折半查找法 261
9.1.4 分塊查找 263
9.2 二叉排序樹、平衡二叉樹 264
9.2.1 二叉排序樹 264
9.2.2 平衡二叉樹 267
9.3 B-樹的基本概念及其基本操作、B+樹的基本概念 269
9.3.1 B-樹的基本概念 269
9.3.2 B-樹的基本操作 271
9.3.3 B+樹的基本概念 275
9.4 散列表 276
9.4.1 散列表的概念 276
9.4.2 散列表的建立方法以及沖突解決方法 276
9.4.3 散列表的性能分析 280
▲真題仿造 281
真題仿造答案與解析 281
上機實戰(zhàn) 282
習(xí)題+歷年真題 282
習(xí)題答案+歷年真題答案 287
第10章 考研中某些算法的分治法解釋 300
附錄 304
附錄A 歷年真題分值、考點統(tǒng)計表 304
附錄B 歷年真題考點索引表 306
參考文獻(xiàn) 308