Practical Introduction to Data Structure and Algorithm

《Practical Introduction to Data Structure and Algorithm》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、APracticalIntroductiontoDataStructuresandAlgorithmAnalysisThirdEdition(Java)CliffordA.ShafferDepartmentofComputerScienceVirginiaTechBlacksburg,VA24061April16,2009Copyrightc2008byCliffordA.Shaffer.ThisdocumentisthedraftofabooktobepublishedbyPrenticeHallandm

2、aynotbeduplicatedwithouttheexpresswrittenconsentofeithertheauthororarepresentativeofthepublisher.ContentsPrefacexiiiIPreliminaries11DataStructuresandAlgorithms31.1APhilosophyofDataStructures41.1.1TheNeedforDataStructures41.1.2CostsandBenefits61.2AbstractDat

3、aTypesandDataStructures81.3DesignPatterns121.3.1Flyweight131.3.2Visitor141.3.3Composite151.3.4Strategy161.4Problems,Algorithms,andPrograms171.5FurtherReading191.6Exercises212MathematicalPreliminaries252.1SetsandRelations252.2MiscellaneousNotation292.3Logar

4、ithms312.4SummationsandRecurrences33iiiivContents2.5Recursion362.6MathematicalProofTechniques392.6.1DirectProof402.6.2ProofbyContradiction402.6.3ProofbyMathematicalInduction412.7Estimating472.8FurtherReading492.9Exercises503AlgorithmAnalysis573.1Introducti

5、on573.2Best,Worst,andAverageCases633.3AFasterComputer,oraFasterAlgorithm?653.4AsymptoticAnalysis673.4.1UpperBounds683.4.2LowerBounds703.4.3ΘNotation713.4.4SimplifyingRules723.4.5ClassifyingFunctions733.5CalculatingtheRunningTimeforaProgram743.6AnalyzingPro

6、blems793.7CommonMisunderstandings813.8MultipleParameters833.9SpaceBounds843.10SpeedingUpYourPrograms863.11EmpiricalAnalysis893.12FurtherReading903.13Exercises913.14Projects95IIFundamentalDataStructures974Lists,Stacks,andQueues99Contentsv4.1Lists1004.1.1Arr

7、ay-BasedListImplementation1034.1.2LinkedLists1064.1.3ComparisonofListImplementations1174.1.4ElementImplementations1194.1.5DoublyLinkedLists1204.2Stacks1254.2.1Array-BasedStacks1254.2.2LinkedStacks1284.2.3ComparisonofArray-BasedandLinkedStacks1294.2.4Implem

8、entingRecursion1294.3Queues1334.3.1Array-BasedQueues1344.3.2LinkedQueues1374.3.3ComparisonofArray-BasedandLinkedQueues1404.4DictionariesandComparators1404.5FurtherReading1474.6Exercises1474.7Projects1505Binar