编辑推荐

适读人群：《数据结构与算法分析 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余所大学用作教材。

目录

Chapter1Programming：AGeneralOverview1
1．1What’sThisBookAbout?1
1．2MathematicsReview2
1．2．1Exponents3
1．2．2Logarithms3
1．2．3Series4
1．2．4ModularArithmetic5
1．2．5ThePWord6
1．3ABriefIntroductiontoRecursion8
1．4C++Classes12
1．4．1BasicclassSyntax12
1．4．2ExtraConstructorSyntaxandAccessors13
1．4．3SeparationofInterfaceandImplementation16
1．4．4vectorandstring19
1．5C++Details21
1．5．1Pointers21
1．5．2Lvalues，Rvalues，andReferences23
1．5．3ParameterPassing25
1．5．4ReturnPassing27
1．5．5std：：swapandstd：：move29
1．5．6TheBig-Five：Destructor，CopyConstructor，MoveConstructor，Copy
Assignmentoperator=，MoveAssignmentoperator=30
1．5．7C-styleArraysandStrings35
1．6Templates36
1．6．1FunctionTemplates37
1．6．2ClassTemplates38
1．6．3Object，Comparable，andanExample39
1．6．4FunctionObjects41
1．6．5SeparateCompilationofClassTemplates44
1．7UsingMatrices44
1．7．1TheDataMembers，Constructor，andBasicAccessors44
1．7．2operator[]45
1．7．3Big-Five46
Summary46
Exercises46
References48
Chapter2AlgorithmAnalysis51
2．1MathematicalBackground51
2．2Model54
2．3WhattoAnalyze54
2．4Running-TimeCalculations57
2．4．1ASimpleExample58
2．4．2GeneralRules58
2．4．3SolutionsfortheMaximumSubsequence
SumProblem60
2．4．4LogarithmsintheRunningTime66
2．4．5LimitationsofWorst-CaseAnalysis70
Summary70
Exercises71
References76
Chapter3Lists，Stacks，andQueues77
3．1AbstractDataTypes(ADTs)77
3．2TheListADT78
3．2．1SimpleArrayImplementationofLists78
3．2．2SimpleLinkedLists79
3．3vectorandlistintheSTL80
3．3．1Iterators82
3．3．2Example：UsingeraseonaList83
3．3．3const_iterators84
3．4Implementationofvector86
3．5Implementationoflist91
3．6TheStackADT103
3．6．1StackModel103
3．6．2ImplementationofStacks104
3．6．3Applications104
3．7TheQueueADT112
3．7．1QueueModel113
3．7．2ArrayImplementationofQueues113
3．7．3ApplicationsofQueues115
Summary116
Exercises116
Chapter4Trees121
4．1Preliminaries121
4．1．1ImplementationofTrees122
4．1．2TreeTraversalswithanApplication123
4．2BinaryTrees126
4．2．1Implementation128
4．2．2AnExample：ExpressionTrees128
4．3TheSearchTreeADT?aBinarySearchTrees132
4．3．1contains134
4．3．2findMinandfindMax135
4．3．3insert136
4．3．4remove139
4．3．5DestructorandCopyConstructor141
4．3．6Average-CaseAnalysis141
4．4AVLTrees144
4．4．1SingleRotation147
4．4．2DoubleRotation149
4．5SplayTrees158
4．5．1ASimpleIdea(ThatDoesNotWork)158
4．5．2Splaying160
4．6TreeTraversals(Revisited)166
4．7B-Trees168
4．8SetsandMapsintheStandardLibrary173
4．8．1Sets173
4．8．2Maps174
4．8．3Implementationofsetandmap175
4．8．4AnExampleThatUsesSeveralMaps176
Summary181
Exercises182
References189
Chapter5Hashing193
5．1GeneralIdea193
5．2HashFunction194
5．3SeparateChaining196
5．4HashTableswithoutLinkedLists201
5．4．1LinearProbing201
5．4．2QuadraticProbing202
5．4．3DoubleHashing207
5．5Rehashing208
5．6HashTablesintheStandardLibrary210
5．7HashTableswithWorst-CaseO(1)Access212
5．7．1PerfectHashing213
5．7．2CuckooHashing215
5．7．3HopscotchHashing227
5．8UniversalHashing230
5．9ExtendibleHashing233
Summary236
Exercises237
References241
Chapter6PriorityQueues(Heaps)245
6．1Model245
6．2SimpleImplementations246
6．3BinaryHeap247
6．3．1StructureProperty247
6．3．2Heap-OrderProperty248
6．3．3BasicHeapOperations249
6．3．4OtherHeapOperations252
6．4ApplicationsofPriorityQueues257
6．4．1TheSelectionProblem258
6．4．2EventSimulation259
6．5d-Heaps260
6．6LeftistHeaps261
6．6．1LeftistHeapProperty261
6．6．2LeftistHeapOperations262
6．7SkewHeaps269
6．8BinomialQueues271
6．8．1BinomialQueueStructure271
6．8．2BinomialQueueOperations271
6．8．3ImplementationofBinomialQueues276
6．9PriorityQueuesintheStandardLibrary282
Summary283
Exercises283
References288
Chapter7Sorting291
7．1Preliminaries291
7．2InsertionSort292
7．2．1TheAlgorithm292
7．2．2STLImplementationofInsertionSort293
7．2．3AnalysisofInsertionSort294
7．3ALowerBoundforSimpleSortingAlgorithms295
7．4Shellsort296
7．4．1Worst-CaseAnalysisofShellsort297
7．5Heapsort300
7．5．1AnalysisofHeapsort301
7．6Mergesort304
7．6．1AnalysisofMergesort306
7．7Quicksort309
7．7．1PickingthePivot311
7．7．2PartitioningStrategy313
7．7．3SmallArrays315
7．7．4ActualQuicksortRoutines315
7．7．5AnalysisofQuicksort318
7．7．6ALinear-Expected-TimeAlgorithmforSelection321
7．8AGeneralLowerBoundforSorting323
7．8．1DecisionTrees323
7．9Decision-TreeLowerBoundsforSelectionProblems325
7．10AdversaryLowerBounds328
7．11Linear-TimeSorts：BucketSortandRadixSort331
7．12ExternalSorting336
7．12．1WhyWeNeedNewAlgorithms336
7．12．2ModelforExternalSorting336
7．12．3TheSimpleAlgorithm337
7．12．4MultiwayMerge338
7．12．5PolyphaseMerge339
7．12．6ReplacementSelection340
Summary341
Exercises341
References347
Chapter8TheDisjointSetsClass351
8．1EquivalenceRelations351
8．2TheDynamicEquivalenceProblem352
8．3BasicDataStructure353
8．4SmartUnionAlgorithms357
8．5PathCompression360
8．6WorstCaseforUnion-by-RankandPathCompression361
8．6．1SlowlyGrowingFunctions362
8．6．2AnAnalysisbyRecursiveDecomposition362
8．6．3AnO(Mlog*N)Bound369
8．6．4AnO(M|á(M，N))Bound370
8．7AnApplication372
Summary374
Exercises375
References376
Chapter9GraphAlgorithms379
9．1Definitions379
9．1．1RepresentationofGraphs380
9．2TopologicalSort382
9．3Shortest-PathAlgorithms386
9．3．1UnweightedShortestPaths387
9．3．2Dijkstra’sAlgorithm391
9．3．3GraphswithNegativeEdgeCosts400
9．3．4AcyclicGraphs400
9．3．5All-PairsShortestPath404
9．3．6ShortestPathExample404
9．4NetworkFlowProblems406
9．4．1ASimpleMaximum-FlowAlgorithm408
9．5MinimumSpanningTree413
9．5．1Prim’sAlgorithm414
9．5．2Kruskal’sAlgorithm417
9．6ApplicationsofDepth-FirstSearch419
9．6．1UndirectedGraphs420
9．6．2Biconnectivity421
9．6．3EulerCircuits425
9．6．4DirectedGraphs429
9．6．5FindingStrongComponents431
9．7IntroductiontoNP-Completeness432
9．7．1Easyvs．Hard433
9．7．2TheClassNP434
9．7．3NP-CompleteProblems434
Summary437
Exercises437
References445
Chapter10AlgorithmDesignTechniques449
10．1GreedyAlgorithms449
10．1．1ASimpleSchedulingProblem450
10．1．2HuffmanCodes453
10．1．3ApproximateBinPacking459
10．2DivideandConquer467
10．2．1RunningTimeofDivide-and-ConquerAlgorithms468
10．2．2Closest-PointsProblem470
10．2．3TheSelectionProblem475
10．2．4TheoreticalImprovementsforArithmeticProblems478
10．3DynamicProgramming482
10．3．1UsingaTableInsteadofRecursion483
10．3．2OrderingMatrixMultiplications485
10．3．3OptimalBinarySearchTree487
10．3．4All-PairsShortestPath491
10．4RandomizedAlgorithms494
10．4．1Random-NumberGenerators495
10．4．2SkipLists500
10．4．3PrimalityTesting503
10．5BacktrackingAlgorithms506
10．5．1TheTurnpikeReconstructionProblem506
10．5．2Games511
Summary518
Exercises518
References527
Chapter11AmortizedAnalysis533
11．1AnUnrelatedPuzzle534
11．2BinomialQueues534
11．3SkewHeaps539
11．4FibonacciHeaps541
11．4．1CuttingNodesinLeftistHeaps542
11．4．2LazyMergingforBinomialQueues544
11．4．3TheFibonacciHeapOperations548
11．4．4ProofoftheTimeBound549
11．5SplayTrees551
Summary555
Exercises556
References557
Chapter12AdvancedDataStructures
andImplementation559
12．1Top-DownSplayTrees559
12．2Red-BlackTrees566
12．2．1Bottom-UpInsertion567
12．2．2Top-DownRed-BlackTrees568
12．2．3Top-DownDeletion570
12．3Treaps576
12．4SuffixArraysandSuffixTrees579
12．4．1SuffixArrays580
12．4．2SuffixTrees583
12．4．3Linear-TimeConstructionofSuffixArraysandSuffixTrees586
12．5k-dTrees596
12．6PairingHeaps602
Summary606
Exercises608
References612
AppendixASeparateCompilationof
ClassTemplates615
A．1EverythingintheHeader616
A．2ExplicitInstantiation616
Index619

前言/序言

目的/目标
《数据结构与算法分析 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++语言描述（第四版）（英文版）》内容大有裨益。
练习
在每章末尾提供的练习与正文中讲授内容的顺序相匹配。最后的一些练习是把一章作为一个整体来处理而不是针对特定的某一节来考虑的。难做的练习标以一个星号，更难的练习标注两个星号。
参考文献
参考文献列于每章的最后。一般说来，这些参考文献或者是历史性质的，代表着书中材料的原始来源，或者阐述对正文中给出结果的扩展和改进。有些文献提供一些练习的解法。
补充材料
所有读者均可从网站http://cssupport.pearsoncmg.com/上获取下列补充资料：
?例子程序的源代码
?勘误表
此外，下列材料只提供给PearsonInstructorResourceCenter(www.pearsonhighered.com/irc)上有资格的教师。如欲获取这些资料，可访问IRC或你的PearsonEducation销售代表。
?书中挑选的一些练习的解答
?《数据结构与算法分析 C++语言描述（第四版）（英文版）》中的一些图示
?勘误表
致谢
在该丛书几部著作的准备过程中作者得到了许许多多朋友的帮助，有些人在《数据结构与算法分析 C++语言描述（第四版）（英文版）》的其他版本中列出。谢谢所有诸位。
如同往常一样，Pearson专家们的努力使得《数据结构与算法分析 C++语言描述（第四版）（英文版）》的写作过程更加轻松。我愿意借此机会感谢我的编辑TracyJohnson，以及制作编辑MarilynLloyd。贤妻Jill因其所做的每一件工作应该得到我特别的感谢。
最后，我还要感谢广大的读者，他们发送E-mail信息并指出较早各版的错误和矛盾之处。我的网站www.cis.fiu.edu/~weiss也将包含更新后(C++和Java)的源代码，一个勘误表，以及到提交问题报告的一个链接。
M．A．W．
Miami，Florida


其他推荐