第2章線性表2.1線性表及其邏輯結(jié)構(gòu)2.2線性表的順序存儲結(jié)構(gòu)及運算實現(xiàn)2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運算實現(xiàn) 2.1線性表及其邏輯結(jié)構(gòu)

2.1.1線性表的定義

線性表是一種線性結(jié)構(gòu)。線性結(jié)構(gòu)的特點是數(shù)據(jù)元素之間是線性關(guān)系，數(shù)據(jù)元素“一個接一個的排列”；并且，在一個線性表中所有數(shù)據(jù)元素的類型都是相同的。簡單地說，一個線性表是n個元素的有限序列，其特點是在數(shù)據(jù)元素的非空集合中：

(1)存在唯一一個稱為“第一個”的元素。

(2)存在唯一一個稱為“最后一個”的元素。

(3)除第一個元素之外，序列中的每一個元素只有一個直接前驅(qū)。

(4)除最后一個元素之外，序列中的每一個元素只有一個直接后繼。

因此，我們可以給出線性表的定義如下：

線性表是具有相同數(shù)據(jù)類型的n(n≥0)個數(shù)據(jù)元素的有限序列，通常記為

(2-1)其中，n為表長，n=0時稱為空表。式(2-1)表示相鄰元素之間存在著順序關(guān)系：ai-1稱為ai的直接前驅(qū)，ai+1稱為ai的直接后繼。也就是說：對于ai，當(dāng)i=2,…,n時，有且僅有一個直接前驅(qū)ai-1；當(dāng)i=1,2,…,n-1時，有且僅有一個直接后繼ai+1；而a1是表中的第一個元素，它沒有前驅(qū)；an是表中的最后一個元素，它沒有后繼。正是由于存在數(shù)據(jù)元素相鄰的這種線性關(guān)系，因此線性表結(jié)構(gòu)是線性的。由式(2-1)還可得知：對非空線性表，每個數(shù)據(jù)元素在表中都有一個確定的位置，即數(shù)據(jù)元素ai在表中的位置僅取決于元素ai本身的序號i。

從邏輯關(guān)系上看，線性結(jié)構(gòu)的特點是數(shù)據(jù)元素之間存在著“一對一”的邏輯關(guān)系。通常把具有這種特點的數(shù)據(jù)結(jié)構(gòu)稱為線性結(jié)構(gòu)。反之，任何一個線性結(jié)構(gòu)(其數(shù)據(jù)元素必須是同一類型)都可以用線性表的形式表示出來，只需按照數(shù)據(jù)元素的邏輯關(guān)系把它們順序排列就可以了。由線性表的定義可以看出，線性表具有如下特征：

(1)均勻性：線性表中的所有數(shù)據(jù)元素必須具有相同的數(shù)據(jù)類型，無論該類型為簡單類型還是結(jié)構(gòu)類型。也即，線性表中每個數(shù)據(jù)元素的長度、大小和類型都相同。

(2)有序性：線性表中各數(shù)據(jù)元素是有序的，且各數(shù)據(jù)元素之間的次序是不能改變的。為了反映這種有序性，對線性表中的每一個數(shù)據(jù)元素用序號標(biāo)識，并且所有序號均為整數(shù)。2.1.2線性表的基本操作

數(shù)據(jù)結(jié)構(gòu)的運算是定義在邏輯結(jié)構(gòu)層面上，而運算的具體實現(xiàn)則建立在存儲結(jié)構(gòu)上。因此，下面定義的線性表基本運算是作為邏輯結(jié)構(gòu)的一部分，并且每一個操作的具體實現(xiàn)只有在確定了線性表的存儲結(jié)構(gòu)之后才能完成。

歸納起來，對線性表實施的基本操作有如下幾種：

(1)置線性表為空：L=Init_List()。操作結(jié)果生成一個空的線性表L。

(2)求線性表的長度：Length_List(L)。求得線性表中數(shù)據(jù)元素的個數(shù)。

(3)取表中第i個元素：Get_List(L,i)。當(dāng)1≤i≤Length_List(L)時，操作結(jié)果是返回線性表L中的第i個數(shù)據(jù)元素ai的值或ai的地址。

(4)按給定值x查找：Locate_List(L,x)。若線性表L中存在值為x的數(shù)據(jù)元素，則返回首次出現(xiàn)在L中其值為x的數(shù)據(jù)元素的序號或地址，即查找成功；否則返回0值。

(5)插入操作：Insert_List(L,i,x)。當(dāng)1≤i≤n+1(n為插入前表L的長度)時，在線性表L的第i個位置上插入一個值為x的新數(shù)據(jù)元素，這樣使序號為i、i+1、…、n的數(shù)據(jù)元素變?yōu)樾蛱枮閕+1、i+2、…、n+1的數(shù)據(jù)元素。插入后新表長=原表長+1。

(6)刪除操作：Delete_List(L,i)。當(dāng)1≤i≤n(n為刪除前表L的長度)時，在線性表L中刪除序號為i的數(shù)據(jù)元素，刪除后使序號為i+1、i+2、…、n的數(shù)據(jù)元素變?yōu)樾蛱枮閕、i+1、...、n-1的數(shù)據(jù)元素。刪除后新表長=原表長-1。

2.2線性表的順序存儲結(jié)構(gòu)及運算實現(xiàn)

2.2.1線性表的順序存儲——順序表

線性表的順序存儲是用一組地址連續(xù)的存儲單元按順序依次存放線性表中的每一個元素(數(shù)據(jù)元素)，這種存儲方式存儲的線性表稱為順序表。在這種順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上也相鄰，也即無需增加額外存儲空間來表示線性表中元素之間的邏輯關(guān)系。

由于順序表中每個元素具有相同的類型，即其長度相同，則順序表中第i個元素ai的存儲地址為Loc(ai)?=?Loc(a1)+(i-1)×L1≤i≤n其中：Loc(a1)為順序表的起始地址(即第一個元素的地址)；L為每個元素所占存儲空間的大小。由此可知，只要知道順序表的起始地址和每個元素所占存儲空間的大小，就可以求出任意一個元素的存儲地址，即順序表中的任意一個元素都可以隨機(jī)存取(隨機(jī)存取的特點是存取每一個元素所花費的時間相同)。

在程序設(shè)計語言中，一維數(shù)組在內(nèi)存中占用的存儲空間就是一組連續(xù)的存儲區(qū)域，并且每個數(shù)組元素的類型相同，故用一維數(shù)組來存儲順序表非常合適。在C語言中，一維數(shù)組的數(shù)組元素下標(biāo)是從0開始的，這樣順序表中序號為i的元素ai存儲在一維數(shù)組中時其下標(biāo)為i-1。為了避免這種不一致性，我們約定：順序表中的元素存放于一維數(shù)組時是從下標(biāo)為1的位置開始的。這樣，元素的序號即為其下標(biāo)。此外，考慮到順序表的運算有插入、刪除等操作，即表長是可變的，因此，數(shù)組的容量需要設(shè)計得足夠大。我們用data[MAXSIZE]來存儲順序表，而MAXSIZE是根據(jù)實際問題所定義的一個足夠大的整數(shù)。此時順序表中的數(shù)據(jù)由data[1]開始依次存放。由于當(dāng)前順序表中的實際元素個數(shù)可能還未達(dá)到MAXSIZE-1值，因此需要用一個len變量來記錄當(dāng)前順序表中最后一個元素在數(shù)組中的位置(即下標(biāo))；即len起著一個指針的作用，它始終指向順序表中的最后一個元素且表空時len=0。從結(jié)構(gòu)上考慮，我們將data和len組合在一個結(jié)構(gòu)體里來作為順序表的類型：

typedefstruct

{

datatypedata[MAXSIZE];//存儲順序表中的元素

intlen;//順序表的表長

}SeqList;//順序表類型

其中，datatype為順序表中元素的類型，在具體實現(xiàn)中可為int、float、char類型或其他結(jié)構(gòu)類型。我們約定，data數(shù)組存放順序表的元素是從下標(biāo)1開始的；也即，順序表中的元素可存放在data數(shù)組中下標(biāo)為1～MAXSIZE-1的任何一個位置。這樣，第i個元素的實際存放位置就是i；len為順序表的表長。有了順序表類型，則可以定義如下順序表和指向順序表的指針變量：

SeqListList,*L;

在此，List是一個結(jié)構(gòu)體變量，它內(nèi)部含有一個可存儲順序表的data數(shù)組；L是指向List這類結(jié)構(gòu)體變量的指針變量，如“L=&List;”；或者動態(tài)生成一個順序表存儲空間并由L指向該空間，如“L=(SeqList*)malloc(sizeof(SeqList));”。在這種定義下，List.data[i]或L->data[i]均表示順序表中第i個元素的值；而List.len或L->len均表示順序表的表長。兩種表示示意如圖2-1所示。圖2-1線性表順序存儲的不同表示2.2.2順序表上基本運算的實現(xiàn)

1.順序表的初始化

順序表的初始化就是構(gòu)造一個空表，將L設(shè)為指針變量，然后動態(tài)分配順序表的存儲空間，并設(shè)表長len=0。

算法如下：

SeqList*Init_SeqList()

{

SeqList*L;

L=(SeqList*)malloc(sizeof(SeqList));

L->len=0;

returnL;

}

2.建立順序表

依次輸入順序表的長度n和n個順序表元素即可建立順序表。算法如下：

voidCreatList(SeqList**L)

{

inti,n;

printf("InputlengthofList:");

scanf("%d",&n);

printf("InputelementsofList:\n");

for(i=1;i<=n;i++)

scanf("%d",&(*L)->data[i]);

(*L)->len=n;

}注意，形參**L是為了保證在函數(shù)CreatList中生成的順序表返回到主調(diào)函數(shù)空間時仍能夠找到它，這樣當(dāng)CreatList函數(shù)調(diào)用結(jié)束時，仍可在主調(diào)函數(shù)中訪問該順序表。主調(diào)函數(shù)必需設(shè)置一個SeqList型指針變量(如SeqList*p)，然后使用語句“p=Init_SeqList();”和語句“CreatList(&p);”即可完成順序表的建立。插入時可能出現(xiàn)下述非法情況：

(1)當(dāng)L->len=MAXSIZE-1，順序表已放滿元素。

(2)當(dāng)i＜1或i≥MAXSIZE時，i已超出數(shù)組范圍。

(3)當(dāng)L->len+1＜i＜MAXSIZE時，i雖沒有超出數(shù)組范圍，但i指示的位置使得順序表元素不再連續(xù)存放。

(2)、(3)可以用i＜1或i＞L->len+1表示。算法如下：

voidInsert_SeqList(SeqList*L,inti,datatypex)

{

intj;

if(L->len==MAXSIZE-1) //表滿

printf(“TheListisfull!\n”);

else

if(i<1||i>L->len+1) //插入位置非法

printf(“Thepositionisinvalid!\n”);

else

{

for(j=L->len;j>=i;j--)

//將an～ai順序后移一個元素位置

L->data[j+1]=L->data[j];

L->data[i]=x;

//插入x到第i個位置

L->len++;

//表長增1

}

}順序表進(jìn)行插入運算的時間消耗主要在表中元素的移動上。對n個元素的順序表來說：

(1)可插入的位置從1～n+1共有n+1個位置。

(2)在第i個位置上插入新元素時需要移動的元素個數(shù)為：n-(i-1)?=?n-i?+?1(如圖2-2所示)。圖2-2插入新元素時需要移動的元素示意圖也即，在順序表上做插入操作需要移動表中一半的元素，顯然時間復(fù)雜度為O(n)。刪除時可能會出現(xiàn)下述非法情況：

(1)當(dāng)L->len=0時，順序表為空而無法刪除。

(2)當(dāng)i＜1或i＞L->Len時，i位置上沒有元素，即刪除位置非法。算法如下：

voidDelete_SeqList(SeqList*L,datatypei)

{

intj;

if(L->len==0) //表為空

printf("TheListisempt!\n");

else

if(i<1||i>L->len) //刪除位置非法

printf("Thepositionisinvalid!\n");

else

{

for(j=i+1;j<=L->len;j++) //將ai+1～an順序前移一個位置實現(xiàn)對ai的刪除

L->data[j-1]=L->data[j];

L->len--; //表長減1

}

}與插入運算相同，刪除運算的時間消耗主要在表中元素的移動上。對有n個元素的順序表來說：

(1)可刪除的位置從1～n共有n個。

(2)刪除第i個元素時需要移動的元素的個數(shù)為：n-i(如圖2-3所示)。圖2-3刪除ai時要移動的元素示意圖也即，在順序表上做刪除運算大約需要移動表中一半的元素，顯然算法的時間復(fù)雜度為O(n)。

5.查找運算

查找運算是指在順序表中查找與給定值x相等的元素。在順序表中完成該運算最簡單的方法是：從第一個元素a1起依次和x比較，直到找到一個與x相等的元素時則返回該元素的存儲位置(即下標(biāo))；如果查遍整個表都沒找到與x相等的元素則返回0值。算法一如下：

intLocation_SeqList(SeqList*L,datatypex)

{

inti=1; //從第一個元素開始查找

while(i<L->len&&L->data[i]!=x) //順序表未查完且當(dāng)前元素不是要找的元素

i++;

if(L->data[i]==x)

returni; //找到則返回其位置值

else

return0; //未找到則返回0值

}該算法還可以改進(jìn)為如下算法二：

intLocation_SeqList1(SeqList*L,datatypex)

{

i=L->len;

L->data[0]=x;

while(L->data[i]!=x)

i--;

returni;

}算法一：算法二：因此，查找算法的時間復(fù)雜度為O(n)。

例2.1

已知線性表A長度為n，試寫出將該線性表逆置的算法。

【解】實現(xiàn)對線性表元素逆置的示意如圖2-4所示。因此，對n個元素進(jìn)行逆置的for語句只能循環(huán)n/2次。

實現(xiàn)逆置的算法如下：

voidCoverts(SeqList*A)

{

inti,n;

intx;

n=A->len; //n為線性表*A的長度

for(i=1;i<n/2;i++) //實現(xiàn)逆置

{

x=A->data[i];

A->data[i]=A->data[n-i+1];

A->data[n-i+1]=x;

}

}圖2-4實現(xiàn)線性表元素逆置示意

例2.2

有順序表A和B，其表中元素均按由小到大的順序排列。編寫一個算法將它們合并成一個順序表C，并且要求表C中的元素也按由小到大的順序排列。

【解】算法實現(xiàn)如下：

voidMerge(SeqList*A,SeqList*B,SeqList**C)

{//形參**C是為了保證在返回到主調(diào)函數(shù)時仍能夠找到所生成的順序表C

inti=1,j=1,k=1;

if(A->len+B->len>=MAXSIZE)

printf("Error!\n");

else

{*C=(SeqList*)malloc(sizeof(SeqList));

while(i<=A->len&&j<=B->len)

if(A->data[i]<B->data[j])

(*C)->data[k++]=A->data[i++];

else

(*C)->data[k++]=B->data[j++];

while(i<=A->len) //當(dāng)表A未復(fù)制完

(*C)->data[k++]=A->data[i++];

while(j<=B->len) //當(dāng)表B未復(fù)制完

(*C)->data[k++]=B->data[j++];

(*C)->len=k-1; //存儲表長

}

}

算法的時間復(fù)雜度是O(m+n)，其中m是A的表長，n是B的表長。2.3線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)及運算實現(xiàn)

2.3.1單鏈表由于線性表中的每個元素至多只有一個前驅(qū)元素和一個后繼元素，即元素之間是“一對一”的邏輯關(guān)系。為了在元素之間建立起這種線性關(guān)系，采用鏈表存儲最簡單也最常用的方法是：在每個元素中除了含有數(shù)據(jù)信息外，還要有一個指針用來指向它的直接后繼元素，即通過指針建立起元素之間的線性關(guān)系，我們稱這種元素為結(jié)點，結(jié)點中存放數(shù)據(jù)信息的部分稱為數(shù)據(jù)域，存放指向后繼結(jié)點指針的部分稱為指針域(如圖2-5所示)。因此，線性表中的n個元素通過各自結(jié)點的指針域“鏈”在一起而被稱之為鏈表，因為每個結(jié)點中只有一個指向后繼結(jié)點的指針，所以稱其為單鏈表。圖2-5單鏈表結(jié)點結(jié)構(gòu)鏈表是由一個個結(jié)點構(gòu)成的，單鏈表結(jié)點的定義如下：

typedefstructnode

{

datatypedata; //data為結(jié)點的數(shù)據(jù)信息

structnode*next; //next為指向后繼結(jié)點的指針

}LNode; //單鏈表結(jié)點類型

圖2-6是線性表(a1,a2,a3,a4,a5,a6)對應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)示意圖。當(dāng)然必須將第一個結(jié)點的地址200放入到一個指針變量如H中，最后一個結(jié)點由于沒有后繼，其指針域必須置空(NULL)以表明鏈表到此結(jié)束。我們通過指針H就可以由第一個結(jié)點的地址開始“順藤摸瓜”的找到每一個結(jié)點?？梢钥闯觯€性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)具有以下特點：

(1)邏輯關(guān)系相鄰的元素在物理位置上可以不相鄰。

(2)表中的元素只能順序訪問而不能隨機(jī)訪問。

(3)表的大小可以動態(tài)變化。

(4)插入、刪除等操作只需修改指針(地址)而無需移動元素。

作為線性表的一種存儲結(jié)構(gòu)，我們關(guān)心的是結(jié)點之間的邏輯關(guān)系，而對每個結(jié)點的實際存儲地址并不感興趣。所以通常將單鏈表形象地畫為圖2-7的形式而不再用圖2-6的形式來表示。

通常我們用“頭指針”來標(biāo)識一個單鏈表，如單鏈表L、單鏈表H等均是指單鏈表中的第一個結(jié)點的地址存放在指針變量L或H中。當(dāng)頭指針為“NULL”時，則表示單鏈表為空(如圖2-7所示)。圖2-7不帶頭結(jié)點的單鏈表示意圖通常需要3個指針變量來完成一個單鏈表的建立。例如，我們用指針變量head指向單鏈表的第一個結(jié)點(表頭結(jié)點)；指針變量q則指向單鏈表的鏈尾結(jié)點；指針變量p則指向新產(chǎn)生的鏈表結(jié)點。并且，新產(chǎn)生的鏈表結(jié)點*p總是插入到鏈尾結(jié)點*q的后面而成為新的鏈尾結(jié)點。因此，插入結(jié)束時要使指針變量q指向這個新的鏈尾結(jié)點(即q始終指向鏈尾結(jié)點)。單鏈表建立的過程如下：

(1)表頭結(jié)點的建立

p=(structnode*)malloc(sizeof(structnode)); //動態(tài)申請一個結(jié)點空間

scanf(“%d”,p->data);//給結(jié)點中的數(shù)據(jù)成員輸入數(shù)據(jù)

p->next=NULL; //置鏈尾結(jié)點標(biāo)志

head=p; //第一個產(chǎn)生的鏈表結(jié)點即為頭結(jié)點

q=p; //第一個產(chǎn)生的鏈表結(jié)點同時也是鏈尾結(jié)點

(2)其他鏈表結(jié)點的建立

p=(structnode*)malloc(sizeof(structnode)); //動態(tài)申請一個結(jié)點空間

scanf(“%d”,p->data);//給結(jié)點中的數(shù)據(jù)成員輸入數(shù)據(jù)

p->next=NULL; //置鏈尾結(jié)點標(biāo)志

q->next=p;//將這個新結(jié)點鏈接到原鏈尾結(jié)點的后面

q=p; //使指針q指向這個新的鏈尾結(jié)點由于指針變量head總是指向單鏈表的表頭結(jié)點(第一個鏈表結(jié)點)，因此表頭結(jié)點的建立過程與其他鏈表結(jié)點的建立是有區(qū)別的。另外，新產(chǎn)生的鏈表結(jié)點*p同時又是鏈尾結(jié)點，故除了給結(jié)點*p的數(shù)據(jù)成員賦值之外，還應(yīng)使*p的指針成員p->next為空(NULL)來表示新的鏈尾。表頭結(jié)點的建立如圖2-8(a)所示，在圖2-8(a)中我們用“^”表示空指針值。圖2-8鏈表的建立對于其他鏈表結(jié)點的建立，則多了一個將新產(chǎn)生的鏈表結(jié)點*p鏈接到原鏈尾結(jié)點*q后面的操作。由于指針變量q總是指向單鏈表的鏈尾結(jié)點，因此待新鏈表結(jié)點*p產(chǎn)生之后，原鏈尾結(jié)點*q的指針q->next應(yīng)指向這個新鏈表結(jié)點*p，這樣才能使新鏈表結(jié)點*p鏈到原鏈尾結(jié)點*q之后而成為新的鏈尾結(jié)點，這一操作過程是由語句“q->next=p;”完成的。最后還應(yīng)使指針變量q指向這個新的鏈尾結(jié)點*p，即通過語句“q=p;”來使q指向新的鏈尾結(jié)點，這樣使得指針q始終指向鏈尾結(jié)點。其他鏈表結(jié)點的建立如圖2-8(b)所示。在線性表的鏈?zhǔn)酱鎯χ校瑸榱吮阌趩捂湵淼慕⒉⑶沂共迦牒蛣h除操作的實現(xiàn)在各種情況下統(tǒng)一，通常在單鏈表的第一個結(jié)點之前添加了一個頭結(jié)點；該頭結(jié)點不存儲任何數(shù)據(jù)信息，只是用其指針域中的指針指向單鏈表的第一個數(shù)據(jù)結(jié)點，即通過頭指針指向的頭結(jié)點，可以訪問到單鏈表中的所有數(shù)據(jù)結(jié)點(如圖2-9所示)。在線性表的鏈?zhǔn)酱鎯χ校瑸榱吮阌趩捂湵淼慕⒉⑶沂共迦牒蛣h除操作的實現(xiàn)在各種情況下統(tǒng)一，通常在單鏈表的第一個結(jié)點之前添加了一個頭結(jié)點；該頭結(jié)點不存儲任何數(shù)據(jù)信息，只是用其指針域中的指針指向單鏈表的第一個數(shù)據(jù)結(jié)點，即通過頭指針指向的頭結(jié)點，可以訪問到單鏈表中的所有數(shù)據(jù)結(jié)點(如圖2-9所示)。圖2-9帶頭結(jié)點的單鏈表2.3.2單鏈表上基本運算的實現(xiàn)

1.建立單鏈表

1)在鏈表頭部插入結(jié)點的方式建立單鏈表(頭插法)

鏈表與順序表不同，它是一個動態(tài)生成的過程，鏈表中每個結(jié)點占用的存儲空間不是預(yù)先分配的，而是在程序運行中動態(tài)生成的。在C語言中，動態(tài)生成的結(jié)點其存儲空間都取自于“堆”(堆是一種可以任意申請和釋放的存儲結(jié)構(gòu)，本書不予介紹)，而堆不屬于某一個函數(shù)，故在被調(diào)函數(shù)中生成的單鏈表在被調(diào)函數(shù)運行結(jié)束后仍然存在，只不過必須將單鏈表的頭指針傳回給主調(diào)函數(shù)方可在主調(diào)函數(shù)中訪問到這個單鏈表：一種方法是使用指向指針的指針如**head來完成；另一種方法則是通過能夠返回指針值的被調(diào)函數(shù)來完成。此外，為了保證以后插入、刪除操作變得簡單，所生成的單鏈表還應(yīng)有頭結(jié)點。單鏈表建立是從空表開始的，每讀入一個數(shù)據(jù)則申請一個結(jié)點，然后插在頭結(jié)點之后，圖2-10給出了存儲線性表('A','B','C','D')的單鏈表建立過程，因為是在單鏈表頭部插入，故生成結(jié)點的順序與線性表中元素的順序正好相反。另外，對本章算法中出現(xiàn)的結(jié)點，其類型為datatype的數(shù)據(jù)域data均默認(rèn)為char類型。圖2-10在頭部插入建立單鏈表算法如下：

voidCreateLinkList(LNode**head)

{//將主調(diào)函數(shù)中指向待生成單鏈表的指針地址(如&p)傳給**head

charx;

LNode*p;

*head=(LNode*)malloc(sizeof(LNode)); //在主調(diào)函數(shù)空間生成鏈表頭結(jié)點

(*head)->next=NULL; //*head為鏈表頭指針

printf("Inputanycharstring:\n");

scanf("%c",&x); //結(jié)點的數(shù)據(jù)域為char型，讀入結(jié)點數(shù)據(jù)

while(x!='\n') //生成鏈表的其他結(jié)點

{

p=(LNode*)malloc(sizeof(LNode)); //申請一個結(jié)點空間

p->data=x;

p->next=(*head)->next; //將頭結(jié)點的next值賦給新結(jié)點*p的next

(*head)->next=p; //頭結(jié)點的next指針指向新結(jié)點*p實現(xiàn)在表頭插入

scanf("%c",&x); //繼續(xù)生成下一個新結(jié)點

}

}另一種生成單鏈表的方法是在算法所在的函數(shù)空間中直接生成，然后將單鏈表的頭指針返回給主調(diào)函數(shù)：

LNode*CreateLinkList()

{

LNode*head,*p; //head為單鏈表頭指針，p為生成單鏈表的暫存指針

charx;

head=(LNode*)malloc(sizeof(LNode));//生成鏈表頭結(jié)點

head->next=NULL; //head為鏈表頭指針

printf("Inputanycharstring:\n");

scanf("%c",&x); //結(jié)點的數(shù)據(jù)域為char型，讀入結(jié)點數(shù)據(jù)

while(x!='\n') //生成鏈表的其他結(jié)點

{

p=(LNode*)malloc(sizeof(LNode)); //申請一個結(jié)點空間

p->data=x;

p->next=head->next; //將頭結(jié)點的next值域賦給新結(jié)點的*p的next

head->next=p; //頭結(jié)點的next指針指向新結(jié)點的*p實現(xiàn)在表頭插入

scanf("%c",&x); //繼續(xù)生成下一個新結(jié)點

}

returnhead; //返回單鏈表表頭指針

}

2)在鏈表的尾部插入結(jié)點的方式建立單鏈表(尾接法)

在頭部插入結(jié)點的方式生成單鏈表較為簡單，但生成結(jié)點的順序與線性表中的元素順序正好相反。若希望兩者的次序一致則可采用尾插法來生成單鏈表。由于每次都是將新結(jié)點插入到鏈表的尾部，因此必須再增加一個指針q來始終指向單鏈表的尾結(jié)點，以方便新結(jié)點的插入。圖2-11給出了在鏈尾插入結(jié)點生成單鏈表的過程示意。圖2-11在尾部插入建立單鏈表示意圖算法如下：

LNode*CreateLinkList()

{

LNode*head,*p,*q;

charx;

head=(LNode*)malloc(sizeof(LNode)); //生成頭結(jié)點

head->next=NULL;

p=head;

q=p; //指針q始終指向鏈尾結(jié)點

printf("Inputanycharstring:\n");

scanf("%c",&x);

while(x!='\n') //生成鏈表的其他結(jié)點

{

p=(LNode*)malloc(sizeof(LNode));

p->data=x;

p->next=NULL;

q->next=p; //在鏈尾插入

q=p;

scanf("%c",&x);

}

returnhead; //返回單鏈表表頭指針

}

2.求表長

算法如下：

intLength_LinkList(LNode*head)

{

LNode*p=head; //p指向單鏈表頭結(jié)點

inti=0; //i為結(jié)點計數(shù)器

while(p->next!=NULL)

{

p=p->next;

i++;

}

returni; //返回表長值i

}

求表長算法的時間復(fù)雜度為O(n)。

3.查找

1)按序號查找

從鏈表的第一個結(jié)點開始查找，若當(dāng)前結(jié)點是第i個結(jié)點則返回指向該結(jié)點的指針值，否則繼續(xù)向后查找。如果整個表都無序號為i的結(jié)點(即i大于鏈表中結(jié)點的個數(shù))則返回空指針值。算法如下：

LNode*Get_LinkList(LNode*head,inti)

{ //在單鏈表head中查找第i個結(jié)點

LNode*p=head; //由第一個結(jié)點開始查找

intj=0;

while(p!=NULL&&j<i) //當(dāng)未查到鏈尾且j小于i時繼續(xù)查找

{

p=p->next;

j++;

}

returnp; //找到則返回指向i結(jié)點的指針值，找不到則p已為空返回空值

}

2)按值查找

從鏈表的第一個數(shù)據(jù)結(jié)點開始查找，若當(dāng)前結(jié)點值等于x則返回指向該結(jié)點的指針值，否則繼續(xù)向后查找。如果整個表都找不到值等于x的結(jié)點，則返回空值。

算法如下：

LNode*Locate_LinkList(LNode*head,charx)

{ //在單鏈表中查找結(jié)點值為x的結(jié)點

LNode*p=head->next;//由第一個數(shù)據(jù)結(jié)點開始查找

while(p!=NULL&&p->data!=x) //當(dāng)未查到鏈尾且當(dāng)前結(jié)點不等于x時繼續(xù)查找

p=p->next;

returnp; //找到則返回指向值為x的結(jié)點的指針值，找不到則p已為空返回空值

}

查找算法的時間復(fù)雜度均為O(n)。

4.插入

因為鏈表中的各結(jié)點是通過指針鏈接起來的，所以我們可以通過改變鏈表結(jié)點中指針的指向來實現(xiàn)鏈表結(jié)點的插入與刪除。我們知道，數(shù)組進(jìn)行插入或刪除操作時需要移動大量的數(shù)組元素，但是鏈表的插入或刪除操作由于僅需修改有關(guān)指針的指向而變得非常容易。

在鏈表結(jié)點*p(即指針p所指結(jié)點)之后插入鏈表結(jié)點*q的示意如圖2-12所示。圖2-12在結(jié)點*p之后插入結(jié)點*q插入操作如下：

①q->next=p->next;

②p->next=q;

在涉及改變指針值的操作中一定要注意指針值的改變次序，否則容易出錯。假如上面插入操作的順序改為

①p->next=q;

②q->next=p->next;此時，①將使鏈表結(jié)點*p的指針p->next指向鏈表結(jié)點*q，②將*p的指針p->next值(指向*q)賦給了結(jié)點*q的指針q->next，這使得結(jié)點*q的指針q->next指向結(jié)點*q自身；這種操作的結(jié)果將導(dǎo)致鏈表由此斷為兩截，而后面的一截鏈表就“丟失”了。因此，在插入鏈表結(jié)點*q時，應(yīng)將鏈表結(jié)點*p的指針p->next值(指向后繼結(jié)點)先賦給結(jié)點*q的指針q->next(即語句“q->next=p->next;”)，以防止鏈表的斷開，然后再使結(jié)點*p的指針p->next改為指向結(jié)點*q(即語句“p->next=q;”)。算法如下：

voidInsert_LinkList(LNode*head,inti,batatybex)

{ //在單鏈表head的第i個位置上插入值為x的元素

LNode*p,*q;

p=Get_LinkList(head,i-1); //查找第i-1個結(jié)點

if(p==NULL)

printf("Error!\n"); //第i-1個位置不存在而無法插入

else

{

q=(LNode*)malloc(sizeof(LNode));//申請結(jié)點空間

q->data=x;

q->next=p->next; //完成插入操作①

p->next=q; //完成插入操作②

}

}

該算法的時間花費在尋找第i-1個結(jié)點上，故算法時間復(fù)雜度為O(n)。

5.刪除

要刪除一個鏈表結(jié)點必須知道它的前驅(qū)鏈表結(jié)點，只有使指針變量p指向這個前驅(qū)鏈表結(jié)點時，我們才可以通過下面的語句實現(xiàn)所要刪除的操作(如圖2-13所示)：

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

也即通過改變鏈表結(jié)點*p中指針p->nxet的指向，使它由指向待刪結(jié)點改為指向待刪結(jié)點的后繼結(jié)點，由此達(dá)到從鏈表中刪去待刪結(jié)點的目的。圖2-13刪除鏈表結(jié)點示意圖多數(shù)情況下，在刪除待刪結(jié)點*q前都要先找到這個待刪結(jié)點的前驅(qū)結(jié)點，這就需要借助一個指針變量(如p)來定位于這個前驅(qū)結(jié)點，然后才能通過下面的語句進(jìn)行刪除結(jié)點*q的操作(如圖2-14所示)。

q=p->next;; //q指向第i個結(jié)點

p->next=q->next; //從鏈表中刪除第i個結(jié)點圖2-14刪除一般鏈表結(jié)點示意圖算法如下：

voidDel_LinkList(LNode*head,inti)

{ //刪除單鏈表head上的第i個數(shù)據(jù)結(jié)點

LNode*p,*q;

p=Get_LinkList(head,i-1); //查找第i-1個結(jié)點

if(p==NULL)

printf(“第i-1個結(jié)點不存在!\n”); //待刪結(jié)點的前一個結(jié)點不存在，故無待刪結(jié)點

else

if(p->next==NULL)

printf("第i個結(jié)點不存在!\n"); //待刪結(jié)點不存在

else

{

q=p->next;; //q指向第i個結(jié)點

p->next=q->next; //從鏈表中刪除第i個結(jié)點

free(q); //系統(tǒng)回收第i個結(jié)點的存儲空間

}

}

刪除算法的時間復(fù)雜度為O(n)。2.3.3循環(huán)鏈表

所謂循環(huán)鏈表就是將單鏈表中最后一個結(jié)點的指針值由空改為指向單鏈表的頭結(jié)點，整個鏈表形成一個環(huán)。這樣，從鏈表中的任一結(jié)點位置出發(fā)都可以找到鏈表的其他結(jié)點(如圖2-15所示)。在循環(huán)鏈表上的操作基本上與單鏈表相同，只是將原來判斷指針是否為NULL改為判斷是否為頭指針，而再無其他變化。圖2-15帶頭結(jié)點的循環(huán)鏈表示意圖例如，在帶頭結(jié)點的循環(huán)鏈表中查找值等于x的結(jié)點，其實現(xiàn)算法如下：

LNode*Locate_CycLink(LNode*head,datatypex)

{

LNode*p=head->next; //由第一個數(shù)據(jù)結(jié)點開始查找

while(p!=head&&p->data!=x)//當(dāng)未查完循環(huán)鏈表且當(dāng)前結(jié)點不等于x時繼續(xù)查找

p=p->next;

if(p!=head)

returnp; //找到值等于x的結(jié)點*p，返回其指針值p

else

returnNULL; //當(dāng)p又查到頭結(jié)點時則無等于x值的結(jié)點，故返回NULL值

}由于鏈表的操作通常是在表頭或表尾進(jìn)行，因此也可改變循環(huán)鏈表的標(biāo)識方法，即不用頭指針而用一個指向尾結(jié)點的指針R來標(biāo)識循環(huán)鏈表。這種標(biāo)識的好處是可以直接找到鏈尾結(jié)點，而找到頭結(jié)點也非常容易，R->next即為指向頭結(jié)點的指針。

例如對兩個循環(huán)鏈表H1和H2做鏈接操作，即將H2的第一個數(shù)據(jù)結(jié)點鏈接到H1的尾結(jié)點之后，并將H2的尾結(jié)點中的next指針指向H1的頭結(jié)點。如果采用頭指針標(biāo)識方法，則需要遍歷整個H1鏈表直到尾結(jié)點，其時間復(fù)雜度為O(n)；而采用尾指針R1、R2來分別標(biāo)識H1和H2這兩個循環(huán)鏈表，則時間復(fù)雜度為O(1)。具體操作如下：①P=R1->next; //保存R1的頭結(jié)點指針

②R1->next=R2->next->next; //使R1鏈尾結(jié)點的next指針指向R2的第一個數(shù)據(jù)結(jié)點

free(R2->next); //系統(tǒng)回收R2頭結(jié)點的存儲空間

③R2-next->p; //R2原尾結(jié)點的next指針指向R1的頭結(jié)點而形成循環(huán)鏈表

這一過程如圖2-16所示。圖2-16兩個用尾指針標(biāo)識的循環(huán)鏈表鏈接成一個循環(huán)鏈表示意圖2.3.4雙向鏈表

相對于單鏈表來說，循環(huán)鏈表雖然有其優(yōu)點但仍有不足。因為從循環(huán)鏈表中的某個結(jié)點出發(fā)只能順著指針方向向后尋找其他結(jié)點，而無法直接到達(dá)該結(jié)點的前驅(qū)結(jié)點。要想到達(dá)它的前驅(qū)結(jié)點，則只能循環(huán)遍歷整個鏈表。需要刪除鏈表中某一結(jié)點時也存在著同樣的問題，僅僅知道待刪除結(jié)點的地址是不夠的，還必須知道待刪除結(jié)點的直接前驅(qū)結(jié)點的地址，而要找到這個直接前驅(qū)結(jié)點則又要對鏈表進(jìn)行循環(huán)遍歷。為了克服循環(huán)鏈表這種單向性的缺點，可以采用雙向鏈表結(jié)構(gòu)來滿足那些經(jīng)常需要沿兩個方向移動的鏈表。

顧名思義，所謂雙向鏈表就是指鏈表的每一個結(jié)點中除了數(shù)據(jù)域之外，還設(shè)置了兩個指針域：一個用來指向該結(jié)點的直接前驅(qū)結(jié)點；另一個用來指向該結(jié)點的直接后繼結(jié)點。每個結(jié)點的結(jié)構(gòu)如圖2-17所示。圖2-17雙向鏈表的結(jié)點結(jié)構(gòu)雙向鏈表的結(jié)點定義如下：

typedefstructdlnode

{

datatypedata; //data為結(jié)點的數(shù)據(jù)信息

structdlnode*prior,*next; //prior和next分別為指向直接前驅(qū)和直接后繼結(jié)點的指針

}DLNode; //雙向鏈表結(jié)點類型雙向鏈表也用頭指針來標(biāo)識，通常也是采用帶頭結(jié)點的循環(huán)鏈表結(jié)構(gòu)。圖2-18是帶頭結(jié)點的雙向循環(huán)鏈表示意。也即，在雙向鏈表中可以通過某結(jié)點的指針p直接得到指向它的后繼結(jié)點指針p->next，也可直接得到指向它的前驅(qū)結(jié)點指針p->prior。這樣，在查找前驅(qū)結(jié)點的操作中就無需再循環(huán)遍歷鏈表了。圖2-18帶頭結(jié)點的雙向循環(huán)鏈表示意圖設(shè)p是指向雙向循環(huán)鏈表中某一結(jié)點的指針，則p->prior->next表示的是*p結(jié)點的前驅(qū)指針prior所指前驅(qū)結(jié)點的后繼指針(該前驅(qū)結(jié)點的后繼結(jié)點即為*p結(jié)點)，即與p相等。類似地，p->next->prior也與p相等，因此有以下等式成立：

p＝p->prior->next＝p->next->prior

設(shè)p指向雙向循環(huán)鏈表中的某一結(jié)點，s指向待插入的值為x的新結(jié)點，則插入可分為兩種情況：一種是在*p結(jié)點之后插入結(jié)點*s；另一種是在*p結(jié)點之前插入結(jié)點*s。

1.在結(jié)點*p之后插入結(jié)點*s

在結(jié)點*p之后插入結(jié)點*s要注意如下兩點：

(1)首先修改待插結(jié)點*s的前驅(qū)指針和后繼指針，以避免“斷鏈”現(xiàn)象出現(xiàn)。

(2)接下來先修改*p的后繼結(jié)點之前驅(qū)指針，然后再修改*p的后繼指針。

在結(jié)點*p之后插入結(jié)點*s的示意如圖2-19所示，其操作過程如下：

①s->prior=p;

②s->next=p->next;

③p->next->prior=s;

④p->next=s;圖2-19在結(jié)點*p之后插入結(jié)點*s的操作次序示意圖

2.在結(jié)點*p之前插入結(jié)點*s

在結(jié)點*p之前插入結(jié)點*s要注意如下兩點：

(1)首先修改待插結(jié)點*s的前驅(qū)指針和后繼指針，以避免“斷鏈”現(xiàn)象出現(xiàn)。

(2)接下來先修改*p的前驅(qū)結(jié)點的后繼指針，然后再修改*p的前驅(qū)指針。

在結(jié)點*p之前插入*s的示意如圖2-20所示，其操作過程如下：

①s->prior=p->prior;

②

s->next=p;

③p->prior->next=s;

④p->prior=s;圖2-20在結(jié)點*p之前插入結(jié)點*s的操作次序示意圖注意：兩種插入方法中指針操作的順序不是唯一的但也不是任意的，操作次序不當(dāng)就不能實現(xiàn)正確地插入，還有可能使一部分鏈表“丟失”。

設(shè)指針p指向雙向鏈表中某結(jié)點，則刪除結(jié)點*p的示意圖如圖2-21所示，其操作過程如下：

①p->prior->next=p->next;

②p->next->prior=p->prior;

③free(p);圖2-21雙向鏈表中刪除結(jié)點*p操作次序示意圖建立帶頭結(jié)點的雙向循環(huán)鏈表算法如下：

DLNode*CreateDlinkList()//建立帶頭結(jié)點的雙向循環(huán)鏈表

{

DLNode*head,*s;

charx;

head=(DLNode*)malloc(sizeof(DLNode)); //先生成僅含頭結(jié)點的空雙向循環(huán)鏈表

head->prior=head;

head->next=head;

printf("Inputanycharstring:\n");

scanf("%c",&x); //讀入結(jié)點數(shù)據(jù)

while(x!='\n') //采用頭插法生成雙向循環(huán)鏈表

{

s=(DLNode*)malloc(sizeof(DLNode)); //生成待插入結(jié)點的存儲空間

s->data=x; //將讀入的數(shù)據(jù)賦給待插入結(jié)點*s

s->prior=head; //新插入的結(jié)點*s其前驅(qū)結(jié)點為頭結(jié)點*head

s->next=head->next; //插入后*s的后繼結(jié)點為頭結(jié)點*head原來的后繼結(jié)點

head->next->prior=s; //頭結(jié)點的原后繼結(jié)點其前驅(qū)結(jié)點為*s

head->next=s; //頭結(jié)點此時新的后繼結(jié)點為*s

scanf("%c",&x); //繼續(xù)讀入下一個結(jié)點數(shù)據(jù)

}

returnhead; //返回頭指針

}2.3.5靜態(tài)鏈表

有些高級語言沒有“指針”數(shù)據(jù)類型，要想發(fā)揮鏈表結(jié)構(gòu)的長處，可用一個一維數(shù)組空間來模擬鏈表結(jié)構(gòu)，即稱之為靜態(tài)鏈表。

靜態(tài)鏈表的構(gòu)造方法是用一維數(shù)組的一個數(shù)組元素來表示結(jié)點，結(jié)點中的數(shù)據(jù)域(data)仍用于存儲元素本身的信息，同時設(shè)置一個下標(biāo)域(cursor)來取代單鏈表中的指針域(next)，該下標(biāo)域存放直接后繼結(jié)點在數(shù)組中的位置序號。數(shù)組中序號為0的數(shù)組元素可看成固定的頭結(jié)點，其下標(biāo)域指示靜態(tài)鏈表中第一個數(shù)據(jù)結(jié)點的位置序號，最后一個結(jié)點的下標(biāo)域值為0來標(biāo)記該結(jié)點為鏈表的鏈尾結(jié)點，下標(biāo)域值為-1時，則表示該結(jié)點還未使用。靜態(tài)鏈表示意圖如圖2-22所示。圖2-22靜態(tài)鏈表示意圖表示靜態(tài)鏈表的一維數(shù)組定義如下：

typedefstruct

{

datatypedata; //data為結(jié)點的數(shù)據(jù)信息

intcursor; //cursor標(biāo)識直接后繼結(jié)點

}SNode; //靜態(tài)鏈表結(jié)點類型

SNodeL[MAXSIZE];

這種存儲結(jié)構(gòu)仍需要事先分配一個較大的空間，但在進(jìn)行線性表的插入、刪除操作時卻不需要移動大量的元素，僅需要修改“指針”cursor，因此仍具有鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點。例如，要刪除圖2-22所示靜態(tài)鏈表中的元素a3時，則可將指向a3的指針修改為指向a3的直接后繼a4。即：L[1].cursor=L[4].cursor并置L[4].cursor=-1，則實現(xiàn)了在靜態(tài)鏈表中對a3的刪除。

下面，我們給出靜態(tài)鏈表中在第i個結(jié)點位置插入元素x的算法。首先在靜態(tài)鏈表L中找到第i-1個結(jié)點，若存在這樣的結(jié)點，再從第i-1個結(jié)點位置之后的第一個數(shù)組元素位置開始在數(shù)組中循環(huán)查找空位置(即cursor值為-1的數(shù)組元素位置)用來存放元素x，然后修改該數(shù)組元素(即結(jié)點)的cursor域值，使得在插入該結(jié)點后仍構(gòu)成一靜態(tài)鏈表。實現(xiàn)算法如下：

voidInsertList(SNodeL[],inti,datatypex)

{

intj,j1,j2,k;

j=L[0].cursor; //j指向第一個數(shù)據(jù)結(jié)點

if(i==1) //作為第一個數(shù)據(jù)結(jié)點插入

{

if(j==0) //靜態(tài)鏈表為空

{

L[1].data=x; //將x放入結(jié)點L[1]中

L[0].cursor=1; //頭指針cusor指向這個新插入的結(jié)點

L[1].cursor=0; //置鏈尾標(biāo)志

}

else //靜態(tài)鏈表不空

{

k=j+1;

while(k!=j) //在數(shù)組中循環(huán)查找存放x的位置

if(L[k].cursor==-1) //找到空位置

break;

else

k=(k+1)%MAXSIZE; //否則查找下一個位置

if(k!=j) //在數(shù)組中找到一個空位置來存放x

{

L[k].data=x;

L[k].cursor=L[0].cursor; //將其插入到靜態(tài)鏈表表頭

L[0].cursor=k;

}

else

printf("Listoverflow!\n"); //鏈表已滿無法插入

}

}

else //不是作為第一個結(jié)點插入時

{

k=0;

while(k<i-2&&j!=0) //查找第i-1個結(jié)點，j不等于0則表示未到鏈尾

{

k++;

j=L[j].cursor;

}

if(j==0) //查完整個靜態(tài)鏈表未找到第i-1個結(jié)點，即鏈表長度小于i-1個結(jié)點

printf("Inserterror\n");

else

{

j1=j; //找到第i-1個結(jié)點

j2=L[j].cursor; //用j2保存原L[j].cursor值，此值為第i個結(jié)點的位置值

k=j+1;

while(k!=j) //在數(shù)組中循環(huán)查找存放x的位置

if(L[k].cursor==-1) //找到空位置

break;

else

k=(k+1)%MAXSIZE; //否則查找下一個位置

if(k!=j) //在數(shù)組中找到一個空位置來存放x

{

L[k].data=x;

L[j1].cursor=k; //作為第i個結(jié)點鏈入到靜態(tài)鏈表

L[k].cursor=j2; //新結(jié)點之后再鏈接上原第i個結(jié)點

}

else

printf("Listoverflow!\n"); //鏈表已滿，無法插入

}

}

}2.3.6單鏈表應(yīng)用示例

例2.3

已知單鏈表H如圖2-23所示，寫一算法將其逆置。圖2-23單鏈表示意圖

【解】我們知道：頭插法生成的單鏈表其結(jié)點序列正好與輸入數(shù)據(jù)的順序相反。因此，應(yīng)依次取出題設(shè)鏈表中的每一個數(shù)據(jù)結(jié)點，然后用頭插法再插入到新鏈表中即可實現(xiàn)單鏈表的逆置。在算法中，我們使指針p始終指向由剩余結(jié)點構(gòu)成的鏈表中的第一個數(shù)據(jù)結(jié)點，而指針q則從這剩余結(jié)點鏈表中取出第一個數(shù)據(jù)結(jié)點插入到頭結(jié)點*H之后。當(dāng)然，還應(yīng)使指針p繼續(xù)指向剩余結(jié)點鏈表中的第一數(shù)據(jù)個結(jié)點。即移到剛?cè)〕龅慕Y(jié)點之后的下一個數(shù)據(jù)結(jié)點位