數據結構李云清楊慶紅揭安全人民郵電出版社高等學校精品課程（省級）國家十二五規劃教材高等學校精品課程（省級）國家十二五規劃教材第3章線性表及其鏈式存儲揭安全jieanquan@163.com江西師范大學計算機信息工程學院第3章線性表的鏈式存儲鏈式存儲單鏈表帶頭結點的單鏈表循環單鏈表雙鏈表鏈式棧鏈式隊列

線性表的存儲方式除了常用的順序存儲外，采用鏈式方式存儲也是一種常見的方式。本章將介紹一般線性表的幾種鏈式存儲實現方式，如單鏈表、帶頭結點單鏈表、循環單鏈表、雙鏈表以及特殊的線性表------棧和隊列的鏈式存儲實現。3.1鏈式存儲

數據結構的存儲方式必須體現它的邏輯關系。在鏈式存儲方式下，實現中除存放一個結點的信息外，還需附設指針，用指針體現結點之間的邏輯關系。如果一個結點有多個后繼或多個前驅，那么可以附設相應個數的指針，一個結點附設的指針指向的是這個結點的某個前驅或后繼。

線性結構中，每個結點最多只有一個前驅和一個后繼，這里暫且設定更關心它的后繼，這樣在存儲時除了存放該結點的信息外，只要附設一個指針即可，該指針指向它的后繼結點的存放位置。每個結點的存儲形式是：infonext例，數據的邏輯結構B=（K，R）其中K={k1,k2,k3,k4,k5}R={r}R={<k1,k2>,<k2,k3>,<k3,k4>,<k4,k5>}是一個線性結構，它的鏈式存儲如圖所示100010011002100310041005100610071008存儲地址infonextk41006k21007k11003k5∧k31005

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

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

單鏈表結構的C語言描述如下：///

鏈表實現的頭文件,文件名linklist.h

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

函數功能:建立一個空的單鏈表 //

函數參數:無 //

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

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

{

returnNULL;

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

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

else

{

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

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

}

}

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

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

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

∧head

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

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

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

函數功能:單鏈表第i個結點后插入值為x的新結點

//

函數參數:指向node類型變量的指針head

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

函數返回值:指向node類型變量的指針

//

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

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

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

if(!q&&i!=0)

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

else{

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

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

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

}

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

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

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

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

elser->next=s;

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

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

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

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

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

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

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

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

函數功能:在單鏈表中刪除一個值為x的結點 //

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

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

文件名:slnklist.c,函數名: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的前驅結點/

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

head=head->next; /刪除(1)/elsepre->next=p->next;free(p);returnhead;}算法3.5在單鏈表中刪除一個值為x的結點鏈式存儲的插入和刪除操作比順序存儲方便，但不能隨機訪問某個結點！3.3帶頭結點單鏈表

3.3.1帶頭結點單鏈表

帶頭結點單鏈表見下圖所示：數據2數據1數據3headhead(A)空表(B)非空表^^3.3.2帶頭結點單鏈表的實現

一般的單鏈表中，第一個結點由head指示，而在帶頭結點單鏈表中，head指示的是所謂的頭結點，它不是存儲數據結構中的實際結點，第一個實際的結點是head->next指示的。在帶頭結點單鏈表的操作實現時要注意這一點。

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

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

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

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

else

{

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

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

}

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

函數功能:在帶頭結點的單鏈表中查找第i個結點地址 //

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

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

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

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

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

{

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

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

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

帶頭結點的單鏈表的插入操作的具體實現見算法3.9。

///

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

//

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

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

文件名:hlnklist.c,函數名:insert() ///nodeinsert(nodehead,datatypex,inti){nodep,q;q=find(head,i); /查找帶頭結點的單鏈表中的第i個結點/

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

if(!q) /沒有找到/

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

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

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

∧

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

(1)(1)

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

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

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

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

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

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

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

returnhead;

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

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;循環結束時，將s結點加在pre與q所指示的結點之間！

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;算法設計題：多相式相加問題:A(x)=7+3x+9x8+5x17B(x)=8x+22x7-9x8∧A703198517∧B81227-98C70111227∧5173.4循環單鏈表

3.4.1循環單鏈表head

循環單鏈表類型的描述（略）3.4.2循環單鏈表的實現

單鏈表中某個結點p是表中最后一個結點的特征是p->next==NULL。對于一個循環單鏈表，若首指針為head，表中的某個結點p是最后一個結點的特征應該是p->next==head。

循環單鏈表的頭文件和單鏈表的相同。建立一個空的循環單鏈表

///

函數功能:建立一個空的循環單鏈表 //

函數參數:無 //

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

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

{

returnNULL;

}算法3.11建立一個空的循環單鏈表

///

函數功能:獲得循環單鏈表的最后一個結點的存儲地址 //

函數參數:指向node類型變量的指針變量head //

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

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

p=NULL;

else

{

p=head; /從第一個結點開始/

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

p=p->next; /繼續向后/

}returnp;}算法3.12獲得循環單鏈表的最后一個結點的存儲地址///

函數功能:輸出循環單鏈表中各個結點的值 //

函數參數:指向node類型變量的指針變量head //

函數返回值:空 //

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

else

{

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

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

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

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

{

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

p=p->next;

}

}

}算法3.13輸出循環單鏈表中各個結點的值///

函數功能:循環單鏈表中查找值為x的結點的存儲地址//

函數參數:指向node類型變量的指針變量head

//datatype類型的變量x

//

函數返回值:指向node類型變量的指針

//

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

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

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

{

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

returnNULL;

}q=head; /q指向循環單鏈表的第一個結點,準備查找/

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

q=q->next; /繼續查找/

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

else

returnNULL;

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

headpx

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

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

函數功能:循環單鏈表第i個結點后插入值為x的新結點

//

函數參數:指向node類型變量的指針變量head

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

//

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

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

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

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

p->info=x; /設置新結點的值/

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

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

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

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

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

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

returnhead;}

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

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

q=head; /準備從表中第一個結點開始查找/

j=1; /計數開始/

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

{

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

找不到指定插入位置,即i的值超過表中結點的個數,則不進行插入/

{

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

free(p);

returnhead;

}

else

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

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

(1)(1)pre

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

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

///

函數功能:在循環單鏈表中刪除一個值為x的結點 /

/

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

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

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

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

{

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

returnhead;

}

q=head; /從第1個結點開始準備查找/

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

{

pre=q;

q=q->next; /pre為q的前驅,繼續查找/

} /循環結束后,pre為q的前驅/

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

{

printf("沒有找到值為%d的結點！",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的前驅結點位置*/

head=head->next;

pre->next=head;

free(q);

}

}

returnhead;

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

3.5.1雙鏈表

前面的各種鏈式表中，一個結點的指針域是指向它的后繼結點的，如果需要找一個結點p的前驅結點，則必須從表首指針開始查找，當某個結點pre的指針域指向的是結點p時，即pre->next==p時，則說明pre是p的前驅結點。如果常常需要知道一個結點的前驅和后繼結點，上述的鏈式表是不適合的。既然單鏈表中每個結點有一個指針域指向它的后繼結點，那自然地想到再增設一個指針域指向它的前驅結點，這就構成了雙鏈表。

雙鏈表的結點包括三個域，一個是存放數據信息的info域，另外兩個是指針域，這里用llink和rlink表示，llink指向它的前驅結點，rlink指向它的后繼結點。雙鏈表的一般情形如圖所示：雙鏈表類型的描述（略！）∧∧head3.5.2雙鏈表的實現

雙鏈表結構的C語言描述如下：///

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

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

函數功能:輸出雙鏈表中各個結點的值 //

函數參數:指向dnode類型變量的指針head //

函數返回值:空 //

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

else

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

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

}

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

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

{

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

returnp;

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

∧head

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

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

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

函數功能:雙鏈表第i個結點后插入值為x的新結點 //

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

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

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

p->info=x; /*設置新結點的值*/

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

{

p->llink=NULL; /*新插入的結點沒有前驅*/

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

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

{

head=p;

}

else

{

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

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

}

returnhead;

}

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

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

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

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

{

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

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

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

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

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

{

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

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

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

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

}

returnhead;

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

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

函數功能:在雙鏈表中刪除一個值為x的結點 //

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

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

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

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

q=head;

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

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

}

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

{

head=head->rlink;

head->llink=NULL;

free(q);returnhead;

}

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

{

free(q);

returnNULL;/雙鏈表置空/

}

else

{

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

{

q->llink->rlink=NULL;

free(q);

returnhead;

}

else

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

{

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

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

free(q);returnhead;}}}算法3.21在雙鏈表中刪除一個值為x的結點3.6鏈式棧

3.6.1鏈式棧

棧的鏈式存儲稱為鏈式棧。鏈式棧就是一個特殊的單鏈表，對于這特殊的單鏈表，它的插入和刪除規定在單鏈表的同一端進行。鏈式棧的棧頂指針一般用top表示，鏈式棧如下圖所示。∧top3.6.2鏈式棧的實現

///

函數功能:讀鏈式棧的棧頂結點值 //

函數參數:指向node類型變量的指針top //

函數返回值:datatype類型的變量 //

文件名:lnkstack.c,函數名:read() ///datatyperead(nodetop){if(!top){printf("\n鏈式棧是空的!");exit(1);}

return(top->info);} /*本函數可以調用empty()函數*/

算法3.24取得鏈式棧的棧頂結點值///

函數功能:輸出鏈式棧中各個結點的值 //

函數參數:指向node類型變量的指針top //

函數返回值:空 //

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

p=top;printf("\n");if(!p)printf("\n鏈式棧是空的!");

while(p){printf("%5d",p->info);p=p->next;}}算法3.25輸出鏈式棧中各個結點的值∧xtopp(1)p->next=top;

鏈式棧插入操作鏈式棧進棧操作(1)∧xtopp

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

鏈式棧插入操作(2)top=p;鏈式棧進棧操作向鏈式棧中插入一個值為x的結點

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

p->info=x; /設置新結點的值/

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

top=p;

/插入（2）/

returntop;

}算法3.26向鏈式棧中插入一個值為x的結點∧top(1)q=top;

鏈式棧刪除操作q鏈式棧出棧操作(2)top=top->next;(3)free(q)刪除鏈式棧的棧頂結點

nodepop(nodetop){nodeq;if(!top){printf("\n鏈式棧是空的!");returnNULL;}

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

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

free(q);

returntop;

}算法3.27刪除鏈式棧的棧頂結點3.7鏈式隊列

3.7.1鏈式隊列

隊列的鏈式存儲稱為鏈式隊列。鏈式隊列就是一個特殊的單鏈表，對于這種特殊的單鏈表，它的插入和刪除規定在單鏈表的不同端進行。鏈式隊列的隊首和隊尾指針分別用front和rear表示，鏈式隊列如下圖所示。∧∧qufrontrear(a)空的鏈式隊列∧qufrontrear(b)非空的鏈式隊列3.7.2鏈式隊列的實現

鏈式隊列的結點定義和單鏈表一樣。隊列必須有隊首和隊尾指針，因此增加定義一個結構類型，其中的兩個域分別為隊首和隊尾指針。其定義如下：typedefstruct{nodefront,rear;/定義隊首與隊尾指針/

}queue;建立一個空的鏈式隊列

queueinit()/建立一個空的鏈式隊列/

{

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

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

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

returnqu;

}算法3.28建立一個空的鏈式隊列取得鏈式隊列的隊首結點值

///

函數功能:取得鏈式隊列的隊首結點值 //

函數參數:queue類型的變量qu //

函數返回值:datatype類型 //

文件名:lnkqueue.c,函數名:read() ///datatyperead(queuequ){if(!qu.front){printf("\n鏈式隊列是空的!");exit(1);}

return(qu.front->info);

}算法3.31取得鏈式隊列的隊首結點值鏈式隊列的插入過程圖示見下圖：x∧pqufrontrearqu->front=qu->rear=p;(a)向空鏈式隊列中插入值為x的新結點鏈式隊列的插入過程圖示見下圖：x∧p(1)qu->rear->next=p;(b)在非空鏈式隊列中插入值為x的新結點qufrontrear(2)qu->rear=p;∧向鏈式隊列中插入一個值為x的結點

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

p->info=x; /設置新結點的值/

p->next=NULL;

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

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

else

{

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

qu->rear=p;

}

returnqu;

}算法3.32向鏈式隊列中插入一個值為x的結點鏈式隊列的刪除過程圖示見下圖：∧qqufrontrear(1)q=qu->front;(2)qu->front=q->next;(3)qu->rear=NULL;(a)鏈式隊列刪除操作（隊列中只有一個結點）鏈式隊列的刪除過程圖示見下圖：

∧qufrontrear(b)鏈式隊列刪除操作（隊列中不只一個結點）q(1)q=qu->front;(2)qu->front=q->next;刪除鏈式隊列中隊首結點

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

{

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

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

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

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

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

returnqu;

}算法3.33刪除鏈式隊列中的隊首結點3.1選擇題（1）兩個有序線性表分別具有n個元素與m個元素且n≤m，現將其歸并成一個有序表，其最少的比較次數是（）。A．n B．m C．n

?

1 D．m

+

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

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