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

第二章第二章線性表2.1線性表的概念及運算2.2線性表的順序存儲2.3線性表的鏈?zhǔn)酱鎯?/p>

2.3.1單鏈表

2.3.2單鏈表上的基本運算

2.3.3循環(huán)鏈表

2.3.4雙鏈表2.4順序表和鏈表的比較本章主題：線性表的有關(guān)概念和基本運算教學(xué)目的：掌握線性表的概念和類型定義

教學(xué)重點：線性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)教學(xué)難點：線性表的基本運算2.1線性表的概念及運算

2.1.1線性表的邏輯結(jié)構(gòu)線性表(LinearList)

：由n(n≧0)個數(shù)據(jù)元素(結(jié)點)a1，a2，…，an組成的有限序列。其中數(shù)據(jù)元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表，常常將非空的線性表(n>0)記作：

(a1，a2，…an)

這里的數(shù)據(jù)元素ai(1≦i≦n)只是一個抽象的符號，其具體含義在不同的情況下可以不同。例1、26個英文字母組成的字母表（A，B，C、…、Z）例2、某校從1990年到1999年各種型號的計算機(jī)擁有量的變化情況。（6，17，28，50，92，188）例3、學(xué)生健康情況登記表如下：姓名學(xué)號性別年齡健康情況王小林790631男18

健康陳紅790632女20

一般劉建平790633男21

健康張立立790634男17

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

線性表是一種典型的線性結(jié)構(gòu)。2.1.2線性表的運算線性表的主要操作有如下幾種：1．

Setnull(L)

初始化：構(gòu)造一個空的線性表L。2．

Length(L)

求長度：對給定的線性表L，返回線性表L的數(shù)據(jù)元素的個數(shù)。3．

Get(L,i)

取結(jié)點：對給定的線性表L，返回第i（0≤i≤Length(L)-1）個數(shù)據(jù)元素，否則返回Null。4．

Locate(L,x)

查找定位：對給定的值x，若線性表L中存在一個元素與之相等，則返回該元素在線性表中的位置的序號i，否則返回Null（空）。5．

Insert(L,i,x)

插入：在給定的線性表L中，在第i個元素之前插入數(shù)據(jù)元素x。線性表L長度加1。6．

Delete(L,i)

刪除：在給定的線性表L中，刪除第i個元素。線性表L的長度減1。

對于實際問題中涉及的其它更為復(fù)雜的運算，可用基本運算組合來實現(xiàn)。（見P13頁例2.1）2.2線性表的順序存儲2.2.1順序表

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

LOC(ai+1)=LOC(ai)+c

線性表的第i個數(shù)據(jù)元素ai的存儲位置為：

LOC(ai)=LOC(a1)+(i-1)*c

元素an……..元素ai……..元素a2元素a1bb+cb+(i-1)*cb+(maxlen-1)*c存儲地址內(nèi)存狀態(tài)Loc(元素i)=b+（i-1)*c順序存儲結(jié)構(gòu)示意圖(順序表)：首地址起始地址基地址每個元素所占用的存儲單元個數(shù)由于C語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。又因為除了用數(shù)組來存儲線性表的元素之外，順序表還應(yīng)該用一個變量來表示線性表的長度屬性，所以我們用結(jié)構(gòu)類型來定義順序表類型。

#definemaxsize1024/*定義maxsize

為常數(shù)1024，maxsize

的值作為數(shù)組的最大容量*/

typedefintDataType;

typedefstruc{

DataTypedata[maxsize];

intlast;}Sequenlist;2.2.2順序表上的基本運算在順序表存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作，如線性表的構(gòu)造、第i個元素的訪問。注意：C語言中的數(shù)組下標(biāo)從“0”開始，因此，若L是Sequenlist類型的順序表，則表中第i個元素是L.data[i-1]。

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

1、插入線性表的插入運算是指在表的第i(1≦i≦n+1)個位置上，插入一個新結(jié)點x，

使長度為n的線性表

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

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

(a1，…ai-1，x，ai，…，an)ai-1…..a2a1

aiai+1…an…..a2a1an…..ai+1ai01i-1in-1

插入運算ai-1…..a2a1an…ai+1aix

an……ai+1

aixVoidINSERT(Squenlist*L，DataTypex，inti){

intj;if(i<1||i>((*L).last)+1)/*i值不合法*/

printf(“Positionerror”);returnERRORif((*L).last>=maxsize-1)

printf(“overflow”);returnNULL;for(j=(*L).last;j>=i-1;j--);/*插入位置后的元素依次右移*/

(*L).data[j+1]=(*L).data[j];(*L).data[i-1]=x;/*插入x*/(*L).last++;/*表長加1*/}注意數(shù)組元素從0開始

現(xiàn)在分析算法的復(fù)雜度：這里的問題規(guī)模是表的長度，設(shè)它的值為n。該算法的時間主要花費在循環(huán)的結(jié)點后移語句上，該語句的執(zhí)行次數(shù)（即移動結(jié)點的次數(shù)）是n-i+1。由此可看出，所需移動結(jié)點的次數(shù)不僅依賴于表的長度，而且還與插入位置有關(guān)。當(dāng)i=n+1時，由于循環(huán)變量的終值大于初值，結(jié)點后移語句將不進(jìn)行；這是最好情況，其時間復(fù)雜度O（1）；

當(dāng)i=1時，結(jié)點后移語句將循環(huán)執(zhí)行n次，需移動表中所有結(jié)點，這是最壞情況，其時間復(fù)雜度為O（n）。

由于插入可能在表中任何位置上進(jìn)行，因此需分析算法的平均復(fù)雜度。在長度為n的線性表中第i個位置上插入一個結(jié)點，令Eis(n)表示移動結(jié)點的期望值（即移動的平均次數(shù)），則在第i個位置上插入一個結(jié)點的移動次數(shù)為n-i+1。故

n+1

Eis(n)=∑pi(n-i+1)

i=1式中，pi表示在表中第i個位置上插入一個結(jié)點的概率。不失一般性，假設(shè)在表中任何位置(1≦i≦n+1)上插入結(jié)點的機(jī)會是均等的，則

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

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

n+1

Eis(n)=∑(n-i+1)/(n+1)=n/2i=1

即在順序表上做插入運算，平均要移動表上一半結(jié)點。當(dāng)表長n較大時，算法的效率相當(dāng)?shù)汀ｋm然Eis(n)中n的的系數(shù)較小，但就數(shù)量級而言，它仍然是線性階的。因此算法的平均時間復(fù)雜度為O(n)。2、刪除線性表的刪除運算是指將表的第i(1≦i≦n)結(jié)點刪除，使長度為n的線性表：

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

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

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

VoidDELETE(sequenlist*L，inti){

intj;if(i<1||i>(*L).last+1)

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

該算法的時間分析與插入算法相似，結(jié)點的移動次數(shù)也是由表長n和位置i決定。

若i=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無需移動結(jié)點；若i=1，則前移語句將循環(huán)執(zhí)行n-1次，需移動表中除開始結(jié)點外的所有結(jié)點。這兩種情況下算法的時間復(fù)雜度分別為O(1)和O(n)。

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

n

Ede(n)=∑pi(n-i)i=1

式中，pi表示刪除表中第i個結(jié)點的概率。在等概率的假設(shè)下，

p1=p2=p3=…=pn=1/n

由此可得：

n

Ede(n)=∑(n-i)/n=(n-1)/2i=1

即在順序表上做刪除運算，平均要移動表中約一半的結(jié)點，平均時間復(fù)雜度也是O(n)。2.3線性表的鏈?zhǔn)酱鎯?/p>

線性表的順序表示的特點是用物理位置上的鄰接關(guān)系來表示結(jié)點間的邏輯關(guān)系，這一特點使我們可以隨機(jī)存取表中的任一結(jié)點，但它也使得插入和刪除操作時要移動大量的結(jié)點，同時順序表要求占用連續(xù)的存儲空間，使得預(yù)先分配時難以確定合適的存儲規(guī)模。為了避免以上缺點，下面介紹線性表的另一種存儲方式----鏈?zhǔn)酱鎯Y(jié)構(gòu)，簡稱為鏈表(LinkedList)。2.3.1單鏈表鏈表是指用一組任意的存儲單元來依次存放線性表的結(jié)點，這組存儲單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點間的邏輯關(guān)系，在存儲每個結(jié)點值的同時，還必須存儲指示其后繼結(jié)點的地址（或位置）信息，這個信息稱為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點結(jié)構(gòu)：datanext其中：data域是數(shù)據(jù)域，用來存放結(jié)點的值。next是指針域（亦稱鏈域），用來存放結(jié)點的直接后繼的地址（或位置）。鏈表正是通過每個結(jié)點的鏈域?qū)⒕€性表的n個結(jié)點按其邏輯次序鏈接在一起的。由于上述鏈表的每一個結(jié)點只有一個鏈域，故將這種鏈表稱為單鏈表（SingleLinked)。顯然，單鏈表中每個結(jié)點的存儲地址是存放在其前趨結(jié)點next域中，而開始結(jié)點無前趨，故應(yīng)設(shè)頭指針head指向開始結(jié)點。同時，由于終端結(jié)點無后繼，故終端結(jié)點的指針域為空，即Null（圖示中也可用^表示)。

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

datatypedata;

structnode*next;}linklist;linklist*head,*p;

注意區(qū)分指針變量和結(jié)點變量這兩個不同的概念。

P為動態(tài)變量，它是通過標(biāo)準(zhǔn)函數(shù)生成的，即

p=malloc(sizeof(linklist);

函數(shù)malloc分配了一個類型為linklist的結(jié)點變量的空間，并將其首地址放入指針變量p中。一旦p所指的結(jié)點變量不再需要了，又可通過標(biāo)準(zhǔn)函數(shù)free(p),釋放所指的結(jié)點變量空間。

C語言的庫函數(shù),測算linklist結(jié)點需占用的字節(jié)數(shù)2.3.2單鏈表上的基本運算一、建立單鏈表

假設(shè)線性表中結(jié)點的數(shù)據(jù)類型是字符，我們逐個輸入這些字符型的結(jié)點，并以換行符‘\n’為輸入結(jié)束標(biāo)記。動態(tài)地建立單鏈表的常用方法有如下兩種：

1、頭插法建表該方法從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。

2、尾插法建表頭插法建立鏈表雖然算法簡單，但生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點插入到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。

linklist*CREATLISTF(){charch;

linklist*head,*s;head=NULL;

ch=getchar();while(ch!=‵\n′）{s=malloc(sizeof(linklist));s–>data=ch;s–>next=head;head=s;

ch=getchar();}return(head);}

linklist*CREATLISTR(){charch;

linklist*head*s，*r;;head=NULL;r=NULL;while((ch=getchar()!=‵\n′){s=malloc(sizeof(linklist));s–>data=ch;

if(head=NULL)head=s;else r–>next=s;r=s;}

if(r!=NULL)r–>next=NULL;return(head);}說明：第一個生成的結(jié)點是開始結(jié)點，將開始結(jié)點插入到空表中，是在當(dāng)前鏈表的第一個位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，因為開始結(jié)點的位置存放在頭指針（指針變量）中，而其余結(jié)點的位置是在其前趨結(jié)點的指針域中。算法中的第一個if語句就是用來對第一個位置上的插入操作做特殊處理。算法中的第二個if語句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個字符就是結(jié)束標(biāo)志符，則鏈表head是空表，尾指針r亦為空，結(jié)點*r不存在；否則鏈表head非空，最后一個尾結(jié)點*r是終端結(jié)點，應(yīng)將其指針域置空。如果在鏈表的開始結(jié)點之前附加一個結(jié)點，并稱它為頭結(jié)點，將會帶來以下兩個優(yōu)點：

a、由于開始結(jié)點的位置被存放在頭結(jié)點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其它位置上的操作一致，無需進(jìn)行特殊處理；

b、無論鏈表是否為空，其頭指針是指向頭結(jié)點的非空指針（空表中頭結(jié)點的指針域為空），因此空表和非空表的處理也就統(tǒng)一了。a1a2a3a4^heada1a2a3a4^headhead^head^引入頭結(jié)點后的尾插法建立鏈表算法如下：linklist*CREATLISTR1(){charch;

linklist*head，*s，*r;head=malloc(sizeof(linklist));r=head;while((ch=getchar())!=‵\n′）{s=malloc(sizeof(linklist));s–>data=ch;r–>next=s;r=s;}r–>next=NULL;return(head);}

上述算法里動態(tài)申請新結(jié)點空間時未加錯誤處理，可作下列處理：s=malloc(sizeof(linklist))if(s==NULL)error(〝Nospacefornodecanbeobtained〞);returnERROR;

以上算法的時間復(fù)雜度均為O(n)。二、查找運算

1、按序號查找在鏈表中，即使知道被訪問結(jié)點的序號i，也不能象順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順鏈域next逐個結(jié)點往下搜索，直到搜索到第i個結(jié)點為止。因此，鏈表不是隨機(jī)存取結(jié)構(gòu)。設(shè)單鏈表的長度為n，要查找表中第i個結(jié)點，僅當(dāng)1≦i≦n時，i的值是合法的。但有時需要找頭結(jié)點的位置，故我們將頭結(jié)點看做是第0個結(jié)點，其算法如下：Listnode*GET(linklist*head，inti){

intj;

linklist*p;p=head;j=0;while(p–>next!=NULL&&j<i){p=p–>next;j++;}if(i==j)returnp;elsereturnNULL;}linklist*LOCATE(linklist*head，intkey){p=head–>next;while(p!=NULL&&p–>data!=key)p=p–>next;returnp;}

該算法的執(zhí)行時間亦與輸入實例中的的取值key有關(guān)，其平均時間復(fù)雜度的分析類似于按序號查找，也為O(n)。2、按值查找

按值查找是在鏈表中，查找是否有結(jié)點值等于給定值key的結(jié)點，若有的話，則返回首次找到的其值為key的結(jié)點的存儲位置；否則返回NULL。查找過程從開始結(jié)點出發(fā)，順著鏈表逐個將結(jié)點的值和給定值key作比較。其算法如下：三、插入運算插入運算是將值為x的新結(jié)點插入到表的第i個結(jié)點的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲位置p，然后生成一個數(shù)據(jù)域為x的新結(jié)點，并令結(jié)點*p的指針域指向新結(jié)點，新結(jié)點的指針域指向結(jié)點ai。從而實現(xiàn)三個結(jié)點ai-1，x和ai之間的邏輯關(guān)系的變化，插入過程如下：具體算法如下：

voidINSERT(linklist*head，datetypex，inti){

listnode*p，*s;p=GET(head，i-1);if(p==NULL)error(〝positionerror〞);s=malloc(sizeof(linklist));s–>data=x;s–>next=p–>next;p–>next=s;}

s=malloc(sizeof(linklist));/*生成新結(jié)點*/s->data=x;s->next=p->next;p->next=s;returnOK;}∧anaia1a2Pai-1L

s=malloc(sizeof(linklist));

/*生成新結(jié)點*/

s->data=x;s->next=p->next;p->next=s;returnOK;}∧anaia1a2ai-1PLS

s=malloc(sizeof(linklist));/*生成新結(jié)點*/

s->data=x;

s->next=p->next;p->next=s;returnOK;}∧anaia1a2ai-1PLSx

s=malloc(sizeof(linklist));/*生成新結(jié)點*/s->data=x;s->next=p->next;

p->next=s;returnOK;}∧anaia1a2ai-1xPLSs->next=p->next

s=malloc(sizeof(linklist));/*生成新結(jié)點*/s->data=x;s->next=p->next;p->next=s;

returnOK;}∧anaia1a2ai-1LSxs->next=p->nextPp->next=s

四、刪除運算刪除運算是將表的第i個結(jié)點刪去。因為在單鏈表中結(jié)點ai的存儲地址是在其直接前趨結(jié)點ai-1的指針域next中，所以必須首先找到ai-1的存儲位置p。然后令p–>next指向ai的直接后繼結(jié)點，即把ai從鏈上摘下。最后釋放結(jié)點ai的空間，將其歸還給“存儲池”。具體算法如下：

voidDELETER(linklist*head，inti){linklist*p，*r;p=GET(head，i-1);if(p==NULL||p–>next==NULL)returnERROR;r=p–>next;p–>next=r–>next;free(r);}

設(shè)單鏈表的長度為n，則刪去第i個結(jié)點僅當(dāng)1≦i≦n時是合法的。注意，當(dāng)i=n+1時，雖然被刪結(jié)點不存在，但其前趨結(jié)點卻存在，它是終端結(jié)點。因此被刪結(jié)點的直接前趨*p存在并不意味著被刪結(jié)點就一定存在，僅當(dāng)*p存在（即p!=NULL）且*p不是終端結(jié)點（即p–>next!=NULL）時，才能確定被刪結(jié)點存在。顯然此算法的時間復(fù)雜度也是O(n)。

從上面的討論可以看出，鏈表上實現(xiàn)插入和刪除運算，無須移動結(jié)點，僅需修改指針。ai-1a1aiai+1Lp

if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點*/p->next=q->next;/*修改p結(jié)點的指針域*/free(q);/*刪除并釋放結(jié)點*/}ai-1a1aiai+1Lpq

if(p->next!=NULL){

q=p->next;

/*q指向p的后繼結(jié)點*/p->next=q->next;/*修改p結(jié)點的指針域*/free(q);/*刪除并釋放結(jié)點*/}q=p->nextai-1a1aiai+1Lpq

if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點*/

p->next=q->next;

/*修改p結(jié)點的指針域*/free(q);/*刪除并釋放結(jié)點*/}p->next=q->nextai-1a1aiai+1

if(p->next!=NULL){q=p->next;/*q指向p的后繼結(jié)點*/p->next=q->next;/*修改p結(jié)點的指針域*/free(q);

/*刪除并釋放結(jié)點*/}Lpfree(q)2.3.3循環(huán)鏈表

循環(huán)鏈表是一種頭尾相接的鏈表。其特點是無須增加存儲量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。

單循環(huán)鏈表：在單鏈表中，將終端結(jié)點的指針域NULL改為指向表頭結(jié)點或開始結(jié)點，就得到了單鏈形式的循環(huán)鏈表，并簡單稱為單循環(huán)鏈表。為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個頭結(jié)點。這樣，空循環(huán)鏈表僅有一個自成循環(huán)的頭結(jié)點表示。如下圖所示：

將最后一個結(jié)點的空指針改為指向頭結(jié)點，從任一結(jié)點出發(fā)均可找到其它結(jié)點。a1a2an∧a3L…..帶頭結(jié)點的單鏈表a1a2ana3L…..循環(huán)單鏈表空表在用頭指針表示的單循環(huán)鏈表中，找開始結(jié)點a1的時間是O(1)，然而要找到終端結(jié)點an，則需從頭指針開始遍歷整個鏈表，其時間是O(n)

在很多實際問題中，表的操作常常是在表的首尾位置上進(jìn)行，此時頭指針表示的單循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來表示單循環(huán)鏈表，則查找開始結(jié)點a1和終端結(jié)點an都很方便，它們的存儲位置分別是：

(rear–>next)—>next和rear

顯然，查找時間都是O(1)。因此，實際中多采用尾指針表示單循環(huán)鏈表。由于循環(huán)鏈表中沒有NULL指針，故涉及遍歷操作時，其終止條件就不再像非循環(huán)鏈表那樣判斷p或p—>next是否為空，而是判斷它們是否等于某一指定指針，如頭指針或尾指針等。例1.

在鏈表上實現(xiàn)將兩個線性表(a1，a2，a3，…an)和(b1，b2，b3，…bm)鏈接成一個線性表（a1，…，an，b1，，…，bm

）的運算。

linklist*connect(ra，rb)

linklist*ra,*rb;{

linklist*p;p=ra—>next;

ra—>next=(rb—>next)—>next;free(rb—>next);

rb—>next=p;return(rb);}例2.

一元多項式的表示及相加

符號多項式的表示及其操作是線性表處理的典型用例，在數(shù)學(xué)上，一個一元多項式Pn(x)可以表示為：

Pn(x)=a0+a1x+a2x2+…+anxn

(最多有n+1項)

aixi是多項式的第i項（0≤i≤n），其中ai為系數(shù)，x為變量，i為指數(shù)。它有n+1個系數(shù)，因此，在計算機(jī)里，它可用一個線性表P來表示：P=（a0,a1,a2,…，an）假設(shè)Qn(x)是一元m次多項式，同樣可用線性表Q來示：Q=（b0,b1,b2,…，bm）若m<n，則兩個多項式相加的結(jié)果Rn(x)=Pn(x)+Qn(x)可用線性表R來表示：R=（a0+b0,a1+b1,a2+b2,…,am+bm,am+1,…,an）可以對P、Q和R采用順序存儲結(jié)構(gòu)，也可以采用鏈表存儲結(jié)構(gòu)。Coefexpnextexponent指數(shù)指針域coefficient系數(shù)A(x)=5-4x3+6x550-4365^A使用順序存儲結(jié)構(gòu)可以使多項式相加的算法十分簡單。但當(dāng)多項式中存在大量的零系數(shù)時，這種表示方式就會浪費大量存儲空間。為了有效而合理地利用存儲空間，可以用鏈?zhǔn)酱鎯Y(jié)構(gòu)來表示多項式。采用鏈?zhǔn)酱鎯Y(jié)構(gòu)表示多項式時，多項式中每一個非零系數(shù)的項構(gòu)成鏈表中的一個結(jié)點，而對于系數(shù)為零的項則不需表示。若采用鏈表表示多項式時，每個結(jié)點的數(shù)據(jù)域有兩項：系數(shù)和指數(shù)。（注意：表示多項式的鏈表應(yīng)該是有序鏈表） 多項式：A=7+3x+9x8+5x17 B=8x+22x7-9x8B81227-98∧假設(shè)多項式A=7+3x+9x8+5x17與B=8x+22x7-9x8已經(jīng)用單鏈表表示，其頭指針分別為A與B，如下圖所示。兩式求和后，結(jié)果保留在A的單鏈表之中，。多項式鏈表中的每一個非零項結(jié)點結(jié)構(gòu)用C語言描述如下：Typedef

struct

pnode{intexp;/*指數(shù)為正整數(shù)*/doublecoef;/*系數(shù)為雙精度型*/

struct

pnode*next;/*指針域*/}polynodeA517∧coefexpnnext703198其運算規(guī)則如下：假設(shè)指針qa和qb分別指向多項式A和多項式B中當(dāng)前進(jìn)行比較的某個結(jié)點，則比較兩個結(jié)點的數(shù)據(jù)域的指數(shù)項，有三種情況：（1）指針qa所指結(jié)點的指數(shù)值＜指針qb所指結(jié)點的指數(shù)值時，則保留qa指針?biāo)赶虻慕Y(jié)點，qa指針后移；（2）指針qa所指結(jié)點的指數(shù)值＞指針qb所指結(jié)點的指數(shù)值時，則將qb指針?biāo)赶虻慕Y(jié)點插入到qa所指結(jié)點前，qb指針后移；（3）指針qa所指結(jié)點的指數(shù)值＝指針qb所指結(jié)點的指數(shù)值時，將兩個結(jié)點中的系數(shù)相加,若和不為零，則修改qa所指結(jié)點的系數(shù)值，同時釋放qb所指結(jié)點；反之，從多項式A的鏈表中刪除相應(yīng)結(jié)點，并釋放指針qa和qb所指結(jié)點。多項式：A=7+3x+9x8+5x17 B=8x+22x7-9x8

結(jié)果仍保留在A的單鏈表之中。A703

198517B8

1227-98∧∧qbqa·算法：指數(shù)相等：若系數(shù)之和為零，則兩結(jié)點都刪除。qa、qb

后移。

否則只刪qb->。修改qa->系數(shù)為兩者之和。qa、qb

后移。

qa->指數(shù)?。?/p>

qa

后移。

qa->指數(shù)大：將qb->插入在qa->之前。插入之后，qb

后移。

注意：把兩個多項式的多余部分，插入在qa->之后。AA81227B703198517∧∧qbqaB-98BBA81227-98∧qbqaha703198517∧7011198517∧qbqaha227-98∧Aqbqaha227-98∧7011198517∧A227BqbqaA70111517∧Bqbha70111517∧227【算法】polynode*POLYADD(polynode*A,polynode*B){polynode*qa,*qb,*s,*r,*Ch;qa=A->next;qb=B->next; /*qa和qb分別指向兩個鏈表的第一結(jié)點*/r=qa;Ch=A; /*將鏈表A作為相加后的和鏈表*/while(qa!=NULL&&qb!=NULL) /*兩鏈表均非空*/{if(qa->exp==qb->exp) /*兩者指數(shù)值相等*/{x=qa->coef+qb->coef;if(x!=0){qa->coef=x;r->next=qa;r=qa;s=qb++;free(s);qa++;} /*相加后系數(shù)不為零時*/else{s=qa++;free(s);s=qb++;free(s);}/*相加后系數(shù)為零時*/}elseif(qa->exp<qb->exp){r->next=qa;r=qa;qa++;}/*多項式A的指數(shù)值小*/else{r->next=qb;r=qb;qb++;} /*多項式B的指數(shù)值小*/}if(qa==NULL)r->next=qb;elser->next=qa; /*鏈接多項式A或B中的剩余結(jié)點*/return(Ch);}

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

形式描述為：

typedef

struct

dnode{

datatypedata;

struc

dnode*prior，*next;}dlinklist;

dlinklist*head;priordatanext數(shù)據(jù)域R右指針域L左指針域指向前驅(qū)結(jié)點指向后繼結(jié)點2.3.4雙鏈表^a1a2a3a4^head^a1a2a3^head^^head

和單鏈表類似，雙鏈表一般也是由頭指針唯一確定的，增加頭結(jié)點也能使雙鏈表上的某些運算變得方便，將頭結(jié)點和尾結(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。設(shè)指針p指向某一結(jié)點，則雙向鏈表結(jié)構(gòu)的對稱性可用下式描述：

(p—>prior)—>next=p=(p—>next)—>prior

即結(jié)點*p的存儲位置既存放在其前趨結(jié)點*(p—>prior)的直接后繼指針域中，也存放在它的后繼結(jié)點*(p—>next)的直接前趨指針域中。a1a2a3headheada2a3a4heada1雙向鏈表的前插操作算法如下：voiddinsertbefor(dlinklist*p，datatypex){

dlinklist*s=malloc(sizeof(dlinklist));s—>data=x;s—>prior=p—>prior;s—>next=p;

p—>prior—>next=s;p—>prior=s;}xsyyp這兩步的順序不能顛倒雙向鏈表刪除結(jié)點*p自身的操作算法如下：

voidddeletenode(dlinklist*p){p–>prior–>next=p–>next;p–>next–>prior=p–>prior;free(p);}xp注意：與單鏈表的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時修改兩個方向上的指針。上述兩個算法的時間復(fù)雜度均為O(1)。

適用于沒有動態(tài)存儲分配功能的語言，如FORTRAN、COBOL等；當(dāng)然也可用于C等高級語言。缺點：必須預(yù)估存區(qū)的大小，造成浪費。優(yōu)點：插、刪操作省時。定義一個規(guī)模較大的結(jié)構(gòu)數(shù)組作為備用結(jié)點空間（即存儲池）。當(dāng)申請結(jié)點時，從存儲池內(nèi)取出一個結(jié)點；當(dāng)釋放結(jié)點時，將結(jié)點歸還存儲池內(nèi)。每個點應(yīng)含有兩個域：data域用來存放結(jié)點的數(shù)據(jù)，next域用來存放游標(biāo)。由于必須為備用結(jié)點空間預(yù)先分配一個連續(xù)的空間，故把這種用游標(biāo)實現(xiàn)的鏈表稱為靜態(tài)鏈表。2.3.4靜態(tài)鏈表設(shè)靜態(tài)鏈表的形式定義如下：

#defineMaxSize1024

typedefstruct{datatypedata;intnext;}node;//結(jié)點類型

在鏈表沒有使用前，各個結(jié)點已經(jīng)形成一個鏈，指針AV指示鏈表的第一個結(jié)點。由AV指向的鏈表稱為可利用空間表，可用于管理結(jié)點的分配和回收。當(dāng)用戶需要結(jié)點時，就從AV為頭指針的鏈中摘下第一個結(jié)點分配出去，并通過指針p指示它；頭指針AV移動到可利用空間表的第二個結(jié)點，該指針實際指示的是下一次可分配的結(jié)點地址。當(dāng)用戶不再需要某個結(jié)點時，只需把它鏈入AV所指示的鏈表的最前端，并讓AV指示它即可2.4順序表和鏈表的比較

1.基于空間的考慮

順序表的存儲空間