Chapter 4 Linked Lists

Objects:(item0,item1,,itemN1)Operations:Findingthelength,N,ofalist.Printingalltheitemsinalist.Makinganemptylist.FindingXitemfromalist,0kN.Insertinganewitemafterthek-thitemofalist,0kN.Deletinganitemfromalist.Findingnextofthecurrentitemfromalist.Findingpreviousofthecurrentitemfromalist.4.1TheListADT:CHAPTER4ListsOperations:forListLintlength(ListL)voidprintList(ListL)voidmakeEmpty(ListL)listPointerfind(elementx,ListL)voidinsert(ListL,listPointerx,listPointertemp)listPointerdeletion(ListL,listPointertrail)listPointerfindNext(listPointerp)listPointerfindPrevious(elementx,ListL)SimpleArrayimplementationofListsarray[i]=itemiMaxSizehastobeestimated.AddressContentarray+iitemiarray+i+1itemi+1……………………SequentialmappingFindingtakesO(n)time.InsertionandDeletionnotonlytakeO(N)time,butalsoinvolvealotofdatamovementswhichtakestime.4.2SinglyLinkedLists•Linkedlist–anorderedsequenceofnodeswithlinksrepresentedasarrowsptrbatcatsatvatnull–Deletematfromlist:–Insertmataftercat:ptrbatcatsatvatnullmatptrbatcatsatvatnullmatThecapabilitiestomakelinkedrepresentation:•Defineanode'sstructure----self-referentialstructures•Createanewnode----mallocfunction•Removenodes----freefunction〖Example4.1〗listofwordsendinginatdefineanodetypedefstructlistNode*listPointer;structuretypedefstructlistNode{chardata[4];listPointerlink;};createanewlistlistPointerptr=NULL;(#defineIS_EMPTY(ptr)(!(ptr)))createnewnodesMALLOC(ptr,sizeof(listNode),listPointer);placeawordintotheliststrcpy(ptr-data,bat);ptr-link=NULL;Freepointfree(ptr);addressoffirstnodeptr-dataptr-linkptrbat\0〖Example4.2〗alinkedlistofintegers.defineanodetypedefstructlistNode*listPointer;structuretypedefstructlistNode{intdata;listPointerlink;};createnewnodesMALLOC(ptr,sizeof(listNode),listPointer);FreepointFREE(ptr);createanewlistlistPointerptr=NULL;〖example〗Listinsertiona1firstNULLaiai+1an......btemptemp-link=x-linkx-link=tempQuestion:Whatwillhappeniftheorderofthetwostepsisreversed?ReadProgram4.2onp.153andanswerthequestion:WhyisfirstpassedasapointertolistPointer?x〖example〗Listinsertion#defineIS_FULL(ptr)(!(ptr))voidinsert(listPointer*first,listPointerx){/*insertanewnodewithdata=50intothelistfirstafternodex*/listPointertemp;MALLOC(temp,sizeof(*temp));temp-data=50;if(*first){temp-link=x-link;x-link=temp;}else{temp-link=NULL;*first=temp;}}ptr1020null50tempnode〖example〗listdeletiona1firstNULLaiai+1an......btrailxtrail-link=x-linkfree(node)bnodeQuestion:Howcanwedeletethefirstnodefromalist?ReadProgram4.3onp.155andfindtheanswer.〖example〗listdeletionvoiddelete(listPointer*first,listPointertrail,listPointerx){/*deletenodefromthelist,trailistheprecedingnode,ptristheheadofthelist*/if(trail)trail-link=x-link;else*first=(*first)-link;free(x);}ptr1020null50nodeptr5020nulltrail=NULLbeforedeletionafterdeletionListafterthefunctioncalldelete(&ptr,NULL,ptr)ptr1020null50trailptr1020nullbeforedeletionafterdeletionnodeListafterthefunctioncalldelete(&ptr,ptr,prt-link)〖example〗PrintingoutalistvoidprintList(listPointerfirst){printf(Thelistcontains:);for(;first;first=first-link)printf(%4d”,first-data);printf(\n);}〖练习〗从文件“input.txt”读入一整数序列，建立链表，并依次输出链表中各元素的值。4.3DynamicallyLinkedStacksandQueues•LinkedStackstopnullelementlink....STACKNULLitemitemitemtopPush:itemtoptemptemp-link=toptop=tempReadProgram4.5andProgram4.6onp.121aboutimplementationofpushandpopPop:temp=toptop=top-linktopitem=temp-itemfree(temp)itemreturnitemQuestion:Howtorepresentnstacks?Answer:stackPointertop[n];Program:Addtoalinkedstackvoidpush(inti,elementitem){/*addanelementtothetopofthestack*/stackPointertemp;MALLOC(temp,sizeof(*temp));temp-data=item;temp-link=top[i];top[i]=temp;}#defineMAX_STACKS10/*maximumnumberoldstacks*/typedefstructstack*stackPointer;typedefstructstack{elementdata;stackPointerlink；};stackPointertop[MAX_STACKS];Program:Deletefromalinkedstackelementpop(inti){/*deleteanelementfromthestack*/stackPointertemp=top[i];intitem;if(!temp){fprintf(stderr,Thestackisempty\n);exit(1);}item=temp-item;top[i]=temp-link;FREE(temp);returnitem;}theboudaryconditionforthestacks:top[i]=NULL,ifftheithstackisempty0=iMAX_STACKSIS_FULL(temp)iffthememoryisfullLinkedQueuesQUEUENULLitemitemitemfrontrearaddq:itemtemprear-link=temptemp-link=NULLNULLrear=tempreardeleteq:temp=fronttempfront=temp-linkfrontitem=temp-itemitemfree(temp)returnitemReadProgram4.7andProgram4.8onp.159-160aboutimplementationofaddqanddeleteqQuestion:Howtorepresentnqueues?Answer:queuePointerfront[n],rear[n];frontnullelementlink....rearProgram:Addtotherearofalinkedqueuevoidaddq(inti,elementitem){/*addanelementtotherearofthequeue*/queuePointertemp;MALLOC(temp,sizeof(*temp));temp-data=item;temp-link=NULL;if(front[i])rear[i]-link=temp;elsefront[i]=temp;rear[i]=temp;}#defineMAX_QUEUES10/*maximumnumberofqueues*/typedefstructqueue*queuePointer;typedefstructqueue{elementdata;queuePointerlink:};queuePointerfront[MAX_QUEUES],rear[MAX_QUEUES];Program:Deletefromthefrontofalinkedqueueelementdeleteq(inti){/*deleteanelementfromth