上傳人：6***

認(rèn)證信息

認(rèn)證類型：個人認(rèn)證

認(rèn)證主體：李**（實名認(rèn)證）

IP屬地：湖北

IP屬地：湖北 上傳時間：2023-02-04 格式：PPT 頁數(shù)：123 大小：1.77MB 積分：28 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)李云清楊慶紅揭安全人民郵電出版社高等學(xué)校精品課程（省級）國家十二五規(guī)劃教材高等學(xué)校精品課程（省級）國家十二五規(guī)劃教材第3章線性表及其鏈?zhǔn)酱鎯野踩玧ieanquan@163.com江西師范大學(xué)計算機(jī)信息工程學(xué)院第3章線性表的鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯捂湵韼ь^結(jié)點的單鏈表循環(huán)單鏈表雙鏈表鏈?zhǔn)綏ｆ準(zhǔn)疥犃?/p>

線性表的存儲方式除了常用的順序存儲外，采用鏈?zhǔn)椒绞酱鎯σ彩且环N常見的方式。本章將介紹一般線性表的幾種鏈?zhǔn)酱鎯崿F(xiàn)方式，如單鏈表、帶頭結(jié)點單鏈表、循環(huán)單鏈表、雙鏈表以及特殊的線性表------棧和隊列的鏈?zhǔn)酱鎯崿F(xiàn)。3.1鏈?zhǔn)酱鎯?/p>

數(shù)據(jù)結(jié)構(gòu)的存儲方式必須體現(xiàn)它的邏輯關(guān)系。在鏈?zhǔn)酱鎯Ψ绞较拢瑢崿F(xiàn)中除存放一個結(jié)點的信息外，還需附設(shè)指針，用指針體現(xiàn)結(jié)點之間的邏輯關(guān)系。如果一個結(jié)點有多個后繼或多個前驅(qū)，那么可以附設(shè)相應(yīng)個數(shù)的指針，一個結(jié)點附設(shè)的指針指向的是這個結(jié)點的某個前驅(qū)或后繼。

線性結(jié)構(gòu)中，每個結(jié)點最多只有一個前驅(qū)和一個后繼，這里暫且設(shè)定更關(guān)心它的后繼，這樣在存儲時除了存放該結(jié)點的信息外，只要附設(shè)一個指針即可，該指針指向它的后繼結(jié)點的存放位置。每個結(jié)點的存儲形式是：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>}是一個線性結(jié)構(gòu)，它的鏈?zhǔn)酱鎯θ鐖D所示100010011002100310041005100610071008存儲地址infonextk41006k21007k11003k5∧k31005

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

單鏈表是線性表鏈?zhǔn)酱鎯Φ囊环N形式，其中的結(jié)點一般含有兩個域，一個是存放數(shù)據(jù)信息的info域，另一個是指向該結(jié)點的后繼結(jié)點的存放地址的指針域next。一個單鏈表必須有一個首指針指向單鏈表中的第一個結(jié)點。數(shù)據(jù)1指針◎數(shù)據(jù)2指針◎數(shù)據(jù)3指針◎數(shù)據(jù)域指針域…節(jié)點直觀化的描述方法：單鏈表是由表頭唯一確定，因此單鏈表可以用頭指針的名字來命名。例如：若頭指針名是head，則把鏈表稱為表head。head(a)非空表head=NULL(b)空表3.2.2單鏈表的實現(xiàn)

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

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

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

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

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

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

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

{

returnNULL;

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

voiddisplay(nodehead){nodep;p=head;if(!p)printf("\n單鏈表是空的！");

else

{

printf("\n單鏈表各個結(jié)點的值為:\n");

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

}

}

算法3.2輸出單鏈表中各個結(jié)點的值在單鏈表中查找第i個結(jié)點

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

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

∧head

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

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

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

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

//

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

//datatype類型變量x,int型變量I //

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

//

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

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

q=find(head,i); /查找第i個結(jié)點/

if(!q&&i!=0)

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

else{

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

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

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

}

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

returnhead;}算法3.4在單鏈表中第i個結(jié)點后插入一個值為x的新結(jié)點1、申請空間s=malloc(...)2、填入數(shù)據(jù)域值s->info=ch;單鏈表應(yīng)用-----建立單鏈表方法一：堆棧方式建立單鏈表（頭插法）數(shù)據(jù)1^head數(shù)據(jù)2s數(shù)據(jù)33、新結(jié)點鏈入表頭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、申請空間s=malloc()2、填入數(shù)據(jù)域值s->info=ch;3、新結(jié)點鏈入表尾r->next=s;4、修改表尾指針r=s;方法二：隊列方式建立單鏈表（尾插法）數(shù)據(jù)2head數(shù)據(jù)1s數(shù)據(jù)3r方法二：隊列方式建立單鏈表（尾插法）數(shù)據(jù)2head數(shù)據(jù)1s數(shù)據(jù)3r關(guān)鍵一步：

設(shè)置一個鏈尾指針r，每次將新的結(jié)點鏈在r的后面，使其成為新的表尾結(jié)點。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é)點*/

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

elser->next=s;

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

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

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

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

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

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

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

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

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

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

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

文件名:slnklist.c,函數(shù)名:dele() ///nodedele(nodehead,datatypex){nodepre=NULL,p;if(!head){printf("單鏈表是空的！");returnhead;}

p=head;

while(p&&p->info!=x) /沒有找到并且沒有找完/

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

if(!pre&&p->info==x) /要刪除的是第一個結(jié)點/

head=head->next; /刪除(1)/elsepre->next=p->next;free(p);returnhead;}算法3.5在單鏈表中刪除一個值為x的結(jié)點鏈?zhǔn)酱鎯Φ牟迦牒蛣h除操作比順序存儲方便，但不能隨機(jī)訪問某個結(jié)點！3.3帶頭結(jié)點單鏈表

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

帶頭結(jié)點單鏈表見下圖所示：數(shù)據(jù)2數(shù)據(jù)1數(shù)據(jù)3headhead(A)空表(B)非空表^^3.3.2帶頭結(jié)點單鏈表的實現(xiàn)

一般的單鏈表中，第一個結(jié)點由head指示，而在帶頭結(jié)點單鏈表中，head指示的是所謂的頭結(jié)點，它不是存儲數(shù)據(jù)結(jié)構(gòu)中的實際結(jié)點，第一個實際的結(jié)點是head->next指示的。在帶頭結(jié)點單鏈表的操作實現(xiàn)時要注意這一點。

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

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

voiddisplay(nodehead){nodep;p=head->next; /從第一個（實際）結(jié)點開始/

if(!p)printf("\n帶頭結(jié)點的單鏈表是空的!");

else

{

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

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

}

}算法3.7輸出帶頭結(jié)點的單鏈表中各個結(jié)點的值///

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

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

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

文件名hlnklist.c,函數(shù)名find() ///nodefind(nodehead,inti){intj=0;nodep=head;if(i<0){printf("\n帶頭結(jié)點的單鏈表中不存在第%d個結(jié)點！",i);returnNULL;}

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

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

{

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

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

(2)(1)(2)×qp(b)在q所指的結(jié)點后插入一個p所指的值為x的新結(jié)點(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é)點單鏈表的最前面插入一個值為x的新結(jié)點q

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

///

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

//

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

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

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

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

if(!q) /沒有找到/

{printf("\n帶頭結(jié)點的單鏈表中不存在第%d個結(jié)點！不能插入%d！",i,x);returnhead;}

p=(node)malloc(sizeof(node)); /為準(zhǔn)備插入的新結(jié)點分配空間/

p->info=x; /為新結(jié)點設(shè)置值x/p->next=q->next; /插入(1)/q->next=p; /插入(2),當(dāng)i=0時,由于q指向的是頭結(jié)點,本語句等價于head>next=p/returnhead;}算法3.9在帶頭結(jié)點的單鏈表中第i個結(jié)點后插入一個值為x的新結(jié)點帶頭結(jié)點單鏈表的刪除過程見圖3.8。

∧

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

(1)(1)

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

nodedele(nodehead,datatypex){nodepre=head,q; /首先pre指向頭結(jié)點/

q=head->next; /q從帶頭結(jié)點的第一個實際結(jié)點開始找值為x的結(jié)點/

while(q&&q->info!=x) /沒有查找完并且還沒有找到/

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

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

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

returnhead;

}算法3.10在帶頭結(jié)點的單鏈表中刪除一個值為x的結(jié)點算法設(shè)計題：1、用單鏈表作為存儲結(jié)構(gòu)，實現(xiàn)線性表（a0,a1,…,an-1）就地逆置的操作，所謂就地指輔助空間應(yīng)為O(1)。2、設(shè)單鏈表L是一個遞減有序表，試寫一算法將X插入其中后仍保持L的有序性。3、寫一算法將單鏈表中值重復(fù)的結(jié)點刪除，使所得的結(jié)果表中各結(jié)點值均不相同。4、設(shè)計一個算法，對單鏈表按結(jié)點值從小到大對結(jié)點進(jìn)行排序。算法設(shè)計題：5、設(shè)計一個算法，將兩個有序單鏈表合并成一個有序的單鏈表。6、設(shè)計一個算法，求兩個單鏈表表示的集合的交集，并將結(jié)果用一個新的單鏈表保存并返回。

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é)束時，將s結(jié)點加在pre與q所指示的結(jié)點之間！

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è)計題：多相式相加問題: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)單鏈表類型的描述（略）3.4.2循環(huán)單鏈表的實現(xiàn)

單鏈表中某個結(jié)點p是表中最后一個結(jié)點的特征是p->next==NULL。對于一個循環(huán)單鏈表，若首指針為head，表中的某個結(jié)點p是最后一個結(jié)點的特征應(yīng)該是p->next==head。

循環(huán)單鏈表的頭文件和單鏈表的相同。建立一個空的循環(huán)單鏈表

///

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

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

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

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

{

returnNULL;

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

///

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

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

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

文件名:clnklist.c,函數(shù)名:rear() ///noderear(nodehead){nodep;if(!head) /循環(huán)單鏈表為空/

p=NULL;

else

{

p=head; /從第一個結(jié)點開始/

while(p->next!=head) /沒有到達(dá)最后一個結(jié)點/

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

}returnp;}算法3.12獲得循環(huán)單鏈表的最后一個結(jié)點的存儲地址///

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

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

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

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

else

{

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

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

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

while(p!=head) /沒有回到第一個結(jié)點/

{

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

p=p->next;

}

}

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

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

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

//datatype類型的變量x

//

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

//

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

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

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

{

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

returnNULL;

}q=head; /q指向循環(huán)單鏈表的第一個結(jié)點,準(zhǔn)備查找/

while(q->next!=head&&q->info!=x) /沒有查找到并且沒有查找完整個表/

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

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

else

returnNULL;

}算法3.14在循環(huán)單鏈表中查找一個值為x的結(jié)點循環(huán)單鏈表的插入過程如圖：

headpx

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

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

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

//

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

//datatype類型的變量x,int類型的變量I

//

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

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

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

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

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

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

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

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

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

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

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

returnhead;}

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

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

q=head; /準(zhǔn)備從表中第一個結(jié)點開始查找/

j=1; /計數(shù)開始/

while(i!=j&&q->next!=head) /沒有找到并且沒有找遍整個表/

{

q=q->next;j++; /繼續(xù)查找,計數(shù)器加1/}if(i!=j) /

找不到指定插入位置,即i的值超過表中結(jié)點的個數(shù),則不進(jìn)行插入/

{

printf("\n表中不存在第%d個結(jié)點,無法進(jìn)行插入!\n",i);

free(p);

returnhead;

}

else

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

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

(1)(1)pre

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

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

///

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

/

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

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

文件名:clnklist.c,函數(shù)名:dele() ///nodedele(nodehead,datatypex){nodepre=NULL,q; /q用于查找值為x的結(jié)點,pre指向q的前驅(qū)結(jié)點/

if(!head) /表為空,則無法做刪除操作/

{

printf("\n循環(huán)單鏈表為空,無法做刪除操作！");

returnhead;

}

q=head; /從第1個結(jié)點開始準(zhǔn)備查找/

while(q->next!=head&&q->info!=x) /沒有找遍整個表并且沒有找到/

{

pre=q;

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

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

if(q->info!=x) /沒找到/

{

printf("沒有找到值為%d的結(jié)點！",x);

}

else /找到了,下面要刪除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é)點位置*/

head=head->next;

pre->next=head;

free(q);

}

}

returnhead;

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

3.5.1雙鏈表

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

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

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

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

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

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

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

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

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

else

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

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

}

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

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

{

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

returnp;

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

∧head

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

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

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

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

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

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

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

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

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

{

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

p->rlink=head; /*新插入的結(jié)點的后繼是原來雙鏈表中的第一個結(jié)點*/

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

{

head=p;

}

else

{

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

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

}

returnhead;

}

q=find(head,i); /*查找第i個結(jié)點*/

if(!q) /*第i個結(jié)點不存在*/

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

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

{

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

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

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

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

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

{

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

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

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

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

}

returnhead;

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

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

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

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

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

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

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

q=head;

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

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

}

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

{

head=head->rlink;

head->llink=NULL;

free(q);returnhead;

}

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

{

free(q);

returnNULL;/雙鏈表置空/

}

else

{

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

{

q->llink->rlink=NULL;

free(q);

returnhead;

}

else

/q是有2個以上結(jié)點的雙鏈表中的一個非開始、也非終端結(jié)點/

{

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

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

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

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

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

///

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

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

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

文件名: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é)點值///

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

函數(shù)參數(shù):指向node類型變量的指針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)綏Ｖ懈鱾€結(jié)點的值∧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)綏Ｖ胁迦胍粋€值為x的結(jié)點

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

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

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

top=p;

/插入（2）/

returntop;

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

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

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

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

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

free(q);

returntop;

}算法3.27刪除鏈?zhǔn)綏５臈ｍ斀Y(jié)點3.7鏈?zhǔn)疥犃?/p>

3.7.1鏈?zhǔn)疥犃?/p>

隊列的鏈?zhǔn)酱鎯ΨQ為鏈?zhǔn)疥犃小ｆ準(zhǔn)疥犃芯褪且粋€特殊的單鏈表，對于這種特殊的單鏈表，它的插入和刪除規(guī)定在單鏈表的不同端進(jìn)行。鏈?zhǔn)疥犃械年犑缀完犖仓羔樂謩e用front和rear表示，鏈?zhǔn)疥犃腥缦聢D所示。∧∧qufrontrear(a)空的鏈?zhǔn)疥犃小膓ufrontrear(b)非空的鏈?zhǔn)疥犃?.7.2鏈?zhǔn)疥犃械膶崿F(xiàn)

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

}queue;建立一個空的鏈?zhǔn)疥犃?/p>

queueinit()/建立一個空的鏈?zhǔn)疥犃?

{

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

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

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

returnqu;

}算法3.28建立一個空的鏈?zhǔn)疥犃腥〉面準(zhǔn)疥犃械年犑捉Y(jié)點值

///

函數(shù)功能:取得鏈?zhǔn)疥犃械年犑捉Y(jié)點值 //

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

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

文件名:lnkqueue.c,函數(shù)名:read() ///datatyperead(queuequ){if(!qu.front){printf("\n鏈?zhǔn)疥犃惺强盏?");exit(1);}

return(qu.front->info);

}算法3.31取得鏈?zhǔn)疥犃械年犑捉Y(jié)點值鏈?zhǔn)疥犃械牟迦脒^程圖示見下圖：x∧pqufrontrearqu->front=qu->rear=p;(a)向空鏈?zhǔn)疥犃兄胁迦胫禐閤的新結(jié)點鏈?zhǔn)疥犃械牟迦脒^程圖示見下圖：x∧p(1)qu->rear->next=p;(b)在非空鏈?zhǔn)疥犃兄胁迦胫禐閤的新結(jié)點qufrontrear(2)qu->rear=p;∧向鏈?zhǔn)疥犃兄胁迦胍粋€值為x的結(jié)點

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

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

p->next=NULL;

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

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

else

{

qu->rear->next=p; /隊尾插入/

qu->rear=p;

}

returnqu;

}算法3.32向鏈?zhǔn)疥犃兄胁迦胍粋€值為x的結(jié)點鏈?zhǔn)疥犃械膭h除過程圖示見下圖：∧qqufrontrear(1)q=qu->front;(2)qu->front=q->next;(3)qu->rear=NULL;(a)鏈?zhǔn)疥犃袆h除操作（隊列中只有一個結(jié)點）鏈?zhǔn)疥犃械膭h除過程圖示見下圖：

∧qufrontrear(b)鏈?zhǔn)疥犃袆h除操作（隊列中不只一個結(jié)點）q(1)q=qu->front;(2)qu->front=q->next;刪除鏈?zhǔn)疥犃兄嘘犑捉Y(jié)點

queuedele(queuequ) /刪除隊首結(jié)點/

{

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

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

qu->front=q->next; /隊首指針指向下一個結(jié)點（2）/

free(q); /釋放原隊首結(jié)點空間/

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

returnqu;

}算法3.33刪除鏈?zhǔn)疥犃兄械年犑捉Y(jié)點3.1選擇題（1）兩個有序線性表分別具有n個元素與m個元素且n≤m，現(xiàn)將其歸并成一個有序表，其最少的比較次數(shù)是（）。A．n B．m C．n

?

1 D．m

+

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

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