内容简介

　　《数据结构与算法分析：C语言描述》曾被评为20世纪很好的30部计算机著作之一，作者在数据结构和算法分析方面卓有建树，他的数据结构和算法分析的著作尤其畅销，并受到广泛好评，已被世界500余所大学选作教材。
　　在《数据结构与算法分析：C语言描述》中，作者精炼并强化了他对算法和数据结构方面创新的处理方法。通过C程序的实现，着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间进行了分析。
　　《数据结构与算法分析：C语言描述》特色：着重讨论了算法设计技巧，包括贪婪算法、分治算法、动态规划、随机化算法以及回溯算法。系统介绍了当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树。详细讨论了摊还分析，考查书中介绍的一些高级数据结构。增加了高级数据结构及其实现的内容，包括红黑树、自顶向下伸展树、treap树、k-d树、配对堆等。整合了堆排序平均情况分析的一些新结果。

作者简介

　　MarkAllenWeiss1987年在普林斯顿大学获得计算机科学博士学位。师从RoberlSedgewick，现任美国佛罗里达国际大学计算与信息科学学院教授。他曾担任全美AP（AdvancedPlacement）考试计算机学科委员会主席。其主要研究方向是数据结构、算法和教育学。

目录

Introduction1
1.1.WhatstheBookAbout?1
1.2.MathematicsReview3
1.2.1.Exponents3
1.2.2.Logarithms3
1.2.3.Series4
1.2.4.ModularArithmetic5
1.2.5.ThePWord6
1.3.ABriefIntroductiontoRecursion
Summary12
Exercises12
References13

2AlgorithmAnalysis15
2.1.MathematicalBackground15
2.2.Model18
2.3.WhattoAnalyze18
2.4.RunningTuneCalculations20
2.4.1.ASimpleExample21
2.4.2.GeneralRules21
2.4.3.SolutionsfortheMaximumSubsequenceSumProblem24
2.4.4.LogarithmsintheRunningTune28
2.4.5.CheckingYourAnalysis33
2.4.6.AGrainofSalt33
Summary34
Exercises35
References39

3Lists,Stacks,andQueues41
3.1.AbstractDataTypes(AnTs)41
3.2.TheListADT42
3.2.1.SimpleArrayImplementationofLists43
3.2.2.LinkedLists43
3.2.3.ProgrammingDetails44
3.2.4.CommonErrors49
3.2.5.DoublyLinkedLists51
3.2.6.CircularlyUnkedLists52
3.2.7.Examples52
3.2.8.CursorImplementationofLinkedLists57
3.3.TheStackADT62
3.3.1.StackModel62
3.3.2.ImplementationofStacks63
3.3.3.Applications71
3.4.TheQueueADT79
3.4.1.QueueModel79
3.4.2.ArrayImplementationofQueues79
3.4.3.ApplicationsofQueues84
Summary85
Exercises85

4Trees89
4.1.Preliminaries89
4.1.1.ImplementationofTrees90
4.1.2.TreeTraversalswithanApplication91
4.2.BinaryTrees95
4.2.1.Implementation96
4.2.2.ExpressionTrees97
4.3.TheSearchTreeADT-BinarySearchTrees100
4.3.1.MakeEmpty101
4.3.2.Find101
4.3.3.FindMinandFindMax103
4.3.4.Insert104
4.3.5.Delete105
4.3.6.Average-CaseAnalysis107
4.4.AvITrees110
4.4.1.SingleRotation112
4.4.2.DoubleRotation115
4.5.SplayTrees123
4.5.1.ASimpleIdea(ThatDoesNotWork)124
4.5.2.Splaying126
4.6.TreeTraversals(Revisited)132
4.7.B-Trees133
Summary138
Exercises139
References146

5Hashing149
5.1.GeneralIdea149
5.2.HashFunction150
5.3.SeparateChaining152
5.4.OpenAddressing157
5.4.1.LinearProbing157
5.4.2.QuadraticProbing160
5.4.3.DoubleHashing164
5.5.Rehashing165
5.6.ExtendibleHashing168
Summary171
Exercises172
References175

6PriorityQueues(Heaps)177
6.1.Model177
6.2.SimpleImplementations178
6.3.BinaryHeap179
6.3.1.StroctureProperty179
6.3.2.HeapOrderProperty180
6.3.3.BasicHeapOperations182
6.3.4.OtherHeapOperations186
6.4.ApplicationsofPriorityQueues189
6.4.1.TheSelectionProblem189
6.4.2.EventSimulation191
6.5.d-Heaps192
6.6.LeftistHeaps193
6.6.1.LeftistHeapProperly193
6.6.2.LeftistHeapOperations194
6.7.SkewHeaps200
6.8.BinomialQueues202
6.8.1.BinomialQueueStructure202
6.8.2.BinomialQueueOperations204
6.8.3.ImplementationofBinomialQueues205
Summary212
Exercises212
References216

7Sorting219
7.1.Preliminaries219
7.2.InsertionSort220
7.2.1.TheAlgorithm220
7.2.2.AnalysisofInsertionSort221
7.3.ALowerBoundforSimpleSortingAlgorithms221
7.4.SheUsort222
7.4.1.Worst-CaseAnalysisofShellsort224
7.5.Heapsort226
7.5.1.AnalysisofHeapsort228
7.6.Mergesort230
7.6.1.AnalysisofMergesort232
7.7.Quicksort235
7.7.1.PickingthePivot236
7.7.2.PartitioningStrategy237
7.7.3.SmallArrays240
7.7.4.ActualQuicksortRoutines240
7.7.5.AnalysisofQuicksort241
7.7.6.ALinear-Expected-TimeAlgorithmforSelection245
7.8.SortingLargeStructures247
7.9.AGeneralLowerBoundforSorting247
7.9.1.DecisionTrees247
7.10.BucketSort250
7.11.ExternalSorting250
7.11.1.WhyWeNeedNewAlgorithms251
7.11.2.ModelforExternalSorting251
……
8TheDisjointSetADT
9GraphAlgorithms
10AlgorithmDesignTechniques
11AmortizedAnalysis
12AdvancedDataStructuresandImplementation

精彩书摘

　　Thisexampleillustrateswhatwecallrandomizedalgorithms.Atleastonceduringthealgorithm，arandomnumberisusedtomakeadecision.Therunningtimeofthealgorithmdependsnotonlyontheparticularinput,butalsoontherandomnumbersthatoccur.
　　Theworst-caserunningtimeofarandomizedalgorithmisalmostalwaysthesameastheworst-caserunningtimeofthenonrandomizedalgorithm.Theimportantdifferenceisthatagoodrandomizedalgorithmhasnobadinputs,butonlybadrandomnumbers（relativetotheparticularinput）.Thismayseemlikeonlyaphilosophicaldifference,butactuallyitisquiteimportant,asthefollowingexampleshows.
　　Considertwovariantsofquicksort.VariantAusesthefirstelementaspivot,whilevariantBusesarandomlychosenelementaspivot.Inbothcases,theworst-caserunningtimeis（N2）,becauseitispossibleateachstepthatthelargestelementischosenaspivot.ThedifferencebetweentheseworstcasesisthatthereisaparticularinputthatcanalwaysbepresentedtovariantAtocausethebadrunningtime.VariantAwillrunin（N2）timeeverysingletimeitisgivenanalready-sortedlist.IfvariantBispresentedwiththesameinputtwice,itwillhavetwodifferentrunningtimes,dependingonwhatrandomnumbersoccur.

前言/序言

　　Thisbookdescribesdatastructures，methodsoforganizinglargeamountsofdataandalgorithmanalysistheestimationoftherunningtimeofalgorithms.Ascom-putersbecomefasterandfastertheneedforprogramsthatcanhandlelargeamountsofinputbecomesmoreacute.Paradoxicallythisrequiresmorecarefulattentiontoefficiencysinceinefficienciesinprogramsbecomemostobviouswheninputsizesarelarge.Byanalyzinganalgorithmbeforeitisactuallycodedstudentscandecideifaparticularsolutionwillbefeasible.Forexampleinthistextstudentslookatspecificproblemsandseehowcarefulimplementationscanreducethetimeconstraintforlargeamountsofdatafrom16yearstolessthanasecond.Thereforenoalgorithmordatastructureispresentedwithoutanexplanationofitsrunningtime.Insomecasesminutedetailsthataffecttherunningtimeoftheimplementationareexplored.

　　Onceasolutionmethodisdeterminedaprogrammuststillbewritten.Ascomputershavebecomemorepowerfultheproblemstheymustsolvehavebecomelargerandmorecomplexrequiringdevelopmentofmoreintricateprograms.Thegoalofthistextistoteachstudentsgoodprogrammingandalgorithmanalysisskillssimultaneouslysothattheycandevelopsuchprogramswiththemaximumamountofefficiency.

　　Thisbookissuitableforeitheranadvanceddatastructures（CS7）courseorafirst-yeargraduatecourseinalgorithmanalysis.Studentsshouldhavesomeknow-ledgeofintermediateprogrammingincludingsuchtopicsaspointersandrecursionandsomebackgroundindiscretemath.


其他推荐