SavCpp8PowerPointsSavitch_ch_13

Chapter13,PointersandLinkedLists,Overview,13.1NodesandLinkedLists13.2StacksandQueues,Slide13-3,13.1,NodesandLinkedLists,NodesandLinkedLists,Slide13-5,AlinkedlistisalistthatcangrowandshrinkwhiletheprogramisrunningAlinkedlistisconstructedusingpointersAlinkedlistoftenconsistsofstructsorclassesthatcontainapointervariableconnectingthemtootherdynamicvariablesAlinkedlistcanbevisualizedasitems,drawnasboxes,connectedtootheritemsbyarrows,Nodes,TheboxesinthepreviousdrawingrepresentthenodesofalinkedlistNodescontainthedataitem(s)andapointerthatcanpointtoanothernodeofthesametypeThepointerspointtotheentirenode,notanindividualitemthatmightbeinthenodeThearrowsinthedrawingrepresentpointers,Slide13-6,Display13.1,ImplementingNodes,NodesareimplementedinC+asstructsorclassesExample:Astructuretostoretwodataitemsandapointertoanothernodeofthesametype,alongwithatypedefinitionmightbe:structListNodestringitem;intcount;ListNode*link;typedefListNode*ListNodePtr;,Slide13-7,TheheadofaList,Theboxlabeledhead,indisplay13.1,isnotanode,butapointervariablethatpointstoanodePointervariableheadisdeclaredas:ListNodePtrhead;,Slide13-8,AccessingItemsinaNode,Usingthediagramof13.1,thisisonewaytochangethenumberinthefirstnodefrom10to12:(*head).count=12;headisapointervariableso*headisthenodethatheadpointstoTheparenthesesarenecessarybecausethedotoperator.hashigherprecedencethanthedereferenceoperator*,Slide13-9,TheArrowOperator,Thearrowoperator-combinestheactionsofthedereferencingoperator*andthedotoperatortospecifyamemberofastructorobjectpointedtobyapointer(*head).count=12;canbewrittenashead-count=12;Thearrowoperatorismorecommonlyused,Slide13-10,Display13.2,NULL,ThedefinedconstantNULLisusedasAnendmarkerforalinkedlistAprogramcanstepthroughalistofnodesbyfollowingthepointers,butwhenitfindsanodecontainingNULL,itknowsithascometotheendofthelistThevalueofapointerthathasnothingtopointtoThevalueofNULLis0AnypointercanbeassignedthevalueNULL:double*there=NULL;,Slide13-11,ToUseNULL,AdefinitionofNULLisfoundinseverallibraries,includingandAusingdirectiveisnotneededforNULL,Slide13-12,LinkedLists,ThediagraminDisplay13.2depictsalinkedlistAlinkedlistisalistofnodesinwhicheachnodehasamembervariablethatisapointerthatpointstothenextnodeinthelistThefirstnodeiscalledtheheadThepointervariablehead,pointstothefirstnodeThepointernamedheadisnottheheadofthelistitpointstotheheadofthelistThelastnodecontainsapointersettoNULL,Slide13-13,BuildingaLinkedList:Thenodedefinition,Letsbeginwithasimplenodedefinition:structNodeintdata;Node*link;typedefNode*NodePtr;,Slide13-14,BuildingaLinkedList:DeclaringPointerVariablehead,Withthenodedefinedandatypedefinitiontomakeorcodeeasiertounderstand,wecandeclarethepointervariablehead:NodePtrhead;headisapointervariablethatwillpointtotheheadnodewhenthenodeiscreated,Slide13-15,BuildingaLinkedList:CreatingtheFirstNode,Tocreatethefirstnode,theoperatornewisusedtocreateanewdynamicvariable:head=newNode;Nowheadpointstothefirst,andonly,nodeinthelist,Slide13-16,BuildingaLinkedList:InitializingtheNode,Nowthatheadpointstoanode,weneedtogivevaluestothemembervariablesofthenode:head-data=3;head-link=NULL;Sincethisnodeisthelastnode,thelinkissettoNULL,Slide13-17,Functionhead_insert,Itwouldbebettertocreateafunctiontoinsertnodesattheheadofalist,suchas:voidhead_insert(NodePtrThefirstparameterisaNodePtrparameterthatpointstothefirstnodeinthelinkedlistThesecondparameteristhenumbertostoreinthelisthead_insertwillcreateanewnodeforthenumberThenumberwillbecopiedtothenewnodeThenewnodewillbeinsertedinthelistasthenewheadnode,Slide13-18,Pseudocodeforhead_insert,Createanewdynamicvariablepointedtobytemp_ptrPlacethedatainthenewnodecalled*temp_ptrMaketemp_ptrslinkvariablepointtotheheadnodeMaketheheadpointerpointtotemp_ptr,Slide13-19,Display13.3,Translatinghead_inserttoC+,Thepseudocodeforhead_insertcanbewritteninC+usingtheselinesinplaceofthelinesofpseudocode:NodePtrtemp_ptr;/createthetemporarypointertemp_ptr=newNode;/createthenewnodetemp_ptr-data=the_number;/copythenumbertemp_ptr-link=head;/newnodepointstofirstnodehead=temp_ptr;/headpointstonew/firstnode,Slide13-20,Display13.4,AnEmptyList,AlistwithnothinginitiscalledanemptylistAnemptylinkedlisthasnoheadnodeTheheadpointerofanemptylistisNULLhead=NULL;Anyfunctionswrittentomanipulatealinkedlistshouldchecktoseeifitworksontheemptylist,Slide13-21,LosingNodes,Youmightbetemptedtowritehead_insertusingtheheadpointertoconstructthenewnode:head=newNode;head-data=the_number;NowtoattachthenewnodetothelistThenodethatheadusedtopointtoisnowlost!,Slide13-22,Display13.5,MemoryLeaks,NodesthatarelostbyassigningtheirpointersanewaddressarenotaccessibleanylongerTheprogramhasnowaytorefertothenodesandcannotdeletethemtoreturntheirmemorytothefreestoreProgramsthatlosenodeshaveamemoryleakSignificantmemoryleakscancausesystemcrashes,Slide13-23,SearchingaLinkedList,Todesignafunctionthatwilllocateaparticularnodeinalinkedlist:Wewantthefunctiontoreturnapointertothenodesowecanusethedataifwefindit,elsereturnNULLThelinkedlistisoneargumenttothefunctionThedatawewishtofindistheotherargumentThisdeclarationwillwork:NodePtrsearch(NodePtrhead,inttarget);,Slide13-24,Functionsearch,RefiningourfunctionWewillusealocalpointervariable,namedhere,tomovethroughthelistcheckingforthetargetTheonlywaytomovearoundalinkedlististofollowpointersWewillstartwithherepointingtothefirstnodeandmovethepointerfromnodetonodefollowingthepointeroutofeachnode,Slide13-25,Display13.6,Pseudocodeforsearch,Makepointervariableherepointtotheheadnodewhile(heredoesnotpointtoanodecontainingtargetANDheredoesnotpointtothelastnode)makeherepointtothenextnodeIf(herepointstoanodecontainingthetarget)returnhere;elsereturnNULL;,Slide13-26,MovingThroughtheList,ThepseudocodeforsearchrequiresthatpointerherestepthroughthelistHowdoesherefollowthepointersfromnodetonode?Whenherepointstoanode,here-linkistheaddressofthenextnodeTomakeherepointtothenextnode,maketheassignment:here=here-link;,Slide13-27,ARefinementofsearch,Thesearchfunctioncanberefinedinthisway:here=head;while(here-data!=target,Slide13-28,Checkforlastnode,SearchinganEmptyList,OursearchalgorithmhasaproblemIfthelistisempty,hereequalsNULLbeforethewhileloopsohere-dataisundefinedhere-linkisundefinedTheemptylistrequiresaspecialcaseinoursearchfunctionArefinedsearchfunctionthathandlesanemptylistisshownin,Slide13-29,Display13.7,PointersasIterators,AniteratorisaconstructthatallowsyoutocyclethroughthedataitemsinadatastructuretoperformanactiononeachitemAniteratorcanbeanobjectofaniteratorclass,anarrayindex,orsimplyapointerAgeneraloutlineusingapointerasaniterator:Node_Type*iter;for(iter=Head;iter!=NULL;iter=iter-Link)/performtheactiononthenodeiterpointstoHeadisapointertotheheadnodeofthelist,Slide13-30,IteratorExample,Usingthepreviousoutlineofaniteratorwecandisplaythecontentsofalinkedlistinthisway:NodePtriter;for(iter=Head;iter!=NULL;iter=iter-Link)coutdata);,Slide13-31,InsertingaNodeInsideaList,Toinsertanodeafteraspecifiednodeinthelinkedlist:UseanotherfunctiontoobtainapointertothenodeafterwhichthenewnodewillbeinsertedCallthepointerafter_meUsefunctioninsert,declaredheretoinsertthenode:voidinsert(NodePtrafter_me,intthe_number);,Slide13-32,Display13.8,InsertingtheNewNode,Functioninsertcreatesthenewnodejustashead_insertdidWedonotwantournewnodeattheheadofthelisthowever,soWeusethepointerafter_metoinsertthenewnode,Slide13-33,InsertingtheNewNode,Thiscodewillaccomplishtheinsertionofthenewnode,pointedtobytemp_ptr,afterthenodepointedtobyafter_me:temp_ptr-link=after_me-link;after_me-link=temp_ptr;,Slide13-34,Caution!,TheorderofpointerassignmentsiscriticalIfwechangedafter_me-linktopointtotemp_ptrfirst,wewouldloosetherestofthelist!Thecompleteinsertfunctionisshownin,Slide13-35,Display13.9,FunctioninsertAgain,NoticethatinsertingintoalinkedlistrequiresthatyouonlychangetwopointersThisistrueregardlessofthelengthofthelistUsinganarrayforthelistwouldinvolvecopyingasmanyasallofthearrayelementstonewlocationstomakeroomforthenewitemInsertingintoalinkedlistisoftenmoreefficientthaninsertingintoanarray,Slide13-36,RemovingaNode,ToremoveanodefromalinkedlistPositionapointer,before,topointatthenodepriortothenodetoremovePositionapointer,discard,topointatthenodetoremovePerform:before-link=discard-link;Thenodeisremovedfromthelist,butisstillinmemoryReturn*discardtothefreestore:deletediscard;,Slide13-37,Display13.10,AssignmentWithPointers,Ifhead1andhead2arepointervariablesandhead1pointstotheheadnodeofalist:head2=head1;causeshead2andhead1topointtothesamelistThereisonlyonelist!Ifyouwanthead2topointtoaseparatecopy,youmustcopythelistnodebynodeoroverloadtheassignmentoperatorappropriately,Slide13-38,VariationsonLinkedLists,ManyotherdatastructurescanbeconstructedusingnodesandpointersDoubly-LinkedListEachnodehastwolinks,onetothenextnodeandonetothepreviousnodeAllowseasytraversalofthelistinbothdirectionsstructNodeintdata;Node*forward_link;Node*back_link;,Slide13-39,Display13.11,BinaryTree,Atreeisadatastructurethatlookslikeanupside-downtreewiththerootatthetopNocyclesInabinarytreeeachnodehasatmosttwolinks,Slide13-40,structTreeNodeintdata;TreeNode*left_link;TreeNode*right_link;,Display13.12,LinkedListofClasses,Theprecedingexamplescreatedlinkedlistsofstructs.Wecanalsocreatelinkedlistsusingclasses.LogictouseaclassisidenticalexceptthesyntaxofusinganddefiningaclassshouldbesubstitutedinplaceofthatforastructInterfaceandDefinitionforaNodeClass,Slide13-41,Display13.13,Display13.14(1-2),ProgramusingtheNodeclass,WecancreatealinkedlistofnumbersusingtheNodeclass.,Slide13-42,Display13.15(1-3),Section13.1Conclusion,CanyouWritetypedefinitionsforthenodesandpointersinalinkedlist?CallthenodetypeNodeTypeandcallthepointertypePointerType.Thelinkedlistswillbelistsofletters.Explainwhyinsertingintoanarraycanbelessefficientthaninsertingintoalinkedlist?,Slide13-43,13.2,StacksandQueues,ALinkedListApplication,AstackisadatastructurethatretrievesdatainthereverseorderthedatawasstoredIfA,B,andthenCareplacedinastack,theywillberemovedintheorderC,B,andthenAAstackisalast-in/first-outdatastructurelikethestackofplatesinacafeteria;addingaplatepushesdownthestackandthetopplateisthefirstoneremoved,Slide13-45,Display13.16,ProgramExample:AStackClass,WewillcreateastackclasstostorecharactersAddinganitemtoastackispushingontothestackMemberfunctionpushwillperformthistaskRemovinganitemfromthestackispoppingthetheitemoffthestackMemberfunctionpopwillperformthistaskcontainsthestackclassinterface,Slide13-46,Display13.17,UsingthestackClass,demonstratestheuseofthestackclass,Slide13-47,Display13.18(1-2),Functionpush,ThepushfunctionaddsanitemtothestackItusesaparameterofthetypestoredinthestackvoidpush(charthe_symbol);Pushinganitemontothestackispreciselythesametaskaccomplishedbyfunctionhead_insertofthelinkedlistForastack,apointernamedtopisusedinsteadofapointernamedhead,Slide13-48,Functionpop,Thepopfunctionreturnstheitemthatwasatthetopofthestackcharpop();Beforepoppinganitemfromastack,popchecksthatthestackisnotemptypopstoresthetopiteminalocalvariableresult,andtheitemispoppedby:top=top-link;Atemporarypointermustpointtotheoldtopitemsoitcanbedeletedtopreventamemoryleakpopthenreturnsvariableresult,Slide13-49,EmptyStack,AnemptystackisidentifiedbysettingthetoppointertoNULLtop=NULL;,Slide13-50,TheCopyConstructor,Becausethestackclassusesapointerandcreatesnewnodesusingnew,acopyconstructorisneededThecopyconstructor(aself-testexercise)mustmakeacopyofeachiteminthestackandstorethecopiesinanewstackItemsinthenewstackmustbeinthesamepositioninthestackasintheoriginal,Slide13-51,Thestackdestructor,Becausefunctionpopcallsdeleteeachtimeanitemispoppedoffthestack,stackonlyneedstocallpopuntilthestackisemptycharnext;while(!empty()next=pop();,Slide13-52,stackClassImplementation,Thestackclassimplementationisfoundin,Slide13-53,Display13.19(1),Display13.19(2),AQueue,AqueueisadatastructurethatretrievesdatainthesameorderthedatawasstoredIfA,B,andthenCareplacedinaqueue,theywillberemovedintheorderA,B,andthenCAqueueisafirst-in/first-outdatastructurelikethecheckoutlineinasupermarket,Slide13-54,Display13.20,QueueClassImplementation,Thequeueclassisimplementedinamannersimilartothestackexcepttherearetwopointers,onetotrackthefrontofthelist,andonetotrackthebackofthelistInterface:ProgramusingtheQueueClass:Implementation:,Slide13-55,Display13.21(1-2),Display13.22(1-2),Display13.23(1-3),Section13.2Conclusion,CanyouGiveth