powerpoint 演示文稿 - 鏈表的基本概念

9.4鏈表9.4.1鏈表的基本概念例：在鐵路的中轉(zhuǎn)站，有10個(gè)集裝箱待運(yùn)。每個(gè)集裝箱上有如下五項(xiàng)說(shuō)明：①箱號(hào) （比如AZ81920）②貨物名稱(chēng) （比如蘋(píng)果）③重量 （比如10噸）④發(fā)貨地點(diǎn) （比如山東）⑤到貨地點(diǎn) （比如廣東）12如何在程序中來(lái)描述該列火車(chē)？如何來(lái)描述火車(chē)頭？如何來(lái)描述每一個(gè)集裝箱？如何來(lái)描述各節(jié)車(chē)廂之間的鏈接關(guān)系？3DX11089玩具5噸從上海到深圳

CY20011電飯鍋8噸從上海到湖南

AZ81920花生10噸從山東到廣東

…h(huán)ead結(jié)點(diǎn)2需要引入一種新的數(shù)據(jù)結(jié)構(gòu)：鏈表。鏈表中的每一個(gè)元素稱(chēng)為一個(gè)“結(jié)點(diǎn)”，每個(gè)結(jié)點(diǎn)都應(yīng)該包括兩部分：一為用戶(hù)需要使用的實(shí)際數(shù)據(jù)；二為下一個(gè)結(jié)點(diǎn)的起始地址。另外，鏈表還有一個(gè)頭指針head，指向鏈表的首結(jié)點(diǎn)。結(jié)點(diǎn)1結(jié)點(diǎn)34如何來(lái)實(shí)現(xiàn)鏈表結(jié)構(gòu)？顯然要用到結(jié)構(gòu)體數(shù)據(jù)類(lèi)型。定義如下的結(jié)構(gòu)體類(lèi)型：structTrain_tagstructTrain_tag*next;charNum[8];charName[10];intWeight;charFrom[20];charTo[20];數(shù)據(jù)域指針域59.4.2對(duì)鏈表的操作1.創(chuàng)建靜態(tài)鏈表在程序中定義一組結(jié)構(gòu)體變量或一個(gè)結(jié)構(gòu)體數(shù)組，然后用它們來(lái)作為鏈表的結(jié)點(diǎn)，把它們鏈接成一個(gè)鏈表的形式。優(yōu)點(diǎn)：不必去關(guān)心內(nèi)存的分配與釋放。缺點(diǎn)：需要事先知道鏈表結(jié)點(diǎn)的個(gè)數(shù)。6DX11089玩具5噸從上海到深圳

CY20011電飯鍋8噸從上海到湖南

AZ81920花生10噸從山東到廣東NULL…h(huán)ead結(jié)點(diǎn)2結(jié)點(diǎn)1結(jié)點(diǎn)10structTrain_tag{char Num[8]; /*集裝箱編號(hào)*/

char Name[10]; /*貨物名稱(chēng)*/

int Weight; /*貨物重量*/

char From[20]; /*發(fā)貨地點(diǎn)*/

char To[20]; /*到貨地點(diǎn)*/

structTrain_tag*next; /*指向下一結(jié)點(diǎn)*/}array[10],*head;7voidCreate(){inti;head=&array[0]; /*鏈表的頭指針*/

for(i=0;i<10;i++){

輸入array[i]的各個(gè)成員變量的值；

if(i<9)array[i].next=&array[i+1];elsearray[i].next=NULL;}}思路：用第i(0-9)個(gè)數(shù)組元素來(lái)描述第i+1個(gè)鏈表結(jié)點(diǎn)8DX11089玩具5噸從上海到深圳

CY20011電飯鍋8噸從上海到湖南

AZ81920花生10噸從山東到廣東NULL…h(huán)ead結(jié)點(diǎn)2結(jié)點(diǎn)1結(jié)點(diǎn)10array[0]array[1]array[9]92.創(chuàng)建動(dòng)態(tài)鏈表在程序當(dāng)中為鏈表的每一個(gè)結(jié)點(diǎn)動(dòng)態(tài)地分配相應(yīng)的存儲(chǔ)空間，并把它們鏈接成一個(gè)鏈表的形式。優(yōu)點(diǎn)：按需分配，鏈表的長(zhǎng)度可動(dòng)態(tài)增長(zhǎng)。缺點(diǎn)：由程序員來(lái)進(jìn)行內(nèi)存的分配與釋放。10【例】創(chuàng)建一個(gè)鏈表，并輸入每一個(gè)結(jié)點(diǎn)的各種描述信息（集裝箱編號(hào)、貨物名稱(chēng)、貨物重量、發(fā)貨地點(diǎn)、到貨地點(diǎn)等），直到用戶(hù)輸入的貨物重量等于0，表示鏈表結(jié)束。11structTrain_tag{char Num[8]; /*集裝箱編號(hào)*/

char Name[10]; /*貨物名稱(chēng)*/

int Weight; /*貨物重量*/

char From[20]; /*發(fā)貨地點(diǎn)*/

char To[20]; /*到貨地點(diǎn)*/

structTrain_tag*next; /*指向下一結(jié)點(diǎn)*/};structTrain_tag

*head,*p,*q;12①只要用戶(hù)輸入的Weight不為0，就要構(gòu)建鏈表?；舅悸肥菍⒁粋€(gè)一個(gè)的結(jié)點(diǎn)添加至鏈表中。首先用指針p來(lái)申請(qǐng)一個(gè)結(jié)構(gòu)體變量的內(nèi)存空間，并且裝入用戶(hù)輸入的各種描述信息，然后將指針q和head都指向它。如下圖：創(chuàng)建鏈表的過(guò)程可歸納為如下三個(gè)步驟pqheadDX11089玩具5噸從上海到深圳圖鏈表的第一個(gè)結(jié)點(diǎn)建成13②后繼結(jié)點(diǎn)的創(chuàng)建：如果用戶(hù)輸入的Weight又不為0，就要構(gòu)建鏈表的第二個(gè)結(jié)點(diǎn)。首先用指針p來(lái)申請(qǐng)一個(gè)結(jié)構(gòu)體變量的內(nèi)存空間，并且裝入用戶(hù)輸入的各種描述信息，然后要執(zhí)行q->next=p，把第一個(gè)結(jié)點(diǎn)的next指針去指向它，從而建立兩個(gè)結(jié)點(diǎn)之間的鏈接關(guān)系。最后再把q指向新的結(jié)點(diǎn)。如下圖：headqpDX11089玩具5噸從上海到深圳圖鏈表的第二個(gè)結(jié)點(diǎn)建成CY20011電飯鍋8噸從上海到湖南q14headqDX11089玩具5噸從上海到深圳第三個(gè)結(jié)點(diǎn)加入鏈表的過(guò)程：CY20011電飯鍋8噸從上海到湖南qpCZ21026蘋(píng)果8噸從山東到福建15③鏈表創(chuàng)建過(guò)程的結(jié)束：如果用戶(hù)輸入的Weight等于0，意味著鏈表創(chuàng)建過(guò)程的結(jié)束，此時(shí)指針q所指向的就是鏈表的最后一個(gè)結(jié)點(diǎn)，所以要把該結(jié)點(diǎn)的next指針賦值為NULL，即執(zhí)行q->next=NULL，表示這里已是鏈尾，后面不會(huì)再連結(jié)點(diǎn)。如下圖：headDX11089玩具5噸從上海到深圳CY20011電飯鍋8噸從上海到湖南qNULLAZ81920花生10噸從山東到廣東16voidCreate(){intWeight;head=p=q=NULL;while(1){printf("輸入貨物重量：");

scanf("%d",&Weight);if(Weight<=0)break;p=malloc(sizeof(structTrain_tag));p->Weight=Weight;

輸入該結(jié)點(diǎn)的其他信息；

if(head==NULL)head=p;//新建的是首結(jié)點(diǎn)

elseq->next=p; //不是首結(jié)點(diǎn)

q=p; //q指向當(dāng)前尾結(jié)點(diǎn)}

if(head!=NULL)q->next=NULL;}173.訪(fǎng)問(wèn)鏈表在創(chuàng)建好一個(gè)鏈表之后，可以依次地訪(fǎng)問(wèn)該鏈表當(dāng)中的各個(gè)結(jié)點(diǎn)的數(shù)據(jù)。voidDisplay(){structTrain_tag*p;p=head;while(p!=NULL){printf("%s,%s,%d,%s,%s\n",p->Num, p->Name,p->Weight,p->From,p->To);p=p->next;}}184.刪除鏈表結(jié)點(diǎn)假設(shè)列車(chē)現(xiàn)在到達(dá)長(zhǎng)沙站，因此需要把到貨地點(diǎn)為湖南的車(chē)廂（假設(shè)有且僅有一節(jié)），從列車(chē)上摘下來(lái)，然后列車(chē)?yán)^續(xù)向南行駛。這里就需要用到鏈表結(jié)點(diǎn)的刪除技術(shù)。19headDX11089玩具5噸從上海到湖南CY20011電飯鍋8噸從上海到深圳NULLAZ81920花生10噸從山東到廣東情形一、待刪除的是首結(jié)點(diǎn)phead=p->next;20DX11089玩具5噸從上海到深圳CY20011電飯鍋8噸從上海到湖南AZ81920花生10噸從山東到廣東情形二、待刪除的不是首結(jié)點(diǎn)pqq->next=p->next;21voidDelete(){structTrain_tag*p,*q;if(head==NULL){printf("空鏈表");return;}p=head;while((p!=NULL)&&strcmp(p->To,"湖南")){

q=p;p=p->next; //把指針p往后移動(dòng)一個(gè)結(jié)點(diǎn)}

if((p!=NULL)&&!strcmp(p->To,"湖南")){

if(p==head)head=p->next; //刪除的是首結(jié)點(diǎn)

elseq->next=p->next; //刪除的是中間結(jié)點(diǎn)}}225.插入鏈表結(jié)點(diǎn)原則：插入操作不應(yīng)破壞原有鏈接關(guān)系；需要插入的這個(gè)結(jié)點(diǎn)應(yīng)該把它放在合適的位置上，也就是說(shuō)，應(yīng)該有一個(gè)插入位置的查找過(guò)程。233head4710NULL86先看下面一個(gè)簡(jiǎn)單的例子： 已有一個(gè)如圖所示的鏈表。它是按結(jié)點(diǎn)中的貨物重量從小到大排序的?，F(xiàn)在要插入一個(gè)新的結(jié)點(diǎn)，該結(jié)點(diǎn)的貨物重量為7噸。24定義：structTrain_tag*head; //頭指針structTrain_tag*p; //鏈表當(dāng)前結(jié)點(diǎn)structTrain_tag*q; //鏈表上一結(jié)點(diǎn)structTrain_tag*pNode;//待插入的結(jié)點(diǎn)25NULLheadDX11089玩具5噸從上海到湖南pNodehead=pNode;第一種情況：鏈表為空，即head=NULL

待插入的pNode

結(jié)點(diǎn)就是鏈表中的第一個(gè)結(jié)點(diǎn)。26pNode->next=head;head=pNode;第二種情況：

pNode

結(jié)點(diǎn)的Weight值小于等于鏈表首結(jié)點(diǎn)的

Weight值，即 pNode->Weight<=head->Weight

這時(shí)要將pNode

結(jié)點(diǎn)插入到首結(jié)點(diǎn)的前面，即執(zhí)行以下兩條語(yǔ)句：27這種情況如下圖5104NULL15NULLheadpNodepNode->next=head;head=pNode;28第三種情況： 即pNode結(jié)點(diǎn)的Weight要大于首結(jié)點(diǎn)的Weight

值，這時(shí)肯定地說(shuō)pNode結(jié)點(diǎn)要插入到首結(jié)點(diǎn)之 后，但究竟插入到哪里需要先找到正確的位置。 我們?cè)O(shè)指針q和指針p分別指向相鄰的兩個(gè)結(jié)點(diǎn)，

q在前p在后（即q更靠近首結(jié)點(diǎn)）。 首先讓q=head，讓p=head->next，然后讓它們 順序往后移動(dòng)，每次移動(dòng)一個(gè)結(jié)點(diǎn)。當(dāng)著滿(mǎn)足：

q->Weight<pNode->Weight<=p->Weight

時(shí)，pNode就插在q與p之間。2951012NULL15NULLheadpNode移動(dòng)指針：q=p;p=p->next;pqpq插入結(jié)點(diǎn)：pNode->next=p;q->next=pNode;30voidInsert(structTrain_tag*pNode){structTrain_tag*p,*q;//第一種情形，鏈表為空

if(head==NULL){head=pNode;return;

}

//第二種情形，新結(jié)點(diǎn)的Weight小于等于首結(jié)點(diǎn)

if(pNode->Weight<=head->Weight){pNode->next=head;head=pNode;return;

}31//第三種情形，循環(huán)地查找正確的插入位置

q=head;p=head->next;while(p!=NULL){if(pNode->Weight<=p->Weight)break;else{q=p;p=p->next;}}

//將pNode結(jié)點(diǎn)插入在正確的位置(q和p之間)

pNode->next=p;q->next=pNode;}32

while(p!=NULL){if(pNode->Weight<=p->Weight)break;else{q=p;p=p->next;}}如果新結(jié)點(diǎn)的Weight大于所有結(jié)點(diǎn)？在這種情形下，當(dāng)循環(huán)語(yǔ)句結(jié)束后，指針q是指向鏈表的尾結(jié)點(diǎn)，而指針p=NULL。3351017NULL15NULLheadpNodeq插入結(jié)點(diǎn)：pNode->next=p;q->next=pNode;pNULLNULL346.鏈表的釋放對(duì)于靜態(tài)鏈表，它們所占用的內(nèi)存空間是由系統(tǒng)自動(dòng)來(lái)分配和釋放的；對(duì)于動(dòng)態(tài)鏈表，必須由程序員自己來(lái)進(jìn)行內(nèi)存的分配與釋放。35voidDestroy(){structTrain_tag*p,*q;p=head;while(p!=NULL){q=p;p=p->next;free(q);}}headDX11089玩具5噸從上海到深圳CY20011電飯鍋8噸從上海到湖南CZ21026蘋(píng)果8噸從山東到福建pqpqpqhead=NULL;369.4.3環(huán)形鏈表環(huán)形鏈表：一種特殊的鏈表，其尾結(jié)點(diǎn)的next指針，又指向了鏈表的首結(jié)點(diǎn)，從而形成了一個(gè)圓環(huán)。從環(huán)形鏈表的任何一個(gè)結(jié)點(diǎn)出發(fā)，都可以遍歷整個(gè)的鏈表。37學(xué)校給高一（三）班分配了一個(gè)名額，去參加

奧運(yùn)會(huì)的開(kāi)幕式。每個(gè)人都爭(zhēng)著要去，可是名

額只有一個(gè)，怎么辦？班長(zhǎng)想出了一個(gè)辦法，

讓班上的所有同學(xué)圍成一圈，按照順時(shí)針?lè)较?/p>

進(jìn)行編號(hào)。然后隨便選定