鏈表的C語(yǔ)言實(shí)現(xiàn)方法
C語(yǔ)言的應(yīng)用范圍廣泛，具備很強(qiáng)的數(shù)據(jù)處理能力，不僅僅是在軟件開發(fā)上，而且各類科研都需要用到C語(yǔ)言，適于編寫系統(tǒng)軟件，三維，二維圖形和動(dòng)畫，具體應(yīng)用比如單片機(jī)以及嵌入式系統(tǒng)開發(fā)。以下是小編為大家搜索整理鏈表的C語(yǔ)言實(shí)現(xiàn)方法，希望能給大家?guī)韼椭?更多精彩內(nèi)容請(qǐng)及時(shí)關(guān)注我們應(yīng)屆畢業(yè)生考試網(wǎng)!
一、為什么用動(dòng)態(tài)內(nèi)存分配
但我們未學(xué)習(xí)鏈表的時(shí)候，如果要存儲(chǔ)數(shù)量比較多的同類型或同結(jié)構(gòu)的數(shù)據(jù)的時(shí)候，總是使用一個(gè)數(shù)組。比如說我們要存儲(chǔ)一個(gè)班級(jí)學(xué)生的某科分?jǐn)?shù)，總是定義一個(gè)float型(存在0.5分)數(shù)組：
float score[30];
但是，在使用數(shù)組的時(shí)候，總有一個(gè)問題困擾著我們：數(shù)組應(yīng)該有多大?
在很多的情況下，你并不能確定要使用多大的數(shù)組，比如上例，你可能并不知道該班級(jí)的學(xué)生的人數(shù)，那么你就要把數(shù)組定義得足夠大。這樣，你的程序在運(yùn)行時(shí)就申請(qǐng)了固定大小的你認(rèn)為足夠大的內(nèi)存空間。即使你知道該班級(jí)的學(xué)生數(shù)，但是如果因?yàn)槟撤N特殊原因人數(shù)有增加或者減少，你又必須重新去修改程序，擴(kuò)大數(shù)組的存儲(chǔ)范圍。這種分配固定大小的內(nèi)存分配方法稱之為靜態(tài)內(nèi)存分配。但是這種內(nèi)存分配的方法存在比較嚴(yán)重的缺陷，特別是處理某些問題時(shí)：在大多數(shù)情況下會(huì)浪費(fèi)大量的內(nèi)存空間，在少數(shù)情況下，當(dāng)你定義的數(shù)組不夠大時(shí)，可能引起下標(biāo)越界錯(cuò)誤，甚至導(dǎo)致嚴(yán)重后果。
那么有沒有其它的方法來解決這樣的外呢體呢?有，那就是動(dòng)態(tài)內(nèi)存分配。
所謂動(dòng)態(tài)內(nèi)存分配就是指在程序執(zhí)行的過程中動(dòng)態(tài)地分配或者回收存儲(chǔ)空間的分配內(nèi)存的方法。動(dòng)態(tài)內(nèi)存分配不象數(shù)組等靜態(tài)內(nèi)存分配方法那樣需要預(yù)先分配存儲(chǔ)空間，而是由系統(tǒng)根據(jù)程序的需要即時(shí)分配，且分配的大小就是程序要求的大小。從以上動(dòng)、靜態(tài)內(nèi)存分配比較可以知道動(dòng)態(tài)內(nèi)存分配相對(duì)于景泰內(nèi)存分配的特點(diǎn)：
1、不需要預(yù)先分配存儲(chǔ)空間;
2、分配的空間可以根據(jù)程序的需要擴(kuò)大或縮小。
二、如何實(shí)現(xiàn)動(dòng)態(tài)內(nèi)存分配及其管理
要實(shí)現(xiàn)根據(jù)程序的需要?jiǎng)討B(tài)分配存儲(chǔ)空間，就必須用到以下幾個(gè)函數(shù)
1、malloc函數(shù)
malloc函數(shù)的原型為：
void *malloc (unsigned int size)
其作用是在內(nèi)存的動(dòng)態(tài)存儲(chǔ)區(qū)中分配一個(gè)長(zhǎng)度為size的連續(xù)空間。其參數(shù)是一個(gè)無(wú)符號(hào)整形數(shù)，返回值是一個(gè)指向所分配的連續(xù)存儲(chǔ)域的起始地址的指針。還有一點(diǎn)必須注意的是，當(dāng)函數(shù)未能成功分配存儲(chǔ)空間(如內(nèi)存不足)就會(huì)返回一個(gè)NULL指針。所以在調(diào)用該函數(shù)時(shí)應(yīng)該檢測(cè)返回值是否為NULL并執(zhí)行相應(yīng)的操作。
下例是一個(gè)動(dòng)態(tài)分配的程序：
[cpp] view plaincopy
#include "malloc.h"
#include "stdlib.h"
main(void)
{
/*count是一個(gè)計(jì)數(shù)器，array是一個(gè)整型指針，也可以理解為指向一個(gè)整型數(shù)組的首地址*/
int count;
int *array;
array=malloc(10 * sizeof(int));
if(array==NULL)
{
printf("Out of memory!\n");
exit(1);
}
/*給數(shù)組賦值*/
for(count=0;count<10;count++)
{
array[count]=count;
}
/*打印數(shù)組元素*/
for(count=0;count<10;count++)
{
printf("%2d\n",array[count]);
}
}
上例中動(dòng)態(tài)分配了10個(gè)整型存儲(chǔ)區(qū)域，然后進(jìn)行賦值并打印。例中if((array(int *) malloc(10*sizeof(int)))==NULL)語(yǔ)句可以分為以下幾步：
1)分配10個(gè)整型的連續(xù)存儲(chǔ)空間，并返回一個(gè)指向其起始地址的整型指針
2)把此整型指針地址賦給array
3)檢測(cè)返回值是否為NULL
2、free函數(shù)
由于內(nèi)存區(qū)域總是有限的，不能不限制地分配下去，而且一個(gè)程序要盡量節(jié)省資源，所以當(dāng)所分配的內(nèi)存區(qū)域不用時(shí)，就要釋放它，以便其它的變量或者程序使用。這時(shí)我們就要用到free函數(shù)。
其函數(shù)原型是：
void free(void *p)
作用是釋放指針p所指向的內(nèi)存區(qū)。
其參數(shù)p必須是先前調(diào)用malloc函數(shù)或calloc函數(shù)(另一個(gè)動(dòng)態(tài)分配存儲(chǔ)區(qū)域的函數(shù))時(shí)返回的指針。給free函數(shù)傳遞其它的值很可能造成死機(jī)或其它災(zāi)難性的后果。
注意：這里重要的是指針的值，而不是用來申請(qǐng)動(dòng)態(tài)內(nèi)存的指針本身。例：
int *p1,*p2;
p1=malloc(10*sizeof(int));
p2=p1;
……
free(p2) /*或者free(p2)*/
malloc返回值賦給p1，又把p1的值賦給p2，所以此時(shí)p1，p2都可作為free函數(shù)的參數(shù)。
malloc函數(shù)是對(duì)存儲(chǔ)區(qū)域進(jìn)行分配的。
free函數(shù)是釋放已經(jīng)不用的內(nèi)存區(qū)域的。
所以由這兩個(gè)函數(shù)就可以實(shí)現(xiàn)對(duì)內(nèi)存區(qū)域進(jìn)行動(dòng)態(tài)分配并進(jìn)行簡(jiǎn)單的管理了。
中 鏈表的C語(yǔ)言實(shí)現(xiàn)之單鏈表的實(shí)現(xiàn)
一、單鏈表的建立
有了動(dòng)態(tài)內(nèi)存分配的基礎(chǔ)，要實(shí)現(xiàn)鏈表就不難了。
所謂鏈表，就是用一組任意的存儲(chǔ)單元存儲(chǔ)線性表元素的一種數(shù)據(jù)結(jié)構(gòu)。鏈表又分為單鏈表、雙向鏈表和循環(huán)鏈表等。我們先講講單鏈表。所謂單鏈表，是指數(shù)據(jù)接點(diǎn)是單向排列的。一個(gè)單鏈表結(jié)點(diǎn)，其結(jié)構(gòu)類型分為兩部分：
1、數(shù)據(jù)域：用來存儲(chǔ)本身數(shù)據(jù)
2、鏈域或稱為指針域：用來存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址或者說指向其直接后繼的指針。
例：
[cpp] view plaincopy
typedef struct node
{
char name[20];
struct node *link;
}stud;
這樣就定義了一個(gè)單鏈表的結(jié)構(gòu)，其中char name[20]是一個(gè)用來存儲(chǔ)姓名的字符型數(shù)組，指針*link是一個(gè)用來存儲(chǔ)其直接后繼的指針。
定義好了鏈表的結(jié)構(gòu)之后，只要在程序運(yùn)行的時(shí)候數(shù)據(jù)域中存儲(chǔ)適當(dāng)?shù)臄?shù)據(jù)，如有后繼結(jié)點(diǎn)，則把鏈域指向其直接后繼，若沒有，則置為NULL。
下面就來看一個(gè)建立帶表頭(若未說明，以下所指鏈表均帶表頭)的單鏈表的完整程序。
[cpp] view plaincopy
#include
#include
#include /*包含動(dòng)態(tài)內(nèi)存分配函數(shù)的頭文件*/
#define N 10 /*N為人數(shù)*/
typedef struct node
{
char name[20];
struct node *link;
}stud;
stud * creat(int n) /*建立單鏈表的函數(shù)，形參n為人數(shù)*/
{
stud *p,*h,*s;/* *h保存表頭結(jié)點(diǎn)的指針，*p指向當(dāng)前結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，*s指向當(dāng)前結(jié)點(diǎn)*/
int i;/*計(jì)數(shù)器*/
if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空間并檢測(cè)*/
{
printf("不能分配內(nèi)存空間!");
exit(0);
}
h->name[0]='\0'; /*把表頭結(jié)點(diǎn)的數(shù)據(jù)域置空*/
h->link=NULL; /*把表頭結(jié)點(diǎn)的鏈域置空*/
p=h; /*p指向表頭結(jié)點(diǎn)*/
for(i=0;i
{
if((s=(stud *) malloc(sizeof(stud)))==NULL) /*分配新存儲(chǔ)空間并檢測(cè)*/
{
printf("不能分配內(nèi)存空間!");
exit(0);
}
p->link=s; /*把s的地址賦給p所指向的結(jié)點(diǎn)的鏈域，這樣就把p和s所指向的結(jié)點(diǎn)連接起來了*/
printf("請(qǐng)輸入第%d個(gè)人的姓名",i+1);
scanf("%s",s->name); /*在當(dāng)前結(jié)點(diǎn)s的數(shù)據(jù)域中存儲(chǔ)姓名*/
s->link=NULL;
p=s;
}
return(h);
}
main()
{
int number; /*保存人數(shù)的變量*/
stud *head; /*head是保存單鏈表的表頭結(jié)點(diǎn)地址的指針*/
number=N;
head=creat(number);/*把所新建的單鏈表表頭地址賦給head*/
}
這樣就寫好了一個(gè)可以建立包含N個(gè)人姓名的單鏈表了。寫動(dòng)態(tài)內(nèi)存分配的程序應(yīng)注意，請(qǐng)盡量對(duì)分配是否成功進(jìn)行檢測(cè)。
鏈表的C語(yǔ)言實(shí)現(xiàn)之循環(huán)鏈表及雙向鏈表
一、循環(huán)鏈表
循環(huán)鏈表是與單鏈表一樣，是一種鏈?zhǔn)降拇鎯?chǔ)結(jié)構(gòu)，所不同的是，循環(huán)鏈表的最后一個(gè)結(jié)點(diǎn)的指針是指向該循環(huán)鏈表的第一個(gè)結(jié)點(diǎn)或者表頭結(jié)點(diǎn)，從而構(gòu)成一個(gè)環(huán)形的鏈。
循環(huán)鏈表的運(yùn)算與單鏈表的運(yùn)算基本一致。所不同的有以下幾點(diǎn)：
1、在建立一個(gè)循環(huán)鏈表時(shí)，必須使其最后一個(gè)結(jié)點(diǎn)的指針指向表頭結(jié)點(diǎn)，而不是象單鏈表那樣置為NULL。此種情況還使用于在最后一個(gè)結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn)。
2、在判斷是否到表尾時(shí)，是判斷該結(jié)點(diǎn)鏈域的值是否是表頭結(jié)點(diǎn)，當(dāng)鏈域值等于表頭指針時(shí)，說明已到表尾。而非象單鏈表那樣判斷鏈域值是否為NULL。
二、雙向鏈表
雙向鏈表其實(shí)是單鏈表的改進(jìn)。
當(dāng)我們對(duì)單鏈表進(jìn)行操作時(shí)，有時(shí)你要對(duì)某個(gè)結(jié)點(diǎn)的直接前驅(qū)進(jìn)行操作時(shí)，又必須從表頭開始查找。這是由單鏈表結(jié)點(diǎn)的結(jié)構(gòu)所限制的.。因?yàn)閱捂湵砻總�(gè)結(jié)點(diǎn)只有一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址的鏈域，那么能不能定義一個(gè)既有存儲(chǔ)直接后繼結(jié)點(diǎn)地址的鏈域，又有存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址的鏈域的這樣一個(gè)雙鏈域結(jié)點(diǎn)結(jié)構(gòu)呢?這就是雙向鏈表。
在雙向鏈表中，結(jié)點(diǎn)除含有數(shù)據(jù)域外，還有兩個(gè)鏈域，一個(gè)存儲(chǔ)直接后繼結(jié)點(diǎn)地址，一般稱之為右鏈域;一個(gè)存儲(chǔ)直接前驅(qū)結(jié)點(diǎn)地址，一般稱之為左鏈域。在c語(yǔ)言中雙向鏈表結(jié)點(diǎn)類型可以定義為：
[cpp] view plaincopy
typedef struct node
{
int data; /*數(shù)據(jù)域*/
struct node *llink,*rlink; /*鏈域，*llink是左鏈域指針，*rlink是右鏈域指針*/
}JD;
當(dāng)然，也可以把一個(gè)雙向鏈表構(gòu)建成一個(gè)雙向循環(huán)鏈表。
雙向鏈表與單向鏈表一樣，也有三種基本運(yùn)算：查找、插入和刪除。
雙向鏈表的基本運(yùn)算：
1、查找
假若我們要在一個(gè)帶表頭的雙向循環(huán)鏈表中查找數(shù)據(jù)域?yàn)橐惶囟ㄖ档哪硞�(gè)結(jié)點(diǎn)時(shí)，我們同樣從表頭結(jié)點(diǎn)往后依次比較各結(jié)點(diǎn)數(shù)據(jù)域的值，若正是該特定值，則返回指向結(jié)點(diǎn)的指針，否則繼續(xù)往后查，直到表尾。
下例就是應(yīng)用雙向循環(huán)鏈表查找算法的一個(gè)程序。
[cpp] view plaincopy
#include
#include
#define N 10
typedef struct node
{
char name[20];
struct node *llink,*rlink;
}stud;
stud * creat(int n)
{
stud *p,*h,*s;
int i;
if((h=(stud *)malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
exit(0);
}
h->name[0]=’\0’;
h->llink=NULL;
h->rlink=NULL;
p=h;
for(i=0;i
{
if((s= (stud *) malloc(sizeof(stud)))==NULL)
{
printf("不能分配內(nèi)存空間!");
exit(0);
}
p->rlink=s;
printf("請(qǐng)輸入第%d個(gè)人的姓名",i+1);
scanf("%s",s->name);
s->llink=p;
s->rlink=NULL;
p=s;
}
h->llink=s;
p->rlink=h;
return(h);
}
stud * search(stud *h,char *x)
{
stud *p;
char *y;
p=h->rlink;
while(p!=h)
{
y=p->name;
if(strcmp(y,x)==0)
return(p);
else p=p->rlink;
}
printf("沒有查找到該數(shù)據(jù)!");
}
void print(stud *h)
{
int n;
stud *p;
p=h->rlink;
printf("數(shù)據(jù)信息為：\n");
while(p!=h)
{
printf("%s ",&*(p->name));
p=p->rlink;
}
printf("\n");
}
main()
{
int number;
char studname[20];
stud *head,*searchpoint;
number=N;
clrscr();
head=creat(number);
print(head);
printf("請(qǐng)輸入你要查找的人的姓名:");
scanf("%s",studname);
searchpoint=search(head,studname);
printf("你所要查找的人的姓名是:%s",*&searchpoint->name);
}
【鏈表的C語(yǔ)言實(shí)現(xiàn)方法】相關(guān)文章：
鏈表的C語(yǔ)言實(shí)現(xiàn)方法編程學(xué)習(xí)02-22
C語(yǔ)言鏈表逆序方法技巧01-27
C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)鏈表逆序并輸出10-22
c語(yǔ)言鏈表的用法03-10
c語(yǔ)言鏈表的用法有哪些01-24
C語(yǔ)言單向鏈表環(huán)測(cè)試并返回環(huán)起始節(jié)點(diǎn)的方法07-22