链表课件(英文)

IntroductiontoComputer(CProgramming)LinkList2023/2/19.10DynamicmemoryallocationDynamicmemoryallocationistheprocessofallocatingmemoryatruntime.Memorymanagementfunctionscanbeusedforallocatingandfreeingmemoryduringprogramexecution.2023/2/19.10DynamicmemoryallocationDynamicmemoryallocationistheprocessofallocatingmemoryatruntime.Memorymanagementfunctionscanbeusedforallocatingandfreeingmemoryduringprogramexecution.FunctionTaskmallocAllocatesrequestsizeofbytesandreturnsapointertothefirstbyteoftheallocatedspacecallocAllocatesspaceforanarrayofelements,initializesthemtozeroandthenreturnsapointertothememoryfreeFreespreviouslyallocatedspacereallocModifiesthesizeofpreviouslyallocatedspace2023/2/19.10.1Useofmalloc()Themallocfunctionreservesablockofmemoryofspecifiedsizeandreturnsapointeroftypevoid:void*malloc(size_tsize);void*meanspointerofanytype.size_tisdefinedinstdlib.h,andsizemeansthebytesizeofmemorytobeallocated.2023/2/19.10.1Useofmalloc()Wecanusemalloclikethefollowing:ptr=(cast-type*)malloc(byte-size);ptrisapointerofcast-type;(cast-type*)isusedfortypeconversion,i.e.convertthevoid*topointerofsomespecifictype;byte-sizeshowshowmanybytestobeallocated.Example:str=(char*)malloc(5);.str2023/2/19.10.1Useofmalloc()Wecanusemalloclikethefollowing:ptr=(cast-type*)malloc(byte-size);ptrisapointerofcast-type;(cast-type*)isusedfortypeconversion,i.e.convertthevoid*topointerofsomespecifictype;byte-sizeshowshowmanybytestobeallocated.Example:str=(char*)malloc(5);.strNotethatthestoragespaceallocateddynamicallyhasnonameandthereforeitscontentscanbeaccessedonlythroughapointer.2023/2/19.10.1Useofmalloc()mallocalsocanbeusedtoallocatespaceforcomplexdatatypessuchasstructures.Example:st_var=(structstudent*)malloc(sizeof(structstudent));2023/2/19.10.1Useofmalloc()RememberThemallocallocatesablockofcontiguousbytes.Theallocationcanfailifthespaceisnotsufficienttosatisfytherequest.Ifitfails,itreturnsaNULL.Weshouldcheckwhethertheallocationissuccessfulbeforeusingthememorypointer.2023/2/19.10.2Useofcalloc()callocisnormallyusedforrequestingmemoryspaceatruntimeforstoringderiveddatatypes,suchasstructures.void*calloc(unsignednum,unsignedsize)Allocatescontiguousspacefornumblocks,eachofsizebytes.Ifthereisnotenoughspace,aNULLpointerisreturned.2023/2/19.10.2Useofcalloc()Thesegmentofaprogramallocatesspaceforastructurevariable:typedefstructstudent{ charname[25]; floatage; longintid_num;}STD;STD*st_ptr;intclass_size=30;st_ptr=(STD*)calloc(class_size,sizeof(STD));…2023/2/19.10.3Useoffree()Whenwenolongerneedtousethatblockforstoringotherinformation,wemayreleasethatblockofmemory.Thisisdonebyusingthefree

function:voidfree(void*ptr)Example:free(st_ptr);2023/2/19.10.3Useoffree()Remember:Itisnotthepointerthatisbeingreleasedbutratherwhatitpointsto.Toreleaseanarrayofmemorythatwasallocatedbycallocweneedonlytoreleasethepointeronce.Itisanerrortoattempttoreleaseelementsindividually.2023/2/1举例:要分配1个char型数据单元char*p;p=(char*)malloc(1);if(p!=NULL){ *p=getch(); printf(“%c”,*p);

free(p);}2023/2/1要分配10个int型数组int*p;intk;p=(int*)malloc(10*sizeof(int));if(p!=NULL){ for(k=0;k<10;k++) p[k]=k+1;}free(p);2023/2/1一维动态数组

#include<stdlib.h>main(){ int*p=NULL,n,i; printf("Pleaseenterarraysize:"); scanf("%d",&n);

p=(int*)malloc(n*sizeof(int));

if(p==NULL) { printf("Noenoughmemory!\n"); exit(0); } printf("Pleaseenterthescore:"); for(i=0;i<n;i++) { scanf("%d",p+i); }

for(i=0;i<n;i++) { printf(“%d”,*(p+i)); }

free(p);

}2023/2/19.10.4Useofrealloc()Theprocessofchangingthememorysizealreadyallocatediscalledthereallocation

ofmemory.Wecanusethefunctionrealloctorealizereallocation.void*realloc(void*block,size_tsize)Example:

iftheoriginalallocationisdonebythestatement:ptr=malloc(size);Thereallocationofspacemaybedonebythestatement:ptr=realloc(ptr,newsize);2023/2/19.10.4Useofrealloc()Thisfunctionallocatesanewmemoryspaceofsizenewsizetothepointervariableptr.Thenewmemoryblockmayormaynotbeginatthesameplaceastheoldone.Ifthefunctionisunsuccessfulinlocatingadditionalspace,itreturnsaNULLpointerandtheoriginalblockisfreed.2023/2/1#include<stdio.h>#include<stdlib.h>voidmain(){ char*p=(char*)malloc(1000); char*q=(char*)realloc(p,5000); printf("%x\n",p); printf("%x\n",q);}2023/2/1PointersinstructuresPointerscanalsoappearinstructures.Considerthefollowingcode: structinventory{

char*name; intnumber; floatprice; }product[2];Inthestructuretypeinventory,weusecharacterpointernametooperatethenameofoneproduct.2023/2/1LinkedlistsThestructuremaycontainmorethanoneitemwithdifferentdatatypes.Especially,oneoftheitemsmustbeapointerofthetypeofitsown.Example:

structlink_list { floatage;

structlink_list*next; };2023/2/1LinkedlistsThen,wecandefinetwovariablesoftypelink_list:structlink_listnode1,node2;Thisstatementcreatesspacefortwonodeseachcontainingtowemptyfieldsasshown:node1node2node1.agenode1.nextnode2.agenode2.next2023/2/1LinkedlistsSequentially,ifwewritethebelowassignmentstatement:node1.next=&node2;

thenwecanestablisheda“link”betweennode1andnode2asshown:node1node2node1.agenode1.nextnode2.agenode2.next2023/2/1LinkedlistsWemaycontinuethisprocesstocreatealikedlistofanynumberofvalues.Everylistmusthaveanend.ChasspecialpointervaluecalledNULLthatcanbestoredinthenextfieldofthelastnode.NULLnode1node2node1.agenode1.nextnode2.agenode2.next2023/2/1LinkedlistAlinkedlistisdynamicdatastructure.Therearesomeadvantagesoflinkedlistoverarrays:Theprimaryoneisthatlinkedlistscangroworshrinkinsizeduringtheexecutionofaprogram.Anotheristhatalinkedlistdoesnotwastememoryspace.Thethird,andthemoreimportantadvantageisthatthelinkedlistsprovideflexibilityisallowingtheitemstoberearrangedefficiently.2023/2/1LinkedlistThemajorlimitationoflinkedlistsisthattheaccesstoanyarbitraryitemislittlecumbersomeandtimeconsuming.ANULL1249BNULL1356CNULL1475DNULL1021NULLhead1249135614751021headnodeNote:alinkedlistisadiscretestructure,wecanonlyfindsomenodebythenodebeforeit.2023/2/1OperationsonlinkedlistWecantreatalinkedlistasanabstractdatatypeandperformthefollowingbasicoperations:CreatingalistTraversingthelist(includingcountingtheitemsinthelist,printingthelist,lookingupanitemforeditingorprinting)InsertinganitemDeletinganitemConcatenatingtwolists2023/2/1CreatingalinkedlistWeuseapointerheadtocreateandaccessanonymousnodes.typedefstructlinked_list{ intnum; structlinked_list*next;}node;node*head=NULL;2023/2/1CreatingalinkedlistHeadindicatesthebeginningofthelinkedlist.Thefollowingstatementsstorevaluesinthememberfields:p->num=10;p->next=NULL;headnodenumnext10NULLp2023/2/1CreatingalinkedlistThesecondnodecanbeaddedasfollows:p->next=(node*)malloc(sizeof(node));p->next->num=20;p->next->next=NULL;Thepointercanbemovedfromthecurrentnodetothenextnodebyaself-replacementstatementsuchas:p=p->next;pnumnext10numnext20NULLhead2023/2/1Creatingalinkedlistnode*create(void){intn=0,num;node*head=NULL,*p1,*p2;printf("Inputanitem:"); scanf("%d",&num); while(num!=0){n++;p1=(node*)malloc(sizeof(node));p1->num=num; p1->next=NULL;if(n==1) head=p1;else p2->next=p1;p2=p1;printf("Inputanitem:"); scanf("%d",&num); }return(head);}2023/2/1TraversingalinkedlistWecanusealooptotraversealinkedlistonenodebyonenode,ortherecursion.//countingthenumberofitemsinthelistintcount(node*head){ node*p=head; if(!p) return(0); else return(1+count(p->next));}2023/2/1Traversingalinkedlist//printingitemsinthelistvoidprint(node*head){ node*p; p=head; if(head!=NULL){ do{ printf("No.%d\n",p->num); p=p->next; }while(p!=NULL); }else printf("Thelistisempty!\n");}2023/2/1Traversingalinkedlist

//lookingupsomeiteminthelistnode*search(node*head,intnum){node*p=head;if(head!=NULL){ do{ if(p->num==num){ printf("No.%disfound.\n",num); returnp; }else p=p->next; }while(p!=NULL); printf("No.%disnotfound.\n",num);}else printf("Thequeueisempty.\n");returnNULL;}2023/2/1InsertinganitemInsertinganewitem,sayX,intothelisthasthreesituation:Insertionatthefrontofthelist.Insertionattheendofthelist.Insertionbetweentwonodesofthelist.2023/2/1InsertinganitemInsertingatthefrontofthelist:Setthenextfieldofthenewnodetopointtothestartofthelist.Changetheheadpointertopointtothenewnode.headnodenumnext10Xnumnext5NULL2023/2/1InsertinganitemInsertingattheendofthelist:Setthenextfieldofthelastnodetopointtothenewnode.headnodenumnext10Xnumnext5NULLNULL2023/2/1InsertinganitemInsertingbetweentownodesinthelist(supposethetwonodesisn1andn2):SetthenextfieldofXtopointtonoden2.Setthenextfieldofn1topointtoX.n1numnext10Xnumnext5NULLn2numnext3NULL2023/2/1Insertinganelement//insertanitemattheheadofthelistnode*insert(node*head,node*newnode){ node*p0=newnode,*p1=head; if(head==NULL){ head=p0; p0->next=NULL; }else{ p0->next=p1; head=p0; } returnhead;}2023/2/1Insertinganelement//insertaniteminordernode*insertInOrder(node*head,node*newnode){node*p1=head,*p2=head;if(!head){head=newnode;//链表为空，head为插入的节点

}else{//设链表按升序排列

while(p1){ if(p1->num<=newnode->num){ p2=p1;p1=p1->next; }elsebreak; }//该循环找到新节点需要插入的位置

newnode->next=p1; p2->next=newnode;}returnhead;}2023/2/1Insertinganelement//insertsortingnode*sort(node*head){ node*newhead=NULL,*p=head,*q; while(