数据结构与算法分析c++版课件_1

《数据结构与算法分析c++版课件_1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法分析APracticalIntroductiontoDataStructuresandAlgorithmAnalysisPreliminaries1DataStructureandAlgorithmsDataStructuresandAlgorithmsDataStructuresandAlgorithms¢APhilosophyofDataStructuresßTheNeedforDataStructuresßCostsandBenefitsCostsandBenefits¢AbstractDataTypesandDataStructu

2、res¢DesignPatternsDesignPatternsßFlyweightßVisitorßCompositeßStrategy¢Problems,Algorithms,andProgramsTheNeedforDataStructuresTheNeedforDataStructuresDatastructuresorganizedata⇒moreefficientppgrograms.Morepowerfulcomputers⇒morecomplllexappliicattiions.Morecomppplexappplicationsde

3、mandmorecalculations.ComplexcomputingtasksareunlikeourComplexcomputingtasksareunlikeoureverydayexperience.Efficiency¢Choiceofdatastructureoralgorithmcanmakethedifferencebetweenaprogramrunninginafewsecondsormanydays.¢AsolutionissaidtobeAsolutionissaidtobeefficientifitsolvesifitso

4、lvestheproblemwithinitsresourceconstraints.ßSpaceßTime¢Thecostofasolutionistheamountofresourcesthatthesolutionconsumes.CostsandBenefitsCostsandBenefitsEachdatastructurehascostsandbenefits.Rarelyisonedatastructurebetterthananotherinallsituations.Anydatastructurerequires:Anydatast

5、ructurerequires:ßspaceforeachdataitemitstores,ßtimetoperformeachbasicoperation,ßprogrammingeffort.CostsandBenefitsCostsandBenefits¢EhbEachprobllhemhasconstittraintsonavaiillbabllespaceanddtime.¢OnlyafteracarefulanalysisofproblemcharacteristicsOnlyafteracarefulanalysisofproblemch

6、aracteristicscanweknowthebestdatastructureforthetask.¢Selectadatastructureasfollows:ßAnalyzetheproblemtodeterminethebasicoperationsthatmustbesupported.ßQuantifytheresourceconstraintsforeachoperationQuantifytheresourceconstraintsforeachoperation.ßSelectthedatastructurethatbestmee

7、tstheserequirements.ExampleBkBankexamplle:ßStartaccount:afewminutesßTtTransactiifons:afewseconddsßCloseaccount:overnight适度插入效率、查找效率高，删除效率低DataStructuresandAlgorithmsDataStructuresandAlgorithms¢APhilosophyofDataStructuresßTheNeedforDataStructuresßCostsandBenefitsCostsandBenefits¢

8、AbstractDataTypesandDataStructures¢DesignPatter