DS2数据结构课件

Chapter2Lists2.1Logicalstructureoflists2.1.1DefinitionofList2.1.2PointsofList2.1.3PopularoperationsforListDefinitionofListListisalimitedsequencewhichconsistsofseveraldataelementsinthesamedatatype.WewilldealwithagenerallistoftheformA1,A2,A3,…,AN.WesaythatthesizeofthislistisN.Wewillcallthespeciallistofsize0anemptylist.PointsofListForanylistexcepttheemptylist,wesaythatAi+1followsAi(i<N)andthatAi-1precedesAi(i>1).ThefirstelementofthelistisA1,andthelastelementisAN.WewillnotdefinethepredecessorofA1orthesuccessorofAN.ThepositionofelementAiinalistisi.PopularoperationsonListInit_List:createsanewemptylistPrint_List:printsallthedataelementinthelistMake_Empty:makesalistemptySize_List:returnsthenumberofdataelememtsinthelistGet_List(i):returnsadataelementinpositioniinthelist,1≤i≤NLocate_List(key):returnsthefirstoccurrenceofkeyInsert_List(x,i):insertssomexfrompositioniinthelist,1≤i≤N+1Delete_List(x,i):deletessomexfrompositioniinthelist,1≤i≤NExample2.1

Ifthelistis34,12,52,16,12Locate_List(12)Insert_List(X,3)Delete_List(4)mightreturn2mightmakethelistinto34,12,X,52,16,12mightmakethelistinto34,12,X,16,122.2SequenceList2.2.1DefinitionofSequenceList2.2.2PointsofSequentialStorage2.2.3BasicOperationsDefinitionofSequenceListSequentialstorageindicatesthateverydataelementsinalistisstoredorderlyinapieceofmemorywhoseunitshaveconsecutiveaddresses.ListsimplementedbythisstorageformarecalledSequenceList.Allofsequencelistcanbeimplementedjustbyusinganarray.Evenifthearrayisdynamicallyallocated,anestimateofmaximumsizeofthelistisrequired.Usuallythisrequiresahighoverestimate,whichwastesconsiderablespace.Wecancalculateanydataelements’positionbyaformulainsequencelist:LOC(ai)=LOC(a1)+(i-1)×L(1≤i≤n)LPointsofSequentialStorageWecanmakeuseofstoragepositionofdataelementstofiguretheirprecedingoroffspringlogicalrelation.Wecanquicklygetanydataelement’smemoryaddressthroughthegivenformula.Therefore,wecanconsiderbrieflythatthetimecostofaccessinganydataelementsinonelistisequal.ThisaccessmethodiscalledRandomAccess.Typedefinitionofsequencelisttypedefstruct{datatypedata[MAXSIZE];intlast;}SeqList;SeqList*L;//PointertoSeqlisttypea1L->data[0]or(*L).data[0]anL->data[L->last]or

(*L).data[(*L).last]nL->last+1or(*L).last+1

BasicOperations(1)Seqlist*Init_Seqlist(){Seqlist*L;L=(Seqlist*)malloc(sizeof(Seqlist));L->last=-1;returnL;}main(){Seqlist*L;L=Init_Seqlist();….}(2)InsertoperationSteps:a)Insertingatpositionirequiresithelementpushingtheentirearraydownonespottomakeroom.b)Insertinganewelementintopositioni.c)Modifyingthelastpointertomakesurepointingtothelastelement.

intInsert_Seqlist(Seqlist*L,inti,datatypex){intj;if(L->last==MAXSIZE-1){printf(“Listisfull.”);return(-1);}

//fullspace

if(i<1||i>L->last+2){printf(“Erroposition!”);return(0);}

//valueofiisillegal

for(j=L->last;j>=i-1;j--)

//normalinsertion

L->data[j+1]=L->data[j];L->data[i-1]=x;L->last++;return(1);}Insertionalgorithmanalysis:Theaverageunitsofmovingdataelements:pi:Theprobabilityofinsertingdatainpositioni.Forconvenience,wecanconsidertheprobleminequalprobabilitycondition.ci:Thetimesofmovingdatawheninsertingdatainpositioni.(3)DeleteoperationSteps:a)Deletingtheithelementrequiresshiftingalltheelementsinthelistupone.b)Modifyingthelastpointertomakesurepointingtothelastelement.

intDelete_Seqlist(Seqlist*L,inti){intj;if(i<1||i>L->last+1)

//checkemptylistandi’slegalvalue

{printf(“Theelementdoesn’texist.”);return(0);}for(j=i;j<=L->last;j++)

//normaldeletion

L->data[j-1]=L->data[j];L->last--;return(1);}Deletionalgorithmanalysis:Theaverageunitsofmovingdataelements:pi:Theprobabilityofinsertingdatainpositioni.Forconvenience,wecanconsidertheprobleminequalprobabilitycondition.ci:Thetimesofmovingdatawheninsertingdatainpositioni.However,insertionanddeletionareexpensive.TheworstcostoftheseoperationisO(N).Onaverage,halfofthelistneedstobemovedforeitheroperation.Becausetherunningtimeforinsertionsanddeletionsissoslowandthelistsizemustbeknowninadvance,simplearraysaregenerallynotusedtoimplementlists.(4)Locationoperation

intLocation_Seqlist(Seqlist*L,datatypex){inti=0;while(i<=L->last&&L->data[i]!=x)i++;if(i>L->last)return(-1);elsereturn(i);}2.3LinkedList2.3.1LinkedListInordertoavoidthelinearcostofinsertionanddeletion,weneedtoensurethatthelistisnotstoredcontiguously,sinceotherwiseentirepartsoflistwillneedtobemoved.ThegeneralideaofalinkedlistThelinkedlistconsistsofaseriesofstructures,whicharenotnecessarilyadjacentinmemory.Eachstructurecontainstheelementandapointertoastructurecontainingitssuccessor.DataPointerWecallthispointertheNextpointer;Thelastcell’sNextpointerpointstoNULL;ANSICspecifiesthatNULLiszero,thisvalueisdefinedtonotconfusedwithanotherpointer.…A1A2A3AN^1000800712992LTypedefinitionofLinkedListtypedefstructnode{datatypedata;structnode*next;}LNode;LNode*LinkList;

DeletionfromalinkedlistStep:(1)q=p->next;(2)p->next=q->next;(3)free(q);A1A2A3A4^p×qInsertionintoalinkedlistStep:(1)q->next=p->next;(2)p->next=q;A1A2A3A4^p×qXProgrammingDetailsThedescriptionaboveisactuallyenoughtogeteverythingworking,butthereareseveralplaceswhereareyoulikelytogowrong.

Thereisnoreallyobviouswaytoinsertatthefrontofthelistfromthedefinitionsgiven;Thecodemustbechanged:q->next=p->next;A1A2A3A4^pqXDeletingfromthefrontofthelistisaspecialcase,becauseitchangesthestartofthelist;carelesscodingwilllosethelist;Thewrongcode:free(L);Therightone:p=L;L=L->next;free(p);A1A2A3A4^L×pA1A2A3A4^pqAthirdproblemconcernsdeletioningeneral.Althoughthepointersmovesabovearesimple,thedeletionalgorithmrequiresustokeeptrackofthecellbeforetheonethatwewanttodelete.ImproveourlinkedlistItturnsoutthatonesimplechangesolvesallproblems.Wewillkeepasentinelnode,whichissometimesreferredtoasaheaderordummynode.…headerA2A3AN^L2.4CircularlyLinkedListApopularconventionistohavethelastcellkeepapointerbacktothefirst.Thiscanbedonewithorwithoutaheader(iftheheaderispresent,thelastcellpointstoit.)…headerA1A2ANLCreationofLinkedListMethodone:Insertingnodesintotheheadoftheemptylinked

list.…headerA1A2AN^sXLLinkListCreat_LinkList1(){LinkListL=NULL;LNode*s;intx;scanf(“%d”,&x);while(x!=flag){s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=L;L=s;scanf(“%d”,&x);}returnL;}CreationofLinkedListInsertingnodesintothetailofthelinked

list.…headerA1A2AN^LsX^r

LinkListCreat_LinkList(){LinkListL,s,r;intx;L=(LNode*)malloc(sizeof(LNode));L->next=NULL;r=L;scanf(“%d”,&x);while(x!=flag){s=(LNode*)malloc(sizeof(LNode));s->data=x;s->next=r->next;r->next=s;r=r->next;scanf(“%d”,&x);}

returnL;}(2)Getthelengthoflinkedlist

intLength_LinkList1(LinkListL){LNode*p=L->next;intj=0;while(p){p=p->next;j++;}returnj;}(3)Searchinthelinkedlistbynumber(Method1)

LNode*Get_LinkList(LinkListL,inti){LNode*p=L->next;intj=0;while(p->next!=NULL&&j<i){p=p->next;j++;}if(j==i)returnp;elsereturnNULL;}(3)Searchinthelinkedlistbyvalue(Method2)

LNode*Locate_LinkList(LinkListL,datatypex){LNode*p=L->next;while(p!=NULL&&p->data!=x)p=p->next;returnp;}(4)InsertionMethodOne:Insertingintonodesafterthegivennode.①q->next=p->next;②p->next=q;(4)InsertionMethodTwo:Insertingintonodesbeforethegivennode.

q=L;while(q->next!=p)q=q->next;s->next=q->next;q->next=s;q①p③②s(5)DeletionMethodOne:Deletesthegivennode’ssuccessor.①q=p->next;