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

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

an)2.線性表的長度線性表中元素的個數(shù)n(n>=0),n=0時,稱為空表。3.位序ai是第i個元素，稱i為數(shù)據(jù)元素ai在線性表中的位序

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

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

初始化InitList（&L）建立一個空表。求表長ListLength（L）返回線性表的長度。讀表元素GetElem（L,i,&e)用e返回L中第i個數(shù)據(jù)元素的值。定位LocateElem（L,e,compare()）返回滿足關(guān)系的數(shù)據(jù)元素的位序。插入ListInsert（&L,i,e）在L中第i個位置之前插入新的數(shù)據(jù)元素e，線性表的長度增1。刪除ListDelete（&L,i,&e）刪除L的第i個位置上的數(shù)據(jù)元素e，線性表的長度減1。輸出ListDisplay（L）按前后次序輸出線性表的所有元素。練習(xí)1：兩個線性表LA和LB分別表示兩個集合A和B，現(xiàn)求一個新的集合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：

兩個線性表LA和LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)將LA和LB歸并為一個新的線性表，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)順序表：

按順序存儲方式構(gòu)造的線性表。

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

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

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

intlistsize;//分配的存儲容量

}SqList；

//ElemTypeelem[MAXSIZE];typedef#ElemType;#為根據(jù)具體問題確定的數(shù)據(jù)類型typedefintStatus;4.順序表上基本運算的實現(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個元素之前插入“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){}算法時間復(fù)雜度:時間主要花在移動元素上，而移動元素的個數(shù)取決于插入元素位置。i=1，需移動n個元素；i=i，需移動n–i+1個元素；i=n+1，需移動0個元素；假設(shè)pi是在第i個元素之前插入一個新元素的概率則長度為n

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

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

刪除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;}算法時間復(fù)雜度:時間主要花在移動元素上，而移動元素的個數(shù)取決于刪除元素位置。i=1，需移動n-

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

的線性表中刪除一個元素所需移動元素次數(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ǔ)要點：無需為表示元素間的邏輯關(guān)系而增加額外的存儲空間，存儲密度大（100%）；可隨機存取表中的任一元素。插入或刪除一個元素時，需平均移動表的一半元素，具體的個數(shù)與該元素的位置有關(guān)，在等概率情況下，插入n/2，刪除(n-1)/2；O(n)

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

2.112.3線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)

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

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

(1)初始化線性表InitList(L)

該運算建立一個空的單鏈表,即創(chuàng)建一個頭結(jié)點。

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

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

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

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

intListEmpty(LinkListL){ return(L->next==NULL);}(4)求線性表的長度ListLength(L)

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

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

逐一掃描單鏈表L的每個數(shù)據(jù)結(jié)點,并顯示各結(jié)點的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é)點（L->next）開始順著鏈域掃描；用j做計數(shù)器，累計當(dāng)前掃描過的結(jié)點數(shù)，當(dāng)j=i時，指針p所指的結(jié)點就是要找的第i個結(jié)點。例，取第i=3個元素。ZhaoQian0LiLSunp=L->nextj=1p=p->nextj=2p=p->nextj=3e=p->data=Sun時間復(fù)雜度:O(n)在單鏈表第i個結(jié)點前插入一個結(jié)點的過程(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個結(jié)點的過程(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;}動態(tài)建立單鏈表的過程頭插法建立單鏈表(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中從頭開始找第1個值域與e相等的結(jié)點,若存在這樣的結(jié)點,則返回位置,否則返回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é)點的非空單鏈表，指針p所指的結(jié)點既不是第一個結(jié)點，也不是最后一個結(jié)點刪除*p結(jié)點的直接后繼結(jié)點的語句序列

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

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

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

q=L->next;L->next=q->next;free(q);刪除最后一個結(jié)點的語句序列

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

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

按序號訪問數(shù)據(jù)元素，使用順序表優(yōu)于鏈表。插入刪除操作，使用鏈表優(yōu)于順序表。

作業(yè)：

2.42.19

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

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

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ǔ)要點在單鏈表中，不能從當(dāng)前結(jié)點出發(fā)訪問到任一結(jié)點。在單鏈表中，刪除某一指定結(jié)點時，必須找到該結(jié)點的前驅(qū)結(jié)點。線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種順序存取的存儲結(jié)構(gòu)，不具有隨機訪問任一元素的特點。設(shè)置頭結(jié)點的作用：使在鏈表的第一個位置上的操作和表中其它位置上的操作一致，無需進(jìn)行特殊處理，對空表和非空表的處理統(tǒng)一。練習(xí)：2.22寫一算法，對單鏈表實現(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)酱鎯Y(jié)構(gòu)；可從當(dāng)前結(jié)點出發(fā)，訪問到任一結(jié)點；循環(huán)單鏈表；多重循環(huán)鏈表。單循環(huán)鏈表設(shè)置尾指針rear,比設(shè)頭指針更好。連接兩個只設(shè)尾指針的單循環(huán)鏈表L1和L2操作如下：p=R1–>next; //保存L1的頭結(jié)點指針R1->next=R2->next->next; //頭尾連接free(R2->next);//釋放第二個表的頭結(jié)點

R2->next=p;

R2b1

bn…×a1

an…R1×p例，取循環(huán)鏈表第i個元素。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){}操作與線性單鏈表基本一致，差別只是在于算法中的循環(huán)結(jié)束條件不是p是否為空，而是p是否等于頭指針。雙鏈表

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

結(jié)點的結(jié)構(gòu)圖:priornextdata雙向鏈表的邏輯表示priordatanextLL2.雙向鏈表(DoubleLinkedList)類型描述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é)點的語句序列

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

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

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

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

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

}}

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

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

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

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

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

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é)點sp->prior->next=s；p->prior=s；

L=t->next;

}∥算法結(jié)束

例

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