數據結構與算法（上下冊）

清華大學計算機系列教材 數據結構與算法 上冊 鄧俊輝◎編著 內 容 簡 介 本書是作者及其團隊在清華大學講授算法類課程三十年的經驗集成，其中的“數據結構”獲評清華大 學首批“標桿課程”，慕課“數據結構”與“計算幾何”已有來自 160 多個國家和地區的 100 余萬人選修。 本書共 14 章，分上下兩冊。上冊包括算法概論、向量、列表、棧與隊列、二叉樹、二叉搜索樹共 6 章，下冊包括搜索樹應用、高級搜索樹、詞典、圖基礎、圖進階、優先級隊列、字符串、排序共 8 章，內 容覆蓋從線性到非線性的典型數據結構，以及算法設計的基本技巧、算法分析的基本方法。 本書語言精練、內容豐富，融知識性、趣味性為一體；配有大量精美的插圖，以可視化的形式揭示算 法的抽象原理及復雜過程；詳盡的交叉鏈接與索引，更令全書渾然一體，為讀者提供了良好的閱讀體驗。 本書是計算機相關專業數據結構與算法類課程的理想教材，是研究生入學考試的重要參考用書，也可作為 計算機相關專業人員的重要參考書。 版權所有，侵權必究。舉報：010-62782989，beiqinquan@tup.tsinghua.edu.cn。 圖書在版編目（CIP）數據 數據結構與算法：上下冊/鄧俊輝編著. --北京：清華大學出版社，2026.10. (清華大學計算機系列教材). -- ISBN 978-7-302-72915-0 Ⅰ. TP311.12 中國國家版本館CIP數據核字第20264GB020號 責任編輯：龍啟銘 封面設計：鄧俊輝 責任校對：李建莊 責任印制：叢懷宇 出版發行：清華大學出版社 網 址：https: www.tup.com.cn，https: www.wqxuetang.com 地 址：北京清華大學學研大廈 A 座 郵 編：100084 社 總 機：010-83470000 郵 購：010-62786544 投稿與讀者服務：010-62776969，c-service@tup.tsinghua.edu.cn 質量反饋：010-62772015，zhiliang@tup.tsinghua.edu.cn 配套資源下載：https: www.tup.com.cn，010-83470236 印 裝 者：小森印刷（北京）有限公司 經 銷：全國新華書店 開 本：185mm×260mm 印 張：22.25 字 數：577 千字 版 次：2026 年 10 月第 1 版 印 次：2026 年 10 月第 1 次印刷 印 數：1～2000 定 價：99.00 元（全兩冊） 產品編號：118607-01 All textbooks are crap imperfect, and this one is no exception. -- Jeff Erickson 第1章 算法概論 1  大師定理 24  大數乘法 25 §1A 從計算，到算法 2  Akra-Bazzi定理 26  工具與過程 2 1E3. 總和最大區間 26  明確與可行 3  從蠻力，到遞增 26  有窮與隨機 3  分而治之 27  不變與正確 4  減而治之 28  魯棒與復用 5  算法 + 數據結構 = 高效率計算 5 §1F 動態規劃 29 1F1. Fibonacci數 29 §1B 計算模型 6  遞歸 29 1B1. 圖靈機 6  記憶化 29 1B2. RAM 7  線性規劃 30 1F2. 最長公共子序列 31 §1C 漸近復雜度 9  LCS 31 1C1. 大O記號 9  遞歸 31  實例 9  子問題空間及轉換模式 32  更多記號 10  記憶化 33  空間復雜度 10  動態規劃 34 1C2. 多項式與可解 11 1C3. 指數與難解 12 第2章 向量 35 §1D 復雜度分析 13 §2A 抽象數據類型 36 1D1. 封底估算 13 2A1. 接口與實現 36 1D2. 級數 16 2A2. 從數組到向量 36 1D3. 可視化 17 2A3. Vector模板類 38  默認構造、析構方法 39 §1E 疊代與遞歸 19  基於復制的構造 40 1E1. 減而治之 19  減治 20 §2B 無序向量 41  遞歸跟蹤與調用樹 20 2B1. 插入與刪除 41  空間復雜度 21 2B2. 擴容 43  遞推方程 21 2B3. 均攤分析 44  數組倒置 21  加倍策略 44 1E2. 分而治之 22  遞增策略 44  還是數組求和 22  縮容 45  遞歸跟蹤 22 2B4. 查找與去重 45  忒修斯的繩線與遞歸深度 23  比對與比較 45  遞推方程 23  順序查找 46 A  去重 46  轉移 74 2B5. 遍歷 47 3B2. 復制與析構 74  深復制 74 §2C 有序向量 48  析構 75 2C1. 去重 48 3B3. 查找與去重 75 2C2. 二分查找（版本A） 50  查找 75 2C3. 二分查找（版本B） 52  去重 76 2C4. 二分查找（版本C） 53 3B4. 遍歷 76 2C5. 插值查找 55 §3C 有序列表 76 §2D 起泡排序 56  去重 76  查找 77  基本版 56  提前終止版 56 §3D 選擇排序 77  跳躍版 57  減而治之 77 §2E 歸並排序 58  實現 78  輪換 79  分治 58   數學期望 79 二路歸並 59  復雜度 60 §3E 插入排序 80 §2F 位圖 61  減而治之 80  實現 80 2F1. 結構 61  性能分析 80 2F2. 應用 62  逆序對 81  去重 62  篩法 63 §3F 歸並排序 82 2F3. 快速初始化 64  分而治之 82  校驗環 64  二路歸並 83  前綴 65  統計逆序對 83 第3章 列表 67 第4章 棧與隊列 85 §3A 抽象數據類型 68 §4A 棧 86  抽象數據類型 86 3A1. 循位置訪問 68  Stack模板類 86 3A2. 接口與實現 68  節點 68 §4B 調用棧 87  列表 69 4B1. 原理與空間 87  初始化 71  忒修斯的繩線 87  模擬循秩訪問 71  空間效率 88 §3B 無序列表 72 4B2. 尾遞歸 88 3B1. 插入、刪除與轉移 72 4B3. 頭遞歸 90  插入 72 §4C 棧的應用 91  刪除 73 B 4C1. 括號匹配 91 第5章 二叉樹 115  減而治之 91  多種括號 92 §5A 樹 116 4C2. 表達式求值 93  術語 116  減而治之 93  ADT接口及實現 117  借棧緩沖 94  §5B 二叉樹 118 實現 95 5B1. 性質與轉換 118 4C3. 逆波蘭表達式 97  求值算法 97 5B2. 實現 119  轉換 98  BinNode模板類 119  BinTree模板類 120 4C4. 棧混洗 98  計數 99 §5C 遍歷 122  甄別 100 5C1. 應用 122  操作序列與括號匹配 100  先序 123 §4D 隊列 101  中序 123  抽象數據類型 101  後序 124  Queue模板類 101 5C2. 先序遍歷 125 5C3. 中序遍歷 126 §4E 隊列的應用 102  輪轉調度 102 5C4. 中序後繼 128  前綴和 102  succ()接口 128  滑動窗口和 103  簡約遍歷 129  性能分析 129 §4F 雙棧當隊 104 5C5. 後序遍歷 130  記賬法 104 5C6. 層次遍歷 131  向量去重 105  算法實現 131  聚合法 106  完全二叉樹與滿二叉樹 132  勢能法 106  5C7. 重建 132 向量去重 107  先序+中序 132 §4G 最大矩形 107  先序+後序 133  蠻力算法 108 §5D Huffman編碼 134  單調棧 108  均攤分析 109 5D1. 問題與算法 134  單趟掃描 110  前綴無關編碼 134  最優帶權編碼樹 135 §4H 最大棧和最大隊列 112  貪心策略 136  最大棧 112 5D2. 正確性 136  壓縮空間 112 5D3. 算法實現 137  最大隊列 113  超字符與Huffman樹 137  優化入隊 114  構造編碼樹 138  棧加隊列 138 §5E 下界與最優 139 C 5E1. 比較樹 139 6C1. 理想平衡與漸近平衡 149  CBA 140 6C2. 等價變換 150  下界與樹高 140 5E2. 線性歸約 140 §6D AVL樹 151  歸約 140 6D1. 漸近平衡 151  SORTING N HUFFMAN 141  SORTING N RBM 142 6D2. 失衡與重平衡 152  SD N DIAM 142 6D3. 插入 152 6D4. 刪除 154 第6章 二叉搜索樹 143 6D5. [3+4-2]重構 155 §6A 查找 144 6A1. 循關鍵碼訪問 144 索引 157 6A2. 中序 145 關 鍵 詞 158 §6B 算法與實現 145 插 圖 162 6B1. 查找 145 6B2. 插入 146 算 法 165 6B3. 刪除 147 代 碼 166 §6C 平衡 148 D 清華大學計算機系列教材 數據結構與算法 下冊 鄧俊輝◎編著 內 容 簡 介 本書是作者及其團隊在清華大學講授算法類課程三十年的經驗集成，其中的“數據結構”獲評清華大 學首批“標桿課程”，慕課“數據結構”與“計算幾何”已有來自 160 多個國家和地區的 100 余萬人選修。 本書共 14 章，分上下兩冊。上冊包括算法概論、向量、列表、棧與隊列、二叉樹、二叉搜索樹共 6 章，下冊包括搜索樹應用、高級搜索樹、詞典、圖基礎、圖進階、優先級隊列、字符串、排序共 8 章，內 容覆蓋從線性到非線性的典型數據結構，以及算法設計的基本技巧、算法分析的基本方法。 本書語言精練、內容豐富，融知識性、趣味性為一體；配有大量精美的插圖，以可視化的形式揭示算 法的抽象原理及復雜過程；詳盡的交叉鏈接與索引，更令全書渾然一體，為讀者提供了良好的閱讀體驗。 本書是計算機相關專業數據結構與算法類課程的理想教材，是研究生入學考試的重要參考用書，也可作為 計算機相關專業人員的重要參考書。 版權所有，侵權必究。舉報：010-62782989，beiqinquan@tup.tsinghua.edu.cn。 圖書在版編目（CIP）數據 數據結構與算法：上下冊/鄧俊輝編著. --北京：清華大學出版社，2026.10. (清華大學計算機系列教材). -- ISBN 978-7-302-72915-0 Ⅰ. TP311.12 中國國家版本館CIP數據核字第20264GB020號 責任編輯：龍啟銘 封面設計：鄧俊輝 責任校對：李建莊 責任印制：叢懷宇 出版發行：清華大學出版社 網 址：https: www.tup.com.cn，https: www.wqxuetang.com 地 址：北京清華大學學研大廈 A 座 郵 編：100084 社 總 機：010-83470000 郵 購：010-62786544 投稿與讀者服務：010-62776969，c-service@tup.tsinghua.edu.cn 質量反饋：010-62772015，zhiliang@tup.tsinghua.edu.cn 配套資源下載：https: www.tup.com.cn，010-83470236 印 裝 者：小森印刷（北京）有限公司 經 銷：全國新華書店 開 本：185mm×260mm 印 張：22.25 字 數：577 千字 版 次：2026 年 10 月第 1 版 印 次：2026 年 10 月第 1 次印刷 印 數：1～2000 定 價：99.00 元（全兩冊） 產品編號：118607-01 a text-book must be quite exceptionally bad if it is not more intelligible than the majority of the notes taken even in good lectures. -- Jeseph John Thomson 第7章 搜索樹應用 167  三種情況 186  綜合評價 187 §7A 區間樹 168 8A4. 算法實現 188  穿刺查詢 168  接口 188  簡單情況 168  伸展 188  構造算法 169  查找 189  查找算法 170  插入 189  刪除 190 §7B 線段樹 171  啟示 171 §8B B-樹 191  空間爆炸 171 8B1. 分級存儲 191  BBST 172  數據爆炸與存儲鴻溝 191  合並 172  分級存儲與I/O 191  構造與查找算法 173  頁與空間局部性 192 §7C 範圍樹 174  訪問次序與緩存友好 192  範圍查詢 174 8B2. 結構 194  BBST 175  等價變換 194  MLST 176  多路平衡 195  分散級聯 177  模板類 196 §7D kd-樹 178 8B3. 查找 197  結構 178  算法及實現 197  查詢算法 179  性能與樹高 198  查詢效率 180 8B4. 插入 198  上溢修復 199 第8章 高級搜索樹 181  算法實現 200 8B5. 刪除 201 §8A 伸展樹 182  下溢修復 202 8A1. 逐層伸展 182  算法實現 204  局部性 182 §8C 紅黑樹 205  逐層伸展 183  壞情況 183 8C1. 動機 205  並發 205 8A2. 雙層伸展 184  持久 206  LR或RL 184  LL或RR 184 8C2. 結構 206  L或R 184  顏色 206  壞情況 185  黑高度 207  (2,4)-樹 208 8A3. 均攤分析 186  漸近平衡 209  勢能 186  接口 209  均攤 186 A 8C3. 插入 210 §9C 排解沖突 231  RR-1 210  RR-2 211 9C1. 開放散列 231  算法實現 212 9C2. 封閉散列 232 8C4. 刪除 213  試探鏈 232  BB-1 214  線性試探 232  BB-2R 214  BB-2B 215  實現 233  BB-3 215 9C3. 刪除與查找 234  算法實現 216 9C4. 插入與重散列 235 §8D 跳轉表 217 9C5. 平方試探 236 8D1. 構思與結構 217 9C6. 雙向平方試探 237  確定 217  隨機 218 §9D 應用 238  模板類 218 9D1. 桶排序 238  空間性能 219 9D2. 最大縫隙 239 8D2. 插入與刪除 219 9D3. 基數排序 239  插入 219 9D4. 整數排序 241  刪除 220 9D5. 計數排序 241 8D3. 查找及復雜度 221  算法 221  期望高度 221 第10章 圖基礎 243  橫向跳轉 222 §10A 概述 244  從線性，到非線性 244 第9章 詞典 223  術語 244 §9A 散列 224 §10B 表示與實現 246 9A1. 循對象訪問 224 10B1. 鄰接矩陣 248 9A2. 散列原理 225  原理 248 9A3. 沖突 226  實現 248  基本操作 249 §9B 散列函數 226  增減邊 250 9B1. 基本 226  增減頂點 250  評價標準與設計原則 227  枚舉鄰居 251  除余法 227 10B2. 鄰接表 251  周期性 227  聚集 228 §10C 廣度優先搜索 252  MAD法 228 10C1. 算法 252  更多 228 10C2. 實例 253 9B2. 隨機數 229 10C3. 推廣 254  生成隨機數 229 10C4. 性質與應用 255  生成隨機序列 230 9B3. 散列碼 230 §10D 深度優先搜索 255 B 10D1. 算法 255 12C2. 敗者樹 283 10D2. 實例 256 §12D 多叉堆 284 10D3. 推廣 256  PFS 284 10D4. 括號引理 257  多叉堆 285  最佳折中 285 §10E 拓撲排序 258 §12E 左式堆 286 10E1. 有向無環圖：零入度策略 258 12E1. 沿藤融合 286 10E2. 以終為始：零出度策略 259 12E2. 控制藤長 287 10E3. 算法實現 259  最右側藤、最短藤與交換 287  NLP與左式堆 287 第11章 圖進階 261 12E3. 融合算法 288 §11A 雙連通分量 262 12E4. ADT基本接口 290  刪除 290 11A1. 割點 262  插入 290 11A2. 準則 263 11A3. 算法 264 第13章 字符串 291 §11B Dijkstra算法 266 §13A 模式匹配 292 11B1. 優先級搜索 266 13A1. 字符串 292 11B2. 最短路徑 267 13A2. 模式匹配 292 11B3. 算法實現 268 13A3. 蠻力算法 293 §11C Prim算法 270 §13B KMP算法 294 11C1. 最小支撐樹 270 13B1. 原理 294 11C2. 算法實現 270 13B2. 查詢表 294 13B3. 建表 296 第12章 優先級隊列 273  理解 296  遞推 297 §12A 概述 274  需求 274 13B4. 均攤分析 298  優先級隊列 274  聚合法 298  記賬法 298 §12B 完全二叉堆 275 13B5. 再改進 298 12B1. 結構 275 §13C BC策略 300 12B2. 插入 275 13C1. 以終為始 300 12B3. 刪除 277 13C2. 壞字符 301 12B4. 建堆 278 13C3. 構造BC表 302 12B5. 堆排序 280 §13D GS策略 302 §12C 錦標賽樹 282 13D1. 好後綴 303 12C1. 勝者樹 282 C 13D2. 構造GS表 303  後向分析 316  MS後綴與SS表 303  移動次數 316  由SS表構造GS表 304 14A6. DUP劃分 317  構造SS表 305 14A7. LGU劃分 317 13D3. 貫通縱覽 306 §14B 選取 318 §13E Karp-Rabin算法 306 14B1. 多數元素 318 13E1. 串即是數 306 14B2. 聯合選取 319 13E2. 散列 307 14B3. 快速選取 321  指紋 307  沖突 307 14B4. 線性選取 322  指紋更新 308 §14C 希爾排序 323 13E3. 位寬 309 14C1. 框架與實現 323  問題規模 309  代價準則 309 14C2. 增量序列 324  Shell序列 324 §13F 鍵樹 310  引理L 325  TRIE 310  定理K 325  PATRICIA 310  Ternary Trie 310  有序性的累積 325 14C3. 更多增量序列 326  Papernov-Stasevic序列 326 第14章 排序 311  Pratt序列 326 §14A 快速排序 312  Sedgewick序列 326 14A1. 軸點與劃分 312 14A2. LUG劃分 313 索引 327 14A3. 疊代與貪心 314 關 鍵 詞 328 14A4. 遞歸深度 315  三者取中 315 插 圖 332  期望深度 315 算 法 335 14A5. 比較與移動 316  遞推分析 316 代 碼 336 D