第二章線性表2.1線性表的類型定義2.2線性表的順序表示和實現2.3線性表的鏈式表示和實現

2.3.1線性鏈表

2.3.2循環鏈表

2.3.3雙向鏈表2.4一元多項式的表示及相加1/29/20251第二章線性表2.1線性表的類型定義線性表(LinearList)：由n(n≧)個數據元素(結點)a1，a2，…an組成的有限序列。其中數據元素的個數n定義為表的長度。當n=0時稱為空表，常常將非空的線性表(n>0)記作：

(a1，a2，…,an)這里的數據元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例1、26個英文字母組成的字母表（A，B，C、…、Z）例2、某校從1978年到1983年各種型號的計算機擁有量的變化情況。（6，17，28，50，92，188）

1/29/20252第二章線性表例3、學生健康情況登記表如下：姓名學號性別年齡健康情況王小林790631男18

健康陳紅790632女20

一般劉建平790633男21

健康張立立790634男17

神經衰弱……..……..…….…….…….1/29/20253第二章線性表例4、一副撲克的點數（2，3，4，…，J，Q，K，A）從以上例子可看出線性表的邏輯特征是：在非空的線性表中，有且僅有一個開始結點a1，它沒有直接前趨，而僅有一個直接后繼a2；有且僅有一個終端結點an，它沒有直接后繼，而僅有一個直接前趨an-1；其余的內部結點ai(2≦i≦n-1)都有且僅有一個直接前趨ai-1和一個直接后繼ai+1。

線性表是一種典型的線性結構。

1/29/20254第二章線性表含有n個元素的線性表是一個數據結構

Linear_list=(D,R)其中D={ai|ai

D0,i=1,2,,n,n0}R={N},N={<ai-1,

ai>|ai-1,

ai

D0

,i=2,3,,n}D0為某個數據對象（可為任何數據類型）對應的邏輯圖如下：線性表與線性結構的關系。數據的運算是定義在邏輯結構上的，而運算的具體實現則是在存儲結構上進行的。抽象數據類型的定義為：P19a1a2ai-1aian……1/29/20255第二章線性表線性表的操作還有合并、拷貝、排序等復雜運算

例2-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-en，e)}}

時間復雜度為O(mn)

1/29/20256第二章線性表例2-2巳知線性表LA和線性表LB中的數據元素按值非遞減有序排列，現要求將LA和LB歸并為一個新的線性表LC，且LC中的元素仍按值非遞減有序排列。此問題的算法如下：

voidmergelist(listla，listlb，list&lc)

initlist(lc);I=j=1;k=0;la-len=listlength(la);lb-len=listlength(lb);while((I<=la-len)&&(j<=lb-len)){

getelem(la，I，ai);getelem(lb，j，bj);1/29/20257第二章線性表if(ai<=bj){listinsert(lc，++k，ai);++I;}

else{listinsert(lc，++k，bj);++j;}}while(I<=la-len){

getelem((la，I++，ai);listinsert(lc，++k，ai);}while(j<=lb-len){

getelem((lb，j++，bj);listinsert(lc，++k，bi);}}//MergeList算法的時間復雜度分析(O(m+n))

1/29/20258第二章線性表

2.2線性表的順序存儲結構1順序表把線性表的結點按邏輯順序依次存放在一組地址連續的存儲單元里。用這種方法存儲的線性表簡稱順序表。假設線性表的每個元素需占用l個存儲單元，并以所占的第一個單元的存儲地址作為數據元素的存儲位置。則線性表中第I+1個數據元素的存儲位置LOC(ai+1)和第i個數據元素的存儲位置LOC(aI)之間滿足下列關系：

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

線性表的第i個數據元素ai的存儲位置為：

LOC(ai)=LOC(a1)+(I-1)*l

1/29/20259第二章線性表由于C語言中的一維數組也是采用順序存儲表示，故可以用數組類型來描述順序表。又因為除了用數組來存儲線性表的元素之外，順序表還應該用一個變量來表示線性表的長度屬性，所以我們用結構類型來定義順序表類型。

#defineListSize100

typedef

int

DataType;

typedef

struc{

DataType

data[ListSize];

intlength;}Sqlist;1/29/202510第二章線性表2順序表上實現的基本操作

在順序表存儲結構中，很容易實現線性表的一些操作，如線性表的構造、第i個元素的訪問。注意：C語言中的數組下標從“0”開始，因此，若L是Sqlist類型的順序表，則表中第i個元素是l.data[I-1]。

以下主要討論線性表的插入和刪除兩種運算。

1、插入線性表的插入運算是指在表的第I(1≦i≦n+1個位置上，插入一個新結點x，1/29/202511第二章線性表使長度為n的線性表

(a1，…ai-1，ai，…，an)

變成長度為n+1的線性表

(a1，…ai-1，x，ai，…，an)算法如下

VoidInsertList(Sqlist*L，DataTypex，intI){

intj;if(I<1||I>l.length+1)

printf(“Positionerror”);returnERROR

1/29/202512第二章線性表

if(l.length>=ListSize)

printf(“overflow”);exit(overflow);for(j=l.length-1;j>=I-1;j--)l.data[j+1]=l.data[j];l.data[I-1]=x;l.length++;}1/29/202513第二章線性表算法的復雜度分析這里的問題規模是表的長度，設它的值為n。該算法的時間主要化費在循環的結點后移語句上，該語句的執行次數（即移動結點的次數）是n-I+1。由此可看出，所需移動結點的次數不僅依賴于表的長度，而且還與插入位置有關。當I=n+1時，由于循環變量的終值大于初值，結點后移語句將不進行；這是最好情況，其時間復雜度O（1）；當I=1時，結點后移語句將循環執行n次，需移動表中所有結點，這是最壞情況，其時間復雜度為O（n）。1/29/202514第二章線性表由于插入可能在表中任何位置上進行，因此需分析算法的平均復雜度在長度為n的線性表中第i個位置上插入一個結點，令Eis(n)表示移動結點的期望值（即移動的平均次數），則在第i個位置上插入一個結點的移動次數為n-I+1。故

Eis(n)=

pi(n-I+1)

不失一般性，假設在表中任何位置(1≦i≦n+1)上插入結點的機會是均等的，則

p1=p2=p3=…=pn+1=1/(n+1)

因此，在等概率插入的情況下，

Eis(n)=

(n-I+1)/(n+1)=n/2

1/29/202515第二章線性表

也就是說，在順序表上做插入運算，平均要移動表上一半結點。當表長n較大時，算法的效率相當低。雖然Eis(n)中n的的系數較小，但就數量級而言，它仍然是線性階的。因此算法的平均時間復雜度為O(n)。

2、刪除線性表的刪除運算是指將表的第i(1≦i≦n)結點刪除，使長度為n的線性表：

(a1，…ai-1，ai，ai+1…，an)

變成長度為n-1的線性表

(a1，…ai-1，ai+1，…，an)1/29/202516第二章線性表

VoiddeleteList(Sqlist*L，intI){

intj;if(I<1||I>l.length)

printf(“Positionerror”);returnERRORfor(j=i;j<=l.length-1;j++)l.data[j-1]=l.data[j];l.length--;}

1/29/202517第二章線性表該算法的時間分析與插入算法相似，結點的移動次數也是由表長n和位置i決定。若I=n，則由于循環變量的初值大于終值，前移語句將不執行，無需移動結點；若I=1，則前移語句將循環執行n-1次，需移動表中除開始結點外的所有結點。這兩種情況下算法的時間復雜度分別為O(1)和O(n)。

刪除算法的平均性能分析與插入算法相似。在長度為n的線性表中刪除一個結點，令Ede(n)表示所需移動結點的平均次數，刪除表中第i個結點的移動次數為n-i，故

Ede(n)=

pi(n-I)

式中，pi表示刪除表中第i個結點的概率。1/29/202518第二章線性表在等概率的假設下，p1=p2=p3=…=pn=1/n

可得：

Ede(n)=

(n-I)/n=(n-1)/2

即在順序表上做刪除運算，平均要移動表中約一半的結點，平均時間復雜度也是O(n)。可討論線性表的其它操作在順序存儲結構上的實現方法和時間復雜度的分析。可討論例2-1和例2-2的操作在順序存儲結構的線性表中的實現方法和時間復雜度的分析。

1/29/202519第二章線性表建立一個順序存儲的線性表

voidcreatsqlist(SqList*L){inti;

pritnt(“請輸入線性表元素個數\n”);

scanf(“%d”,&(*L).len);

printf(“請輸入%d個元素\n”,(*L).len);for(i=0;I<(*L).len;I++)scanf(“%d”,&(*L).elem[I].key);}

1/29/202520第二章線性表順序存儲結構的優缺點優點：隨機存取缺點：1插入、刪除需移動大量元素

2存儲空間不能充分利用

3表的容量難以擴充1/29/202521第二章線性表2.3線性表的鏈式表示和實現線性表的順序表示的特點是用物理位置上的鄰接關系來表示結點間的邏輯關系，這一特點使我們可以隨機存取表中的任一結點，但它也使得插入和刪除操作會移動大量的結點.為避免大量結點的移動，我們介紹線性表的另一種存儲方式--鏈式存儲結構，簡稱為鏈表(LinkedList)。1/29/202522第二章線性表1線性鏈表（單鏈表）鏈表是指用一組任意的存儲單元來依次存放線性表的結點，這組存儲單元即可以是連續的，也可以是不連續的，甚至是零散分布在內存中的任意位置上的。因此，鏈表中結點的邏輯次序和物理次序不一定相同。為了能正確表示結點間的邏輯關系，在存儲每個結點值的同時，還必須存儲指示其后繼結點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結點結構：1/29/202523第二章線性表

其中：存儲數據元素信息的data域是數據域，用來存放結點的值。next是指針域（亦稱鏈域），用來存放結點的直接后繼的地址（或位置）。鏈表正是通過每個結點的鏈域將線性表的n個結點按其邏輯次序鏈接在一起的。由于上述鏈表的每一個結只有一個鏈域，故將這種鏈表稱為線性鏈表或單鏈表（SingleLinked)。

顯然，單鏈表中每個結點的存儲地址是存放在其前趨結點next域中，而開始結點無前趨，故應設頭指針head指向開始結點。同時，由于終端結點無后繼，故終端結點的指針域為空，即null（圖示中也可用^表示)。例1、線性表:(bat，cat，eat，fat，hat，jat，lat，mat)datanext1/29/202524第二章線性表單鏈表示意圖如下：

……110……130135……160頭指針head165170……200205…………………hat200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………

1651/29/202525第二章線性表headbat

cat

eat

mat^…單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例如：若頭指針名是head，則把鏈表稱為表head。用C語言描述的單鏈表如下：Typedefchardatatype;

Typedef

structnode{

datatypedata;

structnode*next;}listnode;1/29/202526第二章線性表

typedef

listnode*linklist;

listnode*p;

linklisthead;注意區分指針變量和結點變量這兩個不同的概念。P為動態變量，它是通過標準函數生成的，即

p=(listnode*)malloc(sizeof(listnode));函數malloc分配了一個類型為listnode的結點變量的空間，并將其首地址放入指針變量p中。一旦p所指的結點變量不再需要了，又可通過標準函數

free(p)釋放所指的結點變量空間。指針變量P和（其值為結點地址）和結點變量*P之間的關系。1/29/202527第二章線性表一、建立單鏈表假設線性表中結點的數據類型是字符，我們逐個輸入這些字符型的結點，并以換行符‘\n’為輸入結束標記。動態地建立單鏈表的常用方法有如下兩種：

1、頭插法建表該方法從一個空表開始，重復讀入數據，生成新結點，將讀入數據存放到新結點的數據域中，然后將新結點插入到當前鏈表的表頭上，直到讀入結束標志為止。1/29/202528第二章線性表

linklistcreatelistf(void){charch;

linklisthead;

listnode*p;head=null;

ch=getchar();while(ch!=‵\n′{p=(listnode*)malloc(sizeof(listnode));

p–>data=ch;p–>next=head;

1/29/202529第二章線性表

head=p;

ch=getchar();}return(head);}1/29/202530第二章線性表

listlinkcreatelist(intn){intdata;

linklisthead;

listnode*phead=null;for(i=n;i>0;--i){p=(listnode*)malloc(sizeof(listnode));

scanf((〝%d〞，&p–>data);p–>next=head;head=p;}1/29/202531第二章線性表

return(head);}2、尾插法建表

頭插法建立鏈表雖然算法簡單，但生成的鏈表中結點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結點插入到當前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當前鏈表的尾結點。例：1/29/202532第二章線性表

linklist

creater(){charch;

linklisthead;

listnode*p，*r;//(，*head;)head=NULL;r=NULL;while((ch=getchar()!=‵\n′){p=(listnode*)malloc(sizeof(listnode));p–>data=ch;if(head=NULL)head=p;else

1/29/202533第二章線性表

r–>next=p;r=p;}if(r!=NULL)r–>next=NULL;return(head);}

說明：第一個生成的結點是開始結點，將開始結點插入到空表中，是在當前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開始結點的位置是存放在頭指針（指針變量）中，

1/29/202534第二章線性表而其余結點的位置是在其前趨結點的指針域中。算法中的第一個if語句就是用來對第一個位置上的插入操作做特殊處理。算法中的第二個if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字符就是結束標志符，則鏈表head是空表，尾指針r亦為空，結點*r不存在；否則鏈表head非空，最后一個尾結點*r是終端結點，應將其指針域置空。如果我們在鏈表的開始結點之前附加一個結點，并稱它為頭結點，那么會帶來以下兩個優點：

a、由于開始結點的位置被存放在頭結點的指針域中，所以在鏈表的第一個位置上的操作就1/29/202535第二章線性表和在表的其它位置上的操作一致，無需進行特殊處理；b、無論鏈表是否為空，其頭指針是指向頭結點的非空指針（空表中頭結點的指針域為空），因此空表和非空表的處理也就統一了。其算法如下：linklistcreatelistr1(){charch;

linklisthead=(linklist)malloc(sizeof(listnode));

listnode*p，*r

1/29/202536第二章線性表

r=head;while((ch=getchar())!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=p;r=p;}r–>next=NULL;return(head);}1/29/202537第二章線性表上述算法里動態申請新結點空間時未加錯誤處理，可作下列處理：

p=(listnode*)malloc(sizeof(listnode))if(p==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;

以上算法的時間復雜度均為O(n)。1/29/202538第二章線性表二、查找運算

1、按序號查找在鏈表中，即使知道被訪問結點的序號i，也不能象順序表中那樣直接按序號i訪問結點，而只能從鏈表的頭指針出發，順鏈域next逐個結點往下搜索，直到搜索到第i個結點為止。因此，鏈表不是隨機存取結構。設單鏈表的長度為n，要查找表中第i個結點，僅當1≦i≦n時，i的值是合法的。但有時需要找頭結點的位置，故我們將頭結點看做是第0個結點，其算法如下：1/29/202539第二章線性表Listnode*getnode(linklisthead，inti){

intj;

listnode*p;p=head;j=0;while(p–>next&&j<I){p=p–>next;j++;}if(i==j)returnp;1/29/202540第二章線性表

elsereturnNULL;}

2、按值查找按值查找是在鏈表中，查找是否有結點值等于給定值key的結點，若有的話，則返回首次找到的其值為key的結點的存儲位置；否則返回NULL。查找過程從開始結點出發，順著鏈表逐個將結點的值和給定值key作比較。其算法如下：1/29/202541第二章線性表Listnode*locatenode(linklisthead，intkey){

listnode*p=head–>next;while(p&&p–>data!=key)p=p–>next;returnp;}

該算法的執行時間亦與輸入實例中的的取值key有關，其平均時間復雜度的分析類似于按序號查找，也為O(n)。1/29/202542第二章線性表三、插入運算插入運算是將值為x的新結點插入到表的第i個結點的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲位置p，然后生成一個數據域為x的新結點*p，并令結點*p的指針域指向新結點，新結點的指針域指向結點ai。從而實現三個結點ai-1，x和ai之間的邏輯關系的變化，插入過程如：1/29/202543第二章線性表單鏈表插入結點時指針變化情況

b

a

a

b

x

ppq插入前插入后snext=pnext;pnext=s;1/29/202544第二章線性表具體算法如下：

voidinsertnode(linklisthead，datetypex，inti){

listnode*p，*q;p=getnode(head，i-1);if(p==NULL)error(〝positionerror〞);q=(listnode*)malloc(sizeof(listnode));q–>data=x;

q–>next=p–next;p–>next=q;

}

1/29/202545第二章線性表設鏈表的長度為n，合法的插入位置是1≦i≦n+1。注意當i=1時，getnode找到的是頭結點，當

i=n+1時，getnode找到的是結點an。因此，用i-1做實參調用getnode時可完成插入位置的合法性檢查。算法的時間主要耗費在查找操作getnode上，故時間復雜度亦為O(n)。四、刪除運算刪除運算是將表的第i個結點刪去。因為在單鏈表中結點ai的存儲地址是在其直接前趨結點

ai-1的指針域next中，所以我們必須首先找到

1/29/202546第二章線性表

ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結點，即把ai從鏈上摘下。最后釋放結點ai的空間，將其歸還給“存儲池”。具體算法如下：

bpc（單鏈表刪除結點時指針變化情況）××rap->next=p->next->next1/29/202547第二章線性表

voiddeletelist(linklisthead，

inti){listnode*p，*r;p=getnode(head，i-1);if(p==NULL||p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;free(r);}1/29/202548第二章線性表設單鏈表的長度為n，則刪去第i個結點僅當1≦i≦n時是合法的。注意，當i=n+1時，雖然被刪結點不存在，但其前趨結點卻存在，它是終端結點。因此被刪結點的直接前趨*p存在并不意味著被刪結點就一定存在，僅當*p存在（即p!=NULL）且*p不是終端結點（即p–>next!=NULL）時，才能確定被刪結點存在。顯然此算法的時間復雜度也是O(n)。從上面的討論可以看出，鏈表上實現插入和刪除運算，無須移動結點，僅需修改指針。1/29/202549第二章線性表2.3.2循環鏈表

循環鏈表時一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環鏈表：在單鏈表中，將終端結點的指針域NULL改為指向表頭結點的或開始結點，就得到了單鏈形式的循環鏈表，并簡單稱為單循環鏈表。為了使空表和非空表的處理一致，循環鏈表中也可設置一個頭結點。這樣，空循環鏈表僅有一個自成循環的頭結點表示。如下圖所示：1/29/202550第二章線性表

a1an

….head⑴非空表⑵空表在用頭指針表示的單鏈表中，找開始結點a1的時間是O(1)，然而要找到終端結點an，則需從頭指針開始遍歷整個鏈表，其時間是O(n)1/29/202551第二章線性表在很多實際問題中，表的操作常常是在表的首尾位置上進行，此時頭指針表示的單循環鏈表就顯得不夠方便.如果改用尾指針rear來表示單循環鏈表，則查找開始結點a1和終端結點an都很方便，它們的存儲位置分別是(rear–>next)—>next和rear，顯然，查找時間都是O(1)。因此，實際中多采用尾指針表示單循環鏈表。由于循環鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指什或尾指針等。1/29/202552第二章線性表例、在鏈表上實現將兩個線性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)鏈接成一個線性表的運算。

linklist

connect(linklist

reara，linklist

rearb){

linklistp=reara—>next;

reara—>next=(rearb—>next)—>next

free(rearb—>next);

rearb—>next=p;

return(rearb);}1/29/202553第二章線性表2.3.3雙鏈表

雙向鏈表(Doublelinkedlist):在單鏈表的每個結點里再增加一個指向其直接前趨的指針域prior。這樣就形成的鏈表中有兩個方向不同的鏈，故稱為雙向鏈表。形式描述為：

typedefstructdlistnode{

datatypedata;

strucdlistnode