编辑推荐

适读人群：《数据结构与算法分析：C++语言描述（第四版）》概念清楚，逻辑性强，内容新颖，适合作为大专院校计算机软件与计算机应用等相关专业的教材或参考书，也适合计算机工程技术人员参考。
　　本版特色如下：
　　*书中的阐述和算法均用C++新标准C++11的代码实现。
　　*unordered_map两个类模板的简要讨论。
　　*增加了基数排序和与选择相关问题下界的证明。增加了对AVL树删除算法的实现。使用新的union/find分析同时改进此前各版的较弱的O(Mlog*N)界。


内容简介

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

作者简介

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

目录

第1章程序设计：综述1
1．1《数据结构与算法分析：C++语言描述（第四版）》讨论的内容1
1．2数学知识复习2
1．2．1指数(exponent)2
1．2．2对数(logarithm)2
1．2．3级数(series)3
1．2．4模运算(modulararithmetic)4
1．2．5证明方法5
1．3递归简论7
1．4C++类10
1．4．1基本的class语法10
1．4．2构造函数的附加语法和访问
函数11
1．4．3接口与实现的分离13
1．4．4vector类和string类16
1．5C++细节17
1．5．1指针(pointer)18
1．5．2左值、右值和引用19
1．5．3参数传递21
1．5．4返回值传递23
1．5．5std：：swap和std：：move25
1．5．6五大函数：析构函数，拷贝构造
函数，移动构造函数，拷贝赋值
operator=，移动赋值operator=26
1．5．7C风格数组和字符串30
1．6模板31
1．6．1函数模板31
1．6．2类模板32
1．6．3Object、Comparable和一个
例子33
1．6．4函数对象34
1．6．5类模板的分离式编译37
1．7使用矩阵37
1．7．1数据成员、构造函数和基本访问
函数38
1．7．2operator[]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表ADT64
3．2．1表的简单数组实现65
3．2．2简单链表65
3．3STL中的vector和list67
3．3．1迭代器68
3．3．2例子：对表使用erase69
3．3．3const_iterators70
3．4vector的实现72
3．5list的实现76
3．6栈ADT86
3．6．1栈模型86
3．6．2栈的实现86
3．6．3应用87
3．7队列ADT93
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．1contains110
4．3．2findMin和findMax111
4．3．3insert112
4．3．4remove113
4．3．5析构函数和拷贝构造函数115
4．3．6平均情况分析115
4．4AVL树118
4．4．1单旋转119
4．4．2双旋转121
4．5伸展树128
4．5．1一个简单的想法(不能直接
使用)128
4．5．2展开130
4．6树的遍历134
4．7B树135
4．8标准库中的集合与映射140
4．8．1集合(set)140
4．8．2映射(map)141
4．8．3set和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．5d堆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对手下界(adversarylower
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(Mlog*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．2Dijkstra算法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．1Prim算法327
9．5．2Kruskal算法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．7NP完全性介绍340
9．7．1难与易341
9．7．2NP类341
9．7．3NP完全问题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．3treap树453
12．4后缀数组和后缀树456
12．4．1后缀数组456
12．4．2后缀树458
12．4．3后缀数组和后缀树的线性
时间构建461
12．5k-d树471
12．6配对堆474
小结479
练习479
参考文献483
附录A类模板的分离式编译486
索引489

前言/序言

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



其他推荐