A Practical Introduction to Data Structures and Algorithm Analysis Third Edition (Java Version) Clifford A. Shaffer DepartmentofComputerScience VirginiaTech Blacksburg,VA24061 January19,2010 Copyright(cid:13)c 2009-2010byCliffordA.Shaffer. Thisdocumentismadefreelyavailableforeducationalandother non-commercialuse. Youmaymakecopiesofthisfileandredistributeitwithoutcharge. Youmayextractportionsofthisdocumentprovidedthatthefrontpage, includingthetitle,author,andthisnoticeareincluded. Anycommercialuseofthisdocumentrequiresthewrittenconsentofthe author. [email protected]. Furtherinformationaboutthistextisavailableat http://people.cs.vt.edu/˜shaffer/Book/ Contents Preface xiii I Preliminaries 1 1 DataStructuresandAlgorithms 3 1.1 APhilosophyofDataStructures 4 1.1.1 TheNeedforDataStructures 4 1.1.2 CostsandBenefits 6 1.2 AbstractDataTypesandDataStructures 8 1.3 DesignPatterns 12 1.3.1 Flyweight 13 1.3.2 Visitor 14 1.3.3 Composite 15 1.3.4 Strategy 16 1.4 Problems,Algorithms,andPrograms 17 1.5 FurtherReading 19 1.6 Exercises 21 2 MathematicalPreliminaries 25 2.1 SetsandRelations 25 2.2 MiscellaneousNotation 29 2.3 Logarithms 31 2.4 SummationsandRecurrences 33 iii iv Contents 2.5 Recursion 36 2.6 MathematicalProofTechniques 39 2.6.1 DirectProof 40 2.6.2 ProofbyContradiction 40 2.6.3 ProofbyMathematicalInduction 41 2.7 Estimating 47 2.8 FurtherReading 49 2.9 Exercises 50 3 AlgorithmAnalysis 57 3.1 Introduction 57 3.2 Best,Worst,andAverageCases 63 3.3 AFasterComputer,oraFasterAlgorithm? 65 3.4 AsymptoticAnalysis 67 3.4.1 UpperBounds 68 3.4.2 LowerBounds 70 3.4.3 ΘNotation 71 3.4.4 SimplifyingRules 72 3.4.5 ClassifyingFunctions 73 3.5 CalculatingtheRunningTimeforaProgram 74 3.6 AnalyzingProblems 79 3.7 CommonMisunderstandings 81 3.8 MultipleParameters 83 3.9 SpaceBounds 84 3.10 SpeedingUpYourPrograms 86 3.11 EmpiricalAnalysis 89 3.12 FurtherReading 90 3.13 Exercises 91 3.14 Projects 95 II FundamentalDataStructures 97 4 Lists,Stacks,andQueues 99 Contents v 4.1 Lists 100 4.1.1 Array-BasedListImplementation 103 4.1.2 LinkedLists 106 4.1.3 ComparisonofListImplementations 117 4.1.4 ElementImplementations 119 4.1.5 DoublyLinkedLists 120 4.2 Stacks 125 4.2.1 Array-BasedStacks 125 4.2.2 LinkedStacks 128 4.2.3 ComparisonofArray-BasedandLinkedStacks 129 4.2.4 ImplementingRecursion 129 4.3 Queues 133 4.3.1 Array-BasedQueues 134 4.3.2 LinkedQueues 137 4.3.3 ComparisonofArray-BasedandLinkedQueues 140 4.4 DictionariesandComparators 140 4.5 FurtherReading 147 4.6 Exercises 147 4.7 Projects 150 5 BinaryTrees 153 5.1 DefinitionsandProperties 153 5.1.1 TheFullBinaryTreeTheorem 156 5.1.2 ABinaryTreeNodeADT 157 5.2 BinaryTreeTraversals 158 5.3 BinaryTreeNodeImplementations 162 5.3.1 Pointer-BasedNodeImplementations 163 5.3.2 SpaceRequirements 169 5.3.3 ArrayImplementationforCompleteBinaryTrees 170 5.4 BinarySearchTrees 171 5.5 HeapsandPriorityQueues 180 5.6 HuffmanCodingTrees 187 5.6.1 BuildingHuffmanCodingTrees 189 vi Contents 5.6.2 AssigningandUsingHuffmanCodes 195 5.7 FurtherReading 198 5.8 Exercises 198 5.9 Projects 202 6 Non-BinaryTrees 205 6.1 GeneralTreeDefinitionsandTerminology 205 6.1.1 AnADTforGeneralTreeNodes 206 6.1.2 GeneralTreeTraversals 207 6.2 TheParentPointerImplementation 208 6.3 GeneralTreeImplementations 216 6.3.1 ListofChildren 217 6.3.2 TheLeft-Child/Right-SiblingImplementation 218 6.3.3 DynamicNodeImplementations 218 6.3.4 Dynamic“Left-Child/Right-Sibling”Implementation 220 6.4 K-aryTrees 221 6.5 SequentialTreeImplementations 223 6.6 FurtherReading 226 6.7 Exercises 226 6.8 Projects 230 III SortingandSearching 233 7 InternalSorting 235 7.1 SortingTerminologyandNotation 236 7.2 ThreeΘ(n2)SortingAlgorithms 237 7.2.1 InsertionSort 238 7.2.2 BubbleSort 240 7.2.3 SelectionSort 241 7.2.4 TheCostofExchangeSorting 243 7.3 Shellsort 244 7.4 Mergesort 246 7.5 Quicksort 249 Contents vii 7.6 Heapsort 256 7.7 BinsortandRadixSort 259 7.8 AnEmpiricalComparisonofSortingAlgorithms 265 7.9 LowerBoundsforSorting 267 7.10 FurtherReading 271 7.11 Exercises 272 7.12 Projects 275 8 FileProcessingandExternalSorting 279 8.1 PrimaryversusSecondaryStorage 280 8.2 DiskDrives 282 8.2.1 DiskDriveArchitecture 283 8.2.2 DiskAccessCosts 286 8.3 BuffersandBufferPools 289 8.4 TheProgrammer’sViewofFiles 297 8.5 ExternalSorting 298 8.5.1 SimpleApproachestoExternalSorting 301 8.5.2 ReplacementSelection 304 8.5.3 MultiwayMerging 307 8.6 FurtherReading 310 8.7 Exercises 311 8.8 Projects 315 9 Searching 317 9.1 SearchingUnsortedandSortedArrays 318 9.2 Self-OrganizingLists 324 9.3 BitVectorsforRepresentingSets 329 9.4 Hashing 330 9.4.1 HashFunctions 331 9.4.2 OpenHashing 336 9.4.3 ClosedHashing 337 9.4.4 AnalysisofClosedHashing 346 9.4.5 Deletion 350 viii Contents 9.5 FurtherReading 351 9.6 Exercises 352 9.7 Projects 355 10 Indexing 357 10.1 LinearIndexing 359 10.2 ISAM 361 10.3 Tree-basedIndexing 364 10.4 2-3Trees 366 10.5 B-Trees 372 10.5.1 B+-Trees 375 10.5.2 B-TreeAnalysis 381 10.6 FurtherReading 382 10.7 Exercises 382 10.8 Projects 385 IV AdvancedDataStructures 387 11 Graphs 389 11.1 TerminologyandRepresentations 390 11.2 GraphImplementations 394 11.3 GraphTraversals 397 11.3.1 Depth-FirstSearch 400 11.3.2 Breadth-FirstSearch 401 11.3.3 TopologicalSort 405 11.4 Shortest-PathsProblems 407 11.4.1 Single-SourceShortestPaths 407 11.5 Minimum-CostSpanningTrees 411 11.5.1 Prim’sAlgorithm 412 11.5.2 Kruskal’sAlgorithm 415 11.6 FurtherReading 416 11.7 Exercises 416 11.8 Projects 420 Contents ix 12 ListsandArraysRevisited 423 12.1 Multilists 423 12.2 MatrixRepresentations 427 12.3 MemoryManagement 430 12.3.1 DynamicStorageAllocation 431 12.3.2 FailurePoliciesandGarbageCollection 438 12.4 FurtherReading 443 12.5 Exercises 444 12.6 Projects 445 13 AdvancedTreeStructures 447 13.1 Tries 447 13.2 BalancedTrees 452 13.2.1 TheAVLTree 453 13.2.2 TheSplayTree 455 13.3 SpatialDataStructures 459 13.3.1 TheK-DTree 461 13.3.2 ThePRquadtree 466 13.3.3 OtherPointDataStructures 471 13.3.4 OtherSpatialDataStructures 471 13.4 FurtherReading 473 13.5 Exercises 473 13.6 Projects 475 V TheoryofAlgorithms 479 14 AnalysisTechniques 481 14.1 SummationTechniques 482 14.2 RecurrenceRelations 487 14.2.1 EstimatingUpperandLowerBounds 487 14.2.2 ExpandingRecurrences 491 14.2.3 DivideandConquerRecurrences 492 14.2.4 Average-CaseAnalysisofQuicksort 495 x Contents 14.3 AmortizedAnalysis 496 14.4 FurtherReading 499 14.5 Exercises 500 14.6 Projects 504 15 LowerBounds 505 15.1 IntroductiontoLowerBoundsProofs 506 15.2 LowerBoundsonSearchingLists 508 15.2.1 SearchinginUnsortedLists 508 15.2.2 SearchinginSortedLists 510 15.3 FindingtheMaximumValue 511 15.4 AdversarialLowerBoundsProofs 513 15.5 StateSpaceLowerBoundsProofs 516 15.6 FindingtheithBestElement 519 15.7 OptimalSorting 522 15.8 FurtherReading 524 15.9 Exercises 525 15.10Projects 527 16 PatternsofAlgorithms 529 16.1 GreedyAlgorithms 529 16.2 DynamicProgramming 530 16.2.1 KnapsackProblem 531 16.2.2 All-PairsShortestPaths 532 16.3 RandomizedAlgorithms 534 16.3.1 SkipLists 536 16.4 NumericalAlgorithms 541 16.4.1 Exponentiation 542 16.4.2 LargestCommonFactor 543 16.4.3 MatrixMultiplication 543 16.4.4 RandomNumbers 546 16.4.5 FastFourierTransform 546 16.5 FurtherReading 551 Contents xi 16.6 Exercises 551 16.7 Projects 552 17 LimitstoComputation 553 17.1 Reductions 554 17.2 HardProblems 559 17.2.1 TheTheoryofNP-Completeness 560 17.2.2 NP-CompletenessProofs 565 17.2.3 CopingwithNP-CompleteProblems 569 17.3 ImpossibleProblems 573 17.3.1 Uncountability 574 17.3.2 TheHaltingProblemIsUnsolvable 577 17.4 FurtherReading 581 17.5 Exercises 581 17.6 Projects 584 Bibliography 585 Index 591