第2章線性表2.1線性表的概念及運算2.2線性表的順序存儲2.3線性表的鏈式存儲2.4一元多項式的表示及相加2.1線性表的概念及運算4.線性表的邏輯結構1.線性表的定義一個線性表是具有n個數據元素的有限序列。記為(a1,…,ai-1,ai,ai+1,…,

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

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

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

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

兩個線性表LA和LB中的數據元素按值非遞減有序排列，現將LA和LB歸并為一個新的線性表，LC中的數據元素仍按值非遞減有序排列。

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)構造Lc=(2,3,5,6,8,8,9,15)358La268Lb915Lcij2首先，La_len=3；Lb_len=5；3ijij5ij6ij88jij9j15j算法結束！2.2線性表的順序表示和實現順序表：

按順序存儲方式構造的線性表。

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

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

int length;//當前長度

intlistsize;//分配的存儲容量

}SqList；

//ElemTypeelem[MAXSIZE];typedef#ElemType;#為根據具體問題確定的數據類型typedefintStatus;4.順序表上基本運算的實現

初始化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){}算法時間復雜度:時間主要花在移動元素上，而移動元素的個數取決于插入元素位置。i=1，需移動n個元素；i=i，需移動n–i+1個元素；i=n+1，需移動0個元素；假設pi是在第i個元素之前插入一個新元素的概率則長度為n

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

pi(n–i+1)n+1i=1設在任何位置插入元素等概率，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;}算法時間復雜度:時間主要花在移動元素上，而移動元素的個數取決于刪除元素位置。i=1，需移動n-

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

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

qi(n–i)ni=1設刪除任何位置的元素等概率，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++;}順序表的基礎要點：無需為表示元素間的邏輯關系而增加額外的存儲空間，存儲密度大（100%）；可隨機存取表中的任一元素。插入或刪除一個元素時，需平均移動表的一半元素，具體的個數與該元素的位置有關，在等概率情況下，插入n/2，刪除(n-1)/2；O(n)

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

2.112.3線性表的鏈式表示和實現

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

structLNode*next；}LNode,*LinkList;單鏈表基本運算實現

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

該運算建立一個空的單鏈表,即創建一個頭結點。

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

釋放單鏈表L占用的內存空間。即逐一釋放全部結點的空間。

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

若單鏈表L沒有數據結點,則返回真,否則返回假。

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

返回單鏈表L中數據結點的個數。

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

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

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

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

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

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

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

存儲空間的占用和分配不同從存儲的角度考慮，順序表的存儲空間是靜態分配的，在程序執行之前必須明確規定它的存儲規模，也就是說事先對“MAXSIZE”要有合適的設定，過大造成浪費，過小造成溢出。而鏈表是動態分配存儲空間的，不用事先估計存儲規模。可見對線性表的長度或存儲規模難以估計時，采用鏈表。線性表運算的實現不同

按序號訪問數據元素，使用順序表優于鏈表。插入刪除操作，使用鏈表優于順序表。

作業：

2.42.19

3.靜態鏈表有些高級程序設計語言并沒有指針類型，如FORTRAN和JAVA。我們可以用數組來表示和實現一個鏈表，稱為靜態鏈表。可定義如下：#defineMAXSIZE1000//最多元素個數typedefstruct{ElemTypedata;intcur;//游標，指示器}component,SLinkList[MAXSIZE];i=s[i].cur;指針后移操作Malloc:i=s[0].cur;第一個可用結點位置

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

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的直接前驅，釋放ks[p].cur=s[k].curFree(k);單鏈表基礎要點在單鏈表中，不能從當前結點出發訪問到任一結點。在單鏈表中，刪除某一指定結點時，必須找到該結點的前驅結點。線性表的鏈式存儲結構是一種順序存取的存儲結構，不具有隨機訪問任一元素的特點。設置頭結點的作用：使在鏈表的第一個位置上的操作和表中其它位置上的操作一致，無需進行特殊處理，對空表和非空表的處理統一。練習：2.22寫一算法，對單鏈表實現就地逆置。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;}}循環鏈表循環鏈表是另一種形式的鏈式存儲結構；可從當前結點出發，訪問到任一結點；循環單鏈表；多重循環鏈表。單循環鏈表設置尾指針rear,比設頭指針更好。連接兩個只設尾指針的單循環鏈表L1和L2操作如下：p=R1–>next; //保存L1的頭結點指針R1->next=R2->next->next; //頭尾連接free(R2->next);//釋放第二個表的頭結點

R2->next=p;

R2b1

bn…×a1

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

希望查找前驅的時間復雜度達到O(1)，我們可以用空間換時間,每個結點再加一個指向前驅的指針域，使鏈表可以進行雙方向查找。用這種結點結構組成的鏈表稱為雙向鏈表。

結點的結構圖:priornextdata雙向鏈表的邏輯表示priordatanextLL2.雙向鏈表(DoubleLinkedList)類型描述typedefstructDuLNode{ElemType

data;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLinkList;雙向循環鏈表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的直接后繼結點的語句序列

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

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

2.82.9循環鏈表算法舉例（1）

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

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

}}

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

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

{s=L；∥s暫存第一結點的指針

t=L->prior;//t暫存尾結點指針

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

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；∥插入原第一結點sp->prior->next=s；p->prior=s；

L=t->next;

}∥算法結束

例

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