第2章線性表學(xué)習(xí)要點(diǎn)

1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計(jì)算機(jī)中表示這種關(guān)系的兩類不同的存儲(chǔ)結(jié)構(gòu)是順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。

2.熟練掌握這兩類存儲(chǔ)結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)。

3.能夠從時(shí)間和空間復(fù)雜度的角度綜合比較線性表兩種存儲(chǔ)結(jié)構(gòu)的不同特點(diǎn)及其適用場合。第2章線性表

線性表是一種最簡單的線性結(jié)構(gòu)。什么是線性結(jié)構(gòu)？簡單地說，線性結(jié)構(gòu)是一個(gè)數(shù)據(jù)元素的有序（次序）集合。它有四個(gè)基本特征：

1．集合中必存在唯一的一個(gè)"第一元素"；

2．集合中必存在唯一的一個(gè)"最后元素"；

3．除最后元素之外，其它數(shù)據(jù)元素均有唯一的"后繼"；

4．除第一元素之外，其它數(shù)據(jù)元素均有唯一的"前驅(qū)"。2.1線性表的定義和基本操作2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2.4線性表的應(yīng)用舉例2.1線性表的定義和基本操作2.1.1

線性表的定義線性表是由n（n≥0）個(gè)類型相同的數(shù)據(jù)元素組成的有限序列。通常表示成下列形式：

L=(a1,a2,...,ai-1,ai,ai+1,...,an)

其中：L為線性表名稱，習(xí)慣用大寫書寫；

ai為組成該線性表的數(shù)據(jù)元素，習(xí)慣用小寫書寫；線性表中數(shù)據(jù)元素的個(gè)數(shù)n被稱為表長，當(dāng)n=0時(shí)，線性表為空，又稱為空表。稱i為ai在線性表中的位序。

舉例

La=（34，89，765，12，90，-34，22）數(shù)據(jù)元素類型為int。

Ls=(

Hello

,

World

,

China

,

Welcome

)數(shù)據(jù)元素類型為string。

Lb=(book1,book2,...,book100)數(shù)據(jù)元素類型為下列所示的結(jié)構(gòu)類型：

structbookinfo{intNo;//圖書編號(hào)

char*name;//圖書名稱

char*auther;//作者名稱

...;}同一線性表中的元素必定具有相同特性不同的數(shù)據(jù)結(jié)構(gòu)其操作集不同，但下列操作必不可缺：

1)結(jié)構(gòu)的生成；

2)結(jié)構(gòu)的銷毀；

3)在結(jié)構(gòu)中查找滿足規(guī)定條件的數(shù)據(jù)元素；

4)在結(jié)構(gòu)中插入新的數(shù)據(jù)元素；

5)刪除結(jié)構(gòu)中已經(jīng)存在的數(shù)據(jù)元素；

6)遍歷。若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在表中依值非遞減或非遞增有序排列，即ai≥ai-1

或ai≤ai-1(i=2,3,…,n)，則稱該為有序表(OrderedList)。以有序表表示集合，來解決有關(guān)集合運(yùn)算方面的問題。2.2線性表的順序存儲(chǔ)結(jié)構(gòu)2.2.1

線性表的順序存儲(chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)(簡稱順序表)是指用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的每個(gè)數(shù)據(jù)元素。即以“存儲(chǔ)位置相鄰”表示“位序相繼的兩個(gè)數(shù)據(jù)元素之間的前驅(qū)和后繼的關(guān)系”，表中第一個(gè)元素的存儲(chǔ)位置作為線性表的起始地址，稱作線性表的基地址。如下圖2-1所示：圖2-1線性表順序存儲(chǔ)結(jié)構(gòu)示意圖

其中，L為每個(gè)數(shù)據(jù)元素所占據(jù)的存儲(chǔ)單元數(shù)目。相鄰兩個(gè)數(shù)據(jù)元素的存儲(chǔ)位置計(jì)算公式

LOC(ai+1)=LOC(ai)+L

線性表中任意一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置的計(jì)算公式為：

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

順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)（1）利用數(shù)據(jù)元素的存儲(chǔ)位置表示線性表中相鄰數(shù)據(jù)元素之間的前后關(guān)系，即線性表的邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)（物理結(jié)構(gòu)）一致；

（2）在訪問線性表時(shí)，可以利用上述給出的數(shù)學(xué)公式，快速地計(jì)算出任何一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址。因此，我們可以粗略地認(rèn)為，訪問每個(gè)數(shù)據(jù)元素所花費(fèi)的時(shí)間相等。這種存取元素的方法被稱為隨機(jī)存取法，使用這種存取方法的存儲(chǔ)結(jié)構(gòu)被稱為隨機(jī)存儲(chǔ)結(jié)構(gòu)。

用C語言描述的順序表類型如下所示：#defineMAXLISTSIZE100//預(yù)設(shè)的存儲(chǔ)空間最大容量

typedefstruct{ElemType*elem;

//存儲(chǔ)空間基址

intlength;

//當(dāng)前長度

intlistsize;//允許的最大存儲(chǔ)容量(以sizeof(ElemType)為單位)

}SqList;

//俗稱順序表

基本操作接口(函數(shù)聲明)

voidInitList(SqList&L,intmaxsize);//構(gòu)造一個(gè)最大存儲(chǔ)容量為maxsize的空的順序表L。

voidDestroyList(SqList&L)

//銷毀順序表L。

boolListEmpty(SqListL)

//若順序表L為空表，則返回TRUE，否則返回FALSE。

intListLength(SqListL)

//返回順序表L中元素個(gè)數(shù)。

intPriorElem(SqListL,ElemTypecur_e)//若cur_e是順序表L的元素，則返回其前驅(qū)的位序(設(shè)第一個(gè)元素的前驅(qū)的位序?yàn)?)，否則返回-1。

intNextElem(SqListL,ElemTypecur_e)

//若cur_e是順序表L的元素，則返回其后繼的位序(設(shè)最后一個(gè)元素的后繼的位序?yàn)長的表長+1)，否則返回-1。boolGetElem(SqListL,intpos,ElemType&e)

//若1≤pos≤LengthList(L)，則用e帶回順序表L中第pos個(gè)元素的值且返回函數(shù)值為TRUE，否則返回函數(shù)值為FALSE。

intLocateElem(SqListL,ElemTypee,bool(*compare)(ElemType,ElemType))

//返回順序表L中第1個(gè)與e滿足關(guān)系compare()的數(shù)據(jù)元素的位序。

//若這樣的元素不存在，則返回值為0。compare()為數(shù)據(jù)元素的判定函數(shù)。

voidListTraverse(SqListL,void(*visit)(ElemType))

//依次對順序表L的每個(gè)元素調(diào)用函數(shù)visit()。

//一旦visit()失敗，則操作失敗。

voidClearList(SqList&L)

//將順序表L重置為空表。

boolPutElem(SqListL,intpos,ElemType&e)

//若1≤pos≤LengthList(L)，則對順序表L中第pos個(gè)元素

//賦值同e的值且返回函數(shù)值為TRUE，否則返回函數(shù)值為FALSE。

boolListInsert(SqList&L,intpos,ElemTypee)

//若存儲(chǔ)空間未滿且1≤pos≤LengthList(L)+1，則在順序表L的

//第pos個(gè)元素之前插入新的元素e，L的長度增1，且返回函數(shù)值為TRUE，

//否則不改變順序表且返回函數(shù)值為FALSE。

boolListDelete(SqList&L,intpos,ElemType&e)

//若1≤pos≤LengthList(L)，則刪除順序表L的第pos個(gè)元素e，

//

L的長度增1，且返回函數(shù)值為TRUE，否則不改變順序表且返回函數(shù)值為FALSE。

2.2.2順序表中基本操作的實(shí)現(xiàn)

從順序表的存儲(chǔ)結(jié)構(gòu)定義容易看出，由于順序表的“長度”是個(gè)“顯值”，且由于第i個(gè)元素恰好存儲(chǔ)在數(shù)組的第i個(gè)分量(數(shù)組下標(biāo)為i-1)中，因此其“求長”、“判空”以及“存取第i個(gè)數(shù)據(jù)元素”等操作都很容易實(shí)現(xiàn)。下面重點(diǎn)討論順序表類型定義中五個(gè)操作的實(shí)現(xiàn)。一、初始化操作二、元素定位操作三、插入元素操作四、刪除元素操作五、銷毀結(jié)構(gòu)操作一、初始化操作對順序表而言，“初始化”的實(shí)質(zhì)是為它分配一個(gè)“足夠應(yīng)用”的元素存儲(chǔ)空間，由用戶根據(jù)它對線性表的使用要求定義一個(gè)最大存儲(chǔ)容量maxsize，并約定當(dāng)用戶沒有提出特殊需求(maxsize=0)時(shí)，按予設(shè)的最大存儲(chǔ)量MAXLISTSIZE進(jìn)行分配。

一、初始化操作

voidInitList(SqList&L,intmaxsize){//構(gòu)造一個(gè)空的線性表Lif(maxsize==0)maxsize=MAXLISTSIZE;L.elem=newElemType[maxsize];

if(!L.elem)exit(1);//存儲(chǔ)分配失敗L.length=0;//順序表的初始長度為0L.listsize=maxsize;//該順序表可以存儲(chǔ)元素的最大容量}//InitList

此算法的時(shí)間復(fù)雜度為O(1)。

二、元素定位操作在順序表中“查詢”是否存在一個(gè)和給定值滿足判定條件的元素的最簡單的辦法是，依次取出結(jié)構(gòu)中的每個(gè)元素和給定值進(jìn)行比較。二、元素定位操作intLocateElem(SqListL,ElemTypee,

bool(*compare)(ElemType,ElemType))

{

//在順序表L中查找第1個(gè)值與e滿足判定條件compare()的元素，若找到，則返回其在L中的位序，否則返回0。

i=1;

//i的初值為第1元素的位序

p=L.elem;

//p的初值為第1元素的存儲(chǔ)位置

while(i<=L.length&&!(*compare)(*p++,e))

++i;

//依次進(jìn)行判定

if(i<=L.length)returni;//找到滿足判定條件的數(shù)據(jù)元素為第i個(gè)元素

elsereturn0;//該線性表中不存在滿足判定的數(shù)據(jù)元素

}//LocateElem

此算法的時(shí)間復(fù)雜度為：O(ListLength(L))演示三、插入元素操作首先分析，“插入元素”使線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？

假設(shè)在線性表的第i個(gè)元素之前插入一個(gè)元素e，使得線性表(a1,…,ai-1,ai,…,an)改變?yōu)?a1,…,ai-1,e,ai,…,an)

即：

(1)改變了表中元素之間的關(guān)系，使<ai-1,ai>改變?yōu)?lt;ai-1,e>和<e,ai>

(2)表長增1

由于順序表是以"存儲(chǔ)位置相鄰"表示"元素之間的前驅(qū)和后繼關(guān)系"，則必須"移動(dòng)元素"來體現(xiàn)"元素之間發(fā)生的變化"。三、插入元素操作

boolListInsert(SqList&L,intpos,ElemTypee){//若存儲(chǔ)空間不滿且1≤pos≤Listlength(L)+1，則在順序表L的第pos個(gè)元素之前插入新的元素e且返回TRUE，否則返回FALSEif(pos<1||pos>L.length+1)returnFALSE;//插入位置不合法if(L.length>=L.listsize)returnFALSE;//當(dāng)前存儲(chǔ)空間已滿，無法插入for(j=L.length-1;j>=pos-1;--j)L.elem[j+1]=L.elem[j];//插入位置及之后的元素右移L.elem[pos-1]=e;//插入e++L.length;//表長增1returnTRUE;}//ListInsert此算法的時(shí)間復(fù)雜度為：O(ListLength(L))演示四、刪除元素操作

假設(shè)刪除線性表中第i個(gè)元素，對順序表而言，需要改變從第i+1個(gè)元素起到第n個(gè)元素的存儲(chǔ)位置，即進(jìn)行"從第i+1到第n個(gè)元素往前移動(dòng)一個(gè)位置"。四、刪除元素操作

boolListDelete(SqList&L,intpos,ElemType&e){//若1≤pos≤Listlength(L)，則以e帶回從順序表L中刪除的第pos個(gè)元素且返回TRUE，否則返回FALSEif((pos<1)||(pos>L.length))

returnFALSE;//刪除位置不合法for(j=pos;j<L.length;++j)L.elem[j-1]=L.elem[j];//被刪除元素之后的元素左移

--L.length;//表長減1returnTRUE;}//ListDelete此算法的時(shí)間復(fù)雜度為：O(ListLength(L))演示五、銷毀結(jié)構(gòu)操作voidDestroyList(SqList&L){//釋放順序表L所占存儲(chǔ)空間delete[

]L.elem;L.listsize=0;L.length=0;}//DestroyList_Sq

此算法的時(shí)間復(fù)雜度為：O(1)插入和刪除操作的性能分析

在順序表中任何一個(gè)合法位置上進(jìn)行"一次"插入或刪除操作時(shí)，需要移動(dòng)的元素個(gè)數(shù)的平均值是多少？

插入算法的分析假設(shè)線性表中含有n個(gè)數(shù)據(jù)元素，在進(jìn)行插入操作時(shí)，若假定在n+1個(gè)位置上插入元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：

刪除算法的分析在進(jìn)行刪除操作時(shí)，若假定刪除每個(gè)元素的可能性均等，則平均移動(dòng)元素的個(gè)數(shù)為：

分析結(jié)論在順序存儲(chǔ)表示的線性表中插入或刪除一個(gè)數(shù)據(jù)元素，平均約需移動(dòng)表中一半元素。這個(gè)數(shù)目在線性表的長度較大時(shí)是很可觀的。這個(gè)缺陷完全是由于順序存儲(chǔ)要求線性表的元素依次緊挨存放造成的。因此，這種順序存儲(chǔ)表示僅適用于不常進(jìn)行插入和刪除操作、表中元素相對穩(wěn)定的線性表。順序表其它算法舉例

例1

試編寫算法“比較”兩個(gè)順序表的大小。算法的基本思想為：若aj=bj，則j增1，之后繼續(xù)比較后繼元素；否則即可得出比較結(jié)果。顯然，j的初值應(yīng)為0，循環(huán)的條件是j不超出其中任何一個(gè)表的范圍。若在循環(huán)內(nèi)不能得出比較結(jié)果，則循環(huán)結(jié)束時(shí)有三種可能出現(xiàn)的情況需要區(qū)分。intcompare(SqListA,SqListB)

{

//若A<B，則返回-1；若A=B，則返回0；若A>B，則返回1

j=0;

while(j<A.length&&j<B.length)

if(A.elem[j]<B.elem[j])return(-1);

elseif(A.elem[j]>B.elem[j])return(1);

elsej++;

if(A.length==B.length)return(0);

elseif(A.length<B.length)return(-1);

elsereturn(1);

}//compare上述算法中只有一個(gè)while循環(huán)，它的執(zhí)行次數(shù)依賴于待比較的順序表的表長，因此，算法2.9的時(shí)間復(fù)雜度為O(Min(A.length,B.length))例2試設(shè)計(jì)一個(gè)算法，用盡可能少的輔助空間將順序表中前m個(gè)元素和后n個(gè)元素進(jìn)行互換，即將線性表(a1,a2,…,am,b1,b2,…,bn)改變成(b1,b2,…,bn,a1,a2,…,am)。此題的一種比較簡單的算法是，從表中第m+1個(gè)元素起依次插入到元素a1之前。則首先需將該元素bk(k=1，2，…，n)暫存在一個(gè)輔助變量中，然后將它之前的m個(gè)元素(a1,a2,…,am)依次后移一個(gè)位置。顯然，由于對每一個(gè)bk都需要移動(dòng)m個(gè)元素，因此算法的時(shí)間復(fù)雜度為O(m×n)。

演示也可采用另一種算法為，對順序表進(jìn)行三次"逆置"，第一次是對整個(gè)順序表進(jìn)行逆置，之后分別對前n個(gè)和后m個(gè)元素進(jìn)行逆置。

演示voidinvert(ElemType&R[],ints,intt)

{

//

本算法將數(shù)組R中下標(biāo)自s到t的元素逆置，即將

//

（Rs,Rs+1,…,Rt-1,Rt）改變?yōu)椋≧t,Rt-1,…,Rs+1,Rs）

for(k=s;k<=(s+t)/2;k++)

{

w=R[k];

R[k]=R[t-k+s];

R[t-k+s]=w;

}//for

}//invert

voidexchange(SqList&A,intm)

{

//

本算法實(shí)現(xiàn)順序表中前m

個(gè)元素和后n個(gè)元素的互換

if(m>0&&m<A.length){

n=A.length-m;

invert(A.elem,0,m+n-1);

invert(A.elem,0,n-1);

invert(A.elem,n,m+n-1);

}

}//exchange由于逆置順序表可以利"交換"相應(yīng)元素進(jìn)行，其時(shí)間復(fù)雜度為線性級(jí)別，則三次調(diào)用逆置算法完成的操作的時(shí)間復(fù)雜度仍然是線性級(jí)別的，即為O(m+n)。

例3編寫算法刪除順序表中“多余”的數(shù)據(jù)元素，即使操作之后的順序表中所有元素的值都不相同。容易想到此題的一個(gè)簡單算法是：

對表中任一個(gè)元素ai，令j從i+1到n，將aj和ai進(jìn)行比較，若相等，則從順序表中刪除該元素，即令從j+1到n的元素均向前移動(dòng)一個(gè)位置。

演示由于順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，在刪除元素時(shí)必然會(huì)引起一連串的元素向前移動(dòng)，但在上述算法中“每發(fā)現(xiàn)一個(gè)和相同的元素，立即將在它之后的元素向前移動(dòng)一個(gè)位置”的做法，將會(huì)使那些值和不同的元素重復(fù)多次移動(dòng)操作，而每次都只移動(dòng)一個(gè)位置（試設(shè)想在此元素之后還有很多和值相同的元素）。算法的時(shí)間復(fù)雜度將是O(n2)（n為表長）。但如果不是從“刪除”而是從“插入”來考慮問題，這個(gè)題的解法就會(huì)有不同的結(jié)果。

設(shè)想另建立一個(gè)順序表，表中只包含原表中所有值不同的元素，對原順序表中每一個(gè)當(dāng)前考察的數(shù)據(jù)元素，在“新表”中進(jìn)行查找，如果有相同的則舍棄之，否則就插入到“新表”中。由于問題的實(shí)質(zhì)是“刪除”，因此所謂“新表”，在存儲(chǔ)結(jié)構(gòu)上并非是新建的表，它和原表可以共享存儲(chǔ)空間，只須新建一個(gè)指針來指示其表尾的當(dāng)前位置即可。

演示voidpurge_Sq(SqList&L)

{

//

刪除順序表L中的冗余元素，即使操作之后的順序表中只保留

//

操作之前表中所有值都不相同的元素

k=-1;

//k指示新表的表尾

for(i=0;i<L.length;++i)

//

順序考察表中每個(gè)元素

{

j=0;

while(j<=k&&L.elem[j]!=L.elem[i])

++j;

//

在新表中查詢是否存在和L.elem[i]相同的元素

if(k==-1||j>k)

//k=-1表明當(dāng)前考察的是第一個(gè)元素

L.elem[++k]=L.elem[i];

}//for

L.length=k+1;

//

修改表長

}//purge_Sq

此算法的時(shí)間復(fù)雜度為O(ListLength2(L))

分析：

算法中的基本操作為"比較"，控制結(jié)構(gòu)為兩重循環(huán)，外循環(huán)的執(zhí)行次數(shù)和順序表的表長相同，內(nèi)循環(huán)的執(zhí)行次數(shù)則不超過表長。此外，"比較"操作相對于"移動(dòng)"操作所需的時(shí)間也少。

從這個(gè)題的算法可以得到一些有益的啟示，某種情況下，"刪除"操作也可利用"插入"來實(shí)現(xiàn)。例4教材P26算法2.7順序表的合并2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

線性表順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)它是一種簡單、方便的存儲(chǔ)方式。它要求線性表的數(shù)據(jù)元素依次存放在連續(xù)的存儲(chǔ)單元中，從而利用數(shù)據(jù)元素的存儲(chǔ)順序表示相應(yīng)的邏輯順序，這種存儲(chǔ)方式屬于靜態(tài)存儲(chǔ)形式。暴露的問題

l 在做插入或刪除元素的操作時(shí)，會(huì)產(chǎn)生大量的數(shù)據(jù)元素移動(dòng)；

l 對于長度變化較大的線性表，要一次性地分配足夠的存儲(chǔ)空間，但這些空間常常又得不到充分的利用；

l 線性表的容量難以擴(kuò)充。

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是指用一組任意的存儲(chǔ)單元（可以連續(xù)，也可以不連續(xù)）存儲(chǔ)線性表中的數(shù)據(jù)元素。為了反映數(shù)據(jù)元素之間的邏輯關(guān)系，對于每個(gè)數(shù)據(jù)元素不僅要表示它的具體內(nèi)容，還要附加一個(gè)表示它的直接后繼元素存儲(chǔ)位置的信息。假設(shè)有一個(gè)線性表（a,b,c,d），可用下圖2-2所示的形式存儲(chǔ)：圖2-2線性表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)示意圖

術(shù)語表示每個(gè)數(shù)據(jù)元素的兩部分信息組合在一起被稱為結(jié)點(diǎn)；其中表示數(shù)據(jù)元素內(nèi)容的部分被稱為數(shù)據(jù)域（data）；表示直接后繼元素存儲(chǔ)地址的部分被稱為指針或指針域（next）。單鏈表簡化的圖2-3描述形式headd^

cba圖2-3單鏈表結(jié)構(gòu)示意圖

其中，head是頭指針，它指向單鏈表中的第一個(gè)結(jié)點(diǎn)，這是單鏈表操作的入口點(diǎn)。由于最后一個(gè)結(jié)點(diǎn)沒有直接后繼結(jié)點(diǎn)，所以，它的指針域放入一個(gè)特殊的值NULL。NULL值在圖示中常用（^）符號(hào)表示。帶頭結(jié)點(diǎn)的單鏈表為了簡化對鏈表的操作，人們經(jīng)常在鏈表的第一個(gè)結(jié)點(diǎn)（首元結(jié)點(diǎn)）之前附加一個(gè)結(jié)點(diǎn)，并稱為頭結(jié)點(diǎn)。這樣可以免去對鏈表第一個(gè)結(jié)點(diǎn)的特殊處理。如下圖2-4所示：headd^

cba圖2-4帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)示意圖

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)（1）線性表中的數(shù)據(jù)元素在存儲(chǔ)單元中的存放順序與邏輯順序不一定一致；（2）在對線性表操作時(shí)，只能通過頭指針進(jìn)入鏈表，并通過每個(gè)結(jié)點(diǎn)的指針域向后掃描其余結(jié)點(diǎn)，這樣就會(huì)造成尋找第一個(gè)結(jié)點(diǎn)和尋找最后一個(gè)結(jié)點(diǎn)所花費(fèi)的時(shí)間不等，具有這種特點(diǎn)的存取方式被稱為順序存取方式。用C語言中的“結(jié)構(gòu)指針”來描述鏈表結(jié)構(gòu)。

typedefstructLNode

{

ElemTypedata;

structLNode*next;

}LNode,*SLink;

若設(shè)LNode*p,*q;

SLinkH;

則p，q和H均為以上定義的指針型變量。若p的值非空，則表明p指向某個(gè)結(jié)點(diǎn)，p->data表示p所指結(jié)點(diǎn)中的數(shù)據(jù)域，p->next表示p所指結(jié)點(diǎn)中的指針域，若非空，則指向其“后繼”結(jié)點(diǎn)。指針型變量只能作同類型的指針賦值與比較操作。并且，指針型變量的"值"除了由同類型的指針變量賦值得到外，都必須用C語言中的動(dòng)態(tài)分配函數(shù)得到。例如，p=newLNode;表示在運(yùn)行時(shí)刻系統(tǒng)動(dòng)態(tài)生成了一個(gè)LNode類型的結(jié)點(diǎn)，并令指針p"指向"該結(jié)點(diǎn)。反之，當(dāng)指針p所指結(jié)點(diǎn)不再使用，可用deletep;釋放此結(jié)點(diǎn)空間。2.3.2單鏈表中基本操作的實(shí)現(xiàn)1.初始化操作初始化建一個(gè)空的鏈表即為建立一個(gè)只有頭結(jié)點(diǎn)的鏈表voidInitList(SLink&L){//創(chuàng)建一個(gè)帶頭結(jié)點(diǎn)的空鏈表,L為指向頭結(jié)點(diǎn)的指針(頭指針)

L=newLNode;

if(!L)exit(1);

//存儲(chǔ)空間分配失敗

L->next=NULL;

}//InitList

算法的時(shí)間復(fù)雜度為O(1)。2.銷毀鏈表voidDestroyList(SLink&L)

{

//銷毀以L為頭指針的單鏈表，釋放鏈表中所有結(jié)點(diǎn)空間

while(L)

{

p=L;

L=L->next;

deletep;

}//while

L=NULL;//雖然頭結(jié)點(diǎn)占有的空間已經(jīng)釋放，但指針變量L中的值沒有改變，為安全起見，置L為"空"，以防止對系統(tǒng)空間的訪問。

}//DestroyList

算法的時(shí)間復(fù)雜度為O(Listlength(L))。3.存取元素操作單鏈表是一種“順序存取”的結(jié)構(gòu)，即：為取第i元素，首先必須先找到第i-1個(gè)元素。因此不論i值為多少，都必須從頭結(jié)點(diǎn)開始起“點(diǎn)數(shù)”，直數(shù)到第i個(gè)為止。頭結(jié)點(diǎn)可看成是第0個(gè)結(jié)點(diǎn)。3.存取元素操作

boolGetElem(SLinkL,intpos,ElemType&e)

{

//若1≤pos≤LengthList(L)，則用e帶回指針L指向頭結(jié)點(diǎn)的單鏈表中第pos個(gè)元素的值且返回函數(shù)值為TRUE,否則返回函數(shù)值為FALSE

p=L->next;j=1;//變量初始化，p指向第一個(gè)結(jié)點(diǎn)

while(p&&j<pos)

{

//順結(jié)點(diǎn)的指針向后查找，直至p指到第pos個(gè)結(jié)點(diǎn)或p為空止

p=p->next;++j;

}//while

if(!p||j>pos)returnFALSE;//鏈表中不存在第pos個(gè)結(jié)點(diǎn)

e=p->data;

//取到第pos個(gè)元素

returnTRUE;

}//GetElem

算法的時(shí)間復(fù)雜度為O(ListLength(L))。演示4.插入元素操作算法的基本思想就是，首先找到第i-1個(gè)結(jié)點(diǎn)，然后修改相應(yīng)指針。

4.插入元素操作

boolListInsert(SLink&L,intpos,ElemTypee)

{

//若1≤pos≤LengthList(L)+1，則在指針L指向頭結(jié)點(diǎn)的單鏈表的第pos個(gè)元素之前插入新的元素e，且返回函數(shù)值為TRUE,否則不進(jìn)行插入且返回函數(shù)值為FALSE

p=L;j=0;

while(p&&j<pos-1)

{//查找第pos-1個(gè)結(jié)點(diǎn)，并令指針p指向該結(jié)點(diǎn)

p=p->next;++j;

}//while

if(!p||j>pos-1)

returnFALSE;//參數(shù)不合法，pos小于1或者大于表長+1

s=newLNode;

if(!s)exit(1);

//存儲(chǔ)空間分配失敗

s->data=e;

//創(chuàng)建新元素的結(jié)點(diǎn)

s->next=p->next;p->next=s;//修改指針

returnTRUE;

}//ListInsert算法時(shí)間復(fù)雜度為O(ListLength(L))。演示5.刪除元素操作boolListDelete(SLink&L,intpos,ElemType&e)

{

//若1≤pos≤LengthList(L)，則刪除指針L指向頭結(jié)點(diǎn)的單鏈表中第pos個(gè)元素并以e帶回其值，返回函數(shù)值為TRUE，否則不進(jìn)行刪除操作且返回函數(shù)值為FALSE

p=L;j=0;

while(p->next&&j<pos-1)

{

//尋找第pos個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū)

p=p->next;++j;

}

if(!(p->next)||j>pos-1)

returnFALSE;

//刪除位置不合理

q=p->next;p->next=q->next;

//修改指針

e=q->data;delete(q);

//釋放結(jié)點(diǎn)空間

returnTRUE;

}//ListDelete算法時(shí)間復(fù)雜度為O(ListLength(L))。演示例1.逆序創(chuàng)建鏈表（頭插法建立單鏈表）假設(shè)線性表(a1，a2

，…，an)的數(shù)據(jù)元素存儲(chǔ)在一維數(shù)組A[n]中，則從數(shù)組的最后一個(gè)分量起，依次生成結(jié)點(diǎn)，并逐個(gè)插入到一個(gè)初始為“空”的鏈表中。算法思想：所謂“逆序”創(chuàng)建鏈表指的是，依和線性表的邏輯順序相“逆”的次序輸入元素。由于鏈表的生成是從最后一個(gè)結(jié)點(diǎn)起逐個(gè)插入，因此每個(gè)新生成的結(jié)點(diǎn)都是插入在鏈表的“第一個(gè)”結(jié)點(diǎn)之前，即頭結(jié)點(diǎn)之后，使新插入的結(jié)點(diǎn)成為插入之后的鏈表中的第一個(gè)結(jié)點(diǎn)。例如動(dòng)畫演示了線性表(a,b,c,d,e)的逆序創(chuàng)建的過程。單鏈表其它算法舉例演示具體算法：voidCreateList_L(SLink&L,intn,ElemTypeA[])

{

//已知數(shù)組A中存有線性表的n個(gè)數(shù)據(jù)元素，

//逆序建立帶頭結(jié)點(diǎn)的單鏈表。

L=newLNode;

if(!L)exit(1);

//存儲(chǔ)空間分配失敗

L->next=NULL;//先建立一個(gè)帶頭結(jié)點(diǎn)的空的單鏈表

for(i=n;i>0;--i)

{p=newLNode;

if(!p)exit(1);

//存儲(chǔ)空間分配失敗

p->data=A[i-1];

//賦元素值

p->next=L->next;L->next=p;//插入在頭結(jié)點(diǎn)之后

}//for

}//CreateList_L容易看出，算法的時(shí)間復(fù)雜度為O(ListLength(L))。思考：如何用尾插法創(chuàng)建鏈表？例2.以鏈表作存儲(chǔ)結(jié)構(gòu)將線性表中前m個(gè)元素和后n個(gè)元素進(jìn)行互換，即將線性表(a1,a2,…,am,b1,b2,…,bn)改變成(b1,b2,…,bn,a1,a2,…,am)。因?yàn)閷︽湵韥碚f，"插入"和"刪除"僅需修改指針即可完成，并且由于前m個(gè)元素之間和后n個(gè)元素之間的鏈接關(guān)系分別都不需要改變，則算法的實(shí)際操作為：

(1)從鏈表中刪除(a1,a2,…,am)；

(2)將(b1,b2,…,bn)鏈接到頭結(jié)點(diǎn)之后；

(3)將(a1,a2,…,am)鏈接到bn

之后。

演示voidexchange_L(SLink&L，intm)

{

//本算法實(shí)現(xiàn)單鏈表中前m個(gè)結(jié)點(diǎn)和后n個(gè)結(jié)點(diǎn)的互換

if(m&&L->next)

//鏈表不空且m!=0

{

p=L->next;k=1;

while(k<m&&p)

//查找am所在結(jié)點(diǎn)

{

p=p->next;++k;

}//while

if(p&&p->next)

//n!=0時(shí)才需要修改指針

{

ha=L->next;

//以指針ha記a1結(jié)點(diǎn)的位置

L->next=p->next;

//將b1結(jié)點(diǎn)鏈接在頭結(jié)點(diǎn)之后

p->next=NULL;

//設(shè)am的后繼為空

q=L->next;

//令q指向b1結(jié)點(diǎn)

while(q->next)q=q->next;//查找bn結(jié)點(diǎn)

q->next=ha;

//將a1結(jié)點(diǎn)鏈接到bn結(jié)點(diǎn)之后

}//if(p)

}//if(m)

}//exchange_L

算法的時(shí)間復(fù)雜度為O(ListLength(L))。例3.編寫算法刪除單鏈表中“多余”的數(shù)據(jù)元素，即使操作之后的單鏈表中所有元素的值都不相同。voidpurge_L(SLink&L)

{

//刪除單鏈表L中的冗余元素，即使操作之后的單鏈表中只保留

//操作之前表中所有值都不相同的元素

p=L->next;

L->next=NULL;;

//設(shè)新表為空表

while(p)

//順序考察原表中每個(gè)元素

{

succ=p->next;

//記下結(jié)點(diǎn)*p的后繼

q=L->next;

//q指向新表的第一個(gè)結(jié)點(diǎn)

while(q&&p->data!=q->data)q=q->next;

//在新表中查詢是否存在和p->data相同的元素

if(!q)

//將結(jié)點(diǎn)*p插入到新的表中

{

p->next=L->next;

L->next=p;

}

elsedeletep;

//釋放結(jié)點(diǎn)*p

p=succ;

}//for

}//purge_L此算法的時(shí)間復(fù)雜度為O(ListLength2(L))。

例4.兩個(gè)鏈表的歸并算法要求：已知：線性表A、B，分別由單鏈表LA,LB存儲(chǔ)，其中數(shù)據(jù)元素按值非遞減有序排列，要求：將A，B歸并為一個(gè)新的線性表C,C的數(shù)據(jù)元素仍按值非遞減排列。設(shè)線性表C由單鏈表LC存儲(chǔ)。假設(shè)：A=（3，5，8，11），B=（2，6，8，9，11）預(yù)測：合并后C=（2,3,5,6,8,8,9,11，11）用鏈表可表示為：3511/\8

La2611/\8

Lb92365

Lc8頭結(jié)點(diǎn)算法分析：算法主要包括：搜索、比較、插入三個(gè)操作：搜索：需要兩個(gè)指針?biāo)阉鲀蓚€(gè)鏈表；比較：比較結(jié)點(diǎn)數(shù)據(jù)域中數(shù)據(jù)的大?。徊迦耄簩蓚€(gè)結(jié)點(diǎn)中數(shù)據(jù)小的結(jié)點(diǎn)插入新鏈表。演示算法實(shí)現(xiàn)：

VoidMergeList_L(SLink&La,SLink&Lb,SLink&Lc){//按值排序的單鏈表LA,LB，歸并為LC后也按值排序deleteLb;//釋放Lb的頭結(jié)點(diǎn)}//MergeList_L

pc->next=pa?pa:pb;//插入剩余段while(pa&&pb)//將pa、pb結(jié)點(diǎn)按大小依次插入C中

{if(pa->data<=pb->data){pc->next=pa;pc=pa;pa=pa->next;}else{pc->next=pb;pc=pb;pb=pb->next}}pa=La-->next;pb=Lb-->next;Lc=pc=La；//初始化

從以上對鏈表的各種操作的討論可知，鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)勢在于：能有效利用存儲(chǔ)空間；(2)用“指針”指示數(shù)據(jù)元素之間的后繼關(guān)系，便于進(jìn)行“插入”、“刪除”等操作；

而其劣勢則是不能隨機(jī)存取數(shù)據(jù)元素。同時(shí)，它還丟失了一些順序表有的長處，如線性表的"表長"和數(shù)據(jù)元素在線性表中的"位序"，在上述的單鏈表中都看不見了。又如，不便于在表尾插入元素，需遍歷整個(gè)表才能找到插入的位置。2.3.3

循環(huán)鏈表若將鏈表中最后一個(gè)結(jié)點(diǎn)的next域指向頭結(jié)點(diǎn)實(shí)現(xiàn)循環(huán)鏈表的類型定義與單鏈表完全相同，它的所有操作也都與單鏈表類似。差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是“后繼是否為空”，而是“后繼是否為頭結(jié)點(diǎn)”?？盏难h(huán)鏈表由只含一個(gè)自成循環(huán)的頭結(jié)點(diǎn)表示。head圖2-7帶頭結(jié)點(diǎn)的循環(huán)鏈表示意圖在很多實(shí)際問題中，表的操作常常是在表的首尾位置上進(jìn)行，此時(shí)頭指針表示的循環(huán)鏈表就顯得不夠方便.如果改用尾指針rear來表示循環(huán)鏈表，則查找開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)都很方便。a1的存儲(chǔ)位置是：(rear–>next)—>nextan的存儲(chǔ)位置是：rear顯然，查找時(shí)間都是O(1)因此，實(shí)際中多采用尾指針表示循環(huán)鏈表。非空表空表rearrear頭結(jié)點(diǎn)只有一頭結(jié)點(diǎn)兩個(gè)單循環(huán)鏈表（用尾指針表示）的鏈接示意圖reararearbp①②③④例、在鏈表上實(shí)現(xiàn)將兩個(gè)線性表(a1，a2，a3，…an)和(b1，b2，b3，…bn)鏈接成一個(gè)線性表的運(yùn)算。

SLinkconnect(SLinkreara,SLinkrearb){p=reara—>next;//p為表A的頭指針

reara—>next=(rearb—>next)—>next//將表B連接到表A的尾

delete(rearb—>next);//釋放表B的頭結(jié)點(diǎn)

rearb—>next=p;//將表B的尾結(jié)點(diǎn)的指針域指向表A的頭

return(rearb);//返回新循環(huán)鏈表的尾指針

}只需修改指針，無需遍歷時(shí)間復(fù)雜度為：O（1）2.3.4

雙向鏈表在循環(huán)鏈表中，訪問結(jié)點(diǎn)的特點(diǎn)訪問后繼結(jié)點(diǎn)，只需要向后走一步，而訪問前驅(qū)結(jié)點(diǎn)，就需要轉(zhuǎn)一圈。結(jié)論：循環(huán)鏈表并不適用于經(jīng)常訪問前驅(qū)結(jié)點(diǎn)的情況。解決方法：在需要頻繁地同時(shí)訪問前驅(qū)和后繼結(jié)點(diǎn)的時(shí)候，使用雙向鏈表。所謂雙向鏈表。雙向鏈表就是每個(gè)結(jié)點(diǎn)有兩個(gè)指針域。一個(gè)指向后繼結(jié)點(diǎn)，另一個(gè)指向前驅(qū)結(jié)點(diǎn)。圖2-8headpriordatanext(a)(b)用C語言實(shí)現(xiàn)雙向鏈表的類型定義typedefstructDuLNode{ElemTypedata;structDuLNode*prior;structDuLNode*next;}DuLNode,*DuLink;

與單鏈表類似，雙向鏈表也是由指向頭結(jié)點(diǎn)的頭指針唯一確定，若將頭尾結(jié)點(diǎn)鏈接起來則構(gòu)成雙向循環(huán)鏈表?？盏碾p向循環(huán)鏈表則由只含一個(gè)自成雙環(huán)的頭結(jié)點(diǎn)表示。

在雙向鏈表上進(jìn)行操作基本上和單向鏈表相同，例如，查找結(jié)點(diǎn)也是要從頭指針指示的頭結(jié)點(diǎn)開始，但插入和刪除時(shí)必須同時(shí)修改兩個(gè)方向上的指針。（1）在雙向循環(huán)鏈表中，第i個(gè)數(shù)據(jù)元素之前插入數(shù)據(jù)元素e。在雙向鏈表中的p結(jié)點(diǎn)之前插入s結(jié)點(diǎn)應(yīng)使用下列語句序列：

s->next=p;

s->prior=p->prior;

p->prior->next=s;p->prior=s;圖2-9ps問：在p結(jié)點(diǎn)之后插入呢？完整的算法：voidListInsert_DuL((DuLink&L,inti,ElemTypee){//在雙向循環(huán)鏈表L中第i個(gè)位置之前插入元素eif(i<1||i>ListLength_DuL(L)+1)exit(1);//檢測i值的合理性

s=newDuNode;//為新結(jié)點(diǎn)分配存儲(chǔ)單元

if(!s)exit(1);s->data=e;for(p=L,j=0;p&&j<i;p=p->next,j++);//尋找第i個(gè)結(jié)點(diǎn)

s->next=p;s->prior=p->prior;//將新結(jié)點(diǎn)插入

p->prior->next=s;p->prior=s;}//ListInsert_DuL（2）在雙向循環(huán)鏈表中，刪除第i個(gè)數(shù)據(jù)元素。voidListDelete_DuL(DuLink&L,inti,ElemType&e)

{

//刪除帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L的第i個(gè)結(jié)點(diǎn)，并以e返回它的數(shù)據(jù)元素

if(i<1||i>ListLength_DuL(L)+1)exit(1);//檢測i值的合理性

for(p=L,j=0;p&&j<i;p=p->next,j++);//尋找第i個(gè)結(jié)點(diǎn)

e=p->data;

p->prior->next=p->next;p->next->prior=p->prior;deletep;}//ListDelete_DuL關(guān)于順序表和鏈表的比較（1）順序表是用數(shù)組實(shí)現(xiàn)的，而鏈表是用指針來實(shí)現(xiàn)的。因此：當(dāng)線性表的長度變化較大，難以估計(jì)其存儲(chǔ)規(guī)模時(shí)，宜采用動(dòng)態(tài)鏈表作為存儲(chǔ)結(jié)構(gòu).當(dāng)線性表的長度變化不大，易于事先確定其大小時(shí)，為了節(jié)約存儲(chǔ)空間，宜采用順序表作為存儲(chǔ)結(jié)構(gòu)。（基于空間的考慮）（2）順序表是一種隨機(jī)存取結(jié)構(gòu)，對表中任一結(jié)點(diǎn)都可在O(1)時(shí)間內(nèi)直接存取。而鏈表中的結(jié)點(diǎn)則需用從頭指針開始順鏈掃描，時(shí)間復(fù)雜度為O(n)。因此：若線性表的操作主要是查找，很少涉及到插入、刪除操作時(shí)，可采用順序表結(jié)構(gòu)。若要頻繁地進(jìn)行插入和刪除操作，宜采用鏈表作為存儲(chǔ)結(jié)構(gòu)。若表的插入、刪除操作主要發(fā)生在表的頭尾兩端，則宜采用有尾指針的單循環(huán)鏈表。

靜態(tài)鏈表——用一維數(shù)組和游標(biāo)來描述。利用數(shù)組定義，運(yùn)算過程中存儲(chǔ)空間大小不變。靜態(tài)單鏈表的存儲(chǔ)結(jié)構(gòu)#defineMAXSIZE1000

//預(yù)分配最大的元素個(gè)數(shù)（連續(xù)空間）

typedefstruct{ElemTypedata;//數(shù)據(jù)域

intcur;//指示域

}component,SLinkList[MAXSIZE];

//這是一維結(jié)構(gòu)型例

1、一線性表

S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)，用靜態(tài)鏈表如何表示？data1ZHAO3LI5QIAN6WU0ZHOU4SUN2…………0123456…999cur說明1：假設(shè)S為SLinkList型變量，則S[MAXSIZE]

為一個(gè)靜態(tài)鏈表；S[0].cur則表示第1個(gè)結(jié)點(diǎn)在數(shù)組中的位置。說明2：如果數(shù)組的第i個(gè)分量表示鏈表的第k個(gè)結(jié)點(diǎn)，則:S[i].data表示第k個(gè)結(jié)點(diǎn)的數(shù)據(jù)；S[i].cur

表示第k+1個(gè)結(jié)點(diǎn)(即k的直接后繼)的位置。i頭結(jié)點(diǎn)說明3：靜態(tài)鏈表的插入與刪除操作與普通鏈表一樣，不需要移動(dòng)元素，只需修改指示器就可以了。例2：在線性表

S=(ZHAO,QIAN,SUN,LI,ZHOU,WU)的QIAN,SUN之間插入新元素LIU，可以這樣實(shí)現(xiàn)：Step1:將QIAN的指示器原內(nèi)容備份到臨時(shí)變量temp：temp=S[3].cur；Step2:將QIAN的指示器換為新元素LIU的位置：S[3].cur=7；Step3:將LIU的指示器變?yōu)楹罄^SUN的位置：S[7].cur=temp；data1ZHAO3LI5QIAN6WU0ZHOU4SUN2……01234567……999curi頭結(jié)點(diǎn)temp676LIU為了辨明數(shù)組中哪些分量未被使用，將所有未被使用過以及被刪除的分量用游標(biāo)連成一個(gè)備用的鏈表，即，備用鏈，S[0].cur為備用鏈的頭指針。已使用的分量連成使用鏈，S[1].cur為使用鏈的頭指針。在創(chuàng)建使用鏈時(shí)分配。如，左圖為一個(gè)空鏈data12345678……001234567……999curi備用鏈

頭結(jié)點(diǎn)data82ZHAO4LI6QIAN7WU0ZHOU5SUN3……001234567……999curi備用鏈

頭結(jié)點(diǎn)使用鏈

頭結(jié)點(diǎn)data12345678……001234567……999curi備用鏈

頭結(jié)點(diǎn)靜態(tài)鏈表操作的實(shí)現(xiàn)1、在靜態(tài)鏈表中查找值為e的元素intLocateElem_SL(SLinkListS,ElemTypee)//S為使用鏈的頭{I=S[0].cur;while(I&&S[I].data!=e)

I=S[I].cur;//使用鏈向后指(P=P->next)returnI;}2、在靜態(tài)鏈表中實(shí)現(xiàn)new和delete功能

(1)初始化靜態(tài)鏈表(制作備用鏈表)VoidInitSpace_SL(SLinkList&space)

//將一維數(shù)組space中各分量鏈成一個(gè)備用鏈表，space[0].cur為頭指針，“0”表示空指針{for(I=0;I<MAXSIZE–1;++I)space[I].cur=I+1;space[MAXIZE–1].cur=0;}從備用鏈取得一個(gè)結(jié)點(diǎn)

(返回分配的結(jié)點(diǎn)下標(biāo))IntMalloc_SL(SLinkList&space){I=space[0].cur;if(space[0].cur)space[0].cur=space[I].cur;returnI;}//從備用鏈頭取一結(jié)點(diǎn)I(3)

將空閑結(jié)點(diǎn)鏈結(jié)到備用鏈上

(下標(biāo)為k的空閑結(jié)點(diǎn)回收)voidFree_SL(SLinkList&space,intk){//將下標(biāo)為k的空閑結(jié)點(diǎn)回收到備用鏈表

space[k].cur=space[0].cur;space[0].cur=k;}//插在備用鏈頭3、(A-B)∪(B-A)的算法Voiddifference(SLinklist&space,int&S){InitSpace_SL(space);

S=Malloc_SL(space);

r=S;//r指向Sscanf(m,n);//A和B的元素個(gè)數(shù)

for(j=1;j<=m;++j){I=Malloc_SL(space);scanf(space[I].data);

space[r].cur=I;r=I;//r指向鏈尾

}space[r].cur=0;

for(j=1;j<=n;++j){scanf(b);p=S;//p用來存放訪問結(jié)點(diǎn)的前驅(qū)

k=space[S].cur;//當(dāng)前訪問結(jié)點(diǎn)

while(k!=space[r].cur&&space[k].data!=b){p=k;k=space[k].cur;}//遍歷A鏈

if(k==space[r].cur)//搜索到表尾，需插入

{I=Malloc_SL(space);space[I].data=b;space[I].cur=space[r].curspace[r].cur=I;}//插在r的后面

else//搜索到相同元素，需刪除

{space[p].cur=space[k].cur;Free_SL(