C語言基礎教程課件(英文版)ch13

AFirstBookofANSIC

FourthEditionChapter13DynamicDataStructuresAFirstBookofANSIC,FourthEdition2ObjectivesIntroductiontoLinkedListsDynamicMemoryAllocationStacksQueuesDynamicallyLinkedListsCommonProgrammingandCompilerErrorsAFirstBookofANSIC,FourthEdition3IntroductionDynamicmemoryallocation:analternativetofixedmemoryallocationinwhichmemoryspacegrowsordiminishesduringprogramexecutionDynamicmemoryallocation

makesitunnecessarytoreserveafixedamountofmemoryforascalar,array,orstructurevariableinadvanceAlsoknownasrun-timeallocationRequestsaremadeforallocationandreleaseofmemoryspacewhiletheprogramisrunningAFirstBookofANSIC,FourthEdition4IntroductiontoLinkedListsAnarrayofstructurescanbeusedtoinsertanddeleteorderedstructures,butthisisnotanefficientuseofmemoryBetteralternative:alinkedlistLinkedlist:setofstructures,eachcontainingatleastonememberwhosevalueistheaddressofthenextlogicallyorderedstructureinthelistAlsoknownasself-referencingstructuresAFirstBookofANSIC,FourthEdition5IntroductiontoLinkedLists(continued)AFirstBookofANSIC,FourthEdition6IntroductiontoLinkedLists(continued)AFirstBookofANSIC,FourthEdition7IntroductiontoLinkedLists(continued)ANULLactsasasentinelorflagtoindicatewhenthelaststructurehasbeenprocessedInadditiontoanend-of-listsentinelvalue,wemustprovideaspecialpointerforstoringtheaddressofthefirststructureinthelistAFirstBookofANSIC,FourthEdition8IntroductiontoLinkedLists(continued)AFirstBookofANSIC,FourthEdition9IntroductiontoLinkedLists(continued)AFirstBookofANSIC,FourthEdition10Astructurecancontainanydatatype,includingapointer.Apointermemberofastructureisusedlikeanyotherpointervariable.IntroductiontoLinkedLists(continued)AFirstBookofANSIC,FourthEdition11isevaluatedas(t1.nextaddr)->nameitcanbereplacedby(*t1.nextaddr).nameIntroductiontoLinkedLists(continued)AFirstBookofANSIC,FourthEdition12IntroductiontoLinkedLists(continued)AFirstBookofANSIC,FourthEdition13IntroductiontoLinkedLists(continued)Disadvantage:exactlythreestructuresaredefinedinmain()byname,andstorageforthemisreservedatcompiletimeAFirstBookofANSIC,FourthEdition14IntroductiontoLinkedLists(continued)canbereplacedbywhile(!contents)AFirstBookofANSIC,FourthEdition15DynamicMemoryAllocationAFirstBookofANSIC,FourthEdition16DynamicMemoryAllocation(continued)Themalloc()andcalloc()functionscanfrequentlybeusedinterchangeablyTheadvantageofcalloc()isthatitinitializesallnewlyallocatednumericmemoryto0andcharacterallocatedmemorytoNULLWeusemalloc()becauseitisthemoregeneralpurposeofthetwofunctionsmalloc(10*sizeof(char))orcalloc(10,sizeof(char))requestsenoughmemorytostore10charactersThespaceallocatedbymalloc()comesfromthecomputer’sheapAFirstBookofANSIC,FourthEdition17…Necessarybecausemalloc()returnsvoidDynamicMemoryAllocation(continued)AFirstBookofANSIC,FourthEdition18DynamicMemoryAllocation(continued)malloc()ismoretypicallyusedfordynamicallyallocatingmemoryforstructuresstructOfficeInfo*Off;/*requestspaceforonestructure*/Off=(structOfficeInfo*)malloc(sizeof(structOfficeInfo));/*checkthatspacewasallocated*/if(Off==(structOfficeInfo*)NULL){printf("\nAllocationfailed\n");exit(1);}AFirstBookofANSIC,FourthEdition19StacksStack:specialtypeoflinkedlistinwhichobjectscanonlybeaddedtoandremovedfromthetopofthelistLast-in,first-out(LIFO)listInatruestack,theonlyitemthatcanbeseenandaccessedisthetopitemAFirstBookofANSIC,FourthEdition20Stacks(continued)AFirstBookofANSIC,FourthEdition21StackImplementationCreatingastackrequiresthefollowingfourcomponents:AstructuredefinitionAmethodofdesignatingthecurrenttopstackstructureAnoperationforplacinganewstructureonthestackAnoperationforremovingastructurefromthestackAFirstBookofANSIC,FourthEdition22PUSHandPOPPUSH(addanewstructuretothestack)DynamicallycreateanewstructurePuttheaddressinthetop-of-stackpointerintotheaddressfieldofthenewstructureFillintheremainingfieldsofthenewstructurePuttheaddressofthenewstructureintothetop-of-stackpointerPOP(removeastructurefromthetopofthestack)Movethestructurecontentspointedtobythetop-of-stackpointerintoaworkareaFreethestructurepointedtobythetop-of-stackpointerMovetheaddressintheworkareaaddressfieldintothetop-of-stackpointerAFirstBookofANSIC,FourthEdition23PUSHandPOP(continued)AFirstBookofANSIC,FourthEdition24PUSHandPOP(continued)AFirstBookofANSIC,FourthEdition25PUSHandPOP(continued)AFirstBookofANSIC,FourthEdition26PUSHandPOP(continued)AFirstBookofANSIC,FourthEdition27PUSHandPOP(continued)AsamplerunusingProgram13.5producedthefollowing:Enterasmanynamesasyouwish,oneperlineTostopenteringnames,enterasinglexEnteraname:JaneJonesEnteraname:BillSmithEnteraname:JimRobinsonEnteraname:xThenamespoppedfromthestackare:JimRobinsonBillSmithJaneJonesAFirstBookofANSIC,FourthEdition28QueuesAsecondimportantdatastructurethatreliesonlinkedstructuresiscalledaqueueItemsareremovedfromaqueueintheorderinwhichtheywereenteredItisafirstin,firstout(FIFO)structureAFirstBookofANSIC,FourthEdition29Queues(continued)AFirstBookofANSIC,FourthEdition30Queues(continued)AFirstBookofANSIC,FourthEdition31EnqueandServeEnqueueing:placinganewitemontopofthequeueServing:removinganitemfromaqueueAFirstBookofANSIC,FourthEdition32EnqueandServe(continued)AFirstBookofANSIC,FourthEdition33EnqueandServe(continued)Enqueue(addanewstructuretoanexistingqueue)DynamicallycreateanewastructureSettheaddressfieldofthenewstructuretoaNULLFillintheremainingfieldsofthenewstructureSettheaddressfieldofthepriorstructure(whichispointedtobythequeueInpointer)totheaddressofthenewlycreatedstructureUpdatetheaddressinthequeueInpointerwiththeaddressofthenewlycreatedstructureAFirstBookofANSIC,FourthEdition34EnqueandServe(continued)AFirstBookofANSIC,FourthEdition35EnqueandServe(continued)Serve(removeastructurefromanexistingqueue)MovethecontentsofthestructurepointedtobythequeueOutpointerintoaworkareaFreethestructurepointedtobythequeueOutpointerMovetheaddressintheworkareaaddressfieldintothequeueOutpointerAFirstBookofANSIC,FourthEdition36EnqueandServe(continued)AFirstBookofANSIC,FourthEdition37EnqueandServe(continued)AFirstBookofANSIC,FourthEdition38EnqueandServe(continued)AFirstBookofANSIC,FourthEdition39EnqueandServe(continued)AFirstBookofANSIC,FourthEdition40EnqueandServe(continued)AFirstBookofANSIC,FourthEdition41EnqueandServe(continued)AsamplerunusingProgram13.6producedthefollowing:Enterasmanynamesasyouwish,oneperlineTostopenteringnames,enterasinglexEnteraname:JaneJonesEnteraname:BillSmithEnteraname:JimRobinsonEnteraname:xThenamesservedfromthequeueare:JaneJonesBillSmithJimRobinsonAFirstBookofANSIC,FourthEdition42DynamicallyLinkedListsBothstacksandqueuesareexamplesoflinkedlistsinwhichelementscanonlybeaddedtoandremovedfromtheendsofthelistInadynamicallylinkedlist,thiscapabilityisextendedtopermitaddingordeletingastructurefromanywherewithinthelistSuchacapabilityisextremelyusefulwhenstructuresmustbekeptwithinaspecifiedorderAFirstBookofANSIC,FourthEdition43INSERTandDELETEKeyfieldAFirstBookofANSIC,FourthEdition44INSERTandDELETE(continued)INSERT(addanewstructureintoalinkedlist)DynamicallyallocatespaceforanewstructureIfnostructuresexistinthelistSettheaddressfieldofthenewstructuretoaNULLSetaddressinthefirststructurepointertoaddressofnewlycreatedstructureElse/*weareworkingwithanexistinglist*/LocatewherethisnewstructureshouldbeplacedIfthisstructureshouldbethenewfirststructureinthelistCopycurrentcontentsoffirststructurepointerintoaddressfieldofnewlycreatedstructureSetaddressinthefirststructurepointertoaddressofnewlycreatedstructureElseCopytheaddressinthepriorstructure’saddressmemberintotheaddressfieldofthenewlycreatedstructureSetaddressofpriorstructure’saddressmembertoaddressofnewlycreatedstructureEndIfEndIfAFirstBookofANSIC,FourthEdition45INSERTandDELETE(continued)AFirstBookofANSIC,FourthEdition46INSERTandDELETE(continued)LINEARLOCATIONforINSERTINGaNEWSTRUCTUREIfthekeyfieldofthenewstructureislessthanthefirststructure’skeyfieldthenewstructureshouldbethenewfirststructureElseWhiletherearestillmorestructuresinthelistComparethenewstructure’skeyvaluetoeachstructurekeyStopthecomparisonwhenthenewstructurekeyeitherfallsbetweentwoexistingstructuresorbelongsattheendoftheexistinglistEndWhileEndIfAFirstBookofANSIC,FourthEdition47SeeSlide50SeeSlide50INSERTandDELETE(continued)AFirstBookofANSIC,FourthEdition48INSERTandDELETE(continued)AFirstBookofANSIC,FourthEdition49INSERTandDELETE(continued)AFirstBookofANSIC,FourthEdition50...(codeforinsert()andlocate()goeshere)…INSERTandDELETE(continued)AFirstBookofANSIC,FourthEdition51INSERTandDELETE(continued)Thefollowingsamplerunshowstheresultsofthesetests:Enterasmanynamesasyouwish,oneperlineTostopenteringnames,enterasinglexEnteraname:BinstockEnteraname:ArnoldEnteraname:DuberryEnteraname:CarterEnteraname:xThenamescurrentlyinthelist,inalphabeticalorder,are:ArnoldBinstockCarterDuberryAFirstBookofANSIC,FourthEdition52CommonProgrammingErrorsNotcheckingthereturncodesprovidedbymalloc()andrealloc()Notcorrectlyupdatingallrelevantpointeraddresseswhenaddingorremovingstructuresfromdynamicallycreatedstacks,queues,andlinkedlistsForgettingtofreepreviouslyallocatedmemoryspacewhenthespaceisnolongerneededAFirstBookofANSIC,FourthEdition53CommonProgrammingErrors(continued)Notpreservingtheintegrityoftheaddressescontainedinthetop-of-stackpointer,queue-in,queue-out,andlistpointerwhendealingwithastack,queue,anddynamicallylinked