數(shù)據(jù)結(jié)構(gòu)第2章

第2章線(xiàn)性表2.1線(xiàn)性表的概念及運(yùn)算2.2線(xiàn)性表的順序存儲(chǔ)2.3線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)2.4一元多項(xiàng)式的表示及相加2.1線(xiàn)性表的概念及運(yùn)算4.線(xiàn)性表的邏輯結(jié)構(gòu)1.線(xiàn)性表的定義一個(gè)線(xiàn)性表是具有n個(gè)數(shù)據(jù)元素的有限序列。記為(a1,…,ai-1,ai,ai+1,…,

an)2.線(xiàn)性表的長(zhǎng)度線(xiàn)性表中元素的個(gè)數(shù)n(n>=0),n=0時(shí),稱(chēng)為空表。3.位序ai是第i個(gè)元素，稱(chēng)i為數(shù)據(jù)元素ai在線(xiàn)性表中的位序

。例子：英文字母表(A,B,…,Z)；車(chē)輛登記表

。5.線(xiàn)性表的特點(diǎn)同一性：線(xiàn)性表由同類(lèi)數(shù)據(jù)元素組成，每一個(gè)ai必須屬于同一數(shù)據(jù)對(duì)象。有窮性：線(xiàn)性表由有限個(gè)數(shù)據(jù)元素組成，表長(zhǎng)度就是表中數(shù)據(jù)元素的個(gè)數(shù)。有序性：線(xiàn)性表中相鄰數(shù)據(jù)元素之間存在著序偶關(guān)系<ai,ai+1>。6.線(xiàn)性表的基本運(yùn)算

初始化InitList（&L）建立一個(gè)空表。求表長(zhǎng)ListLength（L）返回線(xiàn)性表的長(zhǎng)度。讀表元素GetElem（L,i,&e)用e返回L中第i個(gè)數(shù)據(jù)元素的值。定位LocateElem（L,e,compare()）返回滿(mǎn)足關(guān)系的數(shù)據(jù)元素的位序。插入ListInsert（&L,i,e）在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，線(xiàn)性表的長(zhǎng)度增1。刪除ListDelete（&L,i,&e）刪除L的第i個(gè)位置上的數(shù)據(jù)元素e，線(xiàn)性表的長(zhǎng)度減1。輸出ListDisplay（L）按前后次序輸出線(xiàn)性表的所有元素。練習(xí)1：兩個(gè)線(xiàn)性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)求一個(gè)新的集合A=A∪B。voidunion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);if(!LocateElem(La,e,equal))ListInsert(La,++La_len,e);}}O(ListLength(La)×ListLength(Lb))練習(xí)2：

兩個(gè)線(xiàn)性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)將LA和LB歸并為一個(gè)新的線(xiàn)性表，LC中的數(shù)據(jù)元素仍按值非遞減有序排列。

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)voidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);La_len=ListLength(La);Lb_len=ListLength(Lb);i=j=1;k=0;while((i<=La_len)&&(j<=Lb_len)){GetElem(La,i,a);GetElem(Lb,j,b);if(a<=b){ListInsert(Lc,++k,a);++i;}else{ListInsert(Lc,++k,b);++j;}}while(i<=La_len){GetElem(La,i++,a);ListInsert(Lc,++k,a);}while(j<=Lb_len){GetElem(Lb,j++,b);ListInsert(Lc,++k,b);}}O(ListLength(La)+ListLength(Lb))例，La=(3,5,8)Lb=(2,6,8,9,15)構(gòu)造Lc=(2,3,5,6,8,8,9,15)358La268Lb915Lcij2首先，La_len=3；Lb_len=5；3ijij5ij6ij88jij9j15j算法結(jié)束！2.2線(xiàn)性表的順序表示和實(shí)現(xiàn)順序表：

按順序存儲(chǔ)方式構(gòu)造的線(xiàn)性表。

假設(shè)線(xiàn)性表中有n個(gè)元素，每個(gè)元素占k個(gè)單元，第一個(gè)元素的地址為loc(a1)，則可以通過(guò)如下公式計(jì)算出第i個(gè)元素的地址loc(ai)：

loc(ai)=loc(a1)+(i-1)×k其中l(wèi)oc(a1)稱(chēng)為基地址。2.順序表的特點(diǎn)：邏輯結(jié)構(gòu)中相鄰的數(shù)據(jù)元素在存儲(chǔ)結(jié)構(gòu)中仍然相鄰。線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。3.順序表的描述：typedefstruct{ElemType*elem；

int length;//當(dāng)前長(zhǎng)度

intlistsize;//分配的存儲(chǔ)容量

}SqList；

//ElemTypeelem[MAXSIZE];typedef#ElemType;#為根據(jù)具體問(wèn)題確定的數(shù)據(jù)類(lèi)型typedefintStatus;4.順序表上基本運(yùn)算的實(shí)現(xiàn)

初始化StatusInitList_Sq(SqList&L){L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;returnOK;}L.elem=newElemType[LIST_INIT_SIZE];順序表的插入：在表中第4個(gè)元素之前插入“21”。順序表中插入元素

插入StatusListInsert_Sq(SqList&L,inti,ElemTypee){

if((i<1)||(i>L.length+1))returnERROR;if(L.length>=L.listsize){realloc(…);….;//越界處理

；

}q=&(L.elem[i-1]);for(p=&(L.elem[L.length-1];p>=q;--p)*(p+1)=*p;*q=e;++L.length;returnOK;}//

越界處理newbase=(ElemType*)realloc(L.elem，

(L.listsize+LISTINCREMENT)*

sizeof(ElemType))；if(!newbase)exit(OVERFLOW)；L.elem=newbase；L.listsize+=LISTINCREMENT；if(L.length>=L.listsize){}算法時(shí)間復(fù)雜度:時(shí)間主要花在移動(dòng)元素上，而移動(dòng)元素的個(gè)數(shù)取決于插入元素位置。i=1，需移動(dòng)n個(gè)元素；i=i，需移動(dòng)n–i+1個(gè)元素；i=n+1，需移動(dòng)0個(gè)元素；假設(shè)pi是在第i個(gè)元素之前插入一個(gè)新元素的概率則長(zhǎng)度為n

的線(xiàn)性表中插入一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為:Eis=∑

pi(n–i+1)n+1i=1設(shè)在任何位置插入元素等概率，pi=n+11Eis=∑(n–i+1)=n+11i=1n+12nO(n)圖順序表中刪除元素順序表的刪除：刪除第5個(gè)元素，

刪除StatusListDelete_Sq(SqList&L,inti,ElemType&e){

if((i<1)||(i>L.length))returnERROR;p=&(L.elem[i-1]);e=*p;q=L.elem+L.length-1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;returnOK;}算法時(shí)間復(fù)雜度:時(shí)間主要花在移動(dòng)元素上，而移動(dòng)元素的個(gè)數(shù)取決于刪除元素位置。i=1，需移動(dòng)n-

1個(gè)元素；i=i，需移動(dòng)n–i個(gè)元素；i=n，需移動(dòng)0個(gè)元素；假設(shè)qi是刪除第i個(gè)元素的概率則長(zhǎng)度為n

的線(xiàn)性表中刪除一個(gè)元素所需移動(dòng)元素次數(shù)的期望值為:Edl=∑

qi(n–i)ni=1設(shè)刪除任何位置的元素等概率，qi=n1Edl=∑(n–i)=n1i=1n2n-

1O(n)順序表的歸并，表中元素非遞減排列。voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){pa=La.elem;pb=Lb.elem;Lc.listsize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(…);if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.length-1;pb_last=Lb.elem+Lb.length-1;while((pa<=pa_last)&&pb<=pb_last)){if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;while(pb<=pb_last)*pc++=*pb++;}順序表的基礎(chǔ)要點(diǎn)：無(wú)需為表示元素間的邏輯關(guān)系而增加額外的存儲(chǔ)空間，存儲(chǔ)密度大（100%）；可隨機(jī)存取表中的任一元素。插入或刪除一個(gè)元素時(shí)，需平均移動(dòng)表的一半元素，具體的個(gè)數(shù)與該元素的位置有關(guān)，在等概率情況下，插入n/2，刪除(n-1)/2；O(n)

存儲(chǔ)分配只能預(yù)先進(jìn)行分配。將兩個(gè)各有n個(gè)元素的有序表歸并為一個(gè)有序表，其最少的比較次數(shù)是：n作業(yè)：

2.112.3線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)：用一組任意的存儲(chǔ)單元存儲(chǔ)線(xiàn)性表的元素，不要求邏輯上相鄰的元素在物理位置上也相鄰；插入刪除時(shí)不需移動(dòng)大量元素；失去順序表可隨機(jī)存取的優(yōu)點(diǎn)。1.線(xiàn)性鏈表（單鏈表）結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映象。數(shù)據(jù)域用來(lái)存儲(chǔ)結(jié)點(diǎn)的值；指針域用來(lái)存儲(chǔ)數(shù)據(jù)元素的直接后繼的地址（或位置）。頭指針指示鏈表中第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置，單鏈表可由頭指針唯一確定。單鏈表的存儲(chǔ)映象頭結(jié)點(diǎn)在鏈表的第一個(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)，頭指針指向頭結(jié)點(diǎn)。設(shè)置頭結(jié)點(diǎn)的目的是統(tǒng)一空表與非空表的操作，簡(jiǎn)化鏈表操作的實(shí)現(xiàn)。首元結(jié)點(diǎn)鏈表中存儲(chǔ)線(xiàn)性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。單鏈表存儲(chǔ)結(jié)構(gòu)描述：typedefstructLNode{ElemTypedata；

structLNode*next；}LNode,*LinkList;單鏈表基本運(yùn)算實(shí)現(xiàn)

(1)初始化線(xiàn)性表InitList(L)

該運(yùn)算建立一個(gè)空的單鏈表,即創(chuàng)建一個(gè)頭結(jié)點(diǎn)。

voidInitList(LinkList&L){ L=(LinkList)malloc(sizeof(LNode)); /*創(chuàng)建頭結(jié)點(diǎn)*/ L->next=NULL;}(2)銷(xiāo)毀線(xiàn)性表DestroyList(L)

釋放單鏈表L占用的內(nèi)存空間。即逐一釋放全部結(jié)點(diǎn)的空間。

voidDestroyList(LinkListL){ LinkListp=L,q=p->next; while(q!=NULL) {free(p); p=q;q=p->next; } free(p);}(3)判線(xiàn)性表是否為空表ListEmpty(L)

若單鏈表L沒(méi)有數(shù)據(jù)結(jié)點(diǎn),則返回真,否則返回假。

intListEmpty(LinkListL){ return(L->next==NULL);}(4)求線(xiàn)性表的長(zhǎng)度ListLength(L)

返回單鏈表L中數(shù)據(jù)結(jié)點(diǎn)的個(gè)數(shù)。

intListLength(LinkListL){ LinkListp=L;inti=0; while(p->next!=NULL) {i++; p=p->next; } return(i);}(5)輸出線(xiàn)性表DispList(L)

逐一掃描單鏈表L的每個(gè)數(shù)據(jù)結(jié)點(diǎn),并顯示各結(jié)點(diǎn)的data域值。

voidDispList(LinkListL){ LinkListp=L->next; while(p!=NULL) {printf("%c",p->data); p=p->next; } printf("\n");}StatusGetElem(LinkListL,inti,ElemType&e){

p=L->next;j=1;while(p&&j<i){p=p->next;++j;}if(!p||j>i)returnERROR;e=p->data;returnOK;}(6)取表元素從頭指針L出發(fā)，從頭結(jié)點(diǎn)（L->next）開(kāi)始順著鏈域掃描；用j做計(jì)數(shù)器，累計(jì)當(dāng)前掃描過(guò)的結(jié)點(diǎn)數(shù)，當(dāng)j=i時(shí)，指針p所指的結(jié)點(diǎn)就是要找的第i個(gè)結(jié)點(diǎn)。例，取第i=3個(gè)元素。ZhaoQian0LiLSunp=L->nextj=1p=p->nextj=2p=p->nextj=3e=p->data=Sun時(shí)間復(fù)雜度:O(n)在單鏈表第i個(gè)結(jié)點(diǎn)前插入一個(gè)結(jié)點(diǎn)的過(guò)程(7)插入StatusListInsert(LinkList&L,inti,ElemTypee){p=L;j=0;while(p&&j<i-1){p=p->next;++j}if(!p||j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));s->data=e;

s->next=p->next;①p->next=s;②returnOK;}刪除單鏈表的第i個(gè)結(jié)點(diǎn)的過(guò)程(8)刪除StatusListDelete(LinkList&L,inti,ElemType&e){p=L;j=0;while(p->next&&j<i-1){p=p->next;++j}if(!(p->next)||j>i-1)returnERROR;r=p->next;e=r->data;

p->next=p->next->next;//(p->next=r->next;)①free(r);returnOK;}動(dòng)態(tài)建立單鏈表的過(guò)程頭插法建立單鏈表(9)頭插法建表CreateList_H(LinkList&L,intn){L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){s=(LinkList)malloc(sizeof(LNode));scanf(&s->data);

s->next=L->next;①L->next=s;②}}尾插法建表(10)尾插法建表CreateList_T(LinkList&L,intn){

tail=L=(LinkList)malloc(sizeof(LNode));L->next=NULL;for(i=n;i>0;--i){s=(LinkList)malloc(sizeof(LNode));scanf(&s->data);s->next=NULL;

tail->next=s;①

tail=s;②}}(11)按元素值查找LocateElem(L,e)

思路：在單鏈表L中從頭開(kāi)始找第1個(gè)值域與e相等的結(jié)點(diǎn),若存在這樣的結(jié)點(diǎn),則返回位置,否則返回0。

intLocateElem(LinkListL,ElemTypee){ LinkListp=L->next;intn=1; while(p!=NULL&&p->data!=e) {p=p->next;n++;} if(p==NULL)return(0); elsereturn(n);}練習(xí)：已知L是帶頭結(jié)點(diǎn)的非空單鏈表，指針p所指的結(jié)點(diǎn)既不是第一個(gè)結(jié)點(diǎn)，也不是最后一個(gè)結(jié)點(diǎn)刪除*p結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)的語(yǔ)句序列

q=p->next;p->next=q->next;free(q);刪除*p結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列

q=L;while(q->next->next!=p)q=q->next;s=q->next;q->next=p;free(s);刪除*p結(jié)點(diǎn)的語(yǔ)句序列

q=L;while(q->next!=p)q=q->next;q->next=p->next;free(p);刪除首元結(jié)點(diǎn)的語(yǔ)句序列

q=L->next;L->next=q->next;free(q);刪除最后一個(gè)結(jié)點(diǎn)的語(yǔ)句序列

while(p->next->next!=NULL)p=p->next;q=p->next;p->next=NULL;free(q);鏈?zhǔn)浇Y(jié)構(gòu)的特點(diǎn)非隨機(jī)存貯結(jié)構(gòu)，所以取表元素要慢于順序表。節(jié)約了大塊內(nèi)存適合于插入和刪除操作實(shí)際上用空間換取了時(shí)間，結(jié)點(diǎn)中加入了指針，使得這兩種操作轉(zhuǎn)換為指針操作;線(xiàn)性表實(shí)現(xiàn)方法的比較實(shí)現(xiàn)不同順序表方法簡(jiǎn)單，各種高級(jí)語(yǔ)言中都有數(shù)組類(lèi)型，容易實(shí)現(xiàn)；鏈表的操作是基于指針的，相對(duì)來(lái)講復(fù)雜些。

存儲(chǔ)空間的占用和分配不同從存儲(chǔ)的角度考慮，順序表的存儲(chǔ)空間是靜態(tài)分配的，在程序執(zhí)行之前必須明確規(guī)定它的存儲(chǔ)規(guī)模，也就是說(shuō)事先對(duì)“MAXSIZE”要有合適的設(shè)定，過(guò)大造成浪費(fèi)，過(guò)小造成溢出。而鏈表是動(dòng)態(tài)分配存儲(chǔ)空間的，不用事先估計(jì)存儲(chǔ)規(guī)模?？梢?jiàn)對(duì)線(xiàn)性表的長(zhǎng)度或存儲(chǔ)規(guī)模難以估計(jì)時(shí)，采用鏈表。線(xiàn)性表運(yùn)算的實(shí)現(xiàn)不同

按序號(hào)訪(fǎng)問(wèn)數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。插入刪除操作，使用鏈表優(yōu)于順序表。

作業(yè)：

2.42.19

3.靜態(tài)鏈表有些高級(jí)程序設(shè)計(jì)語(yǔ)言并沒(méi)有指針類(lèi)型，如FORTRAN和JAVA。我們可以用數(shù)組來(lái)表示和實(shí)現(xiàn)一個(gè)鏈表，稱(chēng)為靜態(tài)鏈表?？啥x如下：#defineMAXSIZE1000//最多元素個(gè)數(shù)typedefstruct{ElemTypedata;intcur;//游標(biāo)，指示器}component,SLinkList[MAXSIZE];i=s[i].cur;指針后移操作Malloc:i=s[0].cur;第一個(gè)可用結(jié)點(diǎn)位置

if(s[0].cur)s[0].cur=s[i].cur;Free://釋放k結(jié)點(diǎn)

s[k].cur=s[0].cur;s[0].cur=k;Insert://將i插在r之后

s[i].cur=s[r].cur;s[r].cur=i;Delete:;//p為k的直接前驅(qū)，釋放ks[p].cur=s[k].curFree(k);單鏈表基礎(chǔ)要點(diǎn)在單鏈表中，不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪(fǎng)問(wèn)到任一結(jié)點(diǎn)。在單鏈表中，刪除某一指定結(jié)點(diǎn)時(shí)，必須找到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種順序存取的存儲(chǔ)結(jié)構(gòu)，不具有隨機(jī)訪(fǎng)問(wèn)任一元素的特點(diǎn)。設(shè)置頭結(jié)點(diǎn)的作用：使在鏈表的第一個(gè)位置上的操作和表中其它位置上的操作一致，無(wú)需進(jìn)行特殊處理，對(duì)空表和非空表的處理統(tǒng)一。練習(xí)：2.22寫(xiě)一算法，對(duì)單鏈表實(shí)現(xiàn)就地逆置。voidReverse_L(LinkList&L){p=L->next;L->next=NULL;while(p!=NULL){q=p;p=p->next;q->next=L->next;L->next=q;}}循環(huán)鏈表循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；可從當(dāng)前結(jié)點(diǎn)出發(fā)，訪(fǎng)問(wèn)到任一結(jié)點(diǎn)；循環(huán)單鏈表；多重循環(huán)鏈表。單循環(huán)鏈表設(shè)置尾指針rear,比設(shè)頭指針更好。連接兩個(gè)只設(shè)尾指針的單循環(huán)鏈表L1和L2操作如下：p=R1–>next; //保存L1的頭結(jié)點(diǎn)指針R1->next=R2->next->next; //頭尾連接free(R2->next);//釋放第二個(gè)表的頭結(jié)點(diǎn)

R2->next=p;

R2b1

bn…×a1

an…R1×p例，取循環(huán)鏈表第i個(gè)元素。p=L->next；j=1

；while(p!=L&&j<i){p=p->next；++j；}if(p==L||j>i)returnERROR；e=p->data；returnOK

；StatusGetElem_L(LinkListL，inti，ElemType&e){}操作與線(xiàn)性單鏈表基本一致，差別只是在于算法中的循環(huán)結(jié)束條件不是p是否為空，而是p是否等于頭指針。雙鏈表

希望查找前驅(qū)的時(shí)間復(fù)雜度達(dá)到O(1)，我們可以用空間換時(shí)間,每個(gè)結(jié)點(diǎn)再加一個(gè)指向前驅(qū)的指針域，使鏈表可以進(jìn)行雙方向查找。用這種結(jié)點(diǎn)結(jié)構(gòu)組成的鏈表稱(chēng)為雙向鏈表。

結(jié)點(diǎn)的結(jié)構(gòu)圖:priornextdata雙向鏈表的邏輯表示priordatanextLL2.雙向鏈表(DoubleLinkedList)類(lèi)型描述typedefstructDuLNode{ElemType

data;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;雙向循環(huán)鏈表p->next->prior=p->prior->next;p雙向鏈表的前(后)插入操作①s->prior=p->prior;②p->prior->next=s;③s->next=p;④p->prior=s;q①s->next=q->next;②q->next->prior=s;③s->prior=q;④q->next=s;③④②①雙向鏈表的刪除操作①p->prior->next=p->next;②p->next->prior=p->prior;刪除*p的直接后繼結(jié)點(diǎn)的語(yǔ)句序列

q=p->next;p->next=p->next->next;p->next->prior=p;free(q);刪除*p的直接前驅(qū)結(jié)點(diǎn)的語(yǔ)句序列

q=p->prior;p->prior=p->prior->prior;p->prior->next=p;free(q);作業(yè)：

2.82.9循環(huán)鏈表算法舉例（1）

假設(shè)一個(gè)單循環(huán)鏈表，其結(jié)點(diǎn)含有三個(gè)域pre、data、link。其中data為數(shù)據(jù)域；pre為指針域，它的值為空指針（null）；link為指針域，它指向后繼結(jié)點(diǎn)。請(qǐng)?jiān)O(shè)計(jì)算法，將此表改成雙向循環(huán)鏈表。voidSToDouble（DuLinkListla）//la是結(jié)點(diǎn)含有pre，data，link三個(gè)域的單循環(huán)鏈表。其中data為數(shù)據(jù)域；pre為空指針域，link是指向后繼的指針域。本算法將其改造成雙向循環(huán)鏈表。{while（la->link->pre==null）

{la->link->pre=la//將結(jié)點(diǎn)la后繼的pre指針指向lala=la->link；//la指針后移

}}

//算法結(jié)束循環(huán)鏈表算法舉例（2）已知一雙向循環(huán)鏈表，從第二個(gè)結(jié)點(diǎn)至表尾遞增有序，（設(shè)a1<x<an）如下圖。試編寫(xiě)程序，將第一個(gè)結(jié)點(diǎn)刪除并插入表中適當(dāng)位置，使整個(gè)鏈表遞增有序

xa1a2anLvoidDInsert（DuLinkList&L）∥L是無(wú)頭結(jié)點(diǎn)的雙向循環(huán)鏈表，自第二結(jié)點(diǎn)起遞增有序。本算法將第一結(jié)點(diǎn)（a1<x<an）插入到鏈表中，使整個(gè)鏈表遞增有序

{s=L；∥s暫存第一結(jié)點(diǎn)的指針

t=L->prior;//t暫存尾結(jié)點(diǎn)指針

p=L->next；∥將第一結(jié)點(diǎn)從鏈表上摘下

p->prior=L->prior；p->prior->next=p；

x=s->data;

while（p->data<x）p=p->next；∥查插入位置

s->next=p；s->prior=p->prior；∥插入原第一結(jié)點(diǎn)sp->prior->next=s；p->prior=s；

L=t->next;

}∥算法結(jié)束

例

編寫(xiě)出判斷帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L是否對(duì)稱(chēng)相等的算法。解:p從左向右掃描L,q從右向左掃描L,若對(duì)應(yīng)數(shù)據(jù)結(jié)點(diǎn)的data域不相等,則退出循環(huán),否則繼續(xù)比較,直到p與q相等或p的下一個(gè)結(jié)點(diǎn)為*q為止。對(duì)應(yīng)算法如下:循環(huán)鏈表算法舉例（3）intEqual(DuLinkListL){intsame=1;DuLinkListp=L->next; /*p指向第一個(gè)數(shù)據(jù)結(jié)點(diǎn)*/DuLinkListq=L->prior;/*q指向最后數(shù)據(jù)結(jié)點(diǎn)*/while(same==1)if(p->data!=q->data)same=0; else{ if(p==q)break; /*數(shù)據(jù)結(jié)點(diǎn)為奇數(shù)的情況*/ q=q->prior; if(p==q)break; /*數(shù)據(jù)結(jié)點(diǎn)為偶