清华大学计算机系列教材 数据结构与算法 上册 邓俊辉◎编著 内 容 简 介 本书是作者及其团队在清华大学讲授算法类课程三十年的经验集成，其中的“数据结构”获评清华大 学首批“标杆课程”，慕课“数据结构”与“计算几何”已有来自 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
