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

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

地址內(nèi)存

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

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

LOC(ai)=

1)+(i-

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

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

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

nn1∑(n–i)=

n-2

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

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

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

p=p-j=

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

60算法：將兩個(gè)有序單鏈表合并為一個(gè)有序單鏈思想 通過(guò)比較不斷后移指針合并鏈表 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é)點(diǎn)有兩個(gè)指針域一個(gè)指向直接后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是指向某個(gè)結(jié)點(diǎn)的指針d->next->prior=d->prior->next=操作:只涉及單向的操作基本相同，但 p Xs找到要在之 的結(jié)點(diǎn)，p記錄s->prior=p->priorp->prior->next=ss->next=pp->prior=s刪ACAC找到要?jiǎng)h除的結(jié)點(diǎn)，p記錄p->prior->next=p->nextp->next->prior=p->priorfree(p)表中最后一個(gè)節(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，形成一個(gè)環(huán)

空表

優(yōu)點(diǎn)

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

(a)

dataA2A2E-B4D1C3┇1234┇maxSize-

maxSize-

例題：一元多項(xiàng)式的表數(shù)學(xué)表示:Pn(xp0p1xp2x2計(jì)算機(jī)表示:Pp0，p1，p2，…，pn可以描述為n+1個(gè)系數(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)實(shí)現(xiàn)方便

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

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

思想:依據(jù)歸并兩個(gè)有序表的過(guò)程，分三種情況考慮 -1-1350 -39-3952470qaqb分別指向多項(xiàng)式AB中當(dāng)前進(jìn)行比較qa->expoqb->expo，qa所指向的結(jié)點(diǎn)應(yīng)和多項(xiàng)式中qa->expoqb->expo，qb所指向的結(jié)點(diǎn)應(yīng)和多項(xiàng)式中qa->expo＝qb->expo，qa->coef+qb->coef＝0，釋qaqb所指結(jié)點(diǎn)≠0，修qa所指結(jié)點(diǎn)的系數(shù)值qb所指結(jié)點(diǎn) 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