第03章數(shù)據(jù)結(jié)構(gòu)課件

高等學(xué)校精品課程

人民郵電出版社

江西省高等學(xué)校精品課程

冷而牌歷大學(xué)

揭安全ill

：

E_mailjieanquan@163.com5

江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院

第3章線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)

＞鏈?zhǔn)酱鎯?chǔ)

A單鏈表

A帶頭結(jié)點(diǎn)的單鏈表

A循環(huán)單鏈表

＞雙鏈表

A鏈?zhǔn)綏?/p>

A鏈?zhǔn)疥?duì)列

退出

線(xiàn)性表的存儲(chǔ)方式除了常用的順序存儲(chǔ)外，采用

鏈?zhǔn)椒绞酱鎯?chǔ)也是一種常見(jiàn)的方式。本章將介紹一般

線(xiàn)性表的幾種鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)方式，如單鏈表、帶頭結(jié)

點(diǎn)單鏈表、循環(huán)單鏈表、雙鏈表以及特殊的線(xiàn)性表--

----棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)。

3」鏈?zhǔn)酱鎯?chǔ)

數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)方式必須體現(xiàn)它的邏輯關(guān)系。

在鏈?zhǔn)酱鎯?chǔ)方式下，實(shí)現(xiàn)中除存放一個(gè)結(jié)點(diǎn)的信息外,

還需附設(shè)指針，用指針體現(xiàn)結(jié)點(diǎn)之間的邏輯關(guān)系。如

果一個(gè)結(jié)點(diǎn)有多個(gè)后繼或多個(gè)前驅(qū)，那么可以附設(shè)相

應(yīng)個(gè)數(shù)的指針，一個(gè)結(jié)點(diǎn)附設(shè)的指針指向的是這個(gè)結(jié)

點(diǎn)的某個(gè)前驅(qū)或后繼。

□

線(xiàn)性結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一個(gè)后繼，這

里暫且設(shè)定更關(guān)心它的后繼，這樣在存儲(chǔ)時(shí)除了存放該結(jié)點(diǎn)的信

息外，只要附設(shè)一個(gè)指針即可，該指針指向它的后繼結(jié)點(diǎn)的存放

位置。每個(gè)結(jié)點(diǎn)的存儲(chǔ)形式是:

infonext

例，數(shù)據(jù)的邏輯結(jié)構(gòu)B=（K,R）

=

其中K{k2,k2,k3/k4,k5)

R={r}

R={<k1/k2>/<k2/k3>/<k3/k4>/<k4,k5>)

是一個(gè)線(xiàn)性結(jié)構(gòu)，它的鏈?zhǔn)酱鎯?chǔ)如圖所示

□

為了清晰，上圖可以更簡(jiǎn)潔地用下圖表示。

head

ki卜3A

網(wǎng)

全?1

3.2單鏈表

單鏈表是線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)的一種形式，其中的結(jié)

點(diǎn)一般含著兩個(gè)域，一個(gè)是存放數(shù)據(jù)信息的info域，

另一個(gè)是指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)的存放地址的指針

域next。一個(gè)單鏈表必須有一個(gè)首指針指向單鏈表

中的第一個(gè)結(jié)點(diǎn)。

仃而中陸火學(xué)

直觀(guān)化的描述方法:

(a)非空表

head=NULL

(b)非空表

單鏈表是由表頭唯一確定，因此單鏈表可以用頭

指針的名字兼命名。例如：若頭指針名是head,

則把鏈表稱(chēng)為表head。

322單鏈表的實(shí)現(xiàn)

單鏈表結(jié)構(gòu)的C語(yǔ)言描述如下：

4上KX^^1^^F

^T*/

/*鏈表實(shí)現(xiàn)的頭文件,文件名sinklist.h*/

vf>>t>^f>>f>>1^^f>K1^^1>>f>%f>^f>^f>>f>^f>/

<T**T**r**T*g

typedefintdatatype;

typedefstructlink_node{

datatypeinfo;

structlinknode*next;

}node;

仃而中陸火學(xué)

????????????????■??????

單鏈表幾個(gè)基本操作的具體實(shí)現(xiàn):

建立一個(gè)空的單鏈表

/KI>K!>/

!^r%^r%/

/*函數(shù)功能:建立一個(gè)空的單鏈表*/

I*pj^['^^Z*/

/*函數(shù)返回值:指向node類(lèi)型變量的指針*/

/*文件名:sinklist.c,函數(shù)名:init()*/

/^IX^Ix/

1*T>1

node*initO/*建立一個(gè)空的單鏈表*/

{

returnNULL;

)

算法3.1建立一個(gè)空的單鏈表

仃而中陸火學(xué)

????????????????■??????

輸出單鏈表中各個(gè)結(jié)點(diǎn)的值

voiddisplay(node*head)

node*p;

p=head;

if(!p)printf(“\n單鏈表是空的！)

else

(

printf(“\n單鏈表各個(gè)結(jié)點(diǎn)的值為:\n")；

while(p){prinTf("%5d”,p->info);p=p->nexT;}

)

)

算法3.2輸出單鏈表中各個(gè)結(jié)點(diǎn)的值

仃而中陸火學(xué)

在單鏈表中查找一個(gè)值為X的結(jié)點(diǎn)

node*find(node*head,inti)

intj=l;

node*p=head;

returnNULL;

while(p<&<&i!=j)

(

p=p->next;j++;

}

returnp;

}

算法3.3在單鏈表中查找一個(gè)值為x的結(jié)點(diǎn)

仃而葉陸大學(xué)

單鏈表的插入過(guò)程見(jiàn)下圖所示:

head

P

(a)在單鏈表的最前面插入一個(gè)值為x的新結(jié)點(diǎn)

仃而中陸火學(xué)

單鏈表的插入過(guò)程見(jiàn)下圖所示:

head

P

(a)在單鏈表的最前面插入一個(gè)值為x的新結(jié)點(diǎn)

仃而中陸火學(xué)網(wǎng)

全?1

單鏈表的插入過(guò)程見(jiàn)下圖所示：

單鏈表的插入過(guò)程見(jiàn)下圖所示：

P

(b)在q所指的結(jié)點(diǎn)后福入一個(gè)p所指的值為x的新結(jié)點(diǎn)

仃而中陸火學(xué)

7,7,7,yf^vl^yj^VI^KI^

^Tw

/*函數(shù)功能:單鏈表第i個(gè)結(jié)點(diǎn)后插入值為x的新結(jié)點(diǎn)*/

/*函數(shù)參數(shù):指向node類(lèi)型變量的指針head*/

/*datatype類(lèi)型變量x,int型變量工*/

/*函數(shù)返回值:指向node類(lèi)型變量的指針*/

/*文件名：sinklist.c,函數(shù)名：insert。*/

7,7,7,^fx7,7,7,^fxyj^vl^KI^yj^VI^KJ^KJ^yj^vl^

<Tw<T><Tw

node*insert(node*head,datatypexjnti)

node*p,*q;

q=find(headj);/*查找第i個(gè)結(jié)點(diǎn)*/

if(!q&&!二0)

printf(“\n找不到第%01個(gè)結(jié)點(diǎn)，不能插入%d!”J,x);

else{

p二(node*)malloc(sizeof(node));/*分酉己空間*/

p->info=x;/*設(shè)置新結(jié)點(diǎn)”

if(i==OX/*插入的結(jié)點(diǎn)作為單鏈表的第一個(gè)結(jié)點(diǎn)★/

p->next=head;/*插入⑴"

head=p;/*插入(2)*/

}

else{

p->next=q->next;/*插入⑴"

q->next=p;/*插入(2)*/

)

}

returnhead;

}

算法3.4在單鏈表中第泠結(jié)點(diǎn)后插入一個(gè)值為始勺新結(jié)點(diǎn)

刪除操作見(jiàn)下圖所示:

head

(2)free(p)

(a)刪除單鏈表的最前面的(第一個(gè))結(jié)點(diǎn)

刪除操作見(jiàn)下圖所示:

head/------?........?A

(1)head=head->next;

(2)free(p)

(a)刪除單鏈表的最前面的(第一個(gè))結(jié)點(diǎn)

仃而葉陸大學(xué)

head__?A

(1)pre->next=p->next;

preP

(b)刪除p指向的結(jié)點(diǎn),pre為p的前驅(qū)結(jié)點(diǎn)

網(wǎng)

全?1

⑴

preP

(b)刪除p指向的結(jié)點(diǎn),pre為p的前驅(qū)結(jié)點(diǎn)

網(wǎng)

全?

⑴

(2)free(p)

(b)刪除p指向的結(jié)點(diǎn)，pre為p的前驅(qū)結(jié)點(diǎn)

vi^7,KI^7,^fx7,7,vf^vi^K!>

/*函數(shù)功能:在單鏈表中刪除一個(gè)值為X的結(jié)點(diǎn)*/

/*函數(shù)參數(shù):指向node類(lèi)型變量的指針head*/

/*datatype類(lèi)型變量x*/

/*函數(shù)返回值:指向node類(lèi)型變量的指針*/

/*文件名:sinklist.c,函數(shù)名:dele()*/

KI^KI^Kl^7,7,^fx7,7,7,^fxKl^

node*dele(node*head.datatypex)

(

node*pre=NULL,*p;

if(!head){printf("串鏈表是空的！H);returnhead;}

p=head;

while(p<&<&p->info!=x)/*沒(méi)有找到并且沒(méi)有找完“

{pre=p;p=p->next;}/*pre指向p的前驅(qū)結(jié)點(diǎn)*/

if(!pre<&<&p->info==x)/*要?jiǎng)h除而是第一個(gè)結(jié)點(diǎn)”

head=head->next;/*冊(cè)U除(1)*/

else

pre->next=p->next;

free(p);

returnhead;

仃而葉陸大學(xué)□退出

3.3帶頭結(jié)點(diǎn)單鏈表

331帶頭結(jié)點(diǎn)單鏈表

帶頭結(jié)點(diǎn)單鏈表見(jiàn)下圖所示:

(B)非空表

網(wǎng)

全I(xiàn)1

332帶頭結(jié)點(diǎn)單鏈表的實(shí)現(xiàn)

一般的單鏈表中，第一個(gè)結(jié)點(diǎn)由head指示，而在

帶頭結(jié)點(diǎn)單鏈表中，head指示的是所謂的頭結(jié)點(diǎn)，它

不是存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中的實(shí)際結(jié)點(diǎn)，第一個(gè)實(shí)際的結(jié)點(diǎn)是

head->next指示的。在帶頭結(jié)點(diǎn)單鏈表的操作實(shí)現(xiàn)時(shí)

要注意這一點(diǎn)。

仃而中陸火學(xué)

node*init()

(

node*head;

head=(node*)malIoc(sizeof(node));

head->next=NULL;

returnhead;

)

算法3.6建立一個(gè)空的帶頭結(jié)點(diǎn)的單鏈表

□網(wǎng)

全I(xiàn)1

voiddisplay(node*head)

node*p;

p=head->next;/*從第一個(gè)(實(shí)際)結(jié)點(diǎn)開(kāi)始*/

if(!p)printf(“\n帶頭結(jié)點(diǎn)的單鏈表是空的!”)；

else

(

printf(“\n帶頭結(jié)點(diǎn)的單鏈表各個(gè)結(jié)點(diǎn)的值為:\n");

while(p){printf("%5d”,p->info);p=p->next;}

}

算法3.7輸出帶頭結(jié)點(diǎn)的單鏈表中各個(gè)結(jié)點(diǎn)的值

仃而中陸火學(xué)

^fx^Ixxjx^jxKI^KJX%|^xl^^F

^F

/*函數(shù)功能:在帶頭結(jié)點(diǎn)的單鏈表中查找第i個(gè)結(jié)點(diǎn)地址*/

/*函數(shù)參數(shù):指向node類(lèi)型變量的指針head*/

/*int類(lèi)型變量i*/

/*函數(shù)返回值:指向node類(lèi)型變量的指針head*/

/*文件名hlnklist.c,函數(shù)名find。*/

-1，7,^S>VI>yj^^jxKI^KI^^Jxxjx^JxKJ^KJX7,^fx/'

/*Tw<Tw/

node*find(node*headjnti)

(

intj=0;

node*p=head;

if(i<O){printf(“\n帶頭結(jié)點(diǎn)的單鏈表中不存在第％(1個(gè)結(jié)點(diǎn)!

11J);returnNULL;}

elseif(i==O)returnp;/*此時(shí)p指向的是頭結(jié)點(diǎn)*/

while(p<&<&il=j)/*沒(méi)有查找完并且還沒(méi)有找到*/

p=p->next;j++;/*繼續(xù)向后（左）查找，計(jì)數(shù)器加1*/

）

returnp;/*返回結(jié)果/二0時(shí),p指示的是頭結(jié)點(diǎn)*/

算法3.8在帶頭結(jié)點(diǎn)的單鏈表中查找第泠結(jié)點(diǎn)

仃而中陸火學(xué)

帶頭結(jié)點(diǎn)單鏈表的插入過(guò)程見(jiàn)圖3.7:

P

⑻非空帶頭結(jié)點(diǎn)單鏈表的最前面插入一個(gè)值為x的新結(jié)點(diǎn)

(2)

P

(b)在q所指的結(jié)點(diǎn)后插入一個(gè)p所指的值為x的新結(jié)點(diǎn)

□網(wǎng)

全I(xiàn)1

帶頭結(jié)點(diǎn)的單鏈表的插入操作的具體實(shí)現(xiàn)見(jiàn)算法3.9。

7,7,7,7,%x^7,7,7,7,%x^7,

*Tw*Tw<T**Tw*Tw*Tw

/*函數(shù)功能:在帶頭結(jié)點(diǎn)的單鏈表中第i個(gè)結(jié)點(diǎn)后插入一個(gè)值為

x的?新^幺吉點(diǎn)*/

/*函數(shù)參數(shù):指向node類(lèi)型變量的指針head*/

/*datatype類(lèi)型變量x,int型變量i*/

/*函數(shù)返回值:指向node類(lèi)型變量法指針head*/

/*文件名：hlnklist.c,函數(shù)名：insert。*/

7,7,7,7,7,7,7,KJ^KJ^KJ^KJ^7,K!^

node*insert(node*head.datatypexjnti)

{node*p,*q;

q=find(headj);/*查找?guī)ь^結(jié)點(diǎn)的單鏈表中的第i個(gè)結(jié)點(diǎn)”

/*i=0,表示新結(jié)點(diǎn)插入在頭結(jié)點(diǎn)之后，此時(shí)q

指向的是頭結(jié)點(diǎn)”

仃而中陸火學(xué)

????????????????■??????

if(!q)/*沒(méi)有找到*/

{printf(“\n帶頭結(jié)點(diǎn)的單鏈表中不存在第%<1個(gè)結(jié)點(diǎn)！不能

插X(qián)%d!returnhead;}

p=(node*)malloc(sizeof(node));/*為準(zhǔn)備插入的新結(jié)點(diǎn)

分配空間*/

p->info=x;/*為新結(jié)點(diǎn)設(shè)置值x*/

p->next=q->next;/*插入(1)*/

q->next=p;/*插入(2),當(dāng)i=0時(shí)，由于q指向的是頭結(jié)點(diǎn)，

本語(yǔ)句等價(jià)于head>next=p*/

returnhead;

}

算法3.9在帶頭結(jié)點(diǎn)的單鏈表中第泠結(jié)點(diǎn)后插入一個(gè)值為必勺

新結(jié)點(diǎn)

仃而中陸火學(xué)

帶頭結(jié)點(diǎn)單鏈表的刪除過(guò)程見(jiàn)圖3.8。

(1)

head

(a)刪除帶頭結(jié)點(diǎn)單鏈表的最前面的(第一個(gè))實(shí)際結(jié)點(diǎn)

hea

(b)在帶頭結(jié)點(diǎn)單鏈表中刪除q指向的結(jié)點(diǎn)，pre為q的前驅(qū)結(jié)點(diǎn)

仃而中陸火學(xué)□網(wǎng)

全I(xiàn)1

node*dele(node*head,datatypex)

node*pre=head,*q;/*首先pre指向頭結(jié)點(diǎn)*/

q=head->next;/*q從帶頭結(jié)點(diǎn)的第一個(gè)實(shí)際

結(jié)點(diǎn)開(kāi)始找值為x的結(jié)點(diǎn)*/

while(q<&<&q->info!=x)/*沒(méi)有查找完并且還沒(méi)有找到“

{pre=q;q=q->next;}/*繼續(xù)查找,pre指向q的前驅(qū)”

if(q){pre->next=q->next;/*刪除“

free(q);)/*釋放空間*/

returnhead;

算法3.10在帶頭結(jié)點(diǎn)的單鏈表中刪除一個(gè)值為用的結(jié)點(diǎn)

算|3法設(shè)計(jì)題:

1、用單鏈表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)線(xiàn)性表(%,%,???，

%1)就地逆置的操作，所謂就地指輔助空間應(yīng)為

O(l)o

2、設(shè)單鏈表L是一個(gè)遞減有序表，試寫(xiě)一算法將X插

入其中后仍保持L的有序性。

3、寫(xiě)一算法修單鏈表中值重復(fù)的結(jié)點(diǎn)刪除，使所得的

結(jié)果表中各結(jié)點(diǎn)值均不相同。

4、設(shè)計(jì)一個(gè)算法，對(duì)單鏈表按結(jié)點(diǎn)值從小到大對(duì)結(jié)點(diǎn)

進(jìn)行排序。

仃而中陸火學(xué)

算|3法設(shè)計(jì)題:

5、設(shè)計(jì)一個(gè)算法，修兩個(gè)有序單鏈表合并成一個(gè)有序

的單鏈表。

6、設(shè)計(jì)一個(gè)算法，求兩個(gè)單鏈表表示的集合的交集,

并將結(jié)果用一個(gè)新的單鏈表保存并返回。

仃而中陸火學(xué)

headp

50?4048010八

鏈表插入排序演示

p

50440--80--10A

s

head

!p

408010A

循環(huán)結(jié)束時(shí)，將

head

s結(jié)點(diǎn)力口在pre與

q所指示的結(jié)點(diǎn)

s之間！

preq=head->next

while(q&&q->data<s->data)

{pre=q;q=q->next;}

仃而葉陸大學(xué)

!p

preq=head->next

while(q&&q->data<s->data)

{pre=q;q=q->next;}

!p

preq=head->next

while(q&&q->data<s->data)

{pre=q;q=q->next;}

p

preq=head->next

while(q&&q->data<s->data)

{pre=q;q=q->next;}

”|3法設(shè)計(jì)題:

多相式相加問(wèn)題：

A(x)=7+3x+9x8+5x17

B(x)=8x+22x7-9x8

3.4循環(huán)單鏈表

3.4.1循環(huán)單鏈表

head

循環(huán)單鏈表類(lèi)型的描述（略）

3.4.2循環(huán)單鏈表的實(shí)現(xiàn)

單鏈表中某個(gè)結(jié)點(diǎn)P是表中最后一個(gè)結(jié)點(diǎn)的特征

是p->next==NULL。對(duì)于一個(gè)循環(huán)單鏈表，若首指

針為head,表中的某個(gè)結(jié)點(diǎn)p是最后一個(gè)結(jié)點(diǎn)的特征

應(yīng)該是p->next==head。

循環(huán)單鏈表的頭文件和單鏈表的相同。

仃而中陸火學(xué)

建立一個(gè)空的循環(huán)單鏈表

/MXMXMXMXMX/

1*TW*TM*T**T**T**TW*T*>T**T**TW*TM*T**T**T**TW*T**T**T**TW*T*>T**T**TW/

/*函數(shù)功能:建立一個(gè)空的循環(huán)單鏈表*/

/*函數(shù)參數(shù):無(wú)*/

/*函數(shù)返回值:指向node類(lèi)型變量的指針*/

/*文件名:clnklist.c,函數(shù)名init()*/

//

1*T**TM<T*>T**TM<T^^TW>T^>T**TM<T*>T**TM<T*>T**TM<T^^Tw>T^>T*1

node*init()/*建立一個(gè)空的循環(huán)單鏈表*/

returnNULL;

}

算法3.11建立一個(gè)空的循環(huán)單鏈表

網(wǎng)

全?1

MX*2XK1^/

^Tw1

/*函數(shù)功能:獲得循環(huán)單鏈表的最后一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址*/

/*函數(shù)參數(shù):指向node類(lèi)型變量的指針變量head*/

/*函數(shù)返回值:指向node類(lèi)型變量的指針*/

/*文件名:clnklist.c,函數(shù)名:rear。*/

//

1#T^<T^^TW#T^<X^<TW#T^*T^1

node*rear(node*head)

{

node*p;

if(!head)/*循環(huán)單鏈表為空*/

p=NULL;

else

{

p=head;/*從第一個(gè)結(jié)點(diǎn)開(kāi)始*/

while(p->next!=head)/*沒(méi)有到達(dá)最后一個(gè)結(jié)點(diǎn)*/

p=p->next;/*繼續(xù)向后*/

returnp;

算法3.12獲得循環(huán)單鏈表的最后一個(gè)結(jié)點(diǎn)的存儲(chǔ)地址

仃而葉陸大學(xué)□

/K1>vl>K!>vl>K1>vl>^|>/

1*1**TW<T**T**T**TW^T%*T**T**TW*T*<T*<T**TW*T**T**TW*T*<T*<T^<TX*T^>T^<T>!

/*函數(shù)功能:輸出循環(huán)單鏈表中各個(gè)結(jié)點(diǎn)的值*/

/*函數(shù)參數(shù):指向node類(lèi)型變量的指針變量head*/

/*函數(shù)返回值:空*/

/*文件名:clnklistc,函數(shù)名:display。*/

/^x>KI^KI^KI^KI^KI^KI^/

1*T**T**T**T**T**T**T*<T*/

voiddisplay(node*head)

{

node*p;

if(!head)printf("\n循環(huán)單鏈表是空的！\n");

else

printf("\n循環(huán)單鏈表各個(gè)結(jié)點(diǎn)的值分別為八n“)；

printf("%5(T\head->info);/*輸出非空表中第一個(gè)結(jié)點(diǎn)的值*/

仃而中陸火學(xué)

????????????????■??????

p=head->next;/*p指向第一個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)*/

while(p!=head)/*沒(méi)有回到第一個(gè)結(jié)點(diǎn)*/

printf(,,%5dt\p->info);

p=p->next;

算法3.13輸出循環(huán)單鏈表中各個(gè)結(jié)點(diǎn)的值

仃而葉陸大學(xué)

/^1^/

1<T**T*^T*<T^<T*<T^*T*^T^<T^<T*<T^<T^*T*<T^<T*1

/*函數(shù)功能:循環(huán)單鏈表中查找值為X的結(jié)點(diǎn)的存儲(chǔ)地址*/

/*函數(shù)參數(shù):指向node類(lèi)型變量的指針變量head*/

/*datatype類(lèi)型的變量x*/

/*函數(shù)返回值:指向node類(lèi)型變量的指針*/

/*文件名:clnklistc,函數(shù)名:行nd()*/

/K!>/

1<T*<T^<T^<T^<T^<T^<T^<T^1

node*find(node*head,datatypex)

{

/*查找一個(gè)值為x的結(jié)點(diǎn)*/

node*q;

if(!head)/*循環(huán)單鏈表是空的*/

{

printff'n循環(huán)單鏈表是空的！無(wú)法找指定結(jié)點(diǎn)！”);

returnNULL;

仃而中陸火學(xué)

????????????????■??????

)

q=head;/*q指向循環(huán)單鏈表的第一個(gè)結(jié)點(diǎn)，準(zhǔn)備查找*/

while(q->next!=head&(&q->info!=x)/*沒(méi)有查找到并且沒(méi)有

查找完整個(gè)表*/

q=q->next;/*繼續(xù)查找*/

if(q->info==x)returnq;

else

returnNULL;

算法3.14在循環(huán)單鏈表中查找一個(gè)值為x的結(jié)點(diǎn)

循環(huán)單鏈表的插入過(guò)程如圖：

⑶

head

(2)

P(3)rear->next=p;

(a)在循環(huán)單鏈表的最前面插入一個(gè)值為x的新結(jié)點(diǎn)

仃而中陸火學(xué)網(wǎng)

全?1

循環(huán)單鏈表的插入過(guò)程如圖:

head

(b)循環(huán)單鏈表，在q所指的結(jié)點(diǎn)后插入一個(gè)p所指的

值為x的新結(jié)點(diǎn)

仃而中陸火學(xué)

KJ^KJ^^JXyjx7,%X^yjx7,yjxKj^yj>yj^yj^yj>yj^/!

/*函數(shù)功能:循環(huán)單鏈表第i個(gè)結(jié)點(diǎn)后插入值為x的新結(jié)點(diǎn)*/

/*函數(shù)參數(shù):指向node類(lèi)型變量的指針變量head*/

/*datatype類(lèi)型的變量x，int類(lèi)型的變量I*/

/*函數(shù)返回值:指向node類(lèi)型麥量的指針*/

/*文件名:clnklist.c,函數(shù)名:insert()*/

//

/*T**T**T^*T**T**T**T^*T**T**T**T^*T**T**T^*T**T**T^*T**T**T^*T**T**T**T^*T**T**T**T^*T**T*^TM*T^*TW/

node*insert(node*head,datatypex,inti)

{/*i為0時(shí)表示將值為x的結(jié)點(diǎn)插入作為循環(huán)單鏈表的第一個(gè)結(jié)點(diǎn)*/

node*p,*q,*myrear;

intj;

p=(node*)malloc(sizeof(node));/*分配空間*/

p->info=x;/*設(shè)置新結(jié)點(diǎn)的值*/

if(i<0)/*如果i小于0,則輸出出錯(cuò)信息*/

{printf("\n無(wú)法找到指定的插入位置！n);free(p);returnhead;}

仃而中陸火學(xué)

????????????????■??????

if(i==O&&!head)/*插入前循環(huán)單鏈表如果是空的,則新結(jié)

點(diǎn)的指針域應(yīng)指向它自己*/

{p->next=p;head=p;returnhead;}

if(i==O&(&head)/*在非空的循環(huán)單鏈表最前面插

入*/

{myrear=rear(head);/*找到循環(huán)單鏈表的最后一個(gè)結(jié)點(diǎn)*/

p->next=head;/*插入(1)*/head=p;/*插入Q)*/

myrear->next=p;/*插入(3)最后一個(gè)結(jié)點(diǎn)而指針域指向新

插入的表中第一個(gè)結(jié)點(diǎn)*/

returnhead;

}

if(i>O&&!head){printf「\n無(wú)法找到指定的插入位置！”)；

free(p);returnhead;}

if(i>O&&head){/*在非空的循環(huán)單鏈表中插入值為x的結(jié)點(diǎn)，并

且插入的結(jié)點(diǎn)不是第一個(gè)結(jié)點(diǎn)*/

仃而中陸火學(xué)

q=head;/*準(zhǔn)備從表中第一個(gè)結(jié)點(diǎn)開(kāi)始查找*/

j=l；/*計(jì)數(shù)開(kāi)始*/

while(i!=j&&q->next!=head)/*沒(méi)有找到并且沒(méi)有找遍

整個(gè)表*/

q=q->next;j++;/*繼續(xù)查找，計(jì)數(shù)器加1*/

}

if(i!=j)/*找不到指定插入位置，即i的值超過(guò)表中結(jié)點(diǎn)

的個(gè)數(shù)，則不進(jìn)行插入*/

{

printf「\n表中不存在第％d個(gè)結(jié)點(diǎn)，無(wú)法進(jìn)行插入!\iP\i);

free(p);

returnhead;

else

/*找到了第i個(gè)結(jié)點(diǎn)，插入x*/

p->next=q->next;/*插入，修改指針(1)*/

q->next=p;/*插入，修改指針(2)*/

returnhead;

算法3.15在循環(huán)單鏈表中第，個(gè)結(jié)點(diǎn)后插入一個(gè)值為x的新結(jié)點(diǎn)

網(wǎng)

全?1

循環(huán)單鏈表的刪除過(guò)程如圖：

⑴⑵X(2)

(a)刪除循環(huán)單鏈表的最前面的(第一個(gè))結(jié)點(diǎn)

仃而中陸火學(xué)

循環(huán)單鏈表的刪除過(guò)程如圖：

preq

(b)刪除q指向的結(jié)點(diǎn)，pre為q的前驅(qū)結(jié)點(diǎn)(q指向的不是循環(huán)單

鏈表的第一個(gè)結(jié)點(diǎn))

仃而中陸火學(xué)

/v!>K!>vl>K!>K!>K1>vl>K!>v!>K!>vl>K!>K!^/

/1

/*函數(shù)功能:在循環(huán)單鏈表中刪除一個(gè)值為X的結(jié)點(diǎn)*/

/*函數(shù)參數(shù):指向node類(lèi)型變量的指針變量head*/

/*datatype類(lèi)型的變量x*/

/*函數(shù)返回值:指向node類(lèi)型變量的指針*/

/*文件名:clnklist.c,函數(shù)名:dele()*/

/K1>K!>K1>vl>K!>v!>K!>vl>K!>K!>K1>vl>K!>v!>K!>vl>K!>/

/*TM*TM*TM1

node*dele(node*head,datatypex)

(

node*pre=NULL,*q;/*q用于查找值為x的結(jié)點(diǎn),pre指向q的

前驅(qū)結(jié)點(diǎn)*/

if(!head)/*表為空，則無(wú)法做刪除操作*/

(

printf("\n循環(huán)單鏈表為空，無(wú)法做刪除操作！”)；

returnhead;

q=head;/*從第1個(gè)結(jié)點(diǎn)開(kāi)始準(zhǔn)備查找*/

while(q->next!=head&&q->info!=x)/*沒(méi)有找遍整個(gè)表并且

沒(méi)有找到*/

pre=q;

q=q->next;/*pre為q的前驅(qū)，繼續(xù)查找*/

}/*循環(huán)結(jié)束后,pre為q的前驅(qū)*/

if(q->info!=x)/*沒(méi)找到*/

printf「沒(méi)有找到值為％(1的結(jié)點(diǎn)！n,x);

else/*找到了，下面要?jiǎng)h除q*/

if(q!=head){pre->next=q->next;free(q);}

else

仃而中陸火學(xué)