2￥-two(天津科技大學(xué))

第二章線(xiàn)性表2.1線(xiàn)性表的類(lèi)型定義2.2線(xiàn)性表的順序表示和實(shí)現(xiàn)2.3線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

2.3.1線(xiàn)性鏈表

2.3.2循環(huán)鏈表

2.3.3雙向鏈表2.4一元多項(xiàng)式的表示及相加10/8/20241第二章線(xiàn)性表2.1線(xiàn)性表的類(lèi)型定義線(xiàn)性表(LinearList)：由n(n≧)個(gè)數(shù)據(jù)元素(結(jié)點(diǎn))a1，a2，…an組成的有限序列。其中數(shù)據(jù)元素的個(gè)數(shù)n定義為表的長(zhǎng)度。當(dāng)n=0時(shí)稱(chēng)為空表，常常將非空的線(xiàn)性表(n>0)記作：

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

10/8/20242第二章線(xiàn)性表例3、學(xué)生健康情況登記表如下：姓名學(xué)號(hào)性別年齡健康情況王小林790631男18

健康陳紅790632女20

一般劉建平790633男21

健康張立立790634男17

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

線(xiàn)性表是一種典型的線(xiàn)性結(jié)構(gòu)。

10/8/20244第二章線(xiàn)性表含有n個(gè)元素的線(xiàn)性表是一個(gè)數(shù)據(jù)結(jié)構(gòu)

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為某個(gè)數(shù)據(jù)對(duì)象（可為任何數(shù)據(jù)類(lèi)型）對(duì)應(yīng)的邏輯圖如下：線(xiàn)性表與線(xiàn)性結(jié)構(gòu)的關(guān)系。數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)則是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。抽象數(shù)據(jù)類(lèi)型的定義為：P19a1a2ai-1aian……10/8/20245第二章線(xiàn)性表線(xiàn)性表的操作還有合并、拷貝、排序等復(fù)雜運(yùn)算

例2-1利用兩個(gè)線(xiàn)性表LA和LB分別表示兩個(gè)集合A和B，現(xiàn)要求一個(gè)新的集合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)}}

時(shí)間復(fù)雜度為O(mn)

10/8/20246第二章線(xiàn)性表例2-2巳知線(xiàn)性表LA和線(xiàn)性表LB中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將LA和LB歸并為一個(gè)新的線(xiàn)性表LC，且LC中的元素仍按值非遞減有序排列。此問(wèn)題的算法如下：

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);10/8/20247第二章線(xiàn)性表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算法的時(shí)間復(fù)雜度分析(O(m+n))

10/8/20248第二章線(xiàn)性表

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

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

線(xiàn)性表的第i個(gè)數(shù)據(jù)元素ai的存儲(chǔ)位置為：

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

10/8/20249第二章線(xiàn)性表由于C語(yǔ)言中的一維數(shù)組也是采用順序存儲(chǔ)表示，故可以用數(shù)組類(lèi)型來(lái)描述順序表。又因?yàn)槌擞脭?shù)組來(lái)存儲(chǔ)線(xiàn)性表的元素之外，順序表還應(yīng)該用一個(gè)變量來(lái)表示線(xiàn)性表的長(zhǎng)度屬性，所以我們用結(jié)構(gòu)類(lèi)型來(lái)定義順序表類(lèi)型。

#defineListSize100

typedef

int

DataType;

typedef

struc{

DataType

data[ListSize];

intlength;}Sqlist;10/8/202410第二章線(xiàn)性表2順序表上實(shí)現(xiàn)的基本操作

在順序表存儲(chǔ)結(jié)構(gòu)中，很容易實(shí)現(xiàn)線(xiàn)性表的一些操作，如線(xiàn)性表的構(gòu)造、第i個(gè)元素的訪(fǎng)問(wèn)。注意：C語(yǔ)言中的數(shù)組下標(biāo)從“0”開(kāi)始，因此，若L是Sqlist類(lèi)型的順序表，則表中第i個(gè)元素是l.data[I-1]。

以下主要討論線(xiàn)性表的插入和刪除兩種運(yùn)算。

1、插入線(xiàn)性表的插入運(yùn)算是指在表的第I(1≦i≦n+1個(gè)位置上，插入一個(gè)新結(jié)點(diǎn)x，10/8/202411第二章線(xiàn)性表使長(zhǎng)度為n的線(xiàn)性表

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

變成長(zhǎng)度為n+1的線(xiàn)性表

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

VoidInsertList(Sqlist*L，DataTypex，intI){

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

printf(“Positionerror”);returnERROR

10/8/202412第二章線(xiàn)性表

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++;}10/8/202413第二章線(xiàn)性表算法的復(fù)雜度分析這里的問(wèn)題規(guī)模是表的長(zhǎng)度，設(shè)它的值為n。該算法的時(shí)間主要化費(fèi)在循環(huán)的結(jié)點(diǎn)后移語(yǔ)句上，該語(yǔ)句的執(zhí)行次數(shù)（即移動(dòng)結(jié)點(diǎn)的次數(shù)）是n-I+1。由此可看出，所需移動(dòng)結(jié)點(diǎn)的次數(shù)不僅依賴(lài)于表的長(zhǎng)度，而且還與插入位置有關(guān)。當(dāng)I=n+1時(shí)，由于循環(huán)變量的終值大于初值，結(jié)點(diǎn)后移語(yǔ)句將不進(jìn)行；這是最好情況，其時(shí)間復(fù)雜度O（1）；當(dāng)I=1時(shí)，結(jié)點(diǎn)后移語(yǔ)句將循環(huán)執(zhí)行n次，需移動(dòng)表中所有結(jié)點(diǎn)，這是最壞情況，其時(shí)間復(fù)雜度為O（n）。10/8/202414第二章線(xiàn)性表由于插入可能在表中任何位置上進(jìn)行，因此需分析算法的平均復(fù)雜度在長(zhǎng)度為n的線(xiàn)性表中第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)，令Eis(n)表示移動(dòng)結(jié)點(diǎn)的期望值（即移動(dòng)的平均次數(shù)），則在第i個(gè)位置上插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-I+1。故

Eis(n)=

pi(n-I+1)

不失一般性，假設(shè)在表中任何位置(1≦i≦n+1)上插入結(jié)點(diǎn)的機(jī)會(huì)是均等的，則

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

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

Eis(n)=

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

10/8/202415第二章線(xiàn)性表

也就是說(shuō)，在順序表上做插入運(yùn)算，平均要移動(dòng)表上一半結(jié)點(diǎn)。當(dāng)表長(zhǎng)n較大時(shí)，算法的效率相當(dāng)?shù)?。雖然Eis(n)中n的的系數(shù)較小，但就數(shù)量級(jí)而言，它仍然是線(xiàn)性階的。因此算法的平均時(shí)間復(fù)雜度為O(n)。

2、刪除線(xiàn)性表的刪除運(yùn)算是指將表的第i(1≦i≦n)結(jié)點(diǎn)刪除，使長(zhǎng)度為n的線(xiàn)性表：

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

變成長(zhǎng)度為n-1的線(xiàn)性表

(a1，…ai-1，ai+1，…，an)10/8/202416第二章線(xiàn)性表

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--;}

10/8/202417第二章線(xiàn)性表該算法的時(shí)間分析與插入算法相似，結(jié)點(diǎn)的移動(dòng)次數(shù)也是由表長(zhǎng)n和位置i決定。若I=n，則由于循環(huán)變量的初值大于終值，前移語(yǔ)句將不執(zhí)行，無(wú)需移動(dòng)結(jié)點(diǎn)；若I=1，則前移語(yǔ)句將循環(huán)執(zhí)行n-1次，需移動(dòng)表中除開(kāi)始結(jié)點(diǎn)外的所有結(jié)點(diǎn)。這兩種情況下算法的時(shí)間復(fù)雜度分別為O(1)和O(n)。

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

Ede(n)=

pi(n-I)

式中，pi表示刪除表中第i個(gè)結(jié)點(diǎn)的概率。10/8/202418第二章線(xiàn)性表在等概率的假設(shè)下，p1=p2=p3=…=pn=1/n

可得：

Ede(n)=

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

即在順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)，平均時(shí)間復(fù)雜度也是O(n)?？捎懻摼€(xiàn)性表的其它操作在順序存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)方法和時(shí)間復(fù)雜度的分析?？捎懻摾?-1和例2-2的操作在順序存儲(chǔ)結(jié)構(gòu)的線(xiàn)性表中的實(shí)現(xiàn)方法和時(shí)間復(fù)雜度的分析。

10/8/202419第二章線(xiàn)性表建立一個(gè)順序存儲(chǔ)的線(xiàn)性表

voidcreatsqlist(SqList*L){inti;

pritnt(“請(qǐng)輸入線(xiàn)性表元素個(gè)數(shù)\n”);

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

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

10/8/202420第二章線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：隨機(jī)存取缺點(diǎn)：1插入、刪除需移動(dòng)大量元素

2存儲(chǔ)空間不能充分利用

3表的容量難以擴(kuò)充10/8/202421第二章線(xiàn)性表2.3線(xiàn)性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)線(xiàn)性表的順序表示的特點(diǎn)是用物理位置上的鄰接關(guān)系來(lái)表示結(jié)點(diǎn)間的邏輯關(guān)系，這一特點(diǎn)使我們可以隨機(jī)存取表中的任一結(jié)點(diǎn)，但它也使得插入和刪除操作會(huì)移動(dòng)大量的結(jié)點(diǎn).為避免大量結(jié)點(diǎn)的移動(dòng)，我們介紹線(xiàn)性表的另一種存儲(chǔ)方式--鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，簡(jiǎn)稱(chēng)為鏈表(LinkedList)。10/8/202422第二章線(xiàn)性表1線(xiàn)性鏈表（單鏈表）鏈表是指用一組任意的存儲(chǔ)單元來(lái)依次存放線(xiàn)性表的結(jié)點(diǎn)，這組存儲(chǔ)單元即可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。因此，鏈表中結(jié)點(diǎn)的邏輯次序和物理次序不一定相同。為了能正確表示結(jié)點(diǎn)間的邏輯關(guān)系，在存儲(chǔ)每個(gè)結(jié)點(diǎn)值的同時(shí)，還必須存儲(chǔ)指示其后繼結(jié)點(diǎn)的地址（或位置）信息，這個(gè)信息稱(chēng)為指針(pointer)或鏈(link)。這兩部分組成了鏈表中的結(jié)點(diǎn)結(jié)構(gòu)：10/8/202423第二章線(xiàn)性表

其中：存儲(chǔ)數(shù)據(jù)元素信息的data域是數(shù)據(jù)域，用來(lái)存放結(jié)點(diǎn)的值。next是指針域（亦稱(chēng)鏈域），用來(lái)存放結(jié)點(diǎn)的直接后繼的地址（或位置）。鏈表正是通過(guò)每個(gè)結(jié)點(diǎn)的鏈域?qū)⒕€(xiàn)性表的n個(gè)結(jié)點(diǎn)按其邏輯次序鏈接在一起的。由于上述鏈表的每一個(gè)結(jié)只有一個(gè)鏈域，故將這種鏈表稱(chēng)為線(xiàn)性鏈表或單鏈表（SingleLinked)。

顯然，單鏈表中每個(gè)結(jié)點(diǎn)的存儲(chǔ)地址是存放在其前趨結(jié)點(diǎn)next域中，而開(kāi)始結(jié)點(diǎn)無(wú)前趨，故應(yīng)設(shè)頭指針head指向開(kāi)始結(jié)點(diǎn)。同時(shí)，由于終端結(jié)點(diǎn)無(wú)后繼，故終端結(jié)點(diǎn)的指針域?yàn)榭眨磏ull（圖示中也可用^表示)。例1、線(xiàn)性表:(bat，cat，eat，fat，hat，jat，lat，mat)datanext10/8/202424第二章線(xiàn)性表單鏈表示意圖如下：

……110……130135……160頭指針head165170……200205…………………h(huán)at200…….……cat135eat170….……matNullbat130fat110…………jat205lat160…………

16510/8/202425第二章線(xiàn)性表headbat

cat

eat

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

Typedef

structnode{

datatypedata;

structnode*next;}listnode;10/8/202426第二章線(xiàn)性表

typedef

listnode*linklist;

listnode*p;

linklisthead;注意區(qū)分指針變量和結(jié)點(diǎn)變量這兩個(gè)不同的概念。P為動(dòng)態(tài)變量，它是通過(guò)標(biāo)準(zhǔn)函數(shù)生成的，即

p=(listnode*)malloc(sizeof(listnode));函數(shù)malloc分配了一個(gè)類(lèi)型為listnode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中。一旦p所指的結(jié)點(diǎn)變量不再需要了，又可通過(guò)標(biāo)準(zhǔn)函數(shù)

free(p)釋放所指的結(jié)點(diǎn)變量空間。指針變量P和（其值為結(jié)點(diǎn)地址）和結(jié)點(diǎn)變量*P之間的關(guān)系。10/8/202427第二章線(xiàn)性表一、建立單鏈表假設(shè)線(xiàn)性表中結(jié)點(diǎn)的數(shù)據(jù)類(lèi)型是字符，我們逐個(gè)輸入這些字符型的結(jié)點(diǎn)，并以換行符‘\n’為輸入結(jié)束標(biāo)記。動(dòng)態(tài)地建立單鏈表的常用方法有如下兩種：

1、頭插法建表該方法從一個(gè)空表開(kāi)始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點(diǎn)，將讀入數(shù)據(jù)存放到新結(jié)點(diǎn)的數(shù)據(jù)域中，然后將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表頭上，直到讀入結(jié)束標(biāo)志為止。10/8/202428第二章線(xiàn)性表

linklistcreatelistf(void){charch;

linklisthead;

listnode*p;head=null;

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

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

10/8/202429第二章線(xiàn)性表

head=p;

ch=getchar();}return(head);}10/8/202430第二章線(xiàn)性表

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;}10/8/202431第二章線(xiàn)性表

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

頭插法建立鏈表雖然算法簡(jiǎn)單，但生成的鏈表中結(jié)點(diǎn)的次序和輸入的順序相反。若希望二者次序一致，可采用尾插法建表。該方法是將新結(jié)點(diǎn)插入到當(dāng)前鏈表的表尾上，為此必須增加一個(gè)尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點(diǎn)。例：10/8/202432第二章線(xiàn)性表

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

10/8/202433第二章線(xiàn)性表

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

說(shuō)明：第一個(gè)生成的結(jié)點(diǎn)是開(kāi)始結(jié)點(diǎn)，將開(kāi)始結(jié)點(diǎn)插入到空表中，是在當(dāng)前鏈表的第一個(gè)位置上插入，該位置上的插入操作和鏈表中其它位置上的插入操作處理是不一樣的，原因是開(kāi)始結(jié)點(diǎn)的位置是存放在頭指針（指針變量）中，

10/8/202434第二章線(xiàn)性表而其余結(jié)點(diǎn)的位置是在其前趨結(jié)點(diǎn)的指針域中。算法中的第一個(gè)if語(yǔ)句就是用來(lái)對(duì)第一個(gè)位置上的插入操作做特殊處理。算法中的第二個(gè)if語(yǔ)句的作用是為了分別處理空表和非空表兩種不同的情況，若讀入的第一個(gè)字符就是結(jié)束標(biāo)志符，則鏈表head是空表，尾指針r亦為空，結(jié)點(diǎn)*r不存在；否則鏈表head非空，最后一個(gè)尾結(jié)點(diǎn)*r是終端結(jié)點(diǎn)，應(yīng)將其指針域置空。如果我們?cè)阪湵淼拈_(kāi)始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)，并稱(chēng)它為頭結(jié)點(diǎn)，那么會(huì)帶來(lái)以下兩個(gè)優(yōu)點(diǎn)：

a、由于開(kāi)始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就10/8/202435第二章線(xiàn)性表和在表的其它位置上的操作一致，無(wú)需進(jìn)行特殊處理；b、無(wú)論鏈表是否為空，其頭指針是指向頭結(jié)點(diǎn)的非空指針（空表中頭結(jié)點(diǎn)的指針域?yàn)榭眨?，因此空表和非空表的處理也就統(tǒng)一了。其算法如下：linklistcreatelistr1(){charch;

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

listnode*p，*r

10/8/202436第二章線(xiàn)性表

r=head;while((ch=getchar())!=‵\n′{p=(listnode*)malloc(sizeof(listnode));p–>data=ch;p–>next=p;r=p;}r–>next=NULL;return(head);}10/8/202437第二章線(xiàn)性表上述算法里動(dòng)態(tài)申請(qǐng)新結(jié)點(diǎn)空間時(shí)未加錯(cuò)誤處理，可作下列處理：

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

以上算法的時(shí)間復(fù)雜度均為O(n)。10/8/202438第二章線(xiàn)性表二、查找運(yùn)算

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

intj;

listnode*p;p=head;j=0;while(p–>next&&j<I){p=p–>next;j++;}if(i==j)returnp;10/8/202440第二章線(xiàn)性表

elsereturnNULL;}

2、按值查找按值查找是在鏈表中，查找是否有結(jié)點(diǎn)值等于給定值key的結(jié)點(diǎn)，若有的話(huà)，則返回首次找到的其值為key的結(jié)點(diǎn)的存儲(chǔ)位置；否則返回NULL。查找過(guò)程從開(kāi)始結(jié)點(diǎn)出發(fā)，順著鏈表逐個(gè)將結(jié)點(diǎn)的值和給定值key作比較。其算法如下：10/8/202441第二章線(xiàn)性表Listnode*locatenode(linklisthead，intkey){

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

該算法的執(zhí)行時(shí)間亦與輸入實(shí)例中的的取值key有關(guān)，其平均時(shí)間復(fù)雜度的分析類(lèi)似于按序號(hào)查找，也為O(n)。10/8/202442第二章線(xiàn)性表三、插入運(yùn)算插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到ai-1與ai之間。因此，我們必須首先找到ai-1的存儲(chǔ)位置p，然后生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)*p，并令結(jié)點(diǎn)*p的指針域指向新結(jié)點(diǎn)，新結(jié)點(diǎn)的指針域指向結(jié)點(diǎn)ai。從而實(shí)現(xiàn)三個(gè)結(jié)點(diǎn)ai-1，x和ai之間的邏輯關(guān)系的變化，插入過(guò)程如：10/8/202443第二章線(xiàn)性表單鏈表插入結(jié)點(diǎn)時(shí)指針變化情況

b

a

a

b

x

ppq插入前插入后snext=pnext;pnext=s;10/8/202444第二章線(xiàn)性表具體算法如下：

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;

}

10/8/202445第二章線(xiàn)性表設(shè)鏈表的長(zhǎng)度為n，合法的插入位置是1≦i≦n+1。注意當(dāng)i=1時(shí)，getnode找到的是頭結(jié)點(diǎn)，當(dāng)

i=n+1時(shí)，getnode找到的是結(jié)點(diǎn)an。因此，用i-1做實(shí)參調(diào)用getnode時(shí)可完成插入位置的合法性檢查。算法的時(shí)間主要耗費(fèi)在查找操作getnode上，故時(shí)間復(fù)雜度亦為O(n)。四、刪除運(yùn)算刪除運(yùn)算是將表的第i個(gè)結(jié)點(diǎn)刪去。因?yàn)樵趩捂湵碇薪Y(jié)點(diǎn)ai的存儲(chǔ)地址是在其直接前趨結(jié)點(diǎn)

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

10/8/202446第二章線(xiàn)性表

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

bpc（單鏈表刪除結(jié)點(diǎn)時(shí)指針變化情況）××rap->next=p->next->next10/8/202447第二章線(xiàn)性表

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);}10/8/202448第二章線(xiàn)性表設(shè)單鏈表的長(zhǎng)度為n，則刪去第i個(gè)結(jié)點(diǎn)僅當(dāng)1≦i≦n時(shí)是合法的。注意，當(dāng)i=n+1時(shí)，雖然被刪結(jié)點(diǎn)不存在，但其前趨結(jié)點(diǎn)卻存在，它是終端結(jié)點(diǎn)。因此被刪結(jié)點(diǎn)的直接前趨*p存在并不意味著被刪結(jié)點(diǎn)就一定存在，僅當(dāng)*p存在（即p!=NULL）且*p不是終端結(jié)點(diǎn)（即p–>next!=NULL）時(shí)，才能確定被刪結(jié)點(diǎn)存在。顯然此算法的時(shí)間復(fù)雜度也是O(n)。從上面的討論可以看出，鏈表上實(shí)現(xiàn)插入和刪除運(yùn)算，無(wú)須移動(dòng)結(jié)點(diǎn)，僅需修改指針。10/8/202449第二章線(xiàn)性表2.3.2循環(huán)鏈表

循環(huán)鏈表時(shí)一種頭尾相接的鏈表。其特點(diǎn)是無(wú)須增加存儲(chǔ)量，僅對(duì)表的鏈接方式稍作改變，即可使得表處理更加方便靈活。單循環(huán)鏈表：在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)的或開(kāi)始結(jié)點(diǎn)，就得到了單鏈形式的循環(huán)鏈表，并簡(jiǎn)單稱(chēng)為單循環(huán)鏈表。為了使空表和非空表的處理一致，循環(huán)鏈表中也可設(shè)置一個(gè)頭結(jié)點(diǎn)。這樣，空循環(huán)鏈表僅有一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。如下圖所示：10/8/202450第二章線(xiàn)性表

a1an

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

linklist

connect(linklist

reara，linklist

rearb){

linklistp=reara—>next;

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

free(rearb—>next);

rearb—>next=p;

return(rearb);}10/8/202453第二章線(xiàn)性表2.3.3雙鏈表

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

typedefstructdlistnode{

datatypedata;

strucdlistnode