C++線性數(shù)據(jù)結(jié)構(gòu)鏈表

2.2線性表

2.2.1線性表的定義及操作定義2-1線性表(Linear-list)是n(n≥0)個(gè)數(shù)據(jù)元素的有限序列（一對(duì)一）。記為：

(a1，a2,...,an)

其中，數(shù)據(jù)元素個(gè)數(shù)n稱為表的長度，n=0時(shí)，稱此線性表為空表。線性表的結(jié)構(gòu)僅涉及諸元素的線性相對(duì)位置，即第i個(gè)元素ai處在第i-1個(gè)元素ai-1的后面和第i+1個(gè)元素ai+1的前面，這種位置上的有序性就是一種線性關(guān)系，所以線性表是一種線性結(jié)構(gòu)。線性表中每個(gè)數(shù)據(jù)元素ai的具體含義，在不同情況下各不相同，它可以是一個(gè)數(shù)，或是一個(gè)符號(hào)，也可以是一頁書，甚至是其它更復(fù)雜的信息。但在同一個(gè)線性表中的數(shù)據(jù)元素必須具有相同的特性(或者說具有相同的類型)。

線性表的邏輯結(jié)構(gòu)：若線性表是非空表，則第一個(gè)元素a1無前驅(qū)（前件）（只有一個(gè)根結(jié)點(diǎn)或首結(jié)點(diǎn)），最后一個(gè)元素an無后繼（后件），其它元素ai(1<i<n)均只有一個(gè)直接前驅(qū)ai-1和一個(gè)直接后繼ai+1。下面給出幾個(gè)線性表的例子：

例2-126個(gè)大寫的英文字母表：(A，B，C，...，Z)

例2-2

某校從1996年到2002年各種型號(hào)計(jì)算機(jī)擁有量的變化情況，可以用線性表給出：

(200，220，250，300，400，700，1200)

例2-3

某單位職工政治面貌登記表如表2-2所示，每個(gè)職工的情況為一條記錄，它由職工號(hào)、姓名、性別、職稱、工齡、政治面貌六個(gè)數(shù)據(jù)項(xiàng)組成。在表2-2中，一個(gè)數(shù)據(jù)元素由若干個(gè)數(shù)據(jù)項(xiàng)組成。在這種情況下，常把數(shù)據(jù)元素稱為記錄，含有大量記錄的線性表又稱為文件。表2-2職工政治面貌登記表

職工號(hào)姓名性別職稱工齡政治面貌

000100020003…張忠王平李林…男女男…工程師助工助工…1222…黨員團(tuán)員團(tuán)員…

線性表是一個(gè)相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，它的長度可以根據(jù)需要增減，操作也比較靈活方便。線性表的基本操作有以下幾種：

(1)INITIATE(L)。初始化操作，設(shè)定一個(gè)空的線性表L。

(2)LENGTH(L)。求表長，求出線性表L中數(shù)據(jù)元素個(gè)數(shù)。

(3)GET(L，i)。取元素函數(shù)，若1≤i≤LENGTH(L)，則函數(shù)值為給定線性表L中第i個(gè)數(shù)據(jù)元素，否則為空元素NULL。

(4)PRIOR(L，elm)。求前趨函數(shù)，若elm的位序大于1，則函數(shù)值為elm的前趨，否則為空元素。

(5)NEXT(L，elm)。求后繼函數(shù)，若elm的位序小于LENGTH(L)，則函數(shù)值為elm的后繼，否則為空元素。

(6)LOCATE(L，x)。定位函數(shù)，返回元素x在線性表L中的位置。若L中有多個(gè)x，則只返回第一個(gè)x的位置，若在L中不存在x，則返回0。

(7)INSERT(L，i，x)。插入操作，在線性表L中的第i個(gè)位置上插入元素x，運(yùn)算結(jié)果使得線性表的長度增加1。

(8)DELETE(L，i)。刪除操作，若1≤i≤LENGTH(L)，刪除給定線性表L中的第i個(gè)數(shù)據(jù)元素，使得線性表的長度減1。

(9)EMPTY(L)。判空表函數(shù)，若L為空表，則返回布爾值“true”，否則返回布爾值“false”。對(duì)線性表還有一些更為復(fù)雜的操作，如將兩個(gè)線性表合并成一個(gè)線性表；把一個(gè)線性表拆分成兩個(gè)或兩個(gè)以上的線性表；重新復(fù)制一個(gè)線性表；對(duì)線性表中的元素按值的大小重新排序等。這些運(yùn)算都可以通過上述基本運(yùn)算來實(shí)現(xiàn)。

2.2.2線性表的順序存儲(chǔ)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)可以用不同的方式來表示線性表，其中最簡單和最常用的方式是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表中的元素。圖2-2線性表順序存儲(chǔ)結(jié)構(gòu)示意圖(設(shè)每個(gè)數(shù)據(jù)元素占有1個(gè)存儲(chǔ)單元)

線性表的順序存儲(chǔ)結(jié)構(gòu)就是將線性表的元素按其邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里。

(1)設(shè)有線性表(a1，a2，...，an)，若1個(gè)數(shù)據(jù)元素只占1個(gè)存儲(chǔ)單元，則這種分配方式如圖2-2所示。若用Loc表示某元素的地址，則線性表中第i個(gè)數(shù)據(jù)元素的存儲(chǔ)地址為：

Loc(ai)=Loc(a1)+(i-1)

其中，Loc(a1)是線性表第一個(gè)數(shù)據(jù)元素的存儲(chǔ)地址，通常稱做線性表的起始地址或者基地址。

(2)若1個(gè)數(shù)據(jù)元素占d個(gè)存儲(chǔ)單元，則有

Loc(ai)=Loc(a1)+(i-1)*dLoc(ai+1)=Loc(ai)+d

可見，線性表中每個(gè)元素的存儲(chǔ)地址是該元素在表中序號(hào)的線性函數(shù)。只要確定了線性表的起始地址，線性表中任一數(shù)據(jù)元素都可以隨機(jī)存取，所以線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。

順序存儲(chǔ)結(jié)構(gòu)是以元素在計(jì)算機(jī)內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間相鄰的邏輯關(guān)系。即順序存儲(chǔ)結(jié)構(gòu)線性表的邏輯關(guān)系的存儲(chǔ)是隱含的。線性表的順序存儲(chǔ)結(jié)構(gòu)通常稱為向量(Vector)?？捎米帜竀來表示，用V［i］表示向量V的第i個(gè)分量，設(shè)向量下界為1，上界為線性表的長度n（i=1~n），則可以用此向量來表示長度為n的線性表。向量的第i個(gè)分量V［i］是線性表的第i個(gè)數(shù)據(jù)元素ai在計(jì)算機(jī)內(nèi)存中的映像。

在C語言中，向量即一維數(shù)組，所以可用一維數(shù)組來描述順序存儲(chǔ)結(jié)構(gòu)。#definemaxlen100

typedef

int

datatype;struct

sqlisttp

{

int

elem[maxlen];datatype

elem[maxlen];

intlast;};

其中，

maxlen是線性表的最大長度，它可以根據(jù)實(shí)際需要而修改。這里假設(shè)線性表的數(shù)據(jù)元素是整數(shù)，當(dāng)然也可以根據(jù)需要取其它類型,甚至還可以是一種結(jié)構(gòu)(即每個(gè)數(shù)據(jù)元素有多個(gè)數(shù)據(jù)項(xiàng))。數(shù)據(jù)域elem描述了線性表中數(shù)據(jù)元素占用的數(shù)組空間，線性表的各個(gè)元素a1，a2，…，an依次存放在一維數(shù)組elem的各個(gè)分量elem[1]，elem[2]，…，elem[n]中。數(shù)據(jù)域last指示最后一個(gè)數(shù)據(jù)元素在數(shù)組中的相對(duì)位置。在這種存儲(chǔ)結(jié)構(gòu)中，線性表的某些操作很容易實(shí)現(xiàn)。如線性表的長度即為last域的值等。下面著重討論線性表的插入和刪除兩種操作。

算法2-1

線性表的插入算法。已知線性表的當(dāng)前狀態(tài)是(a1，a2，…，ai-1，ai，…，an)，要在第i個(gè)位置插入一個(gè)元素x，線性表變?yōu)?a1，a2，…，ai-1，x，ai，…，an)。其實(shí)施步驟為：

(1)

將第n至第i個(gè)元素后移一個(gè)存儲(chǔ)位置；

(2)

將x插入到第i個(gè)位置；

(3)

線性表的長度加1?！?.a2a1an…..ai+1ai01i-1in-1在線性表的第i個(gè)元素之前插入一個(gè)新的元素，先移動(dòng)，后插入。ai-1…..a2a1alast…ai+1aixai-1…..a2a1

aiai+1…alast

alast……ai+1

aix#definemaxlen100struct

sqlisttp{/*定義了sqlisttp型的結(jié)構(gòu)

int

elem[maxlen];/*maxlen=n,elem=a*/

intlast;/*last=length*/};sqlisttp

v;/*定義了sqlisttp型的結(jié)構(gòu)對(duì)象v

voidinsert(sqlisttp

v,int

i,int

x){intk;

if(i<1||i>v.last+1)

printf(''插入位置不合適！\n'');

elseif(v.last>=maxlen-1)

printf(''線性表已滿！\n''); else {for(k=v.last-1;k>=i-1;k--)

v.elem[k+1]=v.elem[k];

v.elem[i-1]=x;

v.last++; }}

算法2-2

線性表的刪除算法。已知線性表的當(dāng)前狀態(tài)是(a1，a2，…，ai-1，ai，ai+1，…，an)，若要?jiǎng)h除第i個(gè)元素ai，則線性表成為(a1，a2，…，ai-1，ai+1，…，an)。具體實(shí)施步驟為：

(1)

若i值合法，則將第i+1至第n個(gè)位置上的元素依次向前移動(dòng)一個(gè)存儲(chǔ)單位；

(2)

將線性表的長度減1?！?.a2a1an…..ai+1ai01i-1in-1刪除線性表的第i個(gè)元素，后面所有元素前移。ai-1…..a2a1alast…ai+1aiai-1…..a2a1

aiai+1…alast刪除結(jié)點(diǎn)aiai+1…alast#definemaxlen100struct

sqlisttp{

int

elem[maxlen];

intlast;};sqlisttp

v;

voiddelete(sqlisttp

v,int

i){intk;

if(i<1||i>v.last)/*存取v的結(jié)構(gòu)成員last

printf(''刪除位置不合適！\n'');

else { for(k=i;k<=v.last-1;k++)

v.elem[k-1]=v.elem[k];

v.last--; }}從上述算法中不難看出，當(dāng)在順序存儲(chǔ)結(jié)構(gòu)的線性表中某個(gè)位置上插入或刪除一個(gè)數(shù)據(jù)元素時(shí)，其時(shí)間主要耗費(fèi)在移動(dòng)元素上，而移動(dòng)元素的個(gè)數(shù)取決于插入或刪除元素的位置。

假設(shè)在第i個(gè)元素之前插入一個(gè)新元素的概率為1/(n+1)，即在表的任何位置(包括an之后)插入新元素的概率是相等的，則插入操作中元素的平均移動(dòng)次數(shù)(實(shí)際上就是時(shí)間復(fù)雜度)為：

T=

對(duì)于刪除操作，假定對(duì)長度為n的線性表，在表的任何位置上刪除元素的概率是相等的，即等于1/n，則刪除操作中元素的平均移動(dòng)次數(shù)(即是時(shí)間復(fù)雜度)為：

T=

從以上分析可以看出，在順序存儲(chǔ)的線性表中進(jìn)行插入或刪除操作，平均要移動(dòng)一半的元素，即T(n)=O(n)。當(dāng)線性表的元素很多，且每個(gè)元素的數(shù)據(jù)項(xiàng)較多時(shí)，花費(fèi)在移動(dòng)元素上的時(shí)間會(huì)很長。一般情況下，線性表的順序存儲(chǔ)結(jié)構(gòu)適合于表中元素變動(dòng)較少的線性表。

2.2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也是相鄰的。因此，可以隨機(jī)存取表中任一元素，它的存儲(chǔ)位置可用一個(gè)簡單、直觀的公式來表示。缺點(diǎn)：

在作插入或刪除操作時(shí)，需移動(dòng)大量元素；在給長度變化較大的線性表預(yù)先分配空間時(shí)，必須按最大空間分配，使存儲(chǔ)空間不能得到充分利用；表的容量難以擴(kuò)充。1．線性鏈表線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表中的數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。這樣，邏輯上相鄰的元素在物理位置上就不一定是相鄰的，為了能正確反映元素的邏輯順序，就必須在存儲(chǔ)每個(gè)元素ai的同時(shí)，存儲(chǔ)其直接后繼元素的存儲(chǔ)位置。為克服線性表順序存儲(chǔ)結(jié)構(gòu)的缺點(diǎn)，引進(jìn)了另一種存儲(chǔ)結(jié)構(gòu)——鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。這時(shí)，存放數(shù)據(jù)元素的結(jié)點(diǎn)至少包括兩個(gè)域，一個(gè)域存放該元素的數(shù)據(jù)，稱為數(shù)據(jù)域(data)；另一個(gè)域存放后繼結(jié)點(diǎn)在存儲(chǔ)器中的地址，稱為指針域或鏈域(next)。這種鏈?zhǔn)椒峙涞拇鎯?chǔ)結(jié)構(gòu)稱為鏈表。datanext此結(jié)構(gòu)的C語言描述為：struct

node{

intdata;

struct

node

*next;/*定義了指向node類型的結(jié)構(gòu)指針 };typedef

structnodeNODE;

/*重新定義該結(jié)構(gòu)類型的新名字NODE}NODE；數(shù)據(jù)元素的結(jié)點(diǎn)結(jié)構(gòu)如下：一般情況下，鏈表中每個(gè)結(jié)點(diǎn)可以包含若干個(gè)數(shù)據(jù)域和指針域。若每個(gè)結(jié)點(diǎn)中只有一個(gè)指針域，則稱此鏈表為線性鏈表或單鏈表，否則被稱為多鏈表。例2-4

設(shè)有線性表由動(dòng)物名組成：(cat,horse,monkey,elephant,pig,panda)。

它的物理狀態(tài)如圖2-3所示。當(dāng)鏈表采用圖2-3來表示時(shí)，邏輯上的順序不易觀察，所以經(jīng)常把鏈表用圖2-4所示的邏輯狀態(tài)來表示。圖2-4線性鏈表的邏輯狀態(tài)示意圖圖2-3線性鏈表的物理狀態(tài)示意圖

在圖2-4中，指針域的值用箭頭代替了，線性鏈表結(jié)點(diǎn)的相鄰關(guān)系用箭頭來指示，邏輯結(jié)構(gòu)的表示非常形象、清晰。在此單鏈表中，head是指向單鏈表中第一個(gè)結(jié)點(diǎn)的指針，我們稱之為頭指針；最后一個(gè)元素panda所在結(jié)點(diǎn)不存在后繼，因而其指針域?yàn)椤翱铡?用NULL或∧

表示)。可以看出，用線性鏈表表示線性表時(shí)，數(shù)據(jù)元素之間的邏輯關(guān)系是由結(jié)點(diǎn)中的指針指示的，邏輯上相鄰的兩個(gè)數(shù)據(jù)元素其存儲(chǔ)的物理位置不要求相鄰，因此，這種存儲(chǔ)結(jié)構(gòu)為非順序映像或鏈?zhǔn)接诚?。在使用中，我們只關(guān)心數(shù)據(jù)元素的邏輯次序而不必關(guān)心它的真正存儲(chǔ)地址。通常，我們?cè)趩捂湵淼谝粋€(gè)元素所在的結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)——頭結(jié)點(diǎn)（增加的目的是統(tǒng)一空表與非空表的處理）。頭結(jié)點(diǎn)的指針域存儲(chǔ)第一個(gè)元素所在結(jié)點(diǎn)的存儲(chǔ)位置；頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息，也可以存儲(chǔ)如線性表的長度等附加信息。若線性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)椤翱铡?，如圖2-5所示。

圖2-5帶頭結(jié)點(diǎn)的單鏈表

2．線性鏈表的運(yùn)算線性鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)表示，所以對(duì)線性鏈表的運(yùn)算與前面所介紹的對(duì)線性表的運(yùn)算相同，只是相應(yīng)的算法與順序存儲(chǔ)的線性表有所不同。設(shè)head為單鏈表的表頭指針。下面主要介紹對(duì)帶頭結(jié)點(diǎn)單鏈表的查找、插入、刪除等常用操作的算法。對(duì)鏈表操作時(shí)，最基本的操作為插入、刪除運(yùn)算。在討論插入、刪除操作之前，首先要解決插入時(shí)的新結(jié)點(diǎn)從何處取出，刪除后的結(jié)點(diǎn)又往何處送的問題。在采用鏈接分配時(shí)，總存在一個(gè)可利用的內(nèi)存空間稱為可利用空間表，至于可利用空間表是怎樣生成的，可以有不同的方法，這里不再介紹。假設(shè)可利用空間表總是可以滿足存儲(chǔ)要求的。這樣，每當(dāng)要調(diào)用新結(jié)點(diǎn)時(shí)就到這個(gè)可利用空間表里去取，刪除時(shí)就把結(jié)點(diǎn)歸還給這個(gè)可利用空間表。在C語言的編程實(shí)現(xiàn)時(shí)，申請(qǐng)與釋放一結(jié)點(diǎn)對(duì)應(yīng)于C語言中兩個(gè)標(biāo)準(zhǔn)函數(shù)malloc(sizeof(NODE))和free(p)。

(1)malloc

是從可利用空間表中調(diào)用一新結(jié)點(diǎn)，并返回該結(jié)點(diǎn)的地址。

(2)free(p)將p指向的結(jié)點(diǎn)歸還給可利用空間表。為方便起見，以后把指針型變量p所指向的結(jié)點(diǎn)稱為p結(jié)點(diǎn)。

1)單鏈表的查找由于鏈表存儲(chǔ)結(jié)構(gòu)不是一種隨機(jī)存取結(jié)構(gòu)，要查找單鏈表中的一個(gè)結(jié)點(diǎn)，必須從頭指針出發(fā)，沿結(jié)點(diǎn)的指針域逐個(gè)往后查找，直到找到要查找的結(jié)點(diǎn)為止。

算法2-3

在帶頭結(jié)點(diǎn)的單鏈表中找出第i個(gè)元素所在的結(jié)點(diǎn)。NODE*get(NODE*head,inti){ NODE*p;/*等同于structnode*p

intcounter=1;p=head->next;/*通過指針訪問結(jié)構(gòu)的成員時(shí)必須使用操作符->while((p!=NULL)&&(counter<i)) { p=p->next; counter++;

}if((p!=NULL)&&(counter=i))/*找到,1<=i<=n*/ returnp;else returnNULL;/*找不到,i>n或i<=0*/}注意（1）需事先定義NULL的具體數(shù)值，比如：

#defineNULL-1

（2）上述算法的平均時(shí)間復(fù)雜度為：

T(n)=O(n)。

2)單鏈表的插入設(shè)有線性表(a1，a2，...，ai-1，ai，...，an)，用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)，頭指針為head，要求在線性表中第i個(gè)元素ai之前插入一個(gè)值為x的元素，線性表變?yōu)?a1，a2，…，ai-1，x，ai，…，an)。

插入前單鏈表的邏輯狀態(tài)如圖2-6所示。

圖2-6帶頭結(jié)點(diǎn)單鏈表的邏輯狀態(tài)

為插入數(shù)據(jù)元素x，

(1)

首先要生成一個(gè)數(shù)據(jù)域?yàn)閤的新結(jié)點(diǎn)s；

(2)

然后確定插入位置，即找到ai之前的元素

ai-1，并使指針p指向之；

(3)

最后改變鏈接，將x插在ai-1與ai之間，修改結(jié)點(diǎn)p和結(jié)點(diǎn)s的指針域。即

s->next=p->next；p->next=s。插入結(jié)點(diǎn)s后單鏈表的邏輯狀態(tài)如圖2-7所示。圖2-7在單鏈表中插入結(jié)點(diǎn)S

算法2-4voidinsert(NODE*head,inti,intx){ NODE*p,*s;

intj=0; p=head; while((p!=NULL)&&(j<i-1)) { p=p->next; j++; }

if((p==NULL)||(j>i-1))

printf(''i值不合法\n'');/*找不到,i>n或i<=0*/ else { s=(NODE*)malloc(sizeof(NODE));/**/ s->data=x;/**/ s->next=p->next;/**/ p->next=s;/**/ } }

如果事先告之p指針?biāo)傅奈恢?，則這種在p指針后插入一個(gè)元素算法的時(shí)間復(fù)雜度T(n)=O(1)，否則平均時(shí)間復(fù)雜度T(n)=O(n)。

3)單鏈表的刪除刪除操作和插入操作一樣，

(1)首先要搜索單鏈表以找到指定刪除結(jié)點(diǎn)的前趨結(jié)點(diǎn)(假設(shè)為p)；

(2)然后改變鏈接，即只要將待刪除結(jié)點(diǎn)的指針域內(nèi)容賦予p結(jié)點(diǎn)的指針域即可。設(shè)有線性表(a1，a2，...，ai-1，ai，ai+1，...，an)，用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)，刪除前的邏輯狀態(tài)如圖2-8所示。

刪除元素ai所在的結(jié)點(diǎn)之后，單鏈表的邏輯狀態(tài)如圖2-9所示。圖2-8帶頭結(jié)點(diǎn)的單鏈表圖2-9在單鏈表中刪除一個(gè)結(jié)點(diǎn)算法2-5voiddelete(NODE*head,inti){ NODE*p,*s;

intj=0; p=head; while((p->next!=NULL)&&(j<i-1)) {p=p->next; j++;}

if((p->next==NULL)||(j>i-1))

printf(“i值不合法\n”);/*找不到,i>n或i<=0*/ else {s=p->next; p->next=s->next; free(s); } }

如果事先告之p指針?biāo)傅奈恢茫瑒t這種在p指針后刪除一個(gè)元素算法的時(shí)間復(fù)雜度T(n)=O(1)，否則平均時(shí)間復(fù)雜度T(n)=O(n)。

4)動(dòng)態(tài)建立單鏈表的算法要對(duì)單鏈表進(jìn)行操作，首先要掌握怎樣建立單鏈表。鏈表是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)，所需的存儲(chǔ)空間只有在程序執(zhí)行malloc之后，才可能申請(qǐng)到一個(gè)可用結(jié)點(diǎn)空間；free(p)的作用是系統(tǒng)回收一個(gè)結(jié)點(diǎn)，回收后的空間可以備作再次生成結(jié)點(diǎn)時(shí)用。整個(gè)可用存儲(chǔ)空間可為多個(gè)鏈表共同享用，每個(gè)鏈表占用的空間不需預(yù)先分配劃定，而是由系統(tǒng)應(yīng)需求即時(shí)生成。因此，建立線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的過程就是一個(gè)動(dòng)態(tài)生成鏈表的過程。即從“空表”的初始狀態(tài)起，依次建立各元素結(jié)點(diǎn)，并逐個(gè)插入鏈表。動(dòng)態(tài)建立線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)有兩種基本方法，分別適用于不同的場合?？筛鶕?jù)所建鏈表結(jié)點(diǎn)的順序要求選擇采用一種方法。

單鏈表建立方法一：反向建立鏈表（頭插法）。

思想：若線性表的元素已順序存放在一維數(shù)組A[N]中，建表方法是從線性表的最后一個(gè)元素開始，從后向前依次插入到當(dāng)前鏈表的第一個(gè)結(jié)點(diǎn)之前。算法2-6#defineNm/*m為鏈表中數(shù)據(jù)元素的個(gè)數(shù),如m=10*/intA[N]; NODE*creatlink1(){ NODE*head,*s;

inti; head=(NODE*)malloc(sizeof(NODE));/*生成頭結(jié)點(diǎn)*/ head->next=NULL;/*置空表*/ for(i=N-1;i>=0;i--)/*插入10個(gè)數(shù)據(jù)*/

{ s=(NODE*)malloc(sizeof(NODE));/*生成新結(jié)點(diǎn)*/ s->data=A[i];/*將輸入數(shù)據(jù)放入新結(jié)點(diǎn)數(shù)據(jù)域*/ s->next=head->next;/*新結(jié)點(diǎn)與原首結(jié)點(diǎn)鏈接*/ head->next=s;/*將新結(jié)點(diǎn)插入到表頭*/ } returnhead;/*返回單鏈表頭指針*/}算法的時(shí)間復(fù)雜度為：T(n)=O(n)

單鏈表建立方法二：正向建立單鏈表（尾插法）。

思想：依次讀入線性表的元素，從前往后依次將元素插入到當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)之后。圖B新結(jié)點(diǎn)*s插入到單鏈表head的尾上算法2-7NODE*creatlink2(){ NODE*head,*p,*s;

intnum; head=(NODE*)malloc(sizeof(NODE));/*生成頭結(jié)點(diǎn)*/

scanf(“%d”,&num);/*讀入第一個(gè)結(jié)點(diǎn)值*/ p=head;/*頭指針=尾指針*/ while(num!=0)/*輸入為0為輸入結(jié)束符*/

{ s=(NODE*)malloc(sizeof(NODE));/*生成新結(jié)點(diǎn)*/ s->data=num;/*新結(jié)點(diǎn)上填入輸入值*/ p->next=s;/*新結(jié)點(diǎn)*s插入到尾結(jié)點(diǎn)*p之后*/ p=s;/*尾指針p指向新的表尾*/

scanf(“%d”,&num);/*讀入下一個(gè)結(jié)點(diǎn)值*/ } p->next=NULL;/*將尾結(jié)點(diǎn)的指針置空*/ returnhead;/*返回單鏈表頭指針*/}算法的時(shí)間復(fù)雜度：T(n)=O(n)

3.線性鏈表算法示例

例2-5

求不帶頭結(jié)點(diǎn)的頭指針為head的單鏈表中的結(jié)點(diǎn)數(shù)目。解：

intlength(NODE*head) {NODE*p;

intj; p=head; j=0;while(p!=NULL) { p=p->next; j++; } returnj;}算法的平均時(shí)間復(fù)雜度：T(n)=O(n)

例2-6

設(shè)計(jì)算法：將一個(gè)帶頭結(jié)點(diǎn)的單鏈表A分解為兩個(gè)帶頭結(jié)點(diǎn)的單鏈表A和B，使得A表中含有原表中序號(hào)為奇數(shù)的元素，B表中含有原表中序號(hào)為偶數(shù)的元素，且保持其相對(duì)順序。解：voiddisA(NODE*A,NODE*B){ NODE*r,*p,*q; B=(NODE*)malloc(sizeof(NODE)); /*建立單鏈表B的頭結(jié)點(diǎn)*/ r=B; p=A->next; while((p!=NULL)&&(p->next!=NULL))

{ q=p->next; p->next=q->next; r->next=q; r=q; p=p->next; } r->next=NULL; p->next=NULL;}

例2-7

已知兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表A、B分別表示兩個(gè)集合，其元素遞增有序。試設(shè)計(jì)算法求出A與B的交集C。要求C另外開辟存儲(chǔ)空間，并同樣以元素值遞增的帶頭結(jié)點(diǎn)的單鏈表形式存儲(chǔ)。解：voidintersectionset(NODE*A,NODE*B,NODE*C){ NODE*r,*p,*q,*s; C=(NODE*)malloc(sizeof(NODE)); r=C; p=A; q=B; while((p!=NULL)&&(q!=NULL)) { if(p->data<q->data)

p=p->next; elseif(p->data>q->data) q=q->next; elseif(p->data==q->data) { s=(NODE*)malloc(sizeof(NODE)); s->data=p->data;r->next=s; r=s; p=p->next; q=q->next; } } r->next=NULL;}

2.2.4循環(huán)鏈表和雙向鏈表

1.循環(huán)鏈表

如果鏈表最后一個(gè)結(jié)點(diǎn)的指針域指向頭結(jié)點(diǎn)，整個(gè)鏈表形成一個(gè)環(huán)，這樣的鏈表稱為循環(huán)鏈表。這樣，從表中任一結(jié)點(diǎn)出發(fā)均可找到表中其它結(jié)點(diǎn)，其邏輯狀態(tài)圖如圖2-10。圖2-10循環(huán)單鏈表

循環(huán)鏈表一般設(shè)表頭結(jié)點(diǎn)，這樣鏈表將永不為空，這將使空表和非空表的邏輯狀態(tài)及運(yùn)算統(tǒng)一起來。循環(huán)鏈表的操作和線性鏈表基本一致，差別僅在于算法中的循環(huán)條件不是p或p->next是否為空，而是它們是否等于頭指針。與單鏈表比較，循環(huán)鏈表有以下特點(diǎn)：

(1)

在循環(huán)單鏈表中，從表中任何一個(gè)結(jié)點(diǎn)出發(fā)都能訪問到其它所有的結(jié)點(diǎn)；而單鏈表一般把頭指針作為入口點(diǎn)，從某一結(jié)點(diǎn)出發(fā)，只能訪問到其所有后繼結(jié)點(diǎn)。

(2)

循環(huán)單鏈表的空表判定條件是：

head->next=head。

2．雙向鏈表前面討論的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中只有一個(gè)指示直接后繼的指針域，所以從某結(jié)點(diǎn)出發(fā)只能順指針往后查找其它結(jié)點(diǎn)。若要查找結(jié)點(diǎn)的直接前趨，則應(yīng)從頭指針出發(fā)(或在循環(huán)單鏈表中從p結(jié)點(diǎn)出發(fā))一直往后找，直到結(jié)點(diǎn)q滿足q->next=p，那么q是p的前趨結(jié)點(diǎn)。為克服鏈表這種單向性的缺點(diǎn)，為有更大的靈活性來操作線性鏈表，可采用雙向鏈表存儲(chǔ)結(jié)構(gòu)。在每個(gè)結(jié)點(diǎn)上增加另一個(gè)指向線性表中每個(gè)元素的前趨結(jié)點(diǎn)的指針域prior，就得到雙向鏈表。其結(jié)點(diǎn)的結(jié)構(gòu)如