鏈表的C語言實現方法

C語言的應用範圍廣泛，具備很強的數據處理能力，不僅僅是在軟件開發上，而且各類科研都需要用到C語言，適於編寫系統軟件，三維，二維圖形和動畫，具體應用比如單片機以及嵌入式系統開發。以下是小編為大家搜索整理鏈表的C語言實現方法，希望能給大家帶來幫助!更多精彩內容請及時關注我們應屆畢業生考試網!

　　一、為什麼用動態內存分配

但我們未學習鏈表的時候，如果要存儲數量比較多的同類型或同結構的數據的時候，總是使用一個數組。比如説我們要存儲一個班級學生的某科分數，總是定義一個float型(存在0.5分)數組：

float score[30];

但是，在使用數組的時候，總有一個問題困擾着我們：數組應該有多大?

在很多的情況下，你並不能確定要使用多大的數組，比如上例，你可能並不知道該班級的學生的人數，那麼你就要把數組定義得足夠大。這樣，你的程序在運行時就申請了固定大小的你認為足夠大的內存空間。即使你知道該班級的學生數，但是如果因為某種特殊原因人數有增加或者減少，你又必須重新去修改程序，擴大數組的存儲範圍。這種分配固定大小的內存分配方法稱之為靜態內存分配。但是這種內存分配的方法存在比較嚴重的缺陷，特別是處理某些問題時：在大多數情況下會浪費大量的內存空間，在少數情況下，當你定義的數組不夠大時，可能引起下標越界錯誤，甚至導致嚴重後果。

那麼有沒有其它的方法來解決這樣的外呢體呢?有，那就是動態內存分配。

所謂動態內存分配就是指在程序執行的過程中動態地分配或者回收存儲空間的分配內存的方法。動態內存分配不象數組等靜態內存分配方法那樣需要預先分配存儲空間，而是由系統根據程序的需要即時分配，且分配的大小就是程序要求的大小。從以上動、靜態內存分配比較可以知道動態內存分配相對於景泰內存分配的特點：

1、不需要預先分配存儲空間;

2、分配的空間可以根據程序的需要擴大或縮小。

　　二、如何實現動態內存分配及其管理

要實現根據程序的需要動態分配存儲空間，就必須用到以下幾個函數

1、malloc函數

malloc函數的原型為：

void *malloc (unsigned int size)

其作用是在內存的動態存儲區中分配一個長度為size的連續空間。其參數是一個無符號整形數，返回值是一個指向所分配的連續存儲域的起始地址的指針。還有一點必須注意的是，當函數未能成功分配存儲空間(如內存不足)就會返回一個NULL指針。所以在調用該函數時應該檢測返回值是否為NULL並執行相應的操作。

下例是一個動態分配的程序：

[cpp] view plaincopy

#include "malloc.h"

#include "stdlib.h"

main(void)

{

/*count是一個計數器，array是一個整型指針，也可以理解為指向一個整型數組的首地址*/

int count;

int *array;

array=malloc(10 * sizeof(int));

if(array==NULL)

{

printf("Out of memory!n");

exit(1);

}

/*給數組賦值*/

for(count=0;count<10;count++)

{

array[count]=count;

}

/*打印數組元素*/

for(count=0;count<10;count++)

{

printf("%2dn",array[count]);

}

}

上例中動態分配了10個整型存儲區域，然後進行賦值並打印。例中if((array(int *) malloc(10*sizeof(int)))==NULL)語句可以分為以下幾步：

1)分配10個整型的連續存儲空間，並返回一個指向其起始地址的整型指針

2)把此整型指針地址賦給array

3)檢測返回值是否為NULL

2、free函數

由於內存區域總是有限的，不能不限制地分配下去，而且一個程序要儘量節省資源，所以當所分配的內存區域不用時，就要釋放它，以便其它的變量或者程序使用。這時我們就要用到free函數。

其函數原型是：

void free(void *p)

作用是釋放指針p所指向的內存區。

其參數p必須是先前調用malloc函數或calloc函數(另一個動態分配存儲區域的函數)時返回的指針。給free函數傳遞其它的值很可能造成死機或其它災難性的後果。

注意：這裏重要的是指針的值，而不是用來申請動態內存的指針本身。例：

int *p1,*p2;

p1=malloc(10*sizeof(int));

p2=p1;

……

free(p2) /*或者free(p2)*/

malloc返回值賦給p1，又把p1的值賦給p2，所以此時p1，p2都可作為free函數的參數。

malloc函數是對存儲區域進行分配的。

free函數是釋放已經不用的內存區域的。

所以由這兩個函數就可以實現對內存區域進行動態分配並進行簡單的管理了。

中 鏈表的C語言實現之單鏈表的實現

　　一、單鏈表的建立

有了動態內存分配的基礎，要實現鏈表就不難了。

所謂鏈表，就是用一組任意的存儲單元存儲線性表元素的一種數據結構。鏈表又分為單鏈表、雙向鏈表和循環鏈表等。我們先講講單鏈表。所謂單鏈表，是指數據接點是單向排列的。一個單鏈表結點，其結構類型分為兩部分：

1、數據域：用來存儲本身數據

2、鏈域或稱為指針域：用來存儲下一個結點地址或者説指向其直接後繼的指針。

例：

[cpp] view plaincopy

typedef struct node

{

char name[20];

struct node *link;

}stud;

這樣就定義了一個單鏈表的結構，其中char name[20]是一個用來存儲姓名的字符型數組，指針*link是一個用來存儲其直接後繼的指針。

定義好了鏈表的結構之後，只要在程序運行的時候數據域中存儲適當的數據，如有後繼結點，則把鏈域指向其直接後繼，若沒有，則置為NULL。

下面就來看一個建立帶表頭(若未説明，以下所指鏈表均帶表頭)的單鏈表的完整程序。

[cpp] view plaincopy

#include

#include

#include /*包含動態內存分配函數的頭文件*/

#define N 10 /*N為人數*/

typedef struct node

{

char name[20];

struct node *link;

}stud;

stud * creat(int n) /*建立單鏈表的函數，形參n為人數*/

{

stud *p,*h,*s;/* *h保存表頭結點的指針，*p指向當前結點的前一個結點，*s指向當前結點*/

int i;/*計數器*/

if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空間並檢測*/

{

printf("不能分配內存空間!");

exit(0);

}

h->name[0]='