数据结构英文版课件1DataStructuresCourse

计算机学院谢芳Data

StructuresUsing

C2017-2-21DataStructures1/92017-2-21DataStructures2/9Prerequisites(Backgrounds)Good

knowledgeofCProgrammingAcourse

indiscrete

mathematics2017-2-21DataStructures3/9Grading

SchemesHomework

+Attendance(20%)Programming

(20%)Terminal

Examination

(60%)2017-2-21DataStructures4/9Recommended Reference Textbook:1.APracticalIntroductiontoDataStrcutresandAlgorithmAnalysis,CliffordA.Shaffer.2.<<数据结构

(C语言版)>>，严蔚敏，吴伟民编著，清华大学出版社。Course

MaterialRequired

Textbook

:

Structures,AlgorithmAnalysis,theelectronicbook.2017-2-21DataStructures5/9ContentsDataStructures-An

OverviewSequentialListsStacksQueuesLinked

ListsTreesGraphsSortingSearching2017-2-21DataStructures6/9WhyC

?Modular

procedural

language

with

arrays,structures,

and

referencesExperimentaltoolVC6.0VS2008Cvs.C++

orJavasmall,

clean,

simplecan

support

learning

datastructureswithoutlearning

toomuch

language

extras2017-2-21DataStructures7/9Learning

Data

StructuresWHY

?WHAT

?HOW?Practise!

Practise!

Practise!2017-2-21DataStructures8/9Whywe

use

Data

Structures?Itshouldgowithoutsayingthatpeoplewriteprogramstosolveproblems.However，itiscrucialtokeepthistruisminmindwhenselectingadatastructuretosolveaparticularproblem.Onlybyfirstanalyzingtheproblemtodeterminetheperformancegoalsthatmustbeachievedcantherebeanyhopeofselectingtherightdatastructurethattheyarefamiliarwithbutwhichisinappropriatetotheproblem.2017-2-21DataStructures9/9Purpose/GoalsDataStructures-ifyourprogramneedstostoreafewthings-number,payrollrecords,orjobdescriptionsforexample-thesimplestandmosteffectiveapproachmightbetoputtheminalist(inc–array).Onlywhenyouhavetoorganizeandsearchthroughalargenumberofthingsdomoresophisticateddatastructuresusuallybecomenecessary.2017-2-21DataStructures10/9Howtouse

Data

Structures?Whenselectingadatastructuretosolveaproblem,youshouldfollowthesesteps:Analyzeyourproblemtodeterminethebasicoperationsthatmustbesupported.Examplesofbasicoperationsincludeinsertingadataitemintothedatastructure,deletingadataitemfromthedatastructure,andfindingaspecifieddataitem.Quantifytheresourceconstraintsforeachoperation.Selectthedatastructurethatbestmeetstheserequirements.2017-2-21DataStructures11/9AbstractDataTypesandDataStructuresThepreviouspagesusedtheterms“dataitem”and“datastructure”withoutproperlydefiningthem.Thissectionpresentsterminologyandmotivatesthedesignprocessembodiedinthethree-stepapproachtoselectingadatastructure.Thismotivationstemsfromtheneedtomanagethetremendouscomplexityofcomputerprograms.2017-2-21DataStructures12/9DataTypes(DT)Atypeisacollectionofvalues.Forexample,-TheBooleantype

consistsofthevaluestrueandfalse.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:Fixed

length

string

method#Example:

char

*str;str=“CHINA”;0 1 2 3 4 5◆Advantage:simple.◆Disadvantage:possible

wastageofmemory

space;complex

operations.str[0]~str[19]NULL6

……. 19CHINA\0…….…Linked

listmethod◆Advantage:nowastageofmemory

space;memory

allocation

isdynamic;si