《计算机科学导论》课件Unit 11Data and File Structure

?计算机科学导论?课件Unit11DataandFileStructure211-1AbstractDataTypes11-2List11-3Stack11-4Queue11-5TreeandGraph11-6FileStructure11-7ReferencesAndRecommendedReading11-8Summary11-9PracticeSetOUTLINE11-1AbstractDataTypesWhendealingwithcomplexity,weassignalabeltoanassemblyofobjectsorconceptsandthenmanipulatethelabelinplaceoftheassembly.Suchalabeliscalledametaphorbycognitivepsychologists.Aparticularlabelmightberelatedtootherlabelsorotherpiecesofinformation.Ahierarchyofconceptsandlabelsisformedbygivingalabeltothiscollection.Thishierarchyoflabelsallowsustopaymoreattentiononcrucialissueswhileignoringunnecessarydetails.Figure11.1showsusthemodelforanADT.11-1AbstractDataTypesFigure11.1ThemodelforanADT11-1AbstractDataTypesTakeacarasanexample.Steering,acceleratingandbrakingarenecessaryactivitiesforitsoperation.Onalmostallpassengercars,thesteeringwheelisturnedforsteering,thegaspedalispushedforaccelerating,andthebrakepedalispushedforapplyingbrakes.ThisdesignforcarscanberegardedasanADTwithoperations“steer,〞“accelerate,〞and“brake〞.Theseoperationsontwodifferentcarsmightbeimplementedverydifferently,driversarenotrequiredtohaveknowledgeofthespecificsofanyparticularengineordrivedesign.Thesedifferencesarehiddendeliberatelyfromusers.11-1AbstractDataTypesFigure11.2Therelationshipbetweendataitems,abstractdatatypes,anddatastructures.Alist【列表】isdefinedasafinite,orderedsequenceofdataitemsknownaselements.Eachelementinthelisthasapositionandadatatype.Array-basedlist【基于数组列表】andlinkedlist【基于链表列表】arethetwostandardmethodstoimplementlists.

11-2ListInthearray-basedlist,elementsarestoredincontiguouscellsofthearray.Andthispropertymustbemaintainedafterinsert,

appendandremoveoperations.

Array-basedListFigure11.3Insertinganelementattheheadofanarray-basedlistItiseasytoinsertorremoveelementsatthetailofthelist,sotheappendoperationtakesO(1)time.Butifanelementneedstobeinsertedattheheadofthelist,allelementsmustshiftonepositiontowardthetailtomakeroom,asillustratedby.ThisprocesstakesO(n)timeifthelisthasncurrentelements.Ifwewanttoinsertanelementatpositioniwithinalisthavinglengthequivalentton,thenn–ielementsmustmovetowardtheend.Removinganelementatpositionirequiremovingn-i–1elementstowardtheheadofthelist.Array-basedListmemory【内存】isallocateddynamicallywhenanewelementisaddedintoit

Aseparatelistcanbemadeasanodeclassbecausenodesinalistaredistinctobjects(asopposedtosimplyacellinanarray).

Thefirstnodeofthelistisaccessedfromapointercalledhead【头指针】.Apointercalledtail【尾指针】isalsokepttothelastlinkofthelist.Anotherpointercalledcurr【当前指针】isdefinedtoindicatethepositionofthecurrentelement.

linkedListFigure11.4Onepossibleimplementationofalinked-listlinkedList

Abetterimplementationof

linked-listIfcurrissettopointtotheprecedingelement,addinganewelementaftercurrismucheasier.linkedListFigure11.6Nodeinsertioninalinkedlist

showsthenewlinkednode’selementfield.showsthenewlinkednode’snextfield.Itispointingtothenodeusedtobethecurrentnode(thenodewithvalue12).showsthenextfieldofthenodeprecedingthecurrentposition.Itwaspointingtothenodehavingvalue12;nowitispointingtothenewnodehavingvalue10.linkedListFigure11.7NoderemovalprocessinlinkedlistRemovinganodefromthelinkedlistneedsonlytoredirecttheappropriatepointeraroundthenodetobedeleted.Becarefulto‘leave’thememoryforthedeletedlinknode.InFigure11.7,shows‘it’pointingthelistnodewithvalue10beingremoved.showsthenextfieldoftheprecedinglistnode,whichispointingthenodefollowingtheonebeingremoved.11-3StackThestack【栈】isalist-likedatastructure.Elementscanonlybeinsertedorremovedfromoneendinstack.Forthisreason,stacksarenotasflexibleaslists.However,intheapplicationsthatrequireonlythelimitedformofinsertandremoveoperations,stacksaremoreefficientthanlists.Longbeforetheinventionofthecomputer,stackswereusedbyaccountants.Theynamedthestacka“LIFO〞【后进先出】list,whichmeans“Last-In,First-Out.〞Stacksremoveelementsinreverseorderoftheirarrival.Theelementweaccesseachtimeiscalledthetopelement.Whenanewelementisadded,wesayitispushedontothestack.Whenremoved,anelementissaidtobepoppedfromthestack.11-3StackFigure11.8showsasimplerepresentationofstackruntimewithpushandpopoperations.Thetwocommonapproachesofstackimplementationpresentedherearearray-basedandlinkedstacks,whichareanalogoustoarray-basedandlinkedlists,respectively.Theapplicationofstacksinamostcommoncomputerapplicationisperhapsnotevenvisibletoitsusers.Liketheuseofstacksduringruntimeofasubroutinecall【子程序调用】inmostoftheprogramminglanguages.

Theimplementationofasubroutineincludespushingitsinformationincludingreturnaddress,parameters,andlocalvariables,ontoastack.Thesubroutine’sinformationisreferredtoasanactivationrecord.Ifasubroutinecallcontainsanothersubroutinecall,itsactivationrecordisalsopushedontothestack.Thetopactivationrecordispoppedoffthestackoneachreturnfromasubroutine.11-3Stack11-4

QueueSimilartostack,thequeue【队列】isalist-likedatastructurethatgiveslimitedaccesstoitselements.Aqueuehastwokindsofoperations.Oneisenqueue【入队】operation,andtheotherisdequeue【出队】operation.Queuesoperatelikestandinginlineatasubwaystation.Ifnobodycheats,thennewcomersgotothebackoftheline.Thepersonatthefrontofthelineisthenexttoenterthesubway.Thus,inqueues,theelementsareretrievedinorderofarrival.Queueisalsocalleda“FIFO〞【先进先出】list,whichmeans“First-In,First-Out.〞11-4QueueFigure11.9showstherepresentationofaqueue.Figure11.10ThecircularqueuewitharraypositionsincreasingintheclockwisedirectionTherearetwoimplementationsofqueue:thearray-basedqueueandlinkedqueue.Inpractice,aqueuecanalsobetreatedasacircle.11-5TreeandGraphAtree【树】isaconnectedundirectedgraphwithfinitesetofelementscallednodesandfinitesetofbranchesthatconnectthenodes.Thedegree【度】ofanodeisdefinedasthenumberofbranchesassociatedwithanode.Thenumberofbranchesdirectedtowardthenodeiscalledthenode’sindegree【入度】while,thenumberofbranchesdirectedawayfromthenodeiscalledoutdegree【出度】.Theroot【根节点】ofatreeisthefirstnode,ifthetreeisnotempty.Theindegreeoftherootiszero.Excepttheroot,eachnodeinatreehasanindegreeofexactlyone.However,outdegreeofanynodeinatreecanbezero,oneormore.Aleaf【叶节点】isanynodewithanoutdegreeofzero.Anodethatisnotarootoraleafiscalledaninternalnode.11-5TreeandGraphFigure11.11Anexampleofangeneraltree

Ifanodehassuccessornodes,thatis,ifithasoutdegreeofatleastone,itiscalledaparent【父节点】.Anodewithapredecessoriscalledachild【子节点】.Childnode’sindegreeisnecessarilyone..Nodeswiththesameparentarereferredtoassiblings【兄弟节点】.Apathisasequenceofnodesinwhicheachnodeisadjacenttothenextone.Everynodehasauniquepathfromtheroot.Anynodeinthepathfromtheroottoaparticularnodeiscalledanancestor,andanynodeinapathbelowaparentnodeiscalledthedescendent.Asubtree【子树】isanyconnectedstructurebelowtheroot.Figure11.11showsanexampleofageneraltree.11-5TreeandGraphThelevelofanodeisitsdistancefromtheroot.Therootisatlevelzeroanditschildnodesareatlevel1,andsoon.Theheight,alsocalleddepth,ofatreeisthehighestlevelplus1.

Abinarytree【二叉树】isarootedtreeinwhicheachnodehasnomorethantwochildren,thatisthemaximumoutdegreeofeachnodeistwo.

AbinarytreeThemaximumheightofbinarytreehavingNnodesisN,whereasminimumheightis[log2N]+1.Conversely,assumetheheightofabinarytreetobeH,thenthenumberofnodesinthisbinarytreerangesfromHto2H-1.Abinarysearchtree(BST)

Abinarysearchtree(BST)【二叉查找树】isakindofbinarytreethathasasemanticpropertyonnodes’values.Thevalueineachnodemustbegreaterthanthevalueinanynodeinitsleftsubtreeandsmallerthanthevalueinanynodeinitsrightsubtree.Figure11.13showsanexampleofabinarysearchtree.Figure11.13ExampleofabinarysearchtreeGraphFigure11.14Anexampleofgraph(directflightsforpartofcitiesinChina)Inatree,anodeisrestrictedtobepointedbyatmostoneothernode.Ifweremovethisrestrictiononnode,thenwegetanewdatastructurecalledagraph.GraphAgraphismadeupofagroupofnodescalledvertices【顶点】andagroupoflinesbetweenthenodescallededges【边】.Anundirectedgraph【无向图】isagraphinwhichedgeshavenodirectionswhileedgesinadirectedgraph【有向图】aredirectedfromonenodetoanother,asshowninFigure11.14.IfweaddflightpricetoeachofthearrowsinFigure11.14,thenwegetaweightedgraph【加权图】.Thepriceontheedgesarecalledtheweights【权重】.Twoverticesconnectedbyanedgearecalledadjacentvertices【邻接点】.Andapath【路径】isasequenceofedgesthatconnectstwonodesinagraph.

graphtraversal

graphtraversalisdefinedasaprocessthataccessesalloftheverticesinagraphonceandonlyonceatatimestartingfromanyvertex.therearetwokindsofgraphtraversalmethods:depth-firstsearch【深度优先搜索】breadth-firstsearch【广度优先搜索】Inadepth-firstsearchprocess,wegotothedeepestbranch.Whenwehavetobacktrack,webackupaslittleaspossibleinadepth-firstsearch.Inabreadth-firstsearch,wewanttobackupasfaraspossibletofindapathoriginatingfromtheearliestvertices.

Bothofthesearchmethodscanhavemorethantwosearchpaths.

graphtraversalFigure11.15Anexampleforgraphtraversal

Inadepth-firstsearch,onepossiblesearchpathis15->8->6->2->9->18->17->16->20->23.Whileinabreadth-firstsearch,onepossiblesearchpathis15->8->18->6->9->17->20->2->16->23.Exceptforthedatastructuresmentionedabove,therearehashtable,red-blacktreeandB-tree.Moreaboutthesethreedatastructuresisavailableinreferencematerialslistedattheendofthechapter.11-6FileStructureDataisstoredintheformoffilesinstoragedevices.Afileisanexternalcollectionofrelateddatatreatedasaunit.Youmayusefileinthefollowingsituations.

Youneedtostoredatapermanently.Thecollectionofdataisoftentoolargetostoretheentiredatasimultaneouslyinmainmemory.Filesarestoredinauxiliaryorsecondarystorage【二级存储】devices(disk).Filescanbeopenedforbothreadingandwriting.UNIXseesalldevicesasfiles.So,wecansaythatthekeyboardisalsoakindoffile,althoughitcannotstoredata.Accessmethods

Sequentialaccess:afileisaccessedsequentially,andrecordsareprocessedoneafteranother,frombeginningtoend.Randomaccess:recordsareaccesseddirectly.

Figure11.16TaxonomyoffilestructuresSequentialfiles

Recordsinasequentialfile【顺序文件】canonlybereadandwritteninsequence.Toaccessaspecificrecordwithinthefile,theprogrammustsuccessivelyretrievethepreviousrecords.AnEOF(end-of-file)markerisputafterthelastrecord.Sequentialfilesareusefulinapplicationswhichneedtoaccessallrecordsinsequencefrombeginningtoend.Forexample,ifpersonalinformationabouteachemployeeinacompanyisstoredinafile,youcanusesequentialaccess【顺序访问】toretrieveeachrecordattheendofmonthtoprintthepaychecks.Inthiscase,sequentialaccessismoreefficientandeasierthanrandomaccess【随机访问】.However,indexedfilesareveryinefficientforrandomaccessoflargedatafiles

Indexedfiles

Akey【键】istheuniqueidentifierofdata(orrecord)inthefilewhichismadeupofoneormorefields.Sequentialfilesmaycontainakey,butitisnotusedtolocatetheaddressofrecords.However,theaddressoftherecordshouldbeknownwhenaccessingarecordinafilerandomly.Anindexedfile【索引文件】containsrecordsorderedbyauniquelyidentifiablekey.Forexample,anaccountnumbermightbethekeyforcustomer’srecordinabank.Anindexedfileismadeupofasequentialdatafileandanindex.Theindexitselfisaverysmallfilewithonlytwofields:thekeyofthesequentialfileandtheaddressofthecorrespondingrecordonthedisk.Figure11.17showsthelogicalviewofanindexedfile.IndexedfilesFigure11.17Logicalviewofanindexedfile

Invertedfile:Oneoftheadvantagesofindexedfileisthatitcanusealternateindexes,eachwithadifferentkey.Forexample,anemployeefilecanberetrievedthroughemployeedepartmentorlastnameratherthanemployeenumber.Thistypeofindexedfileissaidtobeaninvertedfile.Hashedfiles

Theindexisusedtomapthekeytotheaddressinanindexedfile.Thehashedfile【哈希文件】doesnotneedanextrafile(index).Itusesmathematicalfunctiontoimplementthismapping.Thefunctionreturnstheaddressonceakeyisgiven.Hashfilesaremostoftenusedasamethodforverifyingfilesize.Thehashedfileisalsoefficientforrandomaccess.

Incontrastwithindexedfile,thehashedfilecanbespace-efficientandquicktofindthekeyofanaddress.However,hashedfilessometimesmayhavetheirownproblems.HashingmethodsHashingmethodsareusedforkey-addressmapping.Someofthehashingmethodsaredirecthashing,divisionhashing,digitextractionhashing,folding,midsquare,rotation,subtraction,andpseudorandommethod.Directhashing:Indirecthashing,thekeyistheaddresswithoutanyalgorithmicmanipulation.

Modulodivisionhashing:Inmodulodivisionhashing,thekeyisdividedbythefilesizeandtheremainderplus1isusedasthehashaddressofthekey.CollisionFigure11.18Modulodivisionhashinganddirecthashing

Ahashcollisionisasituationwhenahashingalgorithmproducesanaddressforthekeybutthataddressisalreadyoccupied.Collisionisanissueforthehashingmethods.Exceptfordirectmethod.Collisionresolution

Thecollisionofkeysbyaddressescanberesolvedbypacingoneofkeysanddatainanotherlocation.Someofthecollisionresolutionmethodsareopenaddressing,linkedlistresolution,buckethashing,chaining,andquadraticprobing.Inopenaddressresolution,whenacollisionoccurs,theaddressesaresearchedforopenorunoccupiedrecordtostorenewdata.Inthisaddressresolutiontechnique,addressoftheitemisnotdeterminedbyitshashvalue.Amajordisadvantagetoopenaddressingisthat,themorecollisionsyouresolve,theprobabilityoffuturecollisionsalsoincreases.

Linkedlistresolutionresolvetheissueofhighprobabilityoffuturecollisions.

11-7ReferencesAndRecommendedReadingDaleNandLewisJ:ComputerScienceIlluminated,Sudbury,MA:JonesandBartlett,2004ForouzanBandGilbergR:ComputerScience:AStructuredProgrammingApproachUsingC,Boston,MA:CourseTechnology,2007ForouzanBandMosharrafF:FoundationsofComputerScience,CengageLearningEMEA,2021GilbergRandForouzanB:DataStructures–APseudocodeApproachwithC,Boston,MA:CourseTechnology,2005GoodrichMandTamassiaR:DataStructuresandAlgorithmsinJava,NewYork:Wiley,2005ShafferCA:DataStructuresandAlgorithmAnalysis,Blacksburg,VA:DoverPublications,202111-7ReferencesAndRecommendedReadingShafferCA:DataStructures&AlgorithmAnalysisinJava,NewYork,DoverPublications,2021SinghMandGargD:ChoosingBestHashingStrategiesandHashFunctions,IEEEInternationalAdvanceComputingConference,2021WeissMA:DataStructures&AlgorithmAnalysisinC++,England,PearsonEducationLimited,2021ZaqoutF,AbbasM,HosamAS:IndexedSequentialAccessMethod(ISAM):AReviewoftheProcessingFiles,UKSimEuropeanSymposiumonComputerModelingandSimulation,202111-8SummaryAdatatypeiscomposedofatypeandacollectionofoperationstomanipulatethetype.Therealizationofadatatypeisanabstractdatatype(ADT)whichisasoftwarecomponent.AnADTdoesnotspecifyhowtoimplementthedatatype.Thehidingofimplementationdetailsfromtheuserandprotectingitfromoutsideaccessisreferredtoasencapsulation.Alistisafinite,orderedsequenceofdataitemsknownaselements.Thearray-basedlistandthelinkedlistarethetwostandardimplementingapproaches.Comparedtoalist,astackisa“LIFO〞listandaqueueisa“FIFO〞list.So,therearemanyvariationsontheimplementationsofstackandqueue.Abinarysearchtreeisakindofbinarytreethathasasemanticpropertyonno