本书是数据结构和算法分析的经典教材，书中使用主流的程序设计语言C++作为具体的实现语言。书中内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树算法、k-d树和配对堆等。本书把算法分析与C++程序的开发有机地结合起来，深入分析每种算法，内容全面、缜密严格，并细致讲解精心构造程序的方法。 

　　本版特色如下： 
　　*书中的阐述和算法均用C++新标准C++11的代码实现。 
　　*unordered_map两个类模板的简要讨论。 
　　*增加了基数排序和与选择相关问题下界的证明。增加了对AVL树删除算法的实现。使用新的union/find分析同时改进此前各版的较弱的O(Mlog*N)界。 

　　?目的/目标 
　　本书是《数据结构与算法分析——C++语言描述》的第四版，论述组织大量数据的方法——数据结构，以及算法运行时间的估计——算法分析。随着计算机的速度越来越快，对于能够处理大量输入数据的程序需求变得日益急迫。可是，由于在输入量很大时程序的低效率显得非常突出，因此又要求对效率问题给予更加严密的关注。通过在实际编程之前对算法进行分析，学生们可以确定一个特定的解决方案是否可行。例如，在本书中学生可查阅一些特定的问题并看到精心的实现怎样能够把处理大量数据的时间限制从若干个世纪减至不到一秒。因此，若无运行时间的阐释，就不会有算法和数据结构的提出。在某些情况下，对于影响实现的运行时间的一些微小细节都需要认真的探究。 
　　一旦解法被确定，接着就要编写程序。随着计算机功能的日益强大，它们必须解决的问题就变得更加庞大和复杂，这就要求开发更加复杂的程序。本书的目标是同时教授学生良好的程序设计技巧和算法分析能力，使他们开发的程序能够具有最高的效率。 
　　本书适合于高等数据结构课程或是算法分析第一年的研究生课程。学生应该具有中等程度的程序设计知识，包括指针、递归以及面向对象程序设计这样一些内容，此外还要具有一些离散数学的基础。 
　　处理方法 
　　虽然本书的内容大部分都与语言无关，但是，程序设计还是需要使用某种特定的语言。正如书名指出的，我们为本书选择了C++。 
　　C++已经成为主流系统编程语言。除修复C语言的许多语法漏洞之外，C++还提供一些直接结构(类和模板)来实现作为抽象数据类型的泛型数据结构。 
　　编写本书最困难的部分是决定C++所占的篇幅。使用太多C++的特性将使本书难以理解，使用太少又会使读者得不到比支持类的C语言教材更多的收获。 
　　我们所采取的做法是以一种基于对象的处理方式展示书中的内容。这样，本书几乎不存在对继承的使用。书中以类模板描述泛型数据结构。一般我们避免深奥的C++特性，但是使用了vector类和string类，如今它们已是C++标准的一部分。本书以前各版通过把类模板接口从其实现中分离出来已经做到了对类模板的实现。虽然这是有争议的首选方式，但它揭示出编译器使读者难以具体使用代码的一些问题。因此，这一版中联机代码把类模板作为一个独立的单元来介绍，无需接口与实现的分离。第1章提供了用于全书的C++特性的综述，并描述了我们对类模板的处理方式。附录A阐述如何能够重写类模板以使用分离式编译。 
　　以C++和Java二者描述的数据结构的完全版可在互联网上获得。我们使用类似的编码约定以使得这两种语言间平行的结构表现得更加明显。 
　　第四版最重要的变化概述 
　　本书第四版吸收了大量对错误的修正，书中许多部分经过修订以增加表述的清晰度。此外： 
　　第4章包含AVL树删除算法的实现，它是一个常常被读者提出的论题。 
　　第5章已被广泛修订和扩展，现已包含两个更新的算法：杜鹃散列和跳房子散列。此外，还添加了论述通用散列的新的一节。对C++中引入的unordered_set和unordered_ map两个类模板的简要讨论也是新加的内容。 
　　第6章基本没有变化，不过，二叉堆的实现用到了C++11版引入的移动操作(move operation)。 
　　现在的第7章增加了基数排序的内容，并添加了新的一节，论述下界的证明。排序的程序用到C++11版中引入的移动操作。 
　　第8章使用由Seidel和Sharir所作的新的union/find分析，并证明了O(M?(M, N))的界以代替前面各版较弱的O(M log*N)界。 
　　第12章添加了论述后缀树和后缀数组的材料，包括Karkkainen和Sanders的后缀数组线性时间构建算法(及其实现)。删除了讨论确定性跳跃表和AA树的两节。 
　　全书所出现的代码均用C++11作了更新。值得注意的是，这意味着C++11新特性的使用，包括auto关键字、范围for循环、移动构造和赋值，以及统一初始化(uniform initialization)。 
　　内容提要 
　　第1章包含离散数学和递归的一些复习材料。我相信熟练处置递归唯一的办法是反复不断地研读一些好的用法。因此，除第5章外，递归遍及本书每一章的例子之中。另外，第1章还介绍了一些材料，作为对基本C++的回顾，包括在C++类设计中对模板和一些重要结构的讨论。 
　　第2章处理算法分析。这一章阐述渐近分析和它的主要弱点。这里提供了许多例子，包括对对数运行时间的深入解释。通过直观地把一些简单递归程序转变成迭代程序而对它们进行分析。介绍了更复杂的分治程序，不过有些分析(求解递推关系)将推迟到第7章再详细阐述。 
　　第3章包括表、栈和队列。这一章包括对STL中vector类和list类的讨论，其中涉及到迭代器的一些材料，并提供对STL中vector类和list类的重要子集的实现。 
　　第4章讨论树，重点在查找树，包括外部查找树(B树)。UNIX文件系统和表达式树是作为例子来使用的。本章还介绍了AVL树和伸展树。关于查找树实现细节的更详细的处理放在第12章介绍。树的另外一些内容，如文件压缩和博弈树，推迟至第10章讨论。外部媒体上的数据结构作为几章中的最后论题来考虑。STL中set类和map类的讨论也在本章进行，其中包括一个重要的例子，该例使用3个分离的映射高效地解决一个问题。 
　　第5章讨论散列表，包括诸如分离链接法以及线性探测法和平方探测法这样一些经典算法，此外还有几个新算法，即杜鹃散列和跳房子散列。通用散列也在这里讨论，而对可扩散列的讨论则放在本章末尾进行。 
　　第6章是关于优先队列的。二叉堆也安排在这里，还有些额外的材料论述优先队列某些理论上有趣的实现。斐波那契堆在第11章讨论，配对堆在第12章讨论。 
　　第7章是排序。它是关于编程细节和分析的非常特殊的一章。所有重要的通用排序算法均被讨论并进行了比较。详细分析了4种算法：插入排序，希尔排序，堆排序，以及快速排序。本版新增加了基数排序和一些与选择相关问题的下界证明。外部排序的讨论安排在本章的末尾进行。 
　　第8章讨论不相交集算法并证明其运行时间。这是短小且特殊的一章，如果不讨论Kruskal算法则该章可以跳过。 
　　第9章讲授图论算法。图论算法的趣味性不仅因为它们在实践中经常发生，而且还因为它们的运行时间强烈地依赖于数据结构的恰当使用。实际上，所有标准算法都是和相应的数据结构、伪代码以及运行时间的分析一起介绍的。为把这些问题放在一个适当的上下文环境下，本章对复杂性理论(包括NP完全性和不可判定性)进行了简要的讨论。 
　　第10章通过考查一些常见问题的求解技巧来讨论算法设计。这一章通过大量实例而得到强化。这里及后面各章使用的伪代码使得学生对一个算法实例的理解不至于被实现的细节所困扰。 
　　第11章处理摊还分析。对来自第4章和第6章的3种数据结构以及本章介绍的斐波那契堆进行了分析。 
　　第12章讨论查找树算法、后缀树和后缀数组、k-d树、配对堆。不同于其他各章，本章为查找树和配对堆提供了完全和审慎的实现。材料的安排使得教师可以把一些内容整合到其他各章的讨论中。例如，第12章中的自顶向下红黑树可以和AVL树(第4章的)一起讨论。 
　　第1章～第9章为大多数一学期的数据结构课程提供了足够的材料。如果时间允许，那么第10章也可以包括进来。研究生的算法分析课程可以使用第7章～第11章的内容。在第11章所分析的高级数据结构可以容易地在前面各章中查到。第9章中对NP完全性的讨论太过简单，以至于不足以用于这样的一门算法分析课程。读者将会发现，参阅一些论述NP完全性的著述对深化本书内容大有裨益。 
　　练习 
　　在每章末尾提供的练习与正文中讲授内容的顺序相匹配。最后的一些练习是把一章作为一个整体来处理而不是针对特定的某一节来考虑的。难做的练习标以一个星号，更难的练习标注两个星号。 
　　参考文献 
　　参考文献列于每章的最后。一般说来，这些参考文献或者是历史性质的，代表着书中材料的原始来源，或者阐述对正文中给出结果的扩展和改进。有些文献提供一些练习的解法。 
　　补充材料 
　　所有读者均可从网站上获取下列补充资料： 
　　例子程序的源代码 
　　勘误表 
　　此外，下列材料只提供给Pearson Instructor Resource Center 上有资格的教师。如欲获取这些资料，可访问IRC或你的Pearson Education销售代表。 
　　书中挑选的一些练习的解答 
　　本书中的一些图示 
　　勘误表 
　　致谢 
　　在该丛书几部著作的准备过程中作者得到了许许多多朋友的帮助，有些人在本书的其他版本中列出。谢谢所有诸位。 
　　如同往常一样，Pearson专家们的努力使得本书的写作过程更加轻松。我愿意借此机会感谢我的编辑Tracy Johnson，以及制作编辑Marilyn Lloyd。贤妻Jill因其所做的每一件工作应该得到我特别的感谢。 
　　最后，我还要感谢广大的读者，他们发送E-mail信息并指出较早各版的错误和矛盾之处。我的网站www.cis.fiu.edu/~weiss也将包含更新后(C++和Java)的源代码，一个勘误表，以及到提交问题报告的一个链接。 
　　M．A．W． 
　　Miami，Florida 

　　冯舜玺，天津师范大学数学科学学院退休教授，曾任天津市计算数学学会常务理事，主要教学及研究方向为数值代数，组合数学，数据结构与算法分析。 Mark Allen Weiss，佛罗里达国际大学计算与信息科学学院教授、副院长，本科教育主任和研究生教育主任。他于1987年获得普林斯顿大学计算机科学博士学位，师从Bob Sedgewick。他曾经担任全美AP(Advanced Placement)考试计算机学科委员会的主席(2000-2004)。Weiss教授在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评．已被世界500余所大学用作教材。 

第1章 程序设计：综述 1
1．1 本书讨论的内容 1
1．2 数学知识复习 2
1．2．1 指数(exponent) 2
1．2．2 对数(logarithm) 2
1．2．3 级数(series) 3
1．2．4 模运算(modular arithmetic) 4
1．2．5 证明方法 5
1．3 递归简论 7
1．4 C++类 10
1．4．1 基本的class语法 10
1．4．2 构造函数的附加语法和访问
函数 11
1．4．3 接口与实现的分离 13
1．4．4 vector类和string类 16
1．5 C++细节 17
1．5．1 指针(pointer) 18
1．5．2 左值、右值和引用 19
1．5．3 参数传递 21
1．5．4 返回值传递 23
1．5．5 std：：swap和std：：move 25
1．5．6 五大函数：析构函数，拷贝构造
函数，移动构造函数，拷贝赋值
operator=，移动赋值operator= 26
1．5．7 C风格数组和字符串 30
1．6 模板 31
1．6．1 函数模板 31
1．6．2 类模板 32
1．6．3 Object、Comparable和一个
例子 33
1．6．4 函数对象 34
1．6．5 类模板的分离式编译 37
1．7 使用矩阵 37
1．7．1 数据成员、构造函数和基本访问
函数 38
1．7．2 operator[] 38
1．7．3 五大函数 39
小结 39
练习 39
参考文献 41
第2章 算法分析 42
2．1 数学基础 42
2．2 模型 44
2．3 要分析的问题 44
2．4 运行时间计算 47
2．4．1 一个简单的例子 47
2．4．2 一般法则 47
2．4．3 最大子序列和问题的求解 49
2．4．4 运行时间中的对数 54
2．4．5 最坏情形分析的局限性 57
小结 58
练习 58
参考文献 63
第3章 表、栈和队列 64
3．1 抽象数据类型(ADT) 64
3．2 表ADT 64
3．2．1 表的简单数组实现 65
3．2．2 简单链表 65
3．3 STL中的vector和list 67
3．3．1 迭代器 68
3．3．2 例子：对表使用erase 69
3．3．3 const_iterators 70
3．4 vector的实现 72
3．5 list的实现 76
3．6 栈ADT 86
3．6．1 栈模型 86
3．6．2 栈的实现 86
3．6．3 应用 87
3．7 队列ADT 93
3．7．1 队列模型 93
3．7．2 队列的数组实现 93
3．7．3 队列的应用 95
小结 96
练习 96
第4章 树 100
4．1 预备知识 100
4．1．1 树的实现 101
4．1．2 树的遍历及应用 102
4．2 二叉树 105
4．2．1 实现 105
4．2．2 一个例子――表达式树 105
4．3 查找树ADT――二叉查找树 108
4．3．1 contains 110
4．3．2 findMin和findMax 111
4．3．3 insert 112
4．3．4 remove 113
4．3．5 析构函数和拷贝构造函数 115
4．3．6 平均情况分析 115
4．4 AVL树 118
4．4．1 单旋转 119
4．4．2 双旋转 121
4．5 伸展树 128
4．5．1 一个简单的想法(不能直接
使用) 128
4．5．2 展开 130
4．6 树的遍历 134
4．7 B树 135
4．8 标准库中的集合与映射 140
4．8．1 集合(set) 140
4．8．2 映射(map) 141
4．8．3 set和map的实现 142
4．8．4 使用多个映射(map)的例 142
小结 147
练习 147
参考文献 153
第5章 散列 155
5．1 一般想法 155
5．2 散列函数 155
5．3 分离链接法 157
5．4 不用链表的散列表 161
5．4．1 线性探测法 161
5．4．2 平方探测法 163
5．4．3 双散列 166
5．5 再散列 167
5．6 标准库中的散列表 169
5．7 以最坏情形O(1)访问的散列表 170
5．7．1 完美散列 170
5．7．2 杜鹃散列 172
5．7．3 跳房子散列 181
5．8 通用散列 184
5．9 可扩散列 186
小结 188
练习 189
参考文献 193
第6章 优先队列(堆) 196
6．1 模型 196
6．2 一些简单的实现 197
6．3 二叉堆 197
6．3．1 结构性质 197
6．3．2 堆序性质 198
6．3．3 基本的堆操作 199
6．3．4 其他的堆操作 203
6．4 优先队列的应用 206
6．4．1 选择问题 206
6．4．2 事件模拟 207
6．5 d堆 208
6．6 左式堆 209
6．6．1 左式堆的性质 209
6．6．2 左式堆操作 210
6．7 斜堆 215
6．8 二项队列 216
6．8．1 二项队列构建 216
6．8．2 二项队列操作 217
6．8．3 二项队列的实现 219
6．9 标准库中的优先队列 224
小结 225
练习 225
参考文献 229
第7章 排序 232
7．1 预备知识 232
7．2 插入排序 233
7．2．1 算法 233
7．2．2 插入排序的STL实现 233
7．2．3 插入排序的分析 235
7．3 一些简单排序算法的下界 235
7．4 希尔排序 236
7．4．1 希尔排序的最坏情形分析 237
7．5 堆排序 239
7．5．1 堆排序的分析 241
7．6 归并排序 242
7．6．1 归并排序的分析 245
7．7 快速排序 247
7．7．1 选取枢纽元 249
7．7．2 分割策略 250
7．7．3 小数组 252
7．7．4 实际的快速排序例程 252
7．7．5 快速排序的分析 254
7．7．6 选择问题的线性期望时间
算法 256
7．8 排序算法的一般下界 258
7．8．1 决策树 258
7．9 选择问题的决策树下界 260
7．10 对手下界(adversary lower
bounds) 262
7．11 线性时间排序：桶式排序和
基数排序 265
7．12 外部排序 269
7．12．1 为什么需要一些新的算法 269
7．12．2 外部排序模型 269
7．12．3 简单算法 269
7．12．4 多路合并 270
7．12．5 多相合并 271
7．12．6 替换选择 272
小结 273
练习题 273
参考文献 278
第8章 不相交集类 281
8．1 等价关系 281
8．2 动态等价性问题 281
8．3 基本数据结构 283
8．4 灵巧求并算法 286
8．5 路径压缩 288
8．6 按秩求并和路径压缩的最坏
情形 289
8．6．1 缓慢增长的函数 289
8．6．2 通过递归分解进行的分析 290
8．6．3 一个O(M log*N)界 295
8．6．4 一个O(Mα(M， N))界 296
8．7 一个应用 297
小结 299
练习 299
参考文献 301
第9章 图论算法 303
9．1 若干定义 303
9．1．1 图的表示 304
9．2 拓扑排序 305
9．3 最短路径算法 308
9．3．1 无权最短路径 309
9．3．2 Dijkstra算法 312
9．3．3 具有负边值的图 317
9．3．4 无圈图 318
9．3．5 所有顶点对间的最短路径 320
9．3．6 最短路径的例 320
9．4 网络流问题 322
9．4．1 一个简单的最大流算法 323
9．5 最小生成树 326
9．5．1 Prim算法 327
9．5．2 Kruskal算法 329
9．6 深度优先搜索的应用 330
9．6．1 无向图 331
9．6．2 双连通性 332
9．6．3 欧拉回路 335
9．6．4 有向图 338
9．6．5 查找强分支 339
9．7 NP完全性介绍 340
9．7．1 难与易 341
9．7．2 NP类 341
9．7．3 NP完全问题 342
小结 344
练习 344
参考文献 350
第10章 算法设计技巧 353
10．1 贪婪算法 353
10．1．1 一个简单的调度问题 354
10．1．2 哈夫曼编码 355
10．1．3 近似装箱问题 359
10．2 分治算法 366
10．2．1 分治算法的运行时间 367
10．2．2 最近点问题 369
10．2．3 选择问题 371
10．2．4 一些算术问题的理论改进 374
10．3 动态规划 377
10．3．1 用表代替递归 377
10．3．2 矩阵乘法的顺序安排 379
10．3．3 最优二叉查找树 382
10．3．4 所有点对最短路径 384
10．4 随机化算法 386
10．4．1 随机数发生器 387
10．4．2 跳跃表 392
10．4．3 素性测试 393
10．5 回溯算法 396
10．5．1 收费公路重建问题 396
10．5．2 博弈 400




小结 405
练习 406
参考文献 413
第11章 摊还分析 418
11．1 一个无关的智力问题 418
11．2 二项队列 419
11．3 斜堆 423
11．4 斐波那契堆 425
11．4．1 切除左式堆中的节点 425
11．4．2 二项队列的懒惰合并 427
11．4．3 斐波那契堆操作 429
11．4．4 时间界的证明 430
11．5 伸展树 432
小结 436
练习 436
参考文献 437
第12章 高级数据结构及其实现 439
12．1 自顶向下伸展树 439
12．2 红黑树 445
12．2．1 自底向上的插入 446
12．2．2 自顶向下红黑树 447
12．2．3 自顶向下删除 452
12．3 treap树 453
12．4 后缀数组和后缀树 456
12．4．1 后缀数组 456
12．4．2 后缀树 458
12．4．3 后缀数组和后缀树的线性
时间构建 461
12．5 k-d树 471
12．6 配对堆 474
小结 479
练习 479
参考文献 483
附录A 类模板的分离式编译 486
索引 489