《計算機(jī)科學(xué)導(dǎo)論》課件Unit 11Data and File Structure

?計算機(jī)科學(xué)導(dǎo)論?課件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【基于數(shù)組列表】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【內(nèi)存】isallocateddynamicallywhenanewelementisaddedintoit

Aseparatelistcanbemadeasanodeclassbecausenodesinalistaredistinctobjects(asopposedtosimplyacellinanarray).

Thefirstnodeofthelistisaccessedfromapointercalledhead【頭指針】.Apointercalledtail【尾指針】isalsokepttothelastlinkofthelist.Anotherpointercalledcurr【當(dāng)前指針】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【?！縤salist-likedatastructure.Elementscanonlybeinsertedorremovedfromoneendinstack.Forthisreason,stacksarenotasflexibleaslists.However,intheapplicationsthatrequireonlythelimitedformofinsertandremoveoperations,stacksaremoreefficientthanlists.Longbeforetheinventionofthecomputer,stackswereusedbyaccountants.Theynamedthestacka“LIFO〞【后進(jìn)先出】list,whichmeans“Last-In,First-Out.〞Stacksremoveelementsinreverseorderoftheirarrival.Theelementweaccesseachtimeiscalledthetopelement.Whenanewelementisadded,wesayitispushedontothestack.Whenremoved,anelementissaidtobepoppedfromthestack.11-3StackFigure11.8showsasimplerepresentationofstackruntimewithpushandpopoperations.Thetwocommonapproachesofstackimplementationpresentedherearearray-basedandlinkedstacks,whichareanalogoustoarray-basedandlinkedlists,respectively.Theapplicationofstacksinamostcommoncomputerapplicationisperhapsnotevenvisibletoitsusers.Liketheuseofstacksduringruntimeofasubroutinecall【子程序調(diào)用】inmostoftheprogramminglanguages.

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

QueueSimilartostack,thequeue【隊(duì)列】isalist-likedatastructurethatgiveslimitedaccesstoitselements.Aqueuehastwokindsofoperations.Oneisenqueue【入隊(duì)】operation,andtheotherisdequeue【出隊(duì)】operation.Queuesoperatelikestandinginlineatasubwaystation.Ifnobodycheats,thennewcomersgotothebackoftheline.Thepersonatthefrontofthelineisthenexttoenterthesubway.Thus,inqueues,theelementsareretrievedinorderofarrival.Queueisalsocalleda“FIFO〞【先進(jìn)先出】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【根節(jié)點(diǎn)】ofatreeisthefirstnode,ifthetreeisnotempty.Theindegreeoftherootiszero.Excepttheroot,eachnodeinatreehasanindegreeofexactlyone.However,outdegreeofanynodeinatreecanbezero,oneormore.Aleaf【葉節(jié)點(diǎn)】isanynodewithanoutdegreeofzero.Anodethatisnotarootoraleafiscalledaninternalnode.11-5TreeandGraphFigure11.11Anexampleofangeneraltree

Ifanodehassuccessornodes,thatis,ifithasoutdegreeofatleastone,itiscalledaparent【父節(jié)點(diǎn)】.Anodewithapredecessoriscalledachild【子節(jié)點(diǎn)】.Childnode’sindegreeisnecessarilyone..Nodeswiththesameparentarereferredtoassiblings【兄弟節(jié)點(diǎn)】.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【頂點(diǎn)】andagroupoflinesbetweenthenodescallededges【邊】.Anundirectedgraph【無向圖】isagraphinwhichedgeshavenodirectionswhileedgesinadirectedgraph【有向圖】aredirectedfromonenodetoanother,asshowninFigure11.14.IfweaddflightpricetoeachofthearrowsinFigure11.14,thenwegetaweightedgraph【加權(quán)圖】.Thepriceontheedgesarecalledtheweights【權(quán)重】.Twoverticesconnectedbyanedgearecalledadjacentvertices【鄰接點(diǎn)】.Andapath【路徑】isasequenceofedgesthatconnectstwonodesinagraph.

graphtraversal

graphtraversalisdefinedasaprocessthataccessesalloftheverticesinagraphonceandonlyonceatatimestartingfromanyvertex.therearetwokindsofgraphtraversalmethods:depth-firstsearch【深度優(yōu)先搜索】breadth-firstsearch【廣度優(yōu)先搜索】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【隨機(jī)訪問】.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