本书是国外数据结构与算法分析方面的标准教材,介绍了数据结构(大量数据的组织方法)以及算法分析(算法运行时间的估算)。本书的编写目标是同时讲授好的程序设计和算法分析技巧,使读者可以开发出具有***率的程序。 本书可作为**数据结构课程或研究生一年级算法分析课程的教材,使用本书需具有一些中级程序设计知识,还需要离散数学的一些背景知识。

出版者的话 译者序 前言 第1章 引论┊1 1.1 本书讨论的内容┊2 1.2 数学知识复习┊3 1.2.1 指数┊3 1.2.2 对数┊3 1.2.3 级数┊4 1.2.4 模运算┊5 1.2.5 证明方法┊5 1.3 递归简论┊7 总结┊10 练习┊10 参考文献┊11 第2章 算法分析┊13 2.1 数学基础┊14 2.2 模型┊16 2.3 要分析的问题┊16 2.4 运行时间计算┊18 2.4.1 一个简单的例子┊18 2.4.2 一般法则┊19 2.4.3 *大子序列和┊20 2.4.4 运行时间中的对数┊24 2.4.5 检验你的分析┊27 2.4.6 分析结果的准确性┊28 总结┊28 练习┊29 参考文献┊32 第3章 表、栈和队列┊35 3.1 抽象数据类型┊36 3.2 表ADT┊36 3.2.1 表的简单数组实现┊37 3.2.2 链表┊37 3.2.3 程序设计细节┊38 3.2.4 常见的错误┊42 3.2.5 双链表┊43 3.2.6 循环链表┊43 3.2.7 例子┊43 3.2.8 链表的游标实现┊47 3.3 栈ADT┊50 3.3.1 栈模型┊50 3.3.2 栈的实现┊51 3.3.3 应用┊56 3.4 队列ADT┊62 3.4.1 队列模型┊62 3.4.2 队列的数组实现┊62 3.4.3 队列的应用┊65 总结┊66 练习┊66 第4章 树┊71 4.1 预备知识┊72 4.1.1 树的实现┊73 4.1.2 树的遍历及应用┊74 4.2 二叉树┊76 4.2.1 实现┊77 4.2.2 表达式树┊77 4.3 查找树ADT——二叉查找树┊80 4.3.1 MakeEmpty┊80 4.3.2 Find┊81 4.3.3 FindMin和FindMax┊81 4.3.4 Insert┊81 4.3.5 Delete┊83 4.3.6 平均情形分析┊84 4.4 AVL树┊86 4.4.1 单旋转┊88 4.4.2 双旋转┊90 4.5 伸展树┊95 4.5.1 一个简单的想法┊96 4.5.2 展开┊97 4.6 树的遍历┊102 4.7 B树┊103 总结┊107 练习┊108 参考文献┊113 第5章 散列┊117 5.1 一般想法┊118 5.2 散列函数┊118 5.3 分离链接法┊120 5.4 开放定址法┊123 5.4.1 线性探测法┊124 5.4.2 平方探测法┊125 5.4.3 双散列┊129 5.5 再散列┊130 5.6 可扩散列┊132 总结┊133 练习┊134 参考文献┊137 第6章 优先队列(堆)┊139 6.1 模型┊140 6.2 一些简单的实现┊141 6.3 二叉堆┊141 6.3.1 结构性质┊141 6.3.2 堆序性质┊142 6.3.3 基本的堆操作┊143 6.3.4 其他的堆操作┊146 6.4 优先队列的应用┊149 6.4.1 选择问题┊149 6.4.2 事件模拟┊150 6.5 d-堆┊151 6.6 左式堆┊152 6.6.1 左式堆的性质┊152 6.6.2 左式堆的操作┊153 6.7 斜堆┊158 6.8 二项队列┊159 6.8.1 二项队列结构┊159 6.8.2 二项队列操作┊160 6.8.3 二项队列的实现┊162 总结┊165 练习┊166 参考文献┊169 第7章 排序┊173 7.1 预备知识┊174 7.2 插入排序┊174 7.2.1 算法┊174 7.2.2 插入排序的分析┊175 7.3 一些简单排序算法的下界┊175 7.4 希尔排序┊176 7.5 堆排序┊179 7.6 归并排序┊182 7.7 快速排序┊186 7.7.1 选取枢纽元┊187 7.7.2 分割策略┊188 7.7.3 小数组┊190 7.7.4 实际的快速排序例程┊190 7.7.5 快速排序的分析┊192 7.7.6 选择的线性期望时间算法┊194 7.8 大型结构的排序┊195 7.9 排序的一般下界┊196 7.10 桶式排序┊198 7.11 外部排序┊198 7.11.1 为什么需要新的算法┊198 7.11.2 外部排序模型┊199 7.11.3 简单算法┊199 7.11.4 多路合并┊200 7.11.5 多相合并┊201 7.11.6 替换选择┊202 总结┊203 练习┊204 参考文献┊207 第8章 不相交集ADT┊209 8.1 等价关系┊210 8.2 动态等价性问题┊210 8.3 基本数据结构┊212 8.4 灵巧求并算法┊214 8.5 路径压缩┊216 8.6 按秩求并和路径压缩的*坏情形┊217 8.7 一个应用┊221 总结┊222 练习┊222 参考文献┊223 第9章 图论算法┊225 9.1 若干定义┊226 9.2 拓扑排序┊228 9.3 *短路径算法┊230 9.3.1 无权*短路径┊232 9.3.2 Dijkstra算法┊235 9.3.3 具有负边值的图┊240 9.3.4 无圈图┊241 9.3.5 所有点对*短路径┊243 9.4 网络流问题┊243 9.5 *小生成树┊247 9.5.1 Prim算法┊248 9.5.2 Kruskal算法┊250 9.6 深度优先搜索的应用┊251 9.6.1 无向图┊252 9.6.2 双连通性┊253 9.6.3 欧拉回路┊256 9.6.4 有向图┊259 9.6.5 查找强分支┊260 9.7 NP-完全性介绍┊262 9.7.1 难与易┊262 9.7.2 NP类┊263 9.7.3 NP-完全问题┊264 总结┊266 练习┊266 参考文献┊270 第10章 算法设计技巧┊273 10.1 贪婪算法┊274 10.1.1 一个简单的调度问题┊274 10.1.2 Huffman编码┊276 10.1.3 近似装箱问题┊280 10.2 分治算法┊286 10.2.1 分治算法的运行时间┊287 10.2.2 *近点问题┊289 10.2.3 选择问题┊291 10.2.4 一些运算问题的理论改进┊294 10.3 动态规划┊297 10.3.1 用一个表代替递归┊298 10.3.2 矩阵乘法的顺序安排┊300 10.3.3 *优二叉查找树┊301 10.3.4 所有点对*短路径┊304 10.4 随机化算法┊306 10.4.1 随机数发生器┊307 10.4.2 跳跃表┊310 10.4.3 素性测试┊312 10.5 回溯算法┊314 10.5.1 收费公路重建问题┊314 10.5.2 博弈┊318 总结┊323 练习┊323 参考文献┊329 第11章 摊还分析┊333 11.1 一个无关的智力问题┊334 11.2 二项队列┊335 11.3 斜堆┊339 11.4 斐波那契堆┊341 11.4.1 切除左式堆中的节点┊341 11.4.2 二项队列的懒惰合并┊343 11.4.3 斐波那契堆操作┊346 11.4.4 时间界的证明┊346 11.5 伸展树┊348 总结┊351 练习┊351 参考文献┊353 第12章 **数据结构及其实现┊355 12.1 自顶向下伸展树┊356 12.2 红黑树┊361 12.2.1 自底向上插入┊362 12.2.2 自顶向下红黑树┊363 12.2.3 自顶向下删除┊367 12.3 确定性跳跃表┊368 12.4 AA树┊373 12.5 treap树┊378 12.6 k-d树┊379 12.7 配对堆┊383 总结┊387 练习┊387 参考文献┊389 索引┊391