【数据结构英文课件】Linked Stacks and Queues.ppt

《【数据结构英文课件】Linked Stacks and Queues.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Chapter4LinkedStacksandQueues1.PointersandLinkedStructures2.LinkedStacks3.LinkedStackswithSafeguards4.LinkedQueues5.Application:PolynomialArithmetic6.AbstractDataTypesandImplementations7.PointersandPitfallsALinkedListisasequenceofzeroormoreelementscallednodese

2、achcontainingtwokindsofinformation:somedataandoneormorelinkscalledpointerstoothernodesofthelinkedlist.4.1PointersandaLinkedListKeyTermsOverflow:Runningoutofspace.Pointer:Anobject,oftenavariable,thatstoresthelocation(thatisthemachineaddress)ofsomeotherobject,

3、typicallyofastructurecontainingdatathatwewishtomanipulate.(Alsosometimescalledalinkorareference)Linkedlist:Alistinwhicheachentrycontainsapointergivingthelocationofthenextentry.Contiguous:Nexttoeachother,touching,adjoining;usedincontrasttolinked.Automaticobj

4、ect:Anobjectthatexistsaslongastheblockofprogramdeclaringitisactive;referencedbygivingitanamewhenwritingtheprogram.Dynamicobject:Anobjectthatiscreated(andperhapsdestroyed)whiletheprogramisrunning;accessedindirectlyviapointers.PointersinC++Notation:C++usesanas

5、terisk*todenoteapointer.IfItemisatype,thenapointertosuchanItemobjecthasthetypeItem*.Forexample,Item*itemptr;declaresitemptrasapointervariabletoanItemobject.Creatingdynamicobjects:item_ptr=newItem;createsanewdynamicobjectoftypeItemandassignsitslocationtothepoi

6、ntervariableitem_ptr.Thedynamicobjectsthatwecreatearekeptinanareaofcomputermemorycalledthefreestore(ortheheap).Deletingdynamicobjects:deleteitem_ptr;disposesofthedynamicobjecttowhichitem_ptrpointsandreturnsthespaceitoccupiestothefreestoresoitcanbeusedagain.Af

7、terthisdeletestatementisexecuted,thepointervariableitem_ptrisundefinedandsoshouldnotbeuseduntilitisassignedanewvalue.Followingpointers:*item_ptrdenotestheobjecttowhichitem_ptrpoints.Theactionoftaking“*item_ptriscalled*referencingthepointer*item_ptr.”NULLpoin

8、ters:Ifapointervariableitem_ptrhasnodynamicobjecttowhichitcurrentlyrefers,thenitshouldbegiventhespecialvalueitem_ptr=NULL;IndiagramswereservetheelectricalgroundsymbolforNULLpointer