数据结构英文版课件1Data-Structures-Course

计算机学院谢芳DataStructuresUsingC2017-2-21DataStructures1/92017-2-21DataStructures2/9Prerequisites(Backgrounds)◆GoodknowledgeofCProgramming◆Acourseindiscretemathematics2017-2-21DataStructures3/9GradingSchemes1.Homework+Attendance(20%)2.Programming(20%)3.TerminalExamination(60%)2017-2-21DataStructures4/9◆RecommendedReferenceTextbook:1.APracticalIntroductiontoDataStrcutresandAlgorithmAnalysis,CliffordA.Shaffer.2.数据结构(C语言版)，严蔚敏，吴伟民编著，清华大学出版社。CourseMaterial◆RequiredTextbook:Structures,AlgorithmAnalysis,theelectronicbook.2017-2-21DataStructures5/9Contents1.DataStructures-AnOverview2.SequentialLists3.Stacks4.Queues5.LinkedLists6.Trees7.Graphs8.Sorting9.Searching2017-2-21DataStructures6/9WhyC?◆Modularprocedurallanguagewitharrays,structures,andreferences◆Experimentaltool–VC6.0–VS2008◆Cvs.C++orJava–small,clean,simple–cansupportlearningdatastructureswithoutlearningtoomuchlanguageextras2017-2-21DataStructures7/9LearningDataStructuresWHY?WHAT?HOW?Practise!Practise!Practise!2017-2-21DataStructures8/9WhyweuseDataStructures?Itshouldgowithoutsayingthatpeoplewriteprogramstosolveproblems.However，itiscrucialtokeepthistruisminmindwhenselectingadatastructuretosolveaparticularproblem.Onlybyfirstanalyzingtheproblemtodeterminetheperformancegoalsthatmustbeachievedcantherebeanyhopeofselectingtherightdatastructurethattheyarefamiliarwithbutwhichisinappropriatetotheproblem.2017-2-21DataStructures9/9Purpose/GoalsDataStructures-ifyourprogramneedstostoreafewthings-number,payrollrecords,orjobdescriptionsforexample-thesimplestandmosteffectiveapproachmightbetoputtheminalist(inc–array).Onlywhenyouhavetoorganizeandsearchthroughalargenumberofthingsdomoresophisticateddatastructuresusuallybecomenecessary.2017-2-21DataStructures10/9HowtouseDataStructures?Whenselectingadatastructuretosolveaproblem,youshouldfollowthesesteps:1.Analyzeyourproblemtodeterminethebasicoperationsthatmustbesupported.Examplesofbasicoperationsincludeinsertingadataitemintothedatastructure,deletingadataitemfromthedatastructure,andfindingaspecifieddataitem.2.Quantifytheresourceconstraintsforeachoperation.3.Selectthedatastructurethatbestmeetstheserequirements.2017-2-21DataStructures11/9AbstractDataTypesandDataStructuresThepreviouspagesusedtheterms“dataitem”and“datastructure”withoutproperlydefiningthem.Thissectionpresentsterminologyandmotivatesthedesignprocessembodiedinthethree-stepapproachtoselectingadatastructure.Thismotivationstemsfromtheneedtomanagethetremendouscomplexityofcomputerprograms.2017-2-21DataStructures12/9DataTypes(DT)Atypeisacollectionofvalues.Forexample,-TheBooleantypeconsistsofthevaluestrueandfalse.Theintegersalsoformatype.Anintegerisasimpletypebecauseitsvaluescontainnosubparts.-Abankaccountrecordwilltypicallycontainservalpiecesofinformationsuchasname,address,accountnumber,andaccountbalance.Sucharecordisanexampleofanaggregatetypeorcompositetype.2017-2-21DataStructures13/9DataTypes(DT)-Adataitemisapieceofinformationorarecordwhosevalueisdrawnfromatype.Adataitemissaidtobeamemberofatype.-Adatatypeisatypetogetherwithacollectionofoperationstomanipulatethetype.Forexample,anintegervariableisamemberoftheintegerdatatype.Additionisanexampleofanoperationontheintegerdatatype.2017-2-21DataStructures14/9AbstractDataTypes(ADT)Anabstractdatatypeistherealizationofadatatypeasasoftwarecomponent.TheinterfaceoftheADTisdefinedintermsofatypesandasetofoperationsonthattype.Thebehaviorofeachoperationisdeterminedbyitsinputsandoutputs.AnADTdoesnotspecifyhowthedatatypeisimplemented.TheseimplementationdetailsarehiddenfromtheuseroftheADTandprotectedfromoutsideaccess,aconceptreferredtoasencapsulation.(AnADTmustbedefinedbeforeweuseit)2017-2-21DataStructures15/9DistinctionofLogicalConceptofadatatypeanditsphysicalimplementationinacomputerprogramInacomputerprogram,therearetwotraditionalimplementationsforthelistdatatype：thelinkedlistandarray-basedlist.Thelistdatatypecanthereforebeimplementedusingalinkedlistoranarray.“Array”iscommonlyusedincomputerprogrammingtomeanacontiguousblockofmemorylocation,whereeachmemorylocationstoresonefixed-lengthdataitem.Bythismeaning,anarrayisaphysicaldatastructure.2017-2-21DataStructures16/9DistinctionofLogicalConceptofadatatypeanditsphysicalimplementationinacomputerprogramHowever,arraycanalsomeanalogicaldatatypecomposedacollectionofdataitems,witheachdataitemidentifiedbyanindexnumber(incprogramminglanguage,itusespointertorepresenttheindex).Itispossibletoimplementarraysinmanydifferentways.ADTExample:Array:Fixedlengthstringmethod#Example:char*str;str=“CHINA”;012345◆Advantage:simple.◆Disadvantage:possiblewastageofmemoryspace;complexoperations.str[0]~str[19]NULL6…….19CHINA\0…….…Linkedlistmethod◆Advantage:nowastageofmemoryspace;memoryallocationisdynamic;simpleroperations.◆Disadvantage:accessingasubstringrequiredstratingfromthebeginning;requiredmorememoryspace.◆SinglyLinkedliststructnode{chardata;structnode*next;}structnode*header,*string;LogicalRepresentationofstringPhysicalRepresentationofstring(header)datanextS20C30U10header40TPhysicalSpaceTNULL001070Address:20C3030U1040S20704