《【精品数据结构】preface.ppt》由会员分享，可在线阅读，更多相关《【精品数据结构】preface.ppt（53页珍藏版）》请在金锄头文库上搜索。
1、DataStructures Algorithms andApplicationsinC ChenPeipeiMarch13 2003 Chapter1 preface Thepurposeandcontentsofthecourse IntroducemostuseddatastructuresandalgorithmsPrerequisiteofothercoursesIntroducealgorithmanalysisReviewC Thepurposeandcontentsofthecourse 1 Introducemostuseddatastructuresandalgorithm
2、s Useproperdatastructurestosolvedifferentproblems Example GameproblemManagementoflibrarycataloguebycomputerManagementofthetrafficlightsinintersections Thepurposeandcontentsofthecourse Example1 Gameproblem Nextstep xhasfivechoices Thepurposeandcontentsofthecourse Example1usesatreestructure Thepurpose
3、andcontentsofthecourse Example2 Managementoflibrarycataloguebycomputer Itisalinearlist D S SartajSahni000001computer2000 1 Thepurposeandcontentsofthecourse Example3 Managementofthetrafficlightsinintersections C Eareone wayroad thereare13pathtogo Cangoatthesametime A BE CCannotgoatthesametime E BA D
4、Thisisagraph Thepurposeandcontentsofthecourse 2 Prerequisiteofothercourses Principlesofcompiling usestacktocomputeexpressionandimplementrecursiveprocedureOperatingSystem usequeuetoimplementjobschedulingDatabase useB treetoorganize storeandloadmassivedatainthehardmemory Thepurposeandcontentsofthecour
5、se 3 Basicmethodsofalgorithmanalysisstandardsoftheperformanceofanalgorithm timecomplexity spacecomplexity andaccuracy4 ReviewC WhatisDataStructure 1 Dataisthecarrierofinformation Dataisasetofnumbers characters andothersymbolsthatcanbeusedtodescribetheobjectivethings Thesesymbolscanbeinputintocompute
6、rs identifiedandprocessedbythecomputerprogram WhatisDataStructure Datacandividedintotwoclasses numericaldata int float complex non numericaldata character string graph voice WhatisDataStructure DatastructureAdatastructureisadataobjecttogetherwiththerelationshipsamongthedatamembersthatcomposetheobjec
7、tData Structure D R isadataobject RisalimitedsetofrelationshipsofallthedatamembersinD WhatisDataStructure LinearstructureDatastructureNon linearstucture ADTandOO 1 DatatypeDefinition isasetofvaluestogetherwithaoperationsetthatoperateonthesevalues Example inttypevalueset 2 1 0 1 2 operationset ADTand
8、OO Mostoftheprogramminglanguagesprovideagroupofpredefineddatatype Atomdatatype int float double Structuredatatype array struct ADTandOO 2 ADTs AbstractDataTypesAbstract isamethodusedtohidetheinformation Example intx floatx y x 735 x x y 3 0 abstractofintdatatypeabstractoffloatdatatypeassignmentopera
9、tion ADTandOO Abstractdatatype isanewprogrammingmethodthatparttheusageandimplementation inordertoencapsulateandhidetheinformation ADTNaturalNunberisobjects 一个整数的有序子集合 它开始于0 结束于机器能表示的最大整数 MAXINT Function Zero NaturalNumberIsZero x BooleanAdd x y NaturalNumberEqual x y BooleanSuccessor x NaturalNumber
10、Subtract x y NaturalNumberendNaturalNumber ADTandOO 3 OO object oriented object class inherit communicateobject attributevalues operatesclass objectsofsameattributesandoperates aninstanceisanobjectoftheclass differentobjecthasdeferentattributevalue ADTandOO Inherit baseclass integratethesamepart inc
11、ludingattributesandoperations inallthederivedclassesderivedclass addthespecificattributesandoperationstothebaseclassExample baseclass polygonderivedclass quadrilateral triangular ADTandOO Communication eachclassobjectcommunicatewithothersusingmessages Message instructionsthatoneclassobjectusedinorde
12、rtorequireanotherclassobjecttoperformsomeoperation Algorithmdefinition Algorithm anoperationsequenceofsolutingaproblemCharacteristic 1 finite2 deterministic3 initialaction4 sequenceends Algorithmdefinition Program 1 Programiswrittenbylanguagesthatcanbeperformedbymachine Algorithmhasmultipledescripti
13、vemethods suchaslanguage graph table 2 programcan tsatisfythefiniteness Forexample OS TemplatesinC Problem program1 1 intAbc inta intb intc returna b b c a b c a b 4 program1 2 floatAbc floata floatb floatc returna b b c a b c a b 4 TemplatesinC program1 1and1 2differonlyinthedatatypeoftheformalpara
14、metersandofthevaluereturned Wecanwriteagenericcodeinwhichthedatatypeisavariablewhosevalueisdeterminedbythecompiler Thisgenericcodeiswrittenusingthetemplatestatementinprogram1 3 TemplatesinC Program1 3templateTAbc Ta Tb Tc returna b b c a b c a b 4 Fromthisgenericcodethecompilercanconstruct1 1bysubst
15、itutingintforTand1 2bysubstitutingfloatforT Parameterpassing 1 ValueParameters Program1 1 templateTAbc Ta Tb Tc returna b b c a b c a b 4 z Abc 2 x y Parameterpassing 2 ReferenceParameterstemplateTAbc T RecursiveFunction 1 directrecursive2 indirectrecursiveExample1factorialfunctionf n n 1n1 recursiv
16、ecomponent f 5 5f 4 5 4f 3 5 4 3f 2 5 4 3 2f 1 120 f n RecursiveFunction intfactorial intn if n 1 return1 elsereturnn Factorial n 1 RecursiveFunction Example2 computesthesumoftheelementsa 0 througha n 1 Program1 9 a 0 a 1 a n 2 a n 1 RecursiveFunction TemplateTRsum Ta intn if n 0 returnRsum a n 1 a n 1 return0 RecursiveFunction Example3 Permutation Program1 10 a b c abc acb bac bca cab cbapermutationofnelementshasn RecursiveFunction Templatevoidperm Tlist intk intm inti if k m for i 0 i m i cout
