數(shù)據(jù)結(jié)構(gòu)課件chap

Chapter02LinearList

第二章線性表Prof.QingWang2Prof.Q.Wang本章學(xué)習(xí)的線索主要線索重點(diǎn)順序存儲(chǔ)表示鏈?zhǔn)酱鎯?chǔ)表示難點(diǎn)鏈?zhǔn)酱鎯?chǔ)表示及實(shí)現(xiàn)一元多項(xiàng)式的表示和運(yùn)算線性結(jié)構(gòu)ADT順序存儲(chǔ)表示及實(shí)現(xiàn)鏈?zhǔn)酱鎯?chǔ)表示及實(shí)現(xiàn)應(yīng)用一元多項(xiàng)式3Prof.Q.WangContentsADTofLinearlistSequentiallistLinkedlistApplicationsofLinkedlist

RepresentationandoperationsofpolynomialsConclusion4Prof.Q.WangCharacteristicsofLinearstructure在數(shù)據(jù)元素的非空有限集中，（1）存在唯一的一個(gè)被稱為“第一個(gè)”的數(shù)據(jù)元素（2）存在唯一的一個(gè)被稱為“最后一個(gè)”的數(shù)據(jù)元素（3）除第一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)前驅(qū)(predecessor)（4）除最后一個(gè)之外，集合中的每個(gè)數(shù)據(jù)元素均只有一個(gè)后繼(successor)5Prof.Q.Wang2.1LinearListLinearlistisalsocalledlist,whichcontainszeroornelementsdenotedask0,,k1,…,kn-1(n≥1).Thenumberofelementiscalledthelengthofthelist.Ifthenumberiszero,thelistiscalled“emptylist”.Theelementisalsocalled“item”.“線性表”簡(jiǎn)稱為表，是零個(gè)或多個(gè)元素的有窮序列，通常可以表示成a0,a1,…,an-1(n≥1)。表中所含元素的個(gè)數(shù)稱為表的“長(zhǎng)度”。長(zhǎng)度為零的表稱為“空表”。表中的元素又稱“表目”。6Prof.Q.WangBasicfunctionsforLinearList1.Initialization(創(chuàng)建空線性表);2.Elementinsertion(在線性表中插入一個(gè)元素);3.Elementremoval(在線性表中刪除某個(gè)元素);4.Findoutthespecificelement(在線性表中查找某個(gè)特定元素);5.Findoutthesuccessorofthespecificelement(在線性表中查找某個(gè)元素的后繼元素);6.Findoutthepredecessorofthespecificelement(在線性表中查找某個(gè)元素的前驅(qū)元素);7.Judgethelistisemptyornot(判別一個(gè)線性表是否為空表)……7Prof.Q.WangADTofLinearListai,i=0,1,2,….n-1<ai,ai+1>CreateIsEmptyInsertRemoveLocateTraverseNextPrevious11Prof.Q.Wang#include<stdio.h>#include<alloc.h>/*符號(hào)常量*/#defineMAXNUM 100

/*線性表空間大小*/#defineFALSE 0#defineTRUE 1#defineSPECIAL 2147483647/*與DataType類型有關(guān)

32位機(jī)上的最大整數(shù)為231-1*/#definePI 3.1415926/*常用結(jié)構(gòu)*/typedefint DataType; /*定義數(shù)據(jù)類型為整型，也 可定義為其他類型*/typedefint ElemType; /*定義元素類型為整型，也 可定義為其他類型*/typedefint KeyType; 12Prof.Q.WangLogical&PhysicalformsLogicalform:LinearListPhysicalformSequentialList(ArrayorVector)LinkedLista0a1a2...…aiai+1…an-2an-1a0a1a2aian-1an-213Prof.Q.Wang2.2SequentialListThesequentiallistisstoredinthecontiguousstorage,alsocalledVector.Itisasimpleimplementationoflinearlist.Therelationshipoftheaddressesoftwoneighborelementsis: Locate(ai+1)=Locate(ai)+sizeof(DataType)Asaresult,theaddressofthei-thelementis: Locate(ai)=Locate(a0)+sizeof(DataType)*i

Details14Prof.Q.WangLogicaladdressDataelementMemoryaddressDataelementExample0a0Loc(a0)a00X00001a1Loc(a0)+ca10X0004…………0X0008iaiLoc(a0)+i*cai0X0020……0X0024n-1an-1Loc(a0)+(n-1)*can-10X007CSketchmapofSeqListinmemoryExample:n=128(0x80),c=4bytes,Address(a0)=0X000015Prof.Q.WangDefinitionofSeqListThenaivedeclarationofSeqListinCis:DataTypeelement[MAXNUM];intlength;這種定義的缺點(diǎn)在于沒有反映出element和length的內(nèi)在聯(lián)系：即沒有指出length是順序表element本身的屬性。在這個(gè)定義中，length和element完全處于獨(dú)立平等的地位，所以程序中完全可以將length作為一個(gè)自由變量來使用。Thinking…Asaresult,wedefineanewstructSeqListas,16Prof.Q.WangtypedefstructSeqList{ DataTypeelement[MAXNUM]; intlength; /*length<MAXNUM*/}SeqList;在實(shí)際應(yīng)用中，為了使用方便，通常定義一個(gè)structSeqList類型的指針類型和別名：

typedefstructSeqList*PSeqList; typedefstructSeqList SeqList;比較這兩種定義順序表的方法，后者概念較為清晰，符合數(shù)據(jù)抽象的原則，今后我們的定義一般采用后者。17Prof.Q.WangDeclarationofgenericfunctiontypefunctionName(parameterlist)intadd(inta,intb);intfind(int*a,intn,intx);18Prof.Q.WangDeclarationsofthebasicfunctionsofSequentialList:1.

intinsert_seq(PSeqListpalist,DataTypex,intp)在palist所指順序表中下標(biāo)為p的位置上插入一個(gè)值為x的元素，并返回插入成功與否的標(biāo)志。此運(yùn)算在0≤p≤palist->length時(shí)有意義。2.

intdelete_seq(PSeqListpalist,intp)在palist所指順序表中刪除下標(biāo)為p的元素，并返回刪除成功與否的標(biāo)志。此運(yùn)算在0≤p＜palist->length時(shí)有意義。3.

intfirst_seq(PSeqListpalist)求palist所指順序表中第一個(gè)元素的下標(biāo)。當(dāng)palist為空表時(shí)返回一個(gè)特殊的下標(biāo)值-1?！铩颕mpl.Impl.Impl.19Prof.Q.Wlocate_seq(PSeqListpalist,DataTypex)在palist所指順序表中尋找值為ｘ的元素的下標(biāo)，若palist中不存在值為ｘ的元素，則返回一個(gè)特殊的下標(biāo)值-1。5.DataTyperetrieve_seq(PSeqListpalist,intp)在palist所指順序表中，尋找下標(biāo)為p(0≤p＜palist->n)的元素，并將該元素的值作為函數(shù)值返回，若palist中無下標(biāo)為p的元素，則返回一個(gè)特殊的值。6.intnext_seq(PSeqListpalist,intp)求palist所指順序表中下標(biāo)為p的元素的后繼元素下標(biāo)，當(dāng)不存在下標(biāo)為p的元素或雖有該元素但無后繼時(shí)，返回一個(gè)特殊的下標(biāo)值-1?！颕mpl.Impl.Impl.20Prof.Q.Wprevious_seq(PSeqListpalist,intp,)求palist所指順序表中下標(biāo)為p的元素的前驅(qū)元素下標(biāo)，當(dāng)不存在下標(biāo)為p的元素，或雖有該元素但無前驅(qū)時(shí)，本函數(shù)返回一個(gè)特殊的下標(biāo)值-1。8.voidcreateNullList_seq(PSeqListpalist)置palist所指順序表為空表。9.intisNullList_seq(PSeqListpalist)判別palist所指順序表是否為空表。若為空則返回1，否則返回0。Impl.Impl.Impl.21Prof.Q.Wangintinsert_seq(PSeqListpalist,DataTypex,intp)/*在palist所指順序表中下標(biāo)為p的位置上插入元素x*/{ if(palist->length==MAXNUM) /*溢出*/ { printf("Overflow!\n"); return(FALSE); } if(p<0||p>palist->length)/*不存在下標(biāo)為p的元素*/ { printf("notexist!\n"); return(FALSE); }

/*將p及以后的元素后移一個(gè)下標(biāo)位置*/ for(intq=palist->length-1;q>=p;q--) palist->element[q+1]=palist->element[q]; palist->element[p]=x; /*在p下標(biāo)位置上放元素x*/ palist->length=palist->length+1; /*元素個(gè)數(shù)加１*/ return(TRUE);}Algorithm2.1Insertion★Demo22Prof.Q.WangAlgorithm2.2Deletionintdelete_seq(PSeqListpalist,intp)/*在palist所指順序表中刪除下標(biāo)為p的元素*/{ intq; if(p<0||p>palist->length–1)/*不存在下標(biāo)為p的元素*/ { printf("notexist!\n"); return(FALSE); }

/*將p以后的元素前移一個(gè)位置*/ for(q=p;q<palist->length-1;q++) palist->element[q]=palist->element[q+1]; palist->length=palist->length-1; /*元素個(gè)數(shù)減1*/ return(TRUE);};★23Prof.Q.Wangintfirst_seq(PSeqListpalist){ if(palist->length==0) return-1; else return0;}

intlocate_seq(PSeqListpalist,DataTypex)/*求x在palist所指順序表中的下標(biāo)位置*/{ for(intq=0;q<palist->length;q++) if(palist->element[q]==x) return(q); return(-1);}Algorithm2.3FindoutthepositionofthefirstelementAlgorithm2.4Locatethespecificelement★Goback24Prof.Q.WangDataTyperetrieve_seq(PSeqListpalist,intp)/*求palist所指順序表中第p個(gè)（即下標(biāo)為p-1）的元素的值*/{ /*存在下標(biāo)為p-1的元素*/ if(p>0&&p<=palist->length) return(palist->element[p-1]); printf("Notexist.\n"); return-1; /*返回一個(gè)順序表中沒有 的特殊元素值*/};Algorithm2.5Getthevalueofp-thelementinthepalistGoback25Prof.Q.Wangintnext_seq(PSeqListpalist,intp)//求palist所指順序表中下標(biāo)為p的元素的后繼元素的下標(biāo)位置{if((p>=0)&&(p<palist->length-1)) return(p+1);else return(-1);}Algorithm2.6GetthenextpositionofthecurrentpAlgorithm2.7Getthepriorpositionofthecurrentpintprevious_seq(PSeqListpalist,intp)//求palist所指順序表中下標(biāo)為p的元素的前驅(qū)元素的下標(biāo)位置{if(p>0&&p<palist->length)return(p-1);elsereturn(-1);}26Prof.Q.WangAlgorithm2.9JudgethelistisemptyornotAlgorithm2.8Setthelistempty//判別palist所指順序表是否為空表。若為空則返回1，否則返回0intisNullList_seq(PSeqListpalist){ return(palist->length==0);}//置palist所指順序表為空表voidcreateNullList_seq(PSeqListpalist){ palist->length=0;}27Prof.Q.Wang說明：上述算法在具體上機(jī)實(shí)現(xiàn)時(shí)，要將下面的類型說明、常量說明及類型定義包含在文件中。#defineMAXNUM100 /*線性表空間大小*/#defineFALSE0#defineTRUE1typedefintDataType; /*定義元素類型為整型 ，也可定義為其他類型*/#defineSPECIAL2147483647/*與DataType類型有關(guān)，32位機(jī)上的最大整數(shù)為231-1*/structSeqList{ DataTypeelement[MAXNUM]; intlength;};typedefstructSeqListSeqList,*PSeqList;28Prof.Q.WangComplexityAnalysis-SearchingIfsuccess AverageComparisonNumber(ACN)isIffailtosearchx(worstcase), Actualcomparisonnumberisn.29Prof.Q.WangAverageMovementNumber(AMN)isComplexityAnalysis-Insertionlengthlength30Prof.Q.WangAverageMovementNumber(AMN)isComplexityAnalysis-Deletionlengthlength31Prof.Q.WangAnyproblem?typedefstructSeqList{DataTypeelement[MAXNUM]; intlength; /*length<MAXNUM*/}SeqList;32Prof.Q.Wang以上的順序表的實(shí)現(xiàn)中，表的大小是固定不變的，但有時(shí)我們不能確定表的大小，這時(shí)就需要可變大小的順序表。于是我們可以如下定義并實(shí)現(xiàn)順序表：SequentiallistwithflexiblelengthtypedefstructSeqList{ DataType*elem;/*存儲(chǔ)元素連續(xù)空間的地址*/ intlength; /*表中元素的個(gè)數(shù)*/ intsize; /*表的大小*/}SeqList,*PSeqList;InitializationInsertionDeletionAnalysisApplication33Prof.Q.Wang/*Createanewblanklist*/voidInitList(PSeqListpList){ pList->elem= (ElemType*) malloc(InitSize*sizeof(ElemType)); /*Testwhetherallocationissuccessful*/ assert(pList->elem!=NULL); pList->size=InitSize; pList->length=0;} /*EndofInitList()*/InitializationofSeqListclicka0a1a2...…aiai+1…an-2an-1pList->elemInitSize34Prof.Q.WangStatusInsertElem(PSeqListpList,inti,ElemTypeelem){ int j,pos; ElemType *newElem; if(i<0||i>pList->length){ printf("Insertpositionerror!\n"); returnERROR; } /*Ifnoenoughspace,reallocmorespace*/ if(pList->length+1>pList->size){ newElem=(DataType*)realloc(pList->elem, (pList->size+Increment)*sizeof(DataType)); assert(newElem!=NULL); pList->elem=newElem; pList->size+=Increment; }reallocElementInsertioninSeqList35Prof.Q.WangStatusInsertElem(PSeqListpList,inti,ElemTypeelem){ … … … /*Movetheelememtswhichlocatebehindelement‘i’ apositionforward*/ for(j=pList->length;j>i;j--) pList->elem[j]=pList->elem[j-1]; pList->elem[i]=elem; ++pList->length; returnOK;} /*EndofInsertElem()*/ElementInsertioninSeqList(Cont’d)36Prof.Q.WangStatusDeleteElem(PSeqListpList,inti){ intj; if(i<0||i>=pList->length) { printf("Deletepositionerrorornoelements!\n"); returnERROR; } for(j=i;j<pList->length;j++) pList->elem[i]=pList->elem[i+1]; --pList->length; returnOK;} /*EndofDeleteElem()*/ItemRemoval/DeletionfromSeqList37Prof.Q.Wanga1,a2,…,ai…an,a1a2aianb1b2bibmb1,b2,…,bi…bm,biYNInsertGetanotheritemGetanitemPrinciple:SetUnion38Prof.Q.WangvoidUnion(SeqList*la,SeqList*lb){intm,n,i,k; floatx;n=la->length;m=lb->length;for(inti=1;i<=m;i++){ x=retrieve_seq(lb,i); //GetanitemxfromSetlb k=locate_seq(la,x); //SearchxinSetla if(k==-1) //ifnotfound,insertxintola{ insert_seq(la,x,n+1);n++;}}}Howabouttimecomplexity?Implementation:SetUnion39Prof.Q.Wanga1a2aianb1b2bibma1,a2,…,ai…an,aiNYGetanotheritemGetanitemRemovefromAPrinciple:SetIntersection40Prof.Q.WangvoidIntersection(SeqList*la,SeqList*lb){intm,n,i,k;n=la->length;m=lb->length;i=0;while(i<n){x=retrieve_seq(la,i); //GetanitemxfromSetla k=locate_seq(lb,x); //SearchxinSetlb if(k==-1) //ifnotfound,deletexfromla{ delete_seq(la,i);n--; } else i++;

}Howabouttimecomplexity?Implementation:SetIntersection41Prof.Q.WangSortedlistsmergingMergetwosortedlistsintoanewlistandthenewoneisalsosortedasbefore.LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)LC=(2,3,5,6,8,8,9,11,11,15,20)MergeijkDemoHowabouttimecomplexity?42Prof.Q.WangImplementation：SortedlistsmergingvoidMergeSqList(SeqList*la,SeqList*lb,SeqList*lc){inti=0,j=0,k=0;m=la->length;n=lb->length;lc->length=0;while(i<m&&j<n){x=retrieve_seq(la,i); //Getanitemxfromlay=retrieve_seq(lb,j); //Getanitemyfromlb

if(x<=y){Insert_Seq(lc,x,k);i++;k++; //Insertxintolc}else{Insert_Seq(lc,y,k);j++;k++; //Insertyintolc}}

while(i<m){x=retrieve_seq(la,i);Insert_Seq(lc,x,k);i++;k++;}while(j<n){y=retrieve_seq(lb,j);Insert_Seq(lc,y,k);j++;k++;}}對(duì)比分析43Prof.Q.WangAssignment（1）P7 1.1,1.4,1.6,1.19,1.20P162.11,2.21,2.29returnAnyquestion?QuestionArray==Sequentiallist?44Prof.Q.WangPointerQuestion:AdvantagesanddisadvantagesofSeqandLinkedlist?結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映象，由數(shù)據(jù)域和指針域構(gòu)成。DataAddressDataPointer1 Li 437 Qian 1313 Sun 1 19 Wang 0(NULL)25 Wu 3731 Zhao 737 Zheng1943 Zhou 2531HeadpointerH1.Definition2.3.1SingleLinkedList(S-Linkedlist)2.3LinkedListLiZhaoQianSunZhouWuZhengWangHeadHStructureofS-Linkedlist46Prof.Q.WangMemorymapofSingleLinkedlistSinglylinkedlist47Prof.Q.Wanga1a2...HeadHHeadnodeHNon-emptylistEmptylistan48Prof.Q.WangtypedefintDataType; /*定義元素類型為整型，也可定義為其他類型*/structNode

/*單鏈表結(jié)點(diǎn)結(jié)構(gòu)*/{ DataType info; structNode *next;};typedefstructNodeNode,*PNode; /*結(jié)點(diǎn)指針類型*/structLinkList

/*單鏈表類型定義*/{ PNodehead; /*指向單鏈表中的第一個(gè)結(jié)點(diǎn)*/};typedefstructLinkListLinkList,*PLinkList; /*單鏈表類型的指針類型*/PLinkListpllist; /*pllist是指向單鏈表的一個(gè)指針變量*/DefinitionofS-Linkedlist49Prof.Q.Wang1.

voidinsert_link(DataTypex,PNodep)在單鏈表中p位置的后面插入元素x。2.voiddelete_link(PLinkListpllist,DataTypex)在pllist所指的單鏈表中刪除一個(gè)元素為x的結(jié)點(diǎn)。3.

PNodefirst_link(PLinkListpllist)在pllist所指的單鏈表中求第一個(gè)結(jié)點(diǎn)的位置。4.

PNodelocate_link(PLinkListpllist,DataTypex)在pllist所指的單鏈表中求元素為x的結(jié)點(diǎn)位置。5.DataTyperetrieve_link(PNodep)在pllist所指的單鏈表中求p位置上的元素。BasicfunctionsofS-LinkedlistPrin.Prin.Impl.Impl.Impl.Impl.Impl.★★★50Prof.Q.Wang6.

PNodenext_link(PNodep)在pllist所指的單鏈表中求p位置的后繼元素的位置。7.PNodeprevious_link(PLinkListpllist,DataTypex)在pllist所指的單鏈表中求元素為x的結(jié)點(diǎn)的前驅(qū)元素的位置。8.

PLinkListcreateNullList_link(void)創(chuàng)建空鏈表。9.

intisNullList_link(PLinkListpllist)判斷pllist所指的單鏈表是否是空鏈表。10.PNodefind_link(PLinkListpllist,inti)在pllist所指的單鏈表中求第i(i>0)個(gè)結(jié)點(diǎn)的位置。Impl.Impl.Impl.Impl.Impl.★51Prof.Q.Wangvoidinsert_link(PLinkListpList,DataTypex,PNodep)/*在單鏈表中p所指結(jié)點(diǎn)的后面插入元素x*/{ PNode q; q=(PNode)malloc(sizeof(structNode)); if(q==NULL) printf("Outofspace!!!\n"); else{ q->info=x; q->next=p->next; p->next=q; }}Algorithm2.10ElementinsertioninS-Linkedlist52Prof.Q.Wangvoiddelete_link(PLinkListpllist,DataTypex)/*在pllist所指的帶有頭結(jié)點(diǎn)的單鏈表中刪除元素為x的結(jié)點(diǎn)*/{ PNode p,q; p=pllist->head; /*在pllist所指的帶有頭結(jié)點(diǎn)的單鏈表中找元素為x的結(jié)點(diǎn) 的前驅(qū)結(jié)點(diǎn)位置*/ while(p->next!=NULL&&p->next->info!=x) p=p->next; if(p->next==NULL) /*沒找到元素為x的結(jié)點(diǎn)*/ printf("Notexist!\n"); else{ q=p->next; /*找到元素為x的結(jié)點(diǎn)*/ p->next=q->next; free(q); }}Algorithm2.11RemovalfromS-Linkedlist53Prof.Q.WangPNodefirst_link(PLinkListpllist)/*在pllist所指的帶有頭結(jié)點(diǎn)的單鏈表中求第一個(gè)結(jié)點(diǎn)的位置*/{ returnpllist->head->next;}Algorithm2.13LocateelementinS-LinkedlistAlgorithm2.12FindthepositionofthefirstelementPNodelocate_link(PLinkListpllist,DataTypex)/*在pllist所指的帶有頭結(jié)點(diǎn)的單鏈表中找元素為x的結(jié)點(diǎn)位置*/{ PNode p; p=pllist->head->next; while(p!=NULL&&p->info!=x) p=p->next; returnp;}54Prof.Q.WangDataTyperetrieve_link(PNodep){ returnp->info;}Algorithm2.15GetthepointerofthepriorelementAlgorithm2.14GetthevalueofnodepPNodeprevious_link(PLinkListpllist,DataTypex)/*在pllist所指的帶有頭結(jié)點(diǎn)的單鏈表中找元素為x的結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)位置*/{ PNode p; p=pllist->head; while(p->next!=NULL&&p->next->info!=x) p=p->next; if(p==pllist->head||p->next==NULL)/*x是第一個(gè)結(jié)點(diǎn)的值或者不存在值為x的結(jié)點(diǎn)*/ returnNULL; else returnp;}55Prof.Q.WangPLinkListcreateNullList_link(void)/*創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空鏈表*/{ PLinkList pllist; PNode p; pllist=(PLinkList)malloc(sizeof(structLinkList)); if(pllist!=NULL){ p=(PNode)malloc(sizeof(structNode)); if(p!=NULL){ pllist->head=p; p->next=NULL; } else{ printf("Outofspace!\n"); pllist->head=NULL; } } elseprintf("Outofspace!\n");

returnpllist;}Algorithm2.17InitializationStep1:Step2:Step3:56Prof.Q.WangInitializationProcedureofS-LinkedlistMemorypllist的內(nèi)容head的內(nèi)容plliststructNode /*單鏈表結(jié)點(diǎn)結(jié)構(gòu)*/{ DataType info; structNode *next;};typedefstructNode*PNode; /*結(jié)點(diǎn)指針類型*/structLinkList /*單鏈表類型定義*/{ PNodehead; /*指向單鏈表中的第一個(gè)結(jié)點(diǎn)*/};infonextheadpllist->head57Prof.Q.WangPNodenext_link(PNodep){ if(p!=NULL) returnp->next; else returnNULL;}Algorithm2.16GetthepointerofthenextelementAlgorithm2.18JudgealinkedlistisemptyornotintisNullLink_link(PLinkListpllist)/*判斷pllist所指的帶有頭結(jié)點(diǎn)的單鏈表是否是空鏈表*/{ returnpllist->head->next==NULL;}58Prof.Q.WangPNodefind_link(PLinkListpllist,inti)/*在帶有頭結(jié)點(diǎn)的單鏈表pllist中求第i個(gè)結(jié)點(diǎn)的位置*//*當(dāng)表中無第i個(gè)元素時(shí)，返回值為NULL*/{ PNode p; int j; if(i<1){ printf("Thevalueofi=%disnotreasonable.\n",i); returnNULL; } p=pllist->head; for(j=0;j<i;j++){ p=p->next; if(p==NULL) returnNULL; } returnp;}Algorithm2.19Getthepointerofthei-thelement59Prof.Q.WangabpSingleLinkedlistOperations:q->next=p->next;p->next=q;Remark：順序不能反abxqpNodeinsertionprincipleandexample60Prof.Q.WangabpcOperation:p->next=p->next->next;NoderemovalprincipleandexampleabpcSingleLinkedlist61Prof.Q.WangMergetwosortedlinkedlist(withheadnode)LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)11358

9

268

111520LALBLC=(2,3,5,6,8,8,9,11,11,15,20)LC?62Prof.Q.Wang11358

9

268

111520LALBLCResult63Prof.Q.WangvoidMergeList_L(LinkListla,LinkListlb,PLinkListlc){ PNode pa,pb,pc; pa=la.head; pb=lb.head; lc->head=pc=pa; while(pa&&pb){ if(pa->info<=pb->info){ pc->link=pa;pc=pa;pa=pa->link; } else{ pc->link=pb;pc=pb;pb=pb->link; } } pc->link=pa?pa:pb;}Mergingtwosortedlinkedlists(withheadnode)對(duì)比分析64Prof.Q.Wang單鏈表與順序表的比較：(1)單鏈表是一種松耦合的線性結(jié)構(gòu)，順序表是緊耦合的。(2)單鏈表的存儲(chǔ)密度比順序表低，它多占用了存儲(chǔ)空間。但在許多情況下，鏈?zhǔn)降姆峙浔软樞蚍峙溆行?，順序表必須分配足夠大的連續(xù)存儲(chǔ)空間，而鏈表可以利用零星的存儲(chǔ)單元。(3)在單鏈表里進(jìn)行插入、刪除運(yùn)算比在順序表里容易得多。(4)對(duì)于順序表，可隨機(jī)訪問任一個(gè)元素，而在單鏈表中，需要順著鏈逐個(gè)進(jìn)行順序訪問，因此單鏈表適合于在成批、順序處理線性表中的元素時(shí)采用。ComplexityAnalysisofS-Linkedlist65Prof.Q.Wang#defineMaxSize 1000 /*Themaxlengthofthelinklist*/typedefstruct{ DataType data; int cursor;}Component,SLinkList[MaxSize];voidInitList(SLinkListlist); /*use'0'todeputeblankpointer*//*Allocmemory,returnthesubscriptionoftheallocatednode,ifnospaceavailable,return0*/intMalloc(SLinkListlist);/*Retractthespacewhichsubscriptionis'k'*/voidFree(SLinkListlist,intk);2.3.2StaticlinkedlistCircularList66Prof.Q.Wang012345678910123456780ZhaoQianSunLiZhouWuZhengWang0123456789101234968805ZhaoQianSunLiZhouWuZhengWangShiExampleofstaticlinkedlistBeforemodificationAftermodification在Li后插入Shi0123456789101234967805ZhaoQianSunLiZhouWuZhengWangShiAftermodification刪除ZhengCircularList67Prof.Q.WangvoidInitList(SLinkListlist){ inti; for(i=0;i<MaxSize-1;i++) list[i].cursor=i+1; list[MaxSize-1].cursor=0;} /*EndofInitList()*/ImplementationofStaticlinkedlist012345678910123456789100CircularList68Prof.Q.Wang012345678910Zhao012345678910ZhaoQianSunLiZhouWuZhengWang103456789100123456780100012345678910ZhaoQianSunLiZhouWuZhengWangShi92349678050510012345678910ZhaoQianSunLiZhouWuZhengWang

Shi923496880507插入Shi刪除ZhengCircularListImplementationofStaticlinkedlist69Prof.Q.Wang將整個(gè)數(shù)組空間初始化成一個(gè)鏈表；InitList(…)從備用空間取得一個(gè)結(jié)點(diǎn)；Malloc(…)將空閑結(jié)點(diǎn)連接到備用鏈表上；Free(…)Example：集合運(yùn)算voidInitList(SLinkListlist){ inti; for(i=0;i<MaxSize-1;i++) list[i].cursor=i+1; list[MaxSize-1].cursor=0;} /*EndofInitList()*/假設(shè)由終端輸入集合元素，先建立表示集合A的靜態(tài)鏈表S，而后在輸入集合B的元素的同時(shí)查找S表，若存在和B相同的元素，則從S表中刪除之，否則將此元素插入S表。CircularList70Prof.Q.WangintMalloc(SLinkListlist){/*Alwaysreturnthefirstavailableunit*/ inti; i=list[0].cursor; if(list[0].cursor!=0) list[0].cursor=list[i].cursor; returni;} /*EndofMalloc()*//*Inserttherecyclespaceintothefirstplaceofthelist*/voidFree(SLinkListlist,intk){ list[k].cursor=list[0].cursor; list[0].cursor=k;} /*EndofFree()*/71Prof.Q.Wangintdifference(SLinkListlist,int*S){/*依次輸入集合A和B的元素在一維數(shù)組list中建立表示結(jié)果集合的靜態(tài)鏈表，S為其頭指針*/ InitList(list); S=Malloc(list); r=S; scanf(m,n); for(j=1;j<=m,j++){ i=Malloc(list); scanf(list[i].data); list[r].cursor=i;r=i; }//for list[r].cursor=0; … …0123456789101234567891000123456789108234567091001ScbegfdA={cbegfd}B={abnf}AvailablememoryInputSetA頭指針可用內(nèi)存頭指針72Prof.Q.Wang … for(j=1;j<=n,j++){ scanf(b);p=S;k=list[S].cursor; while(k!=list[r].cursor&&list[k].data!=b){//search p=k;k=list[k].cursor; } if(k==list[r].cursor){ //插入

i=Malloc(list); list[i].data=b;list[i].cursor=list[r].cursor; list[r].cursor=i; } //if else{ //刪除

list[p],cursor=list[k].cursor; Free(list,k); if(r==k)r=p; } //else } //for} //difference73Prof.Q.WangA={cbegfd}B={abnf}0123456789108234567091001Scbegfd0123456789109234567801001Scbegfda0123456789103249567801001Scbegfda389474Prof.Q.WangA={cbegfd}B={abnf}0123456789109248567301001Scnegfda33980123456789106248579301001Scnegfda87675Prof.Q.Wang循環(huán)條件：pNode==pList->head表空條件：pList->head->next==pList->head操作與線性鏈表基本一致。2.3.3CircularS-LinkedlistheadheadheadDiscussion：howtoconcattwocircularlinkedlists?76Prof.Q.WangABBAa1anb1bma1anb1bm77Prof.Q.WangAdvantage:easytoaccessbothpredecessorandsuccessor.2.3.4DoublyLinkedListtypedefstructDoubleNode /*Nodedefinition*/{ DataType info; structDoubleNode *llink,*rlink;}DoubleNode,*PDoubleNode;typedefstructDoubleList /*雙向鏈表類型*/{ PDoubleNodehead; /*指向第一個(gè)結(jié)點(diǎn)*/ PDoubleNodetail; /*指向最后一個(gè)結(jié)點(diǎn)*/};PDoubleListpdlist; /*pdlist是指向雙鏈表類型的 指針變量*/llinkinforlink78Prof.Q.WangNon-emptylist

EmptylistRelationshipofrightandleftpointersp==

p→lLink→rLink==p→rLink→lLinkheadhead79Prof.Q.Wang①

s->llink=p->llink;②

p->llink->rlink=s;③

s->rlink=p;④

p->llink=s;ABCspInsertionforD-Linkedlists->rlink=p->rlink;p->rlink->llink=s;s->llink=p;p->rlink=s;ABCsp①②③④Principle80Prof.Q.Wangvoidinsert_dbllink(PDoubleListpdlist,inti,DataTypex)/*在帶有頭結(jié)點(diǎn)的雙鏈表pllist中求第i個(gè)位置前插入元素x*/{ PDoubleNode p; if(!(p=GetData_dbllink(pdlist,i))) printf(“Outofrange!\n”); else { PDoubleNode s; s=(PDoubleNode)malloc(sizeof(DoubleNode)); if(s==NULL) printf("Outofspace!!!\n"); else{ s->info=x; s->llink=p->llink; p->llink->rlink=s; s->rlink=p; p->llink=s; } }}Implementationofinsertion81Prof.Q.Wangp->llink->rlink=p->rlinkp->rlink->llink=p->llinkABCpDeletionforD-LinkedlistPrinciple82Prof.Q.Wangvoiddelete_dbllink(PDoubleListpdlist,inti)/*刪除帶頭結(jié)點(diǎn)的雙鏈表pllist中的第i個(gè)元素*/{ PDoubleNode p; if(!(p=GetData_dbllink(pdlist,i))) printf(“Outofrange!\n”); else { p->llink->rlink=p->rlink; p->rlink->llink=p->llink; free(p); }}Implementationofdeletion83Prof.Q.WangSuccessFailureheadheadSearchinginD-Linkedlist84Prof.Q.WangQuickreviewSinglylinkedlistHeadpointer(tailpointer,length)DeclarationImplementationStaticlinkedlistCircularlinkedlistDoublylinkedlist85Prof.Q.Wang2.4Application:JosephusProblem設(shè)有n個(gè)人圍坐在一個(gè)圓桌周圍，現(xiàn)從第1個(gè)人開始報(bào)數(shù)，數(shù)到第m的人出列，然后從出列的下一個(gè)人重新開始報(bào)數(shù)，數(shù)到第m的人又出列，…，如此反復(fù)直到所有的人全部出列為止。Josephus問題是：對(duì)于任意給定的n和m，求出按出列次序得到的n個(gè)人員的序列?，F(xiàn)以n=8，m=3為例，問題的求解過程如圖2-10所示。圖中箭頭指向開始報(bào)數(shù)位置，斜劃線的是本次應(yīng)該出列的人員。若初始的順序?yàn)?，2，3，4，5，6，7，8，則問題的解為3，6，1，5，2，8，4，7。86Prof.Q.WangJosephusProblem4787Prof.Q.Wang2.4.1順序表表示步驟：1.建立順序表2.出列2.4.2循環(huán)鏈表表示1.建立循環(huán)單鏈表2.尋找第s個(gè)結(jié)點(diǎn)，輸出并刪除第m個(gè)節(jié)點(diǎn)。88Prof.Q.Wang#include“CircList.h”Template<Type>voidCircList<Type>::Josephus(int

n,intm){

First();

for(int

i=0;

i<n-1;

i++){

for(int

j=0;

j<m-1;

j++)Next();

cout<<“Theoutoneis”<<

getData

()<<endl;

Remove();}}void

main(){

CircList<int>clist;

int

n,m;

cout<<“Inputthenumberofpeopleandtheinterval”;

cin>>n>>m;

for(int

i=1;

i<=n;

i++)

clist.insert(i);//ConstructJosephcircle

clist.Josephus(n,m); //CallJosephfunction}89Prof.Q.WangPn(x)=p0+p1x+p2x2++pnxn在計(jì)算機(jī)中可以用一個(gè)線性表P來表示：P=(p0,p1,p2,,pn)每一項(xiàng)的指數(shù)都隱含在系數(shù)pi的序號(hào)里。2.5RepresentationandoperationsofPolynomialAdvantageanddisadvantage?90Prof.Q.Wang這種表示方法對(duì)于所有項(xiàng)都比較全的時(shí)候是很好的，但是如果指數(shù)很高并且變化很大時(shí)，這種表示方法就不合適了。這時(shí)我們可以把