數(shù)據(jù)結(jié)構(gòu)與算法-線性表

2線性表2/49線性表主要知識(shí)點(diǎn)順序表單鏈表循環(huán)單鏈表循環(huán)雙向鏈表靜態(tài)鏈表設(shè)計(jì)舉例雙鏈表3/49

唯一頭元素

唯一尾元素

除頭元素外，均有一個(gè)直接前驅(qū)

除尾元素外，均有一個(gè)直接后繼線性結(jié)構(gòu)特點(diǎn):OOOOO線性頭尾12

3

452.1線性表的概念4/49其中a1是頭元素，an是尾元素，ai是第i個(gè)元素。ai-1是ai的直接前驅(qū)，ai是ai-1的直接后繼。當(dāng)2≤i≤n時(shí)，ai有且只有一個(gè)直接前驅(qū)。當(dāng)1≤i≤n-1時(shí)，ai有且只有一個(gè)直接后繼。線性表可以表示為n個(gè)數(shù)據(jù)元素的有限序列:(a1，…，ai-1，ai，…，an)2.1線性表的概念5/49線性表的存儲(chǔ)順序存儲(chǔ)順序表鏈?zhǔn)酱鎯?chǔ)鏈表6/49用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的數(shù)據(jù)元素。a1a2aian……bb+l…b+(i-1)l…b+(n-1)lb+nl存儲(chǔ)地址內(nèi)存狀態(tài)設(shè)每個(gè)元素需占用l個(gè)存儲(chǔ)單元LOC(ai)表示元素ai的存儲(chǔ)地址則LOC(a1)是第一個(gè)數(shù)據(jù)元素a1的存儲(chǔ)地址，也是整個(gè)線性表的起始地址LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-

1)l2.2順序表7/49算法2.1在第i

個(gè)數(shù)據(jù)元素之前插入一個(gè)新的元素思想:1.將第n

到i

個(gè)元素均向后移動(dòng)一個(gè)位置。2.將新元素放置在第i

個(gè)位置。a1ai-1aian……例，在第i個(gè)元素前插入ba1ai-1aian……b8/49例，在第4個(gè)元素之前插入元素25。451293369512345657693325插入259/49算法時(shí)間復(fù)雜度:移動(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è)元素；10/49假設(shè)pi是在第

i個(gè)元素之前插入一個(gè)新元素的概率則長度為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)11/49算法2.2刪除第i

個(gè)數(shù)據(jù)元素思想:a1ai-1ai+1an……a1ai-1ai+1an……ai1.刪除第i

個(gè)數(shù)據(jù)元素。2.將第i+1

到n

個(gè)元素均向前移動(dòng)一個(gè)位置。12/49例，刪除第4個(gè)元素25。刪除2545129253369123456753369513/49算法時(shí)間復(fù)雜度:移動(dòng)元素的個(gè)數(shù)取決于刪除元素位置。i=1，需移動(dòng)n-

1個(gè)元素；i=i，需移動(dòng)n–i個(gè)元素；i=n，需移動(dòng)0個(gè)元素；14/49假設(shè)qi是刪除第

i個(gè)元素的概率則長度為n

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

qi

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

1O(n)15/49

順序表中的其余操作都和數(shù)據(jù)元素個(gè)數(shù)n無關(guān)，因此，在順序表中插入和刪除一個(gè)數(shù)據(jù)元素的時(shí)間復(fù)雜度為O(n)，其余操作的時(shí)間復(fù)雜度都為O(1)。16/49

可隨機(jī)存取表中任意數(shù)據(jù)元素，算法簡單，空間單元利用率高；優(yōu)點(diǎn):

直接可獲取線性表的長度例，L.elem[i-1]表示第i

個(gè)數(shù)據(jù)元素例，L.length表示線性表長度缺點(diǎn):

數(shù)據(jù)元素的插入、刪除相對(duì)麻煩，需要預(yù)先確定數(shù)據(jù)元素的最大個(gè)數(shù)，插入和刪除時(shí)需要移動(dòng)較多的數(shù)據(jù)元素。順序表特點(diǎn)17/49線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素。存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。2.3鏈表18/49結(jié)點(diǎn):

兩部分信息組成，存儲(chǔ)數(shù)據(jù)元素信息的數(shù)據(jù)域，存儲(chǔ)直接后繼存儲(chǔ)位置信息的指針域。datalink數(shù)據(jù)域，存放數(shù)據(jù)信息指針域，指向下一個(gè)數(shù)據(jù)單元2.3.1單鏈表19/49a1a2…0anHeadHead:

頭指針，指向鏈表中第一個(gè)結(jié)點(diǎn)。0:

空指針，有時(shí)也表示為“NULL”或“∧”。頭結(jié)點(diǎn):

記錄線性表的某些性質(zhì)信息(如長度)。a1a2…0anHead2.3.1單鏈表20/49a1a2…0anHead單鏈表存儲(chǔ)結(jié)構(gòu)typedef

struct

LNode{ElemTypedata；struct

LNode

*next；}LNode

，*

LinkList

；空表:0Head21/49單鏈表特點(diǎn)缺點(diǎn)：不可隨機(jī)存取表中任意數(shù)據(jù)元素不可直接獲取線性表的長度優(yōu)點(diǎn)：插入、刪除方便22/49例，取第i=3個(gè)元素。ZhaoQian0LiLSunp=L->nextj=1p=p->nextj=2p=p->nextj=3e=p->data=Sun時(shí)間復(fù)雜度:O(n)23/49優(yōu)點(diǎn):數(shù)據(jù)元素的插入、刪除相對(duì)方便在a，b之間插入元素x:abpxss->next=p->nextp->next=s24/49刪除元素b:acpbq=p->nextp->next=p->next->next?

p->next=q->nextq=p->next

3）free(q)；25/4921350Lb0627La6789

Lcpapb,pcpapcpb

Lcpc

pbpa

Lcpcpa

pbLcpbpapcLc算法：

將兩個(gè)有序單鏈表合并為一個(gè)有序單鏈表26/49算法：

將兩個(gè)有序單鏈表合并為一個(gè)有序單鏈表pa=La->next；pb=Lb->next；//分別指向第一個(gè)結(jié)點(diǎn)pc->next=pa?pa:pb

；//處理剩余部分while(pa&&pb){if(pa->data<=pb->data){pc->next=pa；pc=pa；pa=pa->next；}else{pc->next=pb

；pc=pb

；pb=pb->next；}

}voidMergeList_L(LinkList&La，LinkList&Lb，LinkList&Lc){}Lc=pc=La；free(Lb)；思想:通過比較不斷后移指針合并鏈表。27/49雙向鏈表的結(jié)點(diǎn)有兩個(gè)指針域:一個(gè)指向直接后繼，一個(gè)指向直接前趨。priordatanext2.3.2雙鏈表28/49雙鏈表結(jié)點(diǎn)定義參考template<classT>classDLLNode{public:

DLLNode(){ next=prior=0; }

DLLNode(constT&el,DLLNode*n=0,DLLNode*p=0){data=el;next=n;prior=p;}Tdata;

DLLNode*next,*prior;};29/49雙鏈表類定義參考template<classT>classDoublyLinkedList{public:

DoublyLinkedList(){head=newDLLNode<T>();}voidaddDLLNode(const

T&,i);voidclear(); ~DoublyLinkedList(){ clear(); }protected:

DLLNode<T>*head;};30/49性質(zhì):設(shè)d

是指向某個(gè)結(jié)點(diǎn)的指針，則有d->next->prior=d->prior->next=d操作:只涉及單向的操作基本相同，但插入、刪除操作變化很大。ACHeadB^^空表:Head^^d31/491)插入ABXsp1.找到要在之前插入的結(jié)點(diǎn)，p記錄。2.s->prior=p->prior；3.p->prior->next=s

；4.s->next=p

；5.p->prior=s

；32/492)刪除ACB1.找到要?jiǎng)h除的結(jié)點(diǎn)，p記錄。p2.p->prior->next=p->next；3.p->next->prior=p->prior；4.free(p)；33/49表中最后一個(gè)節(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，形成一個(gè)環(huán)。a1…anHead0從表的任意結(jié)點(diǎn)出發(fā)均可以找到表中的其他結(jié)點(diǎn)。優(yōu)點(diǎn):2.3.3循環(huán)單鏈表tail空表:Headtail34/492.3.3循環(huán)雙向鏈表ACHeadB空表:Head35/49☆靜態(tài)鏈表在數(shù)組中增加一個(gè)(或兩個(gè))指針域用來存放下一個(gè)(或上一個(gè))數(shù)據(jù)元素在數(shù)組中的下標(biāo)，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。因?yàn)閿?shù)組內(nèi)存空間的申請(qǐng)方式是靜態(tài)的，所以稱為靜態(tài)鏈表，增加的指針稱做仿真指針。結(jié)構(gòu)如下：ABCE∧headD(a)常規(guī)鏈表A1B2C3D4E-1┇(b)靜態(tài)鏈表一datanext01234┇maxSize-1A2E-1B4D1C3┇(b)靜態(tài)鏈表一datanext01234┇maxSize-136/49例題：一元多項(xiàng)式的表示及相加數(shù)學(xué)表示:

Pn(x)=p0+p1x+p2x2+…+pnxn計(jì)算機(jī)表示:P=(p0，p1，p2，…，pn

)可以描述為一個(gè)由n+1

個(gè)系數(shù)構(gòu)成的線性表。多項(xiàng)式相加:設(shè)Pn(x):P=(p0，p1，p2，…，pn

)Qm(x):Q=(q0，q1，q2，…，qm

)m<n則Rn(x)=Pn(x)+Qm(x)R=(p0+q0，p1+q1，p2+q2，…，pm+qm，pm+1，…，pn

)顯然，采用結(jié)構(gòu)實(shí)現(xiàn)方便。順序存儲(chǔ)37/49+Rp0+q0p1+q1…pm+qmpm+1…pnq0q1qmQ…p0p1pmpn…P…38/49采用何種存儲(chǔ)結(jié)構(gòu)取決于需要實(shí)現(xiàn)的操作！P=((p1，e1

)，(p2，e2

)，…，(pm，em

)

)實(shí)現(xiàn)“求值”、“求項(xiàng)數(shù)”這樣的操作，采用順序存儲(chǔ)結(jié)構(gòu)。p1p2pm…e1e2em…39/49然而實(shí)際應(yīng)用中，多項(xiàng)式的次數(shù)往往很高，且可能存在很多缺項(xiàng)。例，S(x)=1+3x10000+2x20000通常情況下，一元n次多項(xiàng)式寫成:Pn(x)=p1x+p2x+…+pmxe1e2empi≠0

；0≤e1＜

e2

＜＜em

≤n…計(jì)算機(jī)表示:P=((p1，e1

)，(p2，e2

)，…，(pm，em

)

)?采用那種存儲(chǔ)結(jié)構(gòu)？40/49“多項(xiàng)式相加”等運(yùn)算則采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)nextcoefexpo系數(shù)指數(shù)下一個(gè)結(jié)點(diǎn)typedef

struct

LNode{ElemType

coef

；struct

LNode

*next；}LNode

，*

LinkList

；ElemTypeexpo；算法2.23多項(xiàng)式相加AddPolyn(&Pa，&Pb)要求:Pa=Pa+Pb41/49思想:依據(jù)歸并兩個(gè)有序表的過程，分三種情況考慮:令qa

和qb

分別指向多項(xiàng)式A和B中當(dāng)前進(jìn)行比較的結(jié)點(diǎn)；qa->expo

＜

qb->expo，qa所指向的結(jié)點(diǎn)應(yīng)插入和多項(xiàng)式中qa->expo

＞

qb->expo，qb所指向的結(jié)點(diǎn)應(yīng)插入和多項(xiàng)式中qa->expo

＝

qb->expo，求和

qa->coef+qb->coef和＝0，釋放qa

和qb

所指結(jié)點(diǎn)；和≠0，修改qa

所指結(jié)點(diǎn)的系數(shù)值，釋放qb

所指結(jié)點(diǎn)；qa-113520-2head1head2-13952740qb42/49qa=Pa->next；qb=Pb->next；case<://插入qa

結(jié)點(diǎn)case>://插入qb

結(jié)點(diǎn)case=://計(jì)算qa->coef+qb->coefswitch(cmp(qa->expo，qb->expo

)){}while(qa&&qb){}FreeNode(hb)；voidAddPolyn(polynomial&Pa，polynomial&Pb){}ha->next=qa?qa:qb

；//處理剩余部分ha=Pa；hb=Pb

；43/49case<:ha=qa

；qa=qa->next；break

；qaqb357haqaha44/49case>:hb->next=qb->next；qb=hb->next；ha=ha->next；break

；ha->nex