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

2.2線性表

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

(a1，a2,...,an)

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

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

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

例2-2

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

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

例2-3

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

職工號姓名性別職稱工齡政治面貌

000100020003…張忠王平李林…男女男…工程師助工助工…1222…黨員團員團員…

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

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

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

(3)GET(L，i)。取元素函數(shù)，若1≤i≤LENGTH(L)，則函數(shù)值為給定線性表L中第i個數(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中有多個x，則只返回第一個x的位置，若在L中不存在x，則返回0。

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

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

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

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

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

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

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

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

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

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

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

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

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

typedef

int

datatype;struct

sqlisttp

{

int

elem[maxlen];datatype

elem[maxlen];

intlast;};

其中，

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

算法2-1

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

(1)

將第n至第i個元素后移一個存儲位置；

(2)

將x插入到第i個位置；

(3)

線性表的長度加1?！?.a2a1an…..ai+1ai01i-1in-1在線性表的第i個元素之前插入一個新的元素，先移動，后插入。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)對象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

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

(1)

若i值合法，則將第i+1至第n個位置上的元素依次向前移動一個存儲單位；

(2)

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

aiai+1…alast刪除結(jié)點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--; }}從上述算法中不難看出，當在順序存儲結(jié)構(gòu)的線性表中某個位置上插入或刪除一個數(shù)據(jù)元素時，其時間主要耗費在移動元素上，而移動元素的個數(shù)取決于插入或刪除元素的位置。

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

T=

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

T=

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

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

在作插入或刪除操作時，需移動大量元素；在給長度變化較大的線性表預先分配空間時，必須按最大空間分配，使存儲空間不能得到充分利用；表的容量難以擴充。1．線性鏈表線性表的鏈式存儲結(jié)構(gòu)的特點是用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素，這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的。這樣，邏輯上相鄰的元素在物理位置上就不一定是相鄰的，為了能正確反映元素的邏輯順序，就必須在存儲每個元素ai的同時，存儲其直接后繼元素的存儲位置。為克服線性表順序存儲結(jié)構(gòu)的缺點，引進了另一種存儲結(jié)構(gòu)——鏈式存儲結(jié)構(gòu)。這時，存放數(shù)據(jù)元素的結(jié)點至少包括兩個域，一個域存放該元素的數(shù)據(jù)，稱為數(shù)據(jù)域(data)；另一個域存放后繼結(jié)點在存儲器中的地址，稱為指針域或鏈域(next)。這種鏈式分配的存儲結(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é)點結(jié)構(gòu)如下：一般情況下，鏈表中每個結(jié)點可以包含若干個數(shù)據(jù)域和指針域。若每個結(jié)點中只有一個指針域，則稱此鏈表為線性鏈表或單鏈表，否則被稱為多鏈表。例2-4

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

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

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

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

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

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

(1)malloc

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

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

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

算法2-3

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

intcounter=1;p=head->next;/*通過指針訪問結(jié)構(gòu)的成員時必須使用操作符->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）上述算法的平均時間復雜度為：

T(n)=O(n)。

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

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

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

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

(1)

首先要生成一個數(shù)據(jù)域為x的新結(jié)點s；

(2)

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

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

(3)

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

s->next=p->next；p->next=s。插入結(jié)點s后單鏈表的邏輯狀態(tài)如圖2-7所示。圖2-7在單鏈表中插入結(jié)點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指針所指的位置，則這種在p指針后插入一個元素算法的時間復雜度T(n)=O(1)，否則平均時間復雜度T(n)=O(n)。

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

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

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

刪除元素ai所在的結(jié)點之后，單鏈表的邏輯狀態(tài)如圖2-9所示。圖2-8帶頭結(jié)點的單鏈表圖2-9在單鏈表中刪除一個結(jié)點算法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指針所指的位置，則這種在p指針后刪除一個元素算法的時間復雜度T(n)=O(1)，否則平均時間復雜度T(n)=O(n)。

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

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

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

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

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

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

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

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

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

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

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

3.線性鏈表算法示例

例2-5

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

intlength(NODE*head) {NODE*p;

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

例2-6

設(shè)計算法：將一個帶頭結(jié)點的單鏈表A分解為兩個帶頭結(jié)點的單鏈表A和B，使得A表中含有原表中序號為奇數(shù)的元素，B表中含有原表中序號為偶數(shù)的元素，且保持其相對順序。解：voiddisA(NODE*A,NODE*B){ NODE*r,*p,*q; B=(NODE*)malloc(sizeof(NODE)); /*建立單鏈表B的頭結(jié)點*/ 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

已知兩個不帶頭結(jié)點的單鏈表A、B分別表示兩個集合，其元素遞增有序。試設(shè)計算法求出A與B的交集C。要求C另外開辟存儲空間，并同樣以元素值遞增的帶頭結(jié)點的單鏈表形式存儲。解：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)鏈表

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

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

(1)

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

(2)

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

head->next=head。

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