鏈表的C語言實現(xiàn)

1、鏈表的C語言實現(xiàn)分類：計算機學(xué)習(xí)2006.12.2909:06作者：ybxycy|評論：0|閱讀：652數(shù)組作為存放同類數(shù)據(jù)的集合，給我們在程序設(shè)計時帶來很多的方便，增加了靈活性。但數(shù)組也同樣存在一些弊病。如數(shù)組的大小在定義時要事先規(guī)定，不能在程序中進行調(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)成對

2、存儲區(qū)的浪費。鏈表是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，其數(shù)據(jù)之間的相互關(guān)系使鏈表分成三種：單鏈表、循環(huán)鏈表、雙向鏈表，下面將逐一介紹。7.4.1單鏈表單鏈表有一個頭節(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é)點的地址由當前節(jié)點給出。無論在表中訪問那一個節(jié)點，都需要從鏈表的頭開始，順序向后查找。鏈表的尾節(jié)點由于無后續(xù)節(jié)點，其搟L域為空，寫作為NULL。圖7-3還給出這樣一層含義，鏈

3、表中的各節(jié)點在內(nèi)存的存儲地址不是連續(xù)的，其各節(jié)點的地址是在需要時向系統(tǒng)申請分配的，系統(tǒng)根據(jù)內(nèi)存的當前情況，既可以連續(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ù)類型使用了未定義成功的數(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 ）

4、將新節(jié)點的指針成員賦值為空。若是空表，將新節(jié)點連接到表頭；若是非空表，將新節(jié)點接到表尾。5 ）判斷一下是否有后續(xù)節(jié)點要接入鏈表，若有轉(zhuǎn)到3）,否則結(jié)束。?單鏈表的輸出過程有以下幾步1）找到表頭。2）若是非空表，輸出節(jié)點的值成員，是空表則退出。3）跟蹤鏈表的增長，即找到下一個節(jié)點的地址。4）轉(zhuǎn)到2）。例7-5創(chuàng)建一個存放正整數(shù)（輸入-999做結(jié)束標志）的單鏈表，并打印輸出。#include<stdlib.h>/包*含malloc（）的頭文件*/#include<stdio.h>structnode/*鏈表節(jié)點的結(jié)構(gòu)*/(intnum;structnode*next;)；m

5、ain()(structnode*creat();/*函數(shù)聲明*/voidprint();/*函數(shù)聲明*/structnode*head;/*定義頭指針*/head=NULL;/*建一個空表*/head=creat(head);/*函數(shù)調(diào)用，創(chuàng)建單鏈表*/print(head);/*打印單鏈表*/)/*/指針*/structnode*creat(structnode*head)函/數(shù)*返回的是與節(jié)點相同類型的(structnode*p1,*p2;p1=p2=(structnode*)malloc(sizeof(structnode);申請/*新節(jié)，點*/scanf("%d"

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

7、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)建成功后，要返回一個鏈表頭節(jié)點的地址，即頭運行建寺：二工7-45E71234SG7施表的創(chuàng)建過程用圖示如下：第一出創(chuàng)建空襲*h

8、eadANULL第二步.申請新節(jié)點：p1INULLp2第三步.若是空表*將箭節(jié)點接到表條：head-P11NULLP2P；uE=pl、單鏈表的建立有了動態(tài)內(nèi)存分配的基礎(chǔ)，要實現(xiàn)鏈表就不難了。所謂鏈表，就是用一組任意的存儲單元存儲線性表元素的一種數(shù)據(jù)結(jié)構(gòu)鏈表又分為單鏈表、雙向鏈表和循環(huán)鏈表等。我們先講講單鏈表。所謂單鏈表，是指數(shù)據(jù)接點是單向排列的。一個單鏈表結(jié)點，其結(jié)構(gòu)類型分為兩部分：1、數(shù)據(jù)域：用來存儲本身數(shù)據(jù)指針2、鏈域或稱為指軌域：用來存儲下一個結(jié)點地址或者說指向其直接后繼的例：typedefstructnode(charname20;structnode*link;stud;這樣就定義了

9、一個單鏈表的結(jié)構(gòu)，其中charname20出一個用來存儲姓名的字符型數(shù)組，指針*link是一個用來存儲其直接后繼的指針。定義好了鏈表的結(jié)構(gòu)之后，只要在程序運行的時候愛數(shù)據(jù)域中存儲適當?shù)臄?shù)據(jù)，如有后繼結(jié)點，則把鏈域指向其直接后繼，若沒有，則置為NULLo下面就來看一個建立帶表頭(若未說明，以下所指鏈表均帶表頭)的單鏈表的完整程序。#include<stdio.h>#include<malloc.h>/*包含動態(tài)內(nèi)存分配函數(shù)的頭文件*/#defineN10/*N為人數(shù)*/typedefstructnodecharname20;structnode*link;stud;stu

10、d*creat(intn)/*建立單鏈表的函數(shù)，形參n為人數(shù)*/stud*p,*h,*s;/*h保存表頭結(jié)點的指針，*p指向當前結(jié)點的前一個結(jié)點，*s指向當前結(jié)點*/inti;/*計數(shù)器*/if(h=(stud*)malloc(sizeof(stud)=NULL)/*分配空間并檢測*/printf("不能分配內(nèi)存空間!");exit(0);h->name0='0'/*把表頭結(jié)點的數(shù)據(jù)域置空*/h->link=NULL;/*把表頭結(jié)點的鏈域置空*/p=h;/*p指向表頭結(jié)點*/for(i=0;i<n;i+)if(s=(stud*)malloc

11、(sizeof(stud)=NULL)/*分配新存儲空間并檢測*/printf("不能分配內(nèi)存空間!");exit(0);)p->link=s;/*把s的地址賦給p所指向的結(jié)點的鏈域，這樣就把p和s所指向的結(jié)點連接起來了*/printf("請輸入第%d個人的姓名”,i+1);scanf("%s",s->name);/*在當前結(jié)點s的數(shù)據(jù)域中存儲姓名*/s->link=NULL;p=s;)return(h);)main()intnumber;/*保存人數(shù)的變量*/stud*head;/*head是保存單鏈表的表頭結(jié)點地址的指針*

12、/number=N;head=creat(number);/*把所新建的單鏈表表頭地址賦給head*/)這樣就寫好了一個可以建立包含N個人姓名的單鏈表了。寫動態(tài)內(nèi)存分配的程序應(yīng)注意，請盡量對分配是否成功進行檢測。二、單鏈表的基本運算建立了一個單鏈表之后，如果要進行一些如插入、刪除等操作該怎么辦？所以還須掌握一些單鏈表的基本算法，來實現(xiàn)這些操作。單鏈表的基本運算包括：查找、插入和刪除。下面我們就一一介紹這三種基本運算的算法，并結(jié)合我們建立單鏈表的例子寫出相應(yīng)的程序。1、查找對單鏈表進行查找的思路為：對單鏈表的結(jié)點依次掃描，檢測其數(shù)據(jù)域是否是我們所要查好的值，若是返回該結(jié)點的指針，否則返回NULL

13、o只要知道該單鏈表因為在單鏈表的鏈域中包含了后繼結(jié)點的存儲地址，所以當我們實現(xiàn)的時候,的頭幽即可依次對每個結(jié)點的數(shù)據(jù)域進行檢測。以下是應(yīng)用查找算法的一個例子：#include<stdio.h>#include<malloc.h>#include<string.h>/*包含一些字符串處理函數(shù)的頭文件*/#defineN10typedefstructnodecharname20;structnode*link;stud;stud*creat(intn)/*建立鏈表的函數(shù)*/stud*p,*h,*s;inti;if(h=(stud*)malloc(sizeof(s

14、tud)=NULL)printf("不能分配內(nèi)存空間!");exit(0);h->name0='0'h->link=NULL;p=h；for(i=0;i<n;i+)(if(s=(stud*)malloc(sizeof(stud)=NULL)(printf("不能分配內(nèi)存空間!");exit(0);p->link=s;printf("請輸入第%d個人的姓名”,i+1);scanf("%s",s->name);s->link=NULL;p=s;return(h);stud*se

15、arch(stud*h,char*x)/*查找鏈表的函數(shù)，其中h指針是鏈表的表頭指針，x指針是要查找的人的姓名*/(stud*p;/*當前指針,指向要與所查找的姓名比較的結(jié)點*/char*y;/*保存結(jié)點數(shù)據(jù)域內(nèi)姓名的指針*/p=h->link;while(p!=NULL)(y=p->name;0,即條件成立*/if(strcmp(y,x)=0)/*把數(shù)據(jù)域里的姓名與所要查找的姓名比較，若相同則返回return(p);/*返回與所要查找結(jié)點的地址*/elsep=p->link;)if(p=NULL)printf("沒有查找到該數(shù)據(jù)!");)main()intnumbe