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

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

唯一頭元素

唯一尾元素

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

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

3

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

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

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

到i

個元素均向后移動一個位置。2.將新元素放置在第i

個位置。a1ai-1aian……例，在第i個元素前插入ba1ai-1aian……b8/49例，在第4個元素之前插入元素25。451293369512345657693325插入259/49算法時間復雜度:移動元素的個數(shù)取決于插入元素位置。i=1，需移動n個元素；i=i，需移動n–i+1個元素；i=n+1，需移動0個元素；10/49假設pi是在第

i個元素之前插入一個新元素的概率則長度為n

的線性表中插入一個元素所需移動元素次數(shù)的期望值為:Eis=∑

pi(n–i+1)n+1i=1設在任何位置插入元素等概率，pi=n+11Eis=∑(n–i+1)=n+11i=1n+12nO(n)11/49算法2.2刪除第i

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

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

到n

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

1個元素；i=i，需移動n–i個元素；i=n，需移動0個元素；14/49假設qi是刪除第

i個元素的概率則長度為n

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

qi

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

1O(n)15/49

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

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

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

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

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

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

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

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

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

struct

LNode{ElemTypedata；struct

LNode

*next；}LNode

，*

LinkList

；空表:0Head21/49單鏈表特點缺點：不可隨機存取表中任意數(shù)據(jù)元素不可直接獲取線性表的長度優(yōu)點：插入、刪除方便22/49例，取第i=3個元素。ZhaoQian0LiLSunp=L->nextj=1p=p->nextj=2p=p->nextj=3e=p->data=Sun時間復雜度:O(n)23/49優(yōu)點:數(shù)據(jù)元素的插入、刪除相對方便在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算法：

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

將兩個有序單鏈表合并為一個有序單鏈表pa=La->next；pb=Lb->next；//分別指向第一個結(jié)點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é)點有兩個指針域:一個指向直接后繼，一個指向直接前趨。priordatanext2.3.2雙鏈表28/49雙鏈表結(jié)點定義參考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ì):設d

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

；4.s->next=p

；5.p->prior=s

；32/492)刪除ACB1.找到要刪除的結(jié)點，p記錄。p2.p->prior->next=p->next；3.p->next->prior=p->prior；4.free(p)；33/49表中最后一個節(jié)點的指針域指向頭結(jié)點，形成一個環(huán)。a1…anHead0從表的任意結(jié)點出發(fā)均可以找到表中的其他結(jié)點。優(yōu)點:2.3.3循環(huán)單鏈表tail空表:Headtail34/492.3.3循環(huán)雙向鏈表ACHeadB空表:Head35/49☆靜態(tài)鏈表在數(shù)組中增加一個(或兩個)指針域用來存放下一個(或上一個)數(shù)據(jù)元素在數(shù)組中的下標，從而構(gòu)成用數(shù)組構(gòu)造的單鏈表。因為數(shù)組內(nèi)存空間的申請方式是靜態(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例題：一元多項式的表示及相加數(shù)學表示:

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

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

個系數(shù)構(gòu)成的線性表。多項式相加:設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)實現(xiàn)方便。順序存儲37/49+Rp0+q0p1+q1…pm+qmpm+1…pnq0q1qmQ…p0p1pmpn…P…38/49采用何種存儲結(jié)構(gòu)取決于需要實現(xiàn)的操作！P=((p1，e1

)，(p2，e2

)，…，(pm，em

)

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

；0≤e1＜

e2

＜＜em

≤n…計算機表示:P=((p1，e1

)，(p2，e2

)，…，(pm，em

)

)?采用那種存儲結(jié)構(gòu)？40/49“多項式相加”等運算則采用鏈式存儲結(jié)構(gòu)nextcoefexpo系數(shù)指數(shù)下一個結(jié)點typedef

struct

LNode{ElemType

coef

；struct

LNode

*next；}LNode

，*

LinkList

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

和qb

分別指向多項式A和B中當前進行比較的結(jié)點；qa->expo

＜

qb->expo，qa所指向的結(jié)點應插入和多項式中qa->expo

＞

qb->expo，qb所指向的結(jié)點應插入和多項式中qa->expo

＝

qb->expo，求和

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

和qb

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

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

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

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

結(jié)點case=://計算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