c語言鏈表的建立、插入和刪除

《c語言鏈表的建立、插入和刪除》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、數(shù)組作為存放同類數(shù)據(jù)的集合，給我們在程序設(shè)計時帶來很多的方便，增加了靈活性。但數(shù)組也同樣存在一些弊病。如數(shù)組的大小在定義時要事先規(guī)定，不能在程序中進(jìn)行調(diào)整，這樣一來，在程序設(shè)計中針對不同問題有時需要30個大小的數(shù)組，有時需要50個數(shù)組的大小，難于統(tǒng)一。我們只能夠根據(jù)可能的最大需求來定義數(shù)組，常常會造成一定存儲空間的浪費。我們希望構(gòu)造動態(tài)的數(shù)組，隨時可以調(diào)整數(shù)組的大小，以滿足不同問題的需要。鏈表就是我們需要的動態(tài)數(shù)組。它是在程序的執(zhí)行過程中根據(jù)需要有數(shù)據(jù)存儲就向系統(tǒng)要求申請存儲空間，決不構(gòu)成對存儲區(qū)的浪

2、費。鏈表是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)之間的相互關(guān)系使鏈表分成三種：單鏈表、循環(huán)鏈表、雙向鏈表，下面將逐一介紹。7.4.1單鏈表圖7-3是單鏈表的結(jié)構(gòu)。單鏈表有一個頭節(jié)點head，指向鏈表在內(nèi)存的首地址。鏈表中的每一個節(jié)點的數(shù)據(jù)類型為結(jié)構(gòu)體類型，節(jié)點有兩個成員：整型成員（實際需要保存的數(shù)據(jù)）和指向下一個結(jié)構(gòu)體類型節(jié)點的指針即下一個節(jié)點的地址（事實上，此單鏈表是用于存放整型數(shù)據(jù)的動態(tài)數(shù)組）。鏈表按此結(jié)構(gòu)對各節(jié)點的訪問需從鏈表的頭找起，后續(xù)節(jié)點的地址由當(dāng)前節(jié)點給出。無論在表中訪問那一個節(jié)點，都需要從鏈表的頭

3、開始，順序向后查找。鏈表的尾節(jié)點由于無后續(xù)節(jié)點，其指針域為空，寫作為NULL。圖7-3還給出這樣一層含義，鏈表中的各節(jié)點在內(nèi)存的存儲地址不是連續(xù)的，其各節(jié)點的地址是在需要時向系統(tǒng)申請分配的，系統(tǒng)根據(jù)內(nèi)存的當(dāng)前情況，既可以連續(xù)分配地址，也可以跳躍式分配地址?？匆幌骆湵砉?jié)點的數(shù)據(jù)結(jié)構(gòu)定義：structnode{intnum;structnode*p;};在鏈表節(jié)點的定義中，除一個整型的成員外，成員p是指向與節(jié)點類型完全相同的指針。在鏈表節(jié)點的數(shù)據(jù)結(jié)構(gòu)中，非常特殊的一點就是結(jié)構(gòu)體內(nèi)的指針域的數(shù)據(jù)類型使用了未

4、定義成功的數(shù)據(jù)類型。這是在C中唯一規(guī)定可以先使用后定義的數(shù)據(jù)結(jié)構(gòu)。?單鏈表的創(chuàng)建過程有以下幾步：1)定義鏈表的數(shù)據(jù)結(jié)構(gòu)。2)創(chuàng)建一個空表。3)利用malloc()函數(shù)向系統(tǒng)申請分配一個節(jié)點。4)將新節(jié)點的指針成員賦值為空。若是空表，將新節(jié)點連接到表頭；若是非空表，將新節(jié)點接到表尾。5)判斷一下是否有后續(xù)節(jié)點要接入鏈表，若有轉(zhuǎn)到3)，否則結(jié)束。?單鏈表的輸出過程有以下幾步1)找到表頭。2)若是非空表，輸出節(jié)點的值成員，是空表則退出。3)跟蹤鏈表的增長，即找到下一個節(jié)點的地址。4)轉(zhuǎn)到2)。[例7-5]創(chuàng)

5、建一個存放正整數(shù)（輸入-999做結(jié)束標(biāo)志）的單鏈表，并打印輸出。#include/包*含malloc()的頭文件*/#includestructnode/*鏈表節(jié)點的結(jié)構(gòu)*/{intnum;structnode*next;};main(){structnode*creat();/*函數(shù)聲明*/voidprint();structnode*head;/*定義頭指針*/head=NULL;/*建一個空表*/head=creat(head);/*創(chuàng)建單鏈表*/print

6、(head);/*打印單鏈表*/}/******************************************/structnode*creat(structnode*head)函/數(shù)*返回的是與節(jié)點相同類型的指針*/{structnode*p1,*p2;p1=p2=(structnode*)malloc(sizeof(structnode));申請/*新節(jié)點*/scanf("%d",&p1->num);/*輸入節(jié)點的值*/p1->next=NULL;/*將新節(jié)點的指針置為空*/while(

7、p1->num>0)/*輸入節(jié)點的數(shù)值大于0*/{if(head==NULL)head=p1;/*空表，接入表頭*/elsep2->next=p1;/*非空表，接到表尾*/p2=p1;p1=(structnode*)malloc(sizeof(structnode));申/請*下一個新節(jié)點*/scanf("%d",&p1->num);/*輸入節(jié)點的值*/}returnhead;/*返回鏈表的頭指針*/}/*******************************************/voidp

8、rint(structnode*head)輸/*出以head為頭的鏈表各節(jié)點的值*/{structnode*temp;temp=head;/*取得鏈表的頭指針*/while(temp!=NULL)/*只要是非空表*/{printf("%6d",temp->num);/*輸出鏈表節(jié)點的值*/temp=temp->next;/*跟蹤鏈表增長*/}}在鏈表的創(chuàng)建過程中，鏈表的頭指針是非常重要的參數(shù)。因為對鏈表的輸出和查找都要從鏈表的頭開始，所以鏈表創(chuàng)建成功后，