第3章-線性表及其鏈?zhǔn)酱鎯?chǔ)

數(shù)據(jù)結(jié)構(gòu)李云清楊慶紅揭安全人民郵電出版社高等學(xué)校精品課程（省級(jí)）國(guó)家十二五規(guī)劃教材高等學(xué)校精品課程（省級(jí)）國(guó)家十二五規(guī)劃教材第3章線性表及其鏈?zhǔn)酱鎯?chǔ)揭安全jieanquan@163.com江西師范大學(xué)計(jì)算機(jī)信息工程學(xué)院第3章線性表的鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)單鏈表帶頭結(jié)點(diǎn)的單鏈表循環(huán)單鏈表雙鏈表鏈?zhǔn)綏ｆ準(zhǔn)疥?duì)列

線性表的存儲(chǔ)方式除了常用的順序存儲(chǔ)外，采用鏈?zhǔn)椒绞酱鎯?chǔ)也是一種常見(jiàn)的方式。本章將介紹一般線性表的幾種鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)方式，如單鏈表、帶頭結(jié)點(diǎn)單鏈表、循環(huán)單鏈表、雙鏈表以及特殊的線性表------棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)實(shí)現(xiàn)。3.1鏈?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ū)或后繼。

線性結(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={k1,k2,k3,k4,k5}R={r}R={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}是一個(gè)線性結(jié)構(gòu)，它的鏈?zhǔn)酱鎯?chǔ)如圖所示100010011002100310041005100610071008存儲(chǔ)地址infonextk41006k21007k11003k5∧k31005

為了清晰，上圖可以更簡(jiǎn)潔地用下圖表示。k1k5∧k2k3k4head3.2單鏈表

單鏈表是線性表鏈?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)。數(shù)據(jù)1指針◎數(shù)據(jù)2指針◎數(shù)據(jù)3指針◎數(shù)據(jù)域指針域…節(jié)點(diǎn)直觀化的描述方法：?jiǎn)捂湵硎怯杀眍^唯一確定，因此單鏈表可以用頭指針的名字來(lái)命名。例如：若頭指針名是head，則把鏈表稱(chēng)為表head。head(a)非空表head=NULL(b)空表3.2.2單鏈表的實(shí)現(xiàn)

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

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

///typedefintdatatype;typedefstructlink_node{datatypeinfo;structlink_nodenext;}node;typedefnode*linklist;單鏈表幾個(gè)基本操作的具體實(shí)現(xiàn)：建立一個(gè)空的單鏈表///

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

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

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

文件名:slnklist.c,函數(shù)名:init() ///nodeinit()/建立一個(gè)空的單鏈表/

{

returnNULL;

}算法3.1建立一個(gè)空的單鏈表輸出單鏈表中各個(gè)結(jié)點(diǎn)的值

voiddisplay(nodehead){nodep;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)的值在單鏈表中查找第i個(gè)結(jié)點(diǎn)

nodefind(nodehead,inti){intj=1;nodep=head;if(i<1)returnNULL;while(p&&i!=j){p=p->next;j++;}returnp;}算法3.3在單鏈表中查找第i個(gè)結(jié)點(diǎn)單鏈表的插入過(guò)程見(jiàn)下圖所示：

∧headpx(2)head=p;(1)(1)p->next=head;(a)在單鏈表的最前面插入一個(gè)值為x的新結(jié)點(diǎn)單鏈表的插入過(guò)程見(jiàn)下圖所示：

∧head

(2)px(2)head=p;(a)在單鏈表的最前面插入一個(gè)值為x的新結(jié)點(diǎn)(1)(1)p->next=head;單鏈表的插入過(guò)程見(jiàn)下圖所示：∧head

(b)在q所指的結(jié)點(diǎn)后插入一個(gè)p所指的值為x的新結(jié)點(diǎn)(1)p->next=q->next;xpq(1)單鏈表的插入過(guò)程見(jiàn)下圖所示：∧head

x(b)在q所指的結(jié)點(diǎn)后插入一個(gè)p所指的值為x的新結(jié)點(diǎn)(1)p->next=q->next;pq(2)q->next=p;(1)(2)///

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

//

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

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

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

//

文件名:slnklist.c,函數(shù)名:insert()

///nodeinsert(nodehead,datatypex,inti){nodep,q;

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

if(!q&&i!=0)

printf("\n找不到第%d個(gè)結(jié)點(diǎn),不能插入%d！",i,x);

else{

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

p->info=x; /設(shè)置新結(jié)點(diǎn)/if(i==0){ /*插入的結(jié)點(diǎn)作為單鏈表的第一個(gè)結(jié)點(diǎn)*/

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

}

else{p->next=q->next; /插入(1)/q->next=p; /插入(2)/}}

returnhead;}算法3.4在單鏈表中第i個(gè)結(jié)點(diǎn)后插入一個(gè)值為x的新結(jié)點(diǎn)1、申請(qǐng)空間s=malloc(...)2、填入數(shù)據(jù)域值s->info=ch;單鏈表應(yīng)用-----建立單鏈表方法一：堆棧方式建立單鏈表（頭插法）數(shù)據(jù)1^head數(shù)據(jù)2s數(shù)據(jù)33、新結(jié)點(diǎn)鏈入表頭s->next=head;4、修改表頭指針head=s;數(shù)據(jù)1^head數(shù)據(jù)2s數(shù)據(jù)34、修改表頭指針head=s;單鏈表應(yīng)用-----建立單鏈表方法一：堆棧方式建立單鏈表（頭插法）#include“l(fā)inklist.h”node*creatlistf(){datatypedata;node*head,*s;head=NULL;printf("\n\nPleaseinputthedataoflinklist\n");

scanf("%d",&data);while(data!=0){s=(node*)malloc(sizeof(node));s->info=data;s->next=head;head=s;

scanf("%d",&data);}returnhead;}1、申請(qǐng)空間s=malloc()2、填入數(shù)據(jù)域值s->info=ch;3、新結(jié)點(diǎn)鏈入表尾r->next=s;4、修改表尾指針r=s;方法二：隊(duì)列方式建立單鏈表（尾插法）數(shù)據(jù)2head數(shù)據(jù)1s數(shù)據(jù)3r方法二：隊(duì)列方式建立單鏈表（尾插法）數(shù)據(jù)2head數(shù)據(jù)1s數(shù)據(jù)3r關(guān)鍵一步：

設(shè)置一個(gè)鏈尾指針r，每次將新的結(jié)點(diǎn)鏈在r的后面，使其成為新的表尾結(jié)點(diǎn)。node*creatlistr(void){datatypedata;node*head,*s,*r;head=NULL;r=NULL;scanf("%d",&data);while(data){s=(node*)malloc(sizeof(node));s->info=data;/*產(chǎn)生新結(jié)點(diǎn)*/

if(head==NULL)head=s;/*新結(jié)點(diǎn)插入空表*/

elser->next=s;

r=s;scanf("%d",&data);

}/*處理表尾結(jié)點(diǎn)指針域*/以0作為輸入結(jié)束條件if(r!=NULL)r->next=NULL;returnhead;}刪除操作見(jiàn)下圖所示：

∧headp(1)head=head->next;(a)刪除單鏈表的最前面的（第一個(gè)）結(jié)點(diǎn)(2)free(p)刪除操作見(jiàn)下圖所示：

∧head(1)head=head->next;(a)刪除單鏈表的最前面的（第一個(gè)）結(jié)點(diǎn)(2)free(p)(b)刪除p指向的結(jié)點(diǎn)，pre為p的前驅(qū)結(jié)點(diǎn)(1)pre->next=p->next;∧head

prep(b)刪除p指向的結(jié)點(diǎn)，pre為p的前驅(qū)結(jié)點(diǎn)(1)pre->next=p->next;∧head

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

pre->next=p->next;∧head

pre(1)(2)free(p)///

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

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

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

文件名:slnklist.c,函數(shù)名:dele() ///nodedele(nodehead,datatypex){nodepre=NULL,p;if(!head){printf("單鏈表是空的！");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; /刪除(1)/elsepre->next=p->next;free(p);returnhead;}算法3.5在單鏈表中刪除一個(gè)值為x的結(jié)點(diǎn)鏈?zhǔn)酱鎯?chǔ)的插入和刪除操作比順序存儲(chǔ)方便，但不能隨機(jī)訪問(wèn)某個(gè)結(jié)點(diǎn)！3.3帶頭結(jié)點(diǎn)單鏈表

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

帶頭結(jié)點(diǎn)單鏈表見(jiàn)下圖所示：數(shù)據(jù)2數(shù)據(jù)1數(shù)據(jù)3headhead(A)空表(B)非空表^^3.3.2帶頭結(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)。

nodeinit(){nodehead;head=(node)malloc(sizeof(node));head->next=NULL;returnhead;}算法3.6建立一個(gè)空的帶頭結(jié)點(diǎn)的單鏈表

請(qǐng)修改頭插法與尾插法建表程序,以建立帶頭結(jié)點(diǎn)的單鏈表。

voiddisplay(nodehead){nodep;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)的值///

函數(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() ///nodefind(nodehead,inti){intj=0;nodep=head;if(i<0){printf("\n帶頭結(jié)點(diǎn)的單鏈表中不存在第%d個(gè)結(jié)點(diǎn)！",i);returnNULL;}

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

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

{

p=p->next;j++; /繼續(xù)向后（左）查找,計(jì)數(shù)器加1/}returnp; /返回結(jié)果,i=0時(shí),p指示的是頭結(jié)點(diǎn)/

}算法3.8在帶頭結(jié)點(diǎn)的單鏈表中查找第i個(gè)結(jié)點(diǎn)帶頭結(jié)點(diǎn)單鏈表的插入過(guò)程見(jiàn)圖3.7：∧x

(2)(1)(2)×qp(b)在q所指的結(jié)點(diǎn)后插入一個(gè)p所指的值為x的新結(jié)點(diǎn)(1)p->next=q->next;(2)q->next=p;headp

(2)

∧head×

(2)(1)x(1)p->next=q->next;(2)q->next=p;(a)非空帶頭結(jié)點(diǎn)單鏈表的最前面插入一個(gè)值為x的新結(jié)點(diǎn)q

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

///

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

//

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

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

文件名:hlnklist.c,函數(shù)名:insert() ///nodeinsert(nodehead,datatypex,inti){nodep,q;q=find(head,i); /查找?guī)ь^結(jié)點(diǎn)的單鏈表中的第i個(gè)結(jié)點(diǎn)/

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

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

{printf("\n帶頭結(jié)點(diǎn)的單鏈表中不存在第%d個(gè)結(jié)點(diǎn)！不能插入%d！",i,x);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)的單鏈表中第i個(gè)結(jié)點(diǎn)后插入一個(gè)值為x的新結(jié)點(diǎn)帶頭結(jié)點(diǎn)單鏈表的刪除過(guò)程見(jiàn)圖3.8。

∧

head×q(1)head->next=q->next;(a)刪除帶頭結(jié)點(diǎn)單鏈表的最前面的（第一個(gè)）實(shí)際結(jié)點(diǎn)

(1)(1)

(1)×(1)(b)在帶頭結(jié)點(diǎn)單鏈表中刪除q指向的結(jié)點(diǎn)，pre為q的前驅(qū)結(jié)點(diǎn)(1)pre->next=q->next;preq∧head

nodedele(nodehead,datatypex){nodepre=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è)值為x的結(jié)點(diǎn)算法設(shè)計(jì)題：1、用單鏈表作為存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)線性表（a0,a1,…,an-1）就地逆置的操作，所謂就地指輔助空間應(yīng)為O(1)。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)行排序。算法設(shè)計(jì)題：5、設(shè)計(jì)一個(gè)算法，將兩個(gè)有序單鏈表合并成一個(gè)有序的單鏈表。6、設(shè)計(jì)一個(gè)算法，求兩個(gè)單鏈表表示的集合的交集，并將結(jié)果用一個(gè)新的單鏈表保存并返回。

50

40

80

10^phead鏈表插入排序演示

50

40

80

10^phead^s^

50

40

80

10^phead^s^preq=head->next

while(q&&q->data<s->data){}pre=q;q=q->next;循環(huán)結(jié)束時(shí)，將s結(jié)點(diǎn)加在pre與q所指示的結(jié)點(diǎn)之間！

50

40

80

10^phead^s^preq=head->next

while(q&&q->data<s->data){}pre=q;q=q->next;s->next=q;pre->next=s;

50

40

80

10^pheads^preq=head->next

while(q&&q->data<s->data){}pre=q;q=q->next;s->next=q;pre->next=s;

50

40

80

10^pheads^preq=head->next

while(q&&q->data<s->data){}pre=q;q=q->next;s->next=q;pre->next=s;算法設(shè)計(jì)題：多相式相加問(wèn)題:A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8∧A703198517∧B81227-98C70111227∧5173.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)單鏈表的頭文件和單鏈表的相同。建立一個(gè)空的循環(huán)單鏈表

///

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

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

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

文件名:clnklist.c,函數(shù)名init() ///nodeinit() /建立一個(gè)空的循環(huán)單鏈表/

{

returnNULL;

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

///

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

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

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

文件名:clnklist.c,函數(shù)名:rear() ///noderear(nodehead){nodep;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ǔ)地址///

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

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

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

文件名:clnklist.c,函數(shù)名:display() ///voiddisplay(nodehead){nodep;if(!head)printf("\n循環(huán)單鏈表是空的！\n");

else

{

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

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

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

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

{

printf("%5d",p->info);

p=p->next;

}

}

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

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

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

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

//

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

//

文件名:clnklist.c,函數(shù)名:find()

///nodefind(nodehead,datatypex){/查找一個(gè)值為x的結(jié)點(diǎn)/

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

{

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

returnNULL;

}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ò)程如圖：

headpx

rear(a)在循環(huán)單鏈表的最前面插入一個(gè)值為x的新結(jié)點(diǎn)(1)p->next=head;(2)head=p;(3)rear->next=p;循環(huán)單鏈表的插入過(guò)程如圖：head

xqp(b)循環(huán)單鏈表，在q所指的結(jié)點(diǎn)后插入一個(gè)p所指的值為x的新結(jié)點(diǎn)(1)p->next=q->next;(2)q->next=p;///

函數(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()

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

nodep,q,*myrear;intj;p=(node)malloc(sizeof(node)); /分配空間/

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

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

{printf("\n無(wú)法找到指定的插入位置！");free(p);returnhead;}if(i==0&&!head) /插入前循環(huán)單鏈表如果是空的,則新結(jié)點(diǎn)的指針域應(yīng)指向它自己/

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

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

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

p->next=head; /插入(1)/head=p;/插入(2)/myrear->next=p; /插入(3)最后一個(gè)結(jié)點(diǎn)的指針域指向新插入的表中第一個(gè)結(jié)點(diǎn)/

returnhead;}

if(i>0&&!head){printf("\n無(wú)法找到指定的插入位置！");free(p);returnhead;}

if(i>0&&head){ /*在非空的循環(huán)單鏈表中插入值為x的結(jié)點(diǎn),并且插入的結(jié)點(diǎn)不是第一個(gè)結(jié)點(diǎn)*/

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

j=1; /計(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)行插入!\n",i);

free(p);

returnhead;

}

else

else{ /找到了第i個(gè)結(jié)點(diǎn),插入x/p->next=q->next; /插入,修改指針(1)/q->next=p; /插入,修改指針(2)/returnhead;}}}算法3.15在循環(huán)單鏈表中第i個(gè)結(jié)點(diǎn)后插入一個(gè)值為x的新結(jié)點(diǎn)循環(huán)單鏈表的刪除過(guò)程如圖：

head×q(1)head=head->next;(2)pre->next=head;(a)刪除循環(huán)單鏈表的最前面的（第一個(gè)）結(jié)點(diǎn)

(1)(1)pre

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

(1)×(1)(b)刪除q指向的結(jié)點(diǎn)，pre為q的前驅(qū)結(jié)點(diǎn)（q指向的不是循環(huán)單鏈表的第一個(gè)結(jié)點(diǎn)）(1)pre->next=q->next;preqhead

///

函數(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() ///nodedele(nodehead,datatypex){nodepre=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)有找到值為%d的結(jié)點(diǎn)！",x);

}

else /找到了,下面要?jiǎng)h除q/{if(q!=head){pre->next=q->next;free(q);}else

if(head->next==head){free(q);head=NULL;}else{pre=head->next;while(pre->next!=q)pre=pre->next; /*找q的前驅(qū)結(jié)點(diǎn)位置*/

head=head->next;

pre->next=head;

free(q);

}

}

returnhead;

}算法3.16在循環(huán)單鏈表中刪除一個(gè)值為x的結(jié)點(diǎn)3．循環(huán)單鏈表的整體插入與刪除操作圖3.12一個(gè)循環(huán)單鏈表整體插入到一個(gè)單鏈表前部的圖示3.5雙鏈表

3.5.1雙鏈表

前面的各種鏈?zhǔn)奖碇校粋€(gè)結(jié)點(diǎn)的指針域是指向它的后繼結(jié)點(diǎn)的，如果需要找一個(gè)結(jié)點(diǎn)p的前驅(qū)結(jié)點(diǎn)，則必須從表首指針開(kāi)始查找，當(dāng)某個(gè)結(jié)點(diǎn)pre的指針域指向的是結(jié)點(diǎn)p時(shí)，即pre->next==p時(shí)，則說(shuō)明pre是p的前驅(qū)結(jié)點(diǎn)。如果常常需要知道一個(gè)結(jié)點(diǎn)的前驅(qū)和后繼結(jié)點(diǎn)，上述的鏈?zhǔn)奖硎遣贿m合的。既然單鏈表中每個(gè)結(jié)點(diǎn)有一個(gè)指針域指向它的后繼結(jié)點(diǎn)，那自然地想到再增設(shè)一個(gè)指針域指向它的前驅(qū)結(jié)點(diǎn)，這就構(gòu)成了雙鏈表。

雙鏈表的結(jié)點(diǎn)包括三個(gè)域，一個(gè)是存放數(shù)據(jù)信息的info域，另外兩個(gè)是指針域，這里用llink和rlink表示，llink指向它的前驅(qū)結(jié)點(diǎn)，rlink指向它的后繼結(jié)點(diǎn)。雙鏈表的一般情形如圖所示：雙鏈表類(lèi)型的描述（略?。摹膆ead3.5.2雙鏈表的實(shí)現(xiàn)

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

雙鏈表的頭文件,文件名dlnklist.h

///typedefintdatatype;typedefstructdlink_node{datatypeinfo;structdlink_nodellink,rlink;}dnode;///

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

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

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

文件名:dlnklist.c,函數(shù)名:display() ///voiddisplay(dnodehead){dnodep;printf("\n");p=head;if(!p)printf("\n雙鏈表是空的!\n");

else

{printf("\n雙鏈表中各個(gè)結(jié)點(diǎn)的值為:\n");

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

}

}算法3.18輸出雙鏈表中各個(gè)結(jié)點(diǎn)的值dnodefind(dnodehead,inti){intj=1;dnodep=head;if(i<1){printf("\n第%d個(gè)結(jié)點(diǎn)不存在!\n",i);returnNULL;}

while(p&&i!=j) /沒(méi)有找完整個(gè)表并且沒(méi)有找到/

{

p=p->rlink;j++;/繼續(xù)沿著右指針向后查找,計(jì)數(shù)器加1/}if(!p){printf("\n第%d個(gè)結(jié)點(diǎn)不存在!\n",i);returnNULL;}

returnp;

}算法3.19查找雙鏈表中第i個(gè)結(jié)點(diǎn)雙鏈表插入過(guò)程如下圖所示：x∧head(1)p->rlink=head;p(a)在雙鏈表的最前面插入一個(gè)值為x的新結(jié)點(diǎn)(2)p->llink=NULL;(3)head->llink=p; (4)head=p;∧∧雙鏈表插入過(guò)程如下圖所示：

∧head

(1)p->rlink=q->rlink;∧qxp(b)在雙鏈表中q所指結(jié)點(diǎn)的后面插入一個(gè)值為x的新結(jié)點(diǎn)(2)p->llink=q;(3)q->rlink->llink=p;(4)q->rlink=p;雙鏈表插入過(guò)程如下圖所示：

(1)p->rlink=q->rlink;qxp(c)在雙鏈表中q所指結(jié)點(diǎn)（是最后一個(gè)結(jié)點(diǎn)）的后面插入一個(gè)值為x的新結(jié)點(diǎn)head

∧(2)p->llink=q;(3)q->rlink=p;∧∧///

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

函數(shù)參數(shù):指向dnode類(lèi)型變量的指針head //datatype類(lèi)型的變量x,int類(lèi)型的變量 //

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

文件名:dlnklist.c,函數(shù)名:insert() ///dnode*insert(dnode*head,datatypex,inti){dnode*p,*q;p=(dnode*)malloc(sizeof(dnode)); /*分配空間*/

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

if(i==0) /*在最前面插入一個(gè)值為x的新結(jié)點(diǎn)*/

{

p->llink=NULL; /*新插入的結(jié)點(diǎn)沒(méi)有前驅(qū)*/

p->rlink=head; /*新插入的結(jié)點(diǎn)的后繼是原來(lái)雙鏈表中的第一個(gè)結(jié)點(diǎn)*/

if(!head) /*原表為空*/

{

head=p;

}

else

{

head->llink=p; /*原來(lái)雙鏈表中第一個(gè)結(jié)點(diǎn)的前驅(qū)是新插入的結(jié)點(diǎn)*/

head=p; /*新結(jié)點(diǎn)成為雙鏈表的第一個(gè)結(jié)點(diǎn)*/

}

returnhead;

}

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

if(!q) /*第i個(gè)結(jié)點(diǎn)不存在*/

{printf("第%d個(gè)結(jié)點(diǎn)不存在,無(wú)法進(jìn)行插入",i);free(p);returnhead;}

if(q->rlink==NULL) /*在最后一個(gè)結(jié)點(diǎn)后插入*/

{

p->rlink=q->rlink; /*即為NULL,新插入的結(jié)點(diǎn)沒(méi)有后繼。插入操作（1）*/

p->llink=q; /*插入操作（2）*/

q->rlink=p; /*插入操（4）*/

} /*注意不能和下面的一般情況一樣處理,這里如執(zhí)行下面的（3）將出錯(cuò)！*/

else /*一般情況下的插入*/

{

p->rlink=q->rlink; /*插入操作（1）*/

p->llink=q; /*插入操作（2）*/

q->rlink->llink=p; /*插入操作（3）*/

q->rlink=p; /*插入操作（4）*/

}

returnhead;

}算法3.20在雙鏈表中第i個(gè)結(jié)點(diǎn)后插入一個(gè)值為x的新結(jié)點(diǎn)雙鏈表刪除操作圖示：∧∧head(a)被刪除的q是雙鏈表中唯一的一個(gè)結(jié)點(diǎn)qNULL∧∧(b)被刪除的q是雙鏈表中的第一個(gè)結(jié)點(diǎn)（表中不只這一個(gè)結(jié)點(diǎn)）qhead(1)head=head->rlink;(2)head->llink=NULL;(1)

×∧(2)雙鏈表刪除操作圖示：∧∧∧head(c)被刪除的q是雙鏈表中的最后一個(gè)結(jié)點(diǎn)qq->llink->rlink=NULL;∧∧q(1)q->llink->rlink=q->rlink;(2)q->rlink->llink=q->llink;(1)(2)head(d)被刪除的q是雙鏈表中既非第一也非最后的一個(gè)結(jié)點(diǎn)///

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

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

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

文件名:dlnklist.c,函數(shù)名:dele() ///dnodedele(dnodehead,datatypex){dnodeq;if(!head) /雙鏈表為空,無(wú)法進(jìn)行刪除操作/

{printf("雙鏈表為空,無(wú)法進(jìn)行刪除操作");returnhead;}

q=head;

while(q&&q->info!=x)q=q->rlink; /循環(huán)結(jié)束后q指向的是值為x的結(jié)點(diǎn)/

if(!q){printf("\n沒(méi)有找到值為%d的結(jié)點(diǎn)!不做刪除操作！",x);

}

if(q==head&&head->rlink) /被刪除的結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)并且表中不只一個(gè)結(jié)點(diǎn)/

{

head=head->rlink;

head->llink=NULL;

free(q);returnhead;

}

if(q==head&&!head->rlink)/被刪除的結(jié)點(diǎn)是第一個(gè)結(jié)點(diǎn)并且表中只有這一個(gè)結(jié)點(diǎn)/

{

free(q);

returnNULL;/雙鏈表置空/

}

else

{

if(!q->rlink)/被刪除的結(jié)點(diǎn)是雙鏈表中的最后一個(gè)結(jié)點(diǎn)/

{

q->llink->rlink=NULL;

free(q);

returnhead;

}

else

/q是有2個(gè)以上結(jié)點(diǎn)的雙鏈表中的一個(gè)非開(kāi)始、也非終端結(jié)點(diǎn)/

{

q->llink->rlink=q->rlink;

q->rlink->llink=q->llink;

free(q);returnhead;}}}算法3.21在雙鏈表中刪除一個(gè)值為x的結(jié)點(diǎn)3.6鏈?zhǔn)綏?/p>

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

棧的鏈?zhǔn)酱鎯?chǔ)稱(chēng)為鏈?zhǔn)綏?。鏈?zhǔn)綏＞褪且粋€(gè)特殊的單鏈表，對(duì)于這特殊的單鏈表，它的插入和刪除規(guī)定在單鏈表的同一端進(jìn)行。鏈?zhǔn)綏５臈ｍ斨羔樢话阌胻op表示，鏈?zhǔn)綏Ｈ缦聢D所示?！膖op3.6.2鏈?zhǔn)綏５膶?shí)現(xiàn)

///

函數(shù)功能:讀鏈?zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)值 //

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

函數(shù)返回值:datatype類(lèi)型的變量 //

文件名:lnkstack.c,函數(shù)名:read() ///datatyperead(nodetop){if(!top){printf("\n鏈?zhǔn)綏Ｊ强盏?");exit(1);}

return(top->info);} /*本函數(shù)可以調(diào)用empty()函數(shù)*/

算法3.24取得鏈?zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)值///

函數(shù)功能:輸出鏈?zhǔn)綏Ｖ懈鱾€(gè)結(jié)點(diǎn)的值 //

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

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

文件名:lnkstack.c,函數(shù)名:display() ///voiddisplay(nodetop){nodep;

p=top;printf("\n");if(!p)printf("\n鏈?zhǔn)綏Ｊ强盏?");

while(p){printf("%5d",p->info);p=p->next;}}算法3.25輸出鏈?zhǔn)綏Ｖ懈鱾€(gè)結(jié)點(diǎn)的值∧xtopp(1)p->next=top;

鏈?zhǔn)綏２迦氩僮麈準(zhǔn)綏＿M(jìn)棧操作(1)∧xtopp

(2)(1)p->next=top;

鏈?zhǔn)綏２迦氩僮?2)top=p;鏈?zhǔn)綏＿M(jìn)棧操作向鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)值為x的結(jié)點(diǎn)

nodepush(nodetop,datatypex){nodep;p=(node)malloc(sizeof(node)); /分配空間/

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

p->next=top; /插入（1）/

top=p;

/插入（2）/

returntop;

}算法3.26向鏈?zhǔn)綏Ｖ胁迦胍粋€(gè)值為x的結(jié)點(diǎn)∧top(1)q=top;

鏈?zhǔn)綏h除操作q鏈?zhǔn)綏３鰲２僮?2)top=top->next;(3)free(q)刪除鏈?zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)

nodepop(nodetop){nodeq;if(!top){printf("\n鏈?zhǔn)綏Ｊ强盏?");returnNULL;}

q=top; /指向被刪除的結(jié)點(diǎn)（1）/

top=top->next; /刪除棧頂結(jié)點(diǎn)（2）/

free(q);

returntop;

}算法3.27刪除鏈?zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)3.7鏈?zhǔn)疥?duì)列

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

隊(duì)列的鏈?zhǔn)酱鎯?chǔ)稱(chēng)為鏈?zhǔn)疥?duì)列。鏈?zhǔn)疥?duì)列就是一個(gè)特殊的單鏈表，對(duì)于這種特殊的單鏈表，它的插入和刪除規(guī)定在單鏈表的不同端進(jìn)行。鏈?zhǔn)疥?duì)列的隊(duì)首和隊(duì)尾指針?lè)謩e用front和rear表示，鏈?zhǔn)疥?duì)列如下圖所示?！摹膓ufrontrear(a)空的鏈?zhǔn)疥?duì)列∧qufrontrear(b)非空的鏈?zhǔn)疥?duì)列3.7.2鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)

鏈?zhǔn)疥?duì)列的結(jié)點(diǎn)定義和單鏈表一樣。隊(duì)列必須有隊(duì)首和隊(duì)尾指針，因此增加定義一個(gè)結(jié)構(gòu)類(lèi)型，其中的兩個(gè)域分別為隊(duì)首和隊(duì)尾指針。其定義如下：typedefstruct{nodefront,rear;/定義隊(duì)首與隊(duì)尾指針/

}queue;建立一個(gè)空的鏈?zhǔn)疥?duì)列

queueinit()/建立一個(gè)空的鏈?zhǔn)疥?duì)列/

{

queuequ;qu=(queue)malloc(sizeof(queue)); /分配空間/

qu->front=NULL; /隊(duì)首指針設(shè)置為空/

qu->rear=NULL; /隊(duì)尾指針設(shè)置為空/

returnqu;

}算法3.28建立一個(gè)空的鏈?zhǔn)疥?duì)列取得鏈?zhǔn)疥?duì)列的隊(duì)首結(jié)點(diǎn)值

///

函數(shù)功能:取得鏈?zhǔn)疥?duì)列的隊(duì)首結(jié)點(diǎn)值 //

函數(shù)參數(shù):queue類(lèi)型的變量qu //

函數(shù)返回值:datatype類(lèi)型 //

文件名:lnkqueue.c,函數(shù)名:read() ///datatyperead(queuequ){if(!qu.front){printf("\n鏈?zhǔn)疥?duì)列是空的!");exit(1);}

return(qu.front->info);

}算法3.31取得鏈?zhǔn)疥?duì)列的隊(duì)首結(jié)點(diǎn)值鏈?zhǔn)疥?duì)列的插入過(guò)程圖示見(jiàn)下圖：x∧pqufrontrearqu->front=qu->rear=p;(a)向空鏈?zhǔn)疥?duì)列中插入值為x的新結(jié)點(diǎn)鏈?zhǔn)疥?duì)列的插入過(guò)程圖示見(jiàn)下圖：x∧p(1)qu->rear->next=p;(b)在非空鏈?zhǔn)疥?duì)列中插入值為x的新結(jié)點(diǎn)qufrontrear(2)qu->rear=p;∧向鏈?zhǔn)疥?duì)列中插入一個(gè)值為x的結(jié)點(diǎn)

queueinsert(queuequ,datatypex){nodep;p=(node)malloc(sizeof(node)); /分配空間/

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

p->next=NULL;

if(qu->front==NULL) /當(dāng)前隊(duì)列為空,新插入的結(jié)點(diǎn)為隊(duì)列中惟一一個(gè)結(jié)點(diǎn)/

qu->front=qu->rear=p;

else

{

qu->rear->next=p; /隊(duì)尾插入/

qu->rear=p;

}

returnqu;

}算法3.32向鏈?zhǔn)疥?duì)列中插入一個(gè)值為x的結(jié)點(diǎn)鏈?zhǔn)疥?duì)列的刪除過(guò)程圖示見(jiàn)下圖：∧qqufrontrear(1)q=qu->front;(2)qu->front=q->next;(3)qu->rear=NULL;(a)鏈?zhǔn)疥?duì)列刪除操作（隊(duì)列中只有一個(gè)結(jié)點(diǎn)）鏈?zhǔn)疥?duì)列的刪除過(guò)程圖示見(jiàn)下圖：

∧qufrontrear(b)鏈?zhǔn)疥?duì)列刪除操作（隊(duì)列中不只一個(gè)結(jié)點(diǎn)）q(1)q=qu->front;(2)qu->front=q->next;刪除鏈?zhǔn)疥?duì)列中隊(duì)首結(jié)點(diǎn)

queuedele(queuequ) /刪除隊(duì)首結(jié)點(diǎn)/

{

nodeq;if(!qu->front){printf("隊(duì)列為空,無(wú)法刪除！");returnqu;}

q=qu->front; /q指向隊(duì)首結(jié)點(diǎn)（1）/

qu->front=q->next; /隊(duì)首指針指向下一個(gè)結(jié)點(diǎn)（2）/

free(q); /釋放原隊(duì)首結(jié)點(diǎn)空間/

if(qu->front==NULL)qu->rear=NULL;/隊(duì)列中的惟一結(jié)點(diǎn)被刪除后,隊(duì)列變空（3）/

returnqu;

}算法3.33刪除鏈?zhǔn)疥?duì)列中的隊(duì)首結(jié)點(diǎn)3.1選擇題（1）兩個(gè)有序線性表分別具有n個(gè)元素與m個(gè)元素且n≤m，現(xiàn)將其歸并成一個(gè)有序表，其最少的比較次數(shù)是（）。A．n B．m C．n

?

1 D．m

+

n（2）非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足（）。A．p->next==NULL

B．p==NULL C．p->next==head D．p==headAC（3）在帶頭結(jié)點(diǎn)的單鏈表中查找