課件-3線性表唯一尾元素

22 雙鏈要 點 點2.1線性結(jié)構(gòu)特點 線性 唯一頭元唯一尾元線性表可以n個數(shù)據(jù)元素的有限序列:其中a1是頭元素，an是尾元素，ai是第i個元素。ai-1是ai的直接前驅(qū)ai是ai-1的直接后繼。當2≤i≤nai有且只有一個直接前驅(qū)。當1≤i≤n-1時，ai有且只有一個直接后繼。順順序鏈鏈用一組地址連續(xù) 單元依 線性表的數(shù)據(jù)元素……

地址內(nèi)存

設(shè)每個元素需占用l 單LOC(a)表示元素a 地… ……b+(i-…b+(n-

LOC(ai+1)=LOC(ai)+

LOC(ai)=

1)+(i-

在第i個數(shù)據(jù)元 例，在第i個元素前 …ai-……ai-b…思想ni將新元素放置在第i個位置例，在第4個 元素25952 4567算法時間復(fù)雜度移動元素的個數(shù)取決 元素位置i=1，需移動n個元素；i=n+1，需移0個元素；i=i，需移ni+1個元素；假設(shè)pi是在第i個 一個新元素的概則長度為n的線性表 一個元素所需移動素次數(shù)的期望值為 Eis=∑pi(n–i+1設(shè)在任何位 元素等概率，pi Eis

n∑(n–i+1)=n+1i=1 n

算法2.2刪除i個數(shù)據(jù)元…ai-……ai-…思想刪除ii+1n個元素均例，刪除第4個元素25923刪除 56算法時間復(fù)雜度移動元素的個數(shù)取決于刪除元i=1，需移動n1個元素；i=i，需移動n–i個元素；假設(shè)qi是刪除第i個元素的概則長度為n的線性表中刪除一個元素所需移n素次數(shù)的期望值為 Edl=∑qi(n–1設(shè)刪除任何位置的元素等概率，qi Edl

nn1∑(n–i)=

n-2

順序表中的其余操作都和數(shù)據(jù)元素個數(shù)n無關(guān)，因此，在順序表中和刪除一個

例，L.elem[i-1]表示第i數(shù)據(jù)元素的、刪除相對麻煩，需要預(yù)先確定數(shù)據(jù)元素的最大個數(shù)，和刪除時需要 單元可以是連續(xù)的，也可以是不連續(xù)的結(jié)點:兩部分信息組成， 數(shù)據(jù)域，存放數(shù)據(jù)指針域，指向下一

2.3.100Head:頭指針，指向鏈表中第一個結(jié)點0:空指針，有時也表示為“NULL”或“∧”。頭結(jié)點:記錄線性表的某些性質(zhì)信息(如長度)。0…000單鏈 結(jié) data；struct *next}LNode，*LinkList0空表0缺點優(yōu)點例，取第i=3p=L-Lj=

p=p-j=

p=p-00j=e=p->data=時間復(fù)雜度 元素x:pababxsxs->next=p->nextp->next=s刪除元素bbca q=p-bcap->next=p->next->nextq=p-p->next=q-3）free(q)算法：將兩個有序單鏈表合并為一個有序單鏈Lc,

60算法：將兩個有序單鏈表合并為一個有序單鏈思想 通過比較不斷后移指針合并鏈表 MergeList_L(LinkList&La，LinkList&Lb，LinkList&Lc)paLa->nextpbLb->next；//分別指向Lc=pc=Lawhile(pa&&pb)if(pa->data<=pb->data pc->next=pa；pc=pa；pa=pa->next；}else{pc->next=pb；pc=pb；pb=pb->next；}}pc->nextpapapb；//處理剩余部free(Lb)}

雙向鏈表的結(jié)點有兩個指針域一個指向直接后template<classclassDLLNode{DLLNode()next=prior=}DLLNode(constT&el,DLLNode*n=0,DLLNode*p=0){data=el;next=n;prior=p;}TDLLNode*next,template<classclassDoublyLinkedList{DoublyLinkedList()head=new}voidaddDLLNode(constT&,i);voidclear();~DoublyLinkedList(){}DLLNode<T>*head;空表

^C^^BA^ ^C^^BA^性質(zhì):設(shè)d是指向某個結(jié)點的指針d->next->prior=d->prior->next=操作:只涉及單向的操作基本相同，但 p Xs找到要在之 的結(jié)點，p記錄s->prior=p->priorp->prior->next=ss->next=pp->prior=s刪ACAC找到要刪除的結(jié)點，p記錄p->prior->next=p->nextp->next->prior=p->priorfree(p)表中最后一個節(jié)點的指針域指向頭結(jié)點，形成一個環(huán)

空表

優(yōu)點

從表的任意結(jié)點出發(fā)均可以找到表中的其他結(jié)點2.3.3ABABC空表 ABCED∧ABCED∧dataA1A1B2C3D4E-┇1234┇

(a)

dataA2A2E-B4D1C3┇1234┇maxSize-

maxSize-

例題：一元多項式的表數(shù)學(xué)表示:Pn(xp0p1xp2x2計算機表示:Pp0，p1，p2，…，pn可以描述為n+1個系數(shù)構(gòu)成的線性表。設(shè)Pn(x) P=(p0，p1，p2，…，pnQm(x) Q=(q0，q1，q2，…，qm Rn(xPn(xR=(p0+q0，p1+q1，p2+q2，…，pm+qm，pm+1，…，pn顯然，采用

結(jié)構(gòu)實現(xiàn)方便

……………p0+p1+…pm+… P=((p1，e1)，(p2，e2)，…，(pm，em)采用何 結(jié)構(gòu)取決于需要實現(xiàn)的操作 ……然而實際應(yīng)用中，多項式的次數(shù)往往很高，且可能存在很多缺項。例，S(x13x10000通常情況n次多項式寫成:Pn(xp1xe1p2xe2pmxempi≠0；0≤e1＜e2

＜em≤計算機表示:Pp1，e1，p2，e2，…，pm，em?采用那 結(jié)構(gòu)“多項式相加”等運算則采用鏈 結(jié)系 指 下一個結(jié) coef expostruct *next}LNode，*LinkList算法 多項式相加AddPolyn(&Pa，&Pb要求:PaPa

思想:依據(jù)歸并兩個有序表的過程，分三種情況考慮 -1-1350 -39-3952470qaqb分別指向多項式AB中當前進行比較qa->expoqb->expo，qa所指向的結(jié)點應(yīng)和多項式中qa->expoqb->expo，qb所指向的結(jié)點應(yīng)和多項式中qa->expo＝qb->expo，qa->coef+qb->coef＝0，釋qaqb所指結(jié)點≠0，修qa所指結(jié)點的系數(shù)值qb所指結(jié)點 AddPolyn(polynomial&Pa，polynomial&Pb){ha=Pa；hb=Pb；qa=Pa->next；qb=Pb->nextwhile(qa&&qb switch(cmp(qa->expo，qb->expo) qa結(jié) qb結(jié) //qa->coefqb-}}ha->nextqaqaqb；//處理剩余部FreeNode(hb)}

<a3ha=qa；qa=qa->next；breaka375 > hb->next=qb->nextha->next=qb；qb->next=qa53qb=hb->next；ha=ha->5378 = 7 7 8- 8 sum=qa->coef+qb->coef (sum!=0.0) qa->coef=sum；haqa；qaqa->next//hb->next=qb->next；Free(qb；qbhb->next；// ha->next=qa->next；Free(qa)；qa=ha->next//qahb->next=qb->next；Free(q