準備：動態(tài)內存分配
一、為什么用動態(tài)內存分配
但我們未學習鏈表的時候，如果要存儲數(shù)量比較多的同類型或同結構的數(shù)據(jù)的時候，總是使用一個數(shù)組。比如說我們要存儲一個班級學生的某科分數(shù)，總是定義一個float型（存在0.5分）數(shù)組：
float score[30];
但是，在使用數(shù)組的時候，總有一個問題困擾著我們：數(shù)組應該有多大？
在很多的情況下，你并不能確定要使用多大的數(shù)組，比如上例，你可能并不知道該班級的學生的人數(shù)，那么你就要把數(shù)組定義得足夠大。這樣，你的程序在運行時就申請了固定大小的你認為足夠大的內存空間。即使你知道該班級的學生數(shù)，但是如果因為某種特殊原因人數(shù)有增加或者減少，你又必須重新去修改程序，擴大數(shù)組的存儲范圍。這種分配固定大小的內存分配方法稱之為靜態(tài)內存分配。但是這種內存分配的方法存在比較嚴重的缺陷，特別是處理某些問題時：在大多數(shù)情況下會浪費大量的內存空間，在少數(shù)情況下，當你定義的數(shù)組不夠大時，可能引起下標越界錯誤，甚至導致嚴重后果。
那么有沒有其它的方法來解決這樣的外呢體呢？有，那就是動態(tài)內存分配。
所謂動態(tài)內存分配就是指在程序執(zhí)行的過程中動態(tài)地分配或者回收存儲空間的分配內存的方法。動態(tài)內存分配不象數(shù)組等靜態(tài)內存分配方法那樣需要預先分配存儲空間，而是由系統(tǒng)根據(jù)程序的需要即時分配，且分配的大小就是程序要求的大小。從以上動、靜態(tài)內存分配比較可以知道動態(tài)內存分配相對于景泰內存分配的特點：
1、不需要預先分配存儲空間；
2、分配的空間可以根據(jù)程序的需要擴大或縮小。
二、如何實現(xiàn)動態(tài)內存分配及其管理
要實現(xiàn)根據(jù)程序的需要動態(tài)分配存儲空間，就必須用到以下幾個函數(shù)
1、malloc函數(shù)
malloc函數(shù)的原型為：
void *malloc (unsigned int size)
其作用是在內存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。其參數(shù)是一個無符號整形數(shù)，返回值是一個指向所分配的連續(xù)存儲域的起始地址的指針。還有一點必須注意的是，當函數(shù)未能成功分配存儲空間（如內存不足）就會返回一個NULL指針。所以在調用該函數(shù)時應該檢測返回值是否為NULL并執(zhí)行相應的操作。
下例是一個動態(tài)分配的程序：
#include
#include
main()
{
int count,*array; /*count是一個計數(shù)器，array是一個整型指針，也可以理解為指向一個整型數(shù)組的首地址*/
if((array(int *) malloc(10*sizeof(int)))==NULL)
{
printf("不能成功分配存儲空間。");
exit(1);
}
for (count=0;count〈10;count++) /*給數(shù)組賦值*/
array[count]=count;
for(count=0;count〈10;count++) /*打印數(shù)組元素*/
printf("-",array[count]);
}
上例中動態(tài)分配了10個整型存儲區(qū)域，然后進行賦值并打印。例中if((array(int *) malloc(10*sizeof(int)))==NULL)語句可以分為以下幾步：
1）分配10個整型的連續(xù)存儲空間，并返回一個指向其起始地址的整型指針
2）把此整型指針地址賦給array
3）檢測返回值是否為NULL
2、free函數(shù)
由于內存區(qū)域總是有限的，不能不限制地分配下去，而且一個程序要盡量節(jié)省資源，所以當所分配的內存區(qū)域不用時，就要釋放它，以便其它的變量或者程序使用。這時我們就要用到free函數(shù)。
其函數(shù)原型是：
void free(void *p)
作用是釋放指針p所指向的內存區(qū)。
其參數(shù)p必須是先前調用malloc函數(shù)或calloc函數(shù)（另一個動態(tài)分配存儲區(qū)域的函數(shù)）時返回的指針。給free函數(shù)傳遞其它的值很可能造成死機或其它災難性的后果。
注意：這里重要的是指針的值，而不是用來申請動態(tài)內存的指針本身。例：
int *p1,*p2;
p1=malloc(10*sizeof(int));
p2=p1;
……
free(p2) /*或者free(p2)*/
malloc返回值賦給p1，又把p1的值賦給p2，所以此時p1，p2都可作為free函數(shù)的參數(shù)。
malloc函數(shù)是對存儲區(qū)域進行分配的。
free函數(shù)是釋放已經(jīng)不用的內存區(qū)域的。
所以由這兩個函數(shù)就可以實現(xiàn)對內存區(qū)域進行動態(tài)分配并進行簡單的管理了。一、單鏈表的建立
有了動態(tài)內存分配的基礎，要實現(xiàn)鏈表就不難了。
所謂鏈表，就是用一組任意的存儲單元存儲線性表元素的一種數(shù)據(jù)結構。
鏈表又分為單鏈表、雙向鏈表和循環(huán)鏈表等。我們先講講單鏈表。
所謂單鏈表，是指數(shù)據(jù)接點是單向排列的。一個單鏈表結點，其結構類型分為兩部分：
1、數(shù)據(jù)域：用來存儲本身數(shù)據(jù)
2、鏈域或稱為指針域：用來存儲下一個結點地址或者說指向其直接后繼的指針。
例：
typedef struct node
{
char name[20];
struct node *link;
}stud;
這樣就定義了一個單鏈表的結構，其中char name[20]是一個用來存儲姓名的字符型數(shù)組，指針*link是一個用來存儲其直接后繼的指針。
定義好了鏈表的結構之后，只要在程序運行的時候愛數(shù)據(jù)域中存儲適當?shù)臄?shù)據(jù)，如有后繼結點，則把鏈域指向其直接后繼，若沒有，則置為NULL。
下面就來看一個建立帶表頭（若未說明，以下所指鏈表均帶表頭）的單鏈表的完整程序。
#include
#include /*包含動態(tà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保存表頭結點的指針，*p指向當前結點的前一個結點，*s指向當前結點*/
int i; /*計數(shù)器*/
if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空間并檢測*/
{
printf("不能分配內存空間!");
exit(0);
}
h->name[0]='\0'; /*把表頭結點的數(shù)據(jù)域置空*/
h->link=NULL; /*把表頭結點的鏈域置空*/
p=h; /*p指向表頭結點*/
for(i=0;i{
if((s= (stud *) malloc(sizeof(stud)))==NULL) /*分配新存儲空間并檢測*/
{
printf("不能分配內存空間!");
exit(0);
}
p->link=s; /*把s的地址賦給p所指向的結點的鏈域，這樣就把p和s所指向的結點連接起來了*/
printf("請輸入第%d個人的姓名",i+1);
scanf("%s",s->name); /*在當前結點s的數(shù)據(jù)域中存儲姓名*/
s->link=NULL;
p=s;
}
return(h);
}
main()
{
int number; /*保存人數(shù)的變量*/
stud *head; /*head是保存單鏈表的表頭結點地址的指針*/
number=N;
head=creat(number); /*把所新建的單鏈表表頭地址賦給head*/
}
這樣就寫好了一個可以建立包含N個人姓名的單鏈表了。
寫動態(tài)內存分配的程序應注意，請盡量對分配是否成功進行檢測。
一、為什么用動態(tài)內存分配
但我們未學習鏈表的時候，如果要存儲數(shù)量比較多的同類型或同結構的數(shù)據(jù)的時候，總是使用一個數(shù)組。比如說我們要存儲一個班級學生的某科分數(shù)，總是定義一個float型（存在0.5分）數(shù)組：
float score[30];
但是，在使用數(shù)組的時候，總有一個問題困擾著我們：數(shù)組應該有多大？
在很多的情況下，你并不能確定要使用多大的數(shù)組，比如上例，你可能并不知道該班級的學生的人數(shù)，那么你就要把數(shù)組定義得足夠大。這樣，你的程序在運行時就申請了固定大小的你認為足夠大的內存空間。即使你知道該班級的學生數(shù)，但是如果因為某種特殊原因人數(shù)有增加或者減少，你又必須重新去修改程序，擴大數(shù)組的存儲范圍。這種分配固定大小的內存分配方法稱之為靜態(tài)內存分配。但是這種內存分配的方法存在比較嚴重的缺陷，特別是處理某些問題時：在大多數(shù)情況下會浪費大量的內存空間，在少數(shù)情況下，當你定義的數(shù)組不夠大時，可能引起下標越界錯誤，甚至導致嚴重后果。
那么有沒有其它的方法來解決這樣的外呢體呢？有，那就是動態(tài)內存分配。
所謂動態(tài)內存分配就是指在程序執(zhí)行的過程中動態(tài)地分配或者回收存儲空間的分配內存的方法。動態(tài)內存分配不象數(shù)組等靜態(tài)內存分配方法那樣需要預先分配存儲空間，而是由系統(tǒng)根據(jù)程序的需要即時分配，且分配的大小就是程序要求的大小。從以上動、靜態(tài)內存分配比較可以知道動態(tài)內存分配相對于景泰內存分配的特點：
1、不需要預先分配存儲空間；
2、分配的空間可以根據(jù)程序的需要擴大或縮小。
二、如何實現(xiàn)動態(tài)內存分配及其管理
要實現(xiàn)根據(jù)程序的需要動態(tài)分配存儲空間，就必須用到以下幾個函數(shù)
1、malloc函數(shù)
malloc函數(shù)的原型為：
void *malloc (unsigned int size)
其作用是在內存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。其參數(shù)是一個無符號整形數(shù)，返回值是一個指向所分配的連續(xù)存儲域的起始地址的指針。還有一點必須注意的是，當函數(shù)未能成功分配存儲空間（如內存不足）就會返回一個NULL指針。所以在調用該函數(shù)時應該檢測返回值是否為NULL并執(zhí)行相應的操作。
下例是一個動態(tài)分配的程序：
#include
#include
main()
{
int count,*array; /*count是一個計數(shù)器，array是一個整型指針，也可以理解為指向一個整型數(shù)組的首地址*/
if((array(int *) malloc(10*sizeof(int)))==NULL)
{
printf("不能成功分配存儲空間。");
exit(1);
}
for (count=0;count〈10;count++) /*給數(shù)組賦值*/
array[count]=count;
for(count=0;count〈10;count++) /*打印數(shù)組元素*/
printf("-",array[count]);
}
上例中動態(tài)分配了10個整型存儲區(qū)域，然后進行賦值并打印。例中if((array(int *) malloc(10*sizeof(int)))==NULL)語句可以分為以下幾步：
1）分配10個整型的連續(xù)存儲空間，并返回一個指向其起始地址的整型指針
2）把此整型指針地址賦給array
3）檢測返回值是否為NULL
2、free函數(shù)
由于內存區(qū)域總是有限的，不能不限制地分配下去，而且一個程序要盡量節(jié)省資源，所以當所分配的內存區(qū)域不用時，就要釋放它，以便其它的變量或者程序使用。這時我們就要用到free函數(shù)。
其函數(shù)原型是：
void free(void *p)
作用是釋放指針p所指向的內存區(qū)。
其參數(shù)p必須是先前調用malloc函數(shù)或calloc函數(shù)（另一個動態(tài)分配存儲區(qū)域的函數(shù)）時返回的指針。給free函數(shù)傳遞其它的值很可能造成死機或其它災難性的后果。
注意：這里重要的是指針的值，而不是用來申請動態(tài)內存的指針本身。例：
int *p1,*p2;
p1=malloc(10*sizeof(int));
p2=p1;
……
free(p2) /*或者free(p2)*/
malloc返回值賦給p1，又把p1的值賦給p2，所以此時p1，p2都可作為free函數(shù)的參數(shù)。
malloc函數(shù)是對存儲區(qū)域進行分配的。
free函數(shù)是釋放已經(jīng)不用的內存區(qū)域的。
所以由這兩個函數(shù)就可以實現(xiàn)對內存區(qū)域進行動態(tài)分配并進行簡單的管理了。一、單鏈表的建立
有了動態(tài)內存分配的基礎，要實現(xiàn)鏈表就不難了。
所謂鏈表，就是用一組任意的存儲單元存儲線性表元素的一種數(shù)據(jù)結構。
鏈表又分為單鏈表、雙向鏈表和循環(huán)鏈表等。我們先講講單鏈表。
所謂單鏈表，是指數(shù)據(jù)接點是單向排列的。一個單鏈表結點，其結構類型分為兩部分：
1、數(shù)據(jù)域：用來存儲本身數(shù)據(jù)
2、鏈域或稱為指針域：用來存儲下一個結點地址或者說指向其直接后繼的指針。
例：
typedef struct node
{
char name[20];
struct node *link;
}stud;
這樣就定義了一個單鏈表的結構，其中char name[20]是一個用來存儲姓名的字符型數(shù)組，指針*link是一個用來存儲其直接后繼的指針。
定義好了鏈表的結構之后，只要在程序運行的時候愛數(shù)據(jù)域中存儲適當?shù)臄?shù)據(jù)，如有后繼結點，則把鏈域指向其直接后繼，若沒有，則置為NULL。
下面就來看一個建立帶表頭（若未說明，以下所指鏈表均帶表頭）的單鏈表的完整程序。
#include
#include /*包含動態(tà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保存表頭結點的指針，*p指向當前結點的前一個結點，*s指向當前結點*/
int i; /*計數(shù)器*/
if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空間并檢測*/
{
printf("不能分配內存空間!");
exit(0);
}
h->name[0]='\0'; /*把表頭結點的數(shù)據(jù)域置空*/
h->link=NULL; /*把表頭結點的鏈域置空*/
p=h; /*p指向表頭結點*/
for(i=0;i{
if((s= (stud *) malloc(sizeof(stud)))==NULL) /*分配新存儲空間并檢測*/
{
printf("不能分配內存空間!");
exit(0);
}
p->link=s; /*把s的地址賦給p所指向的結點的鏈域，這樣就把p和s所指向的結點連接起來了*/
printf("請輸入第%d個人的姓名",i+1);
scanf("%s",s->name); /*在當前結點s的數(shù)據(jù)域中存儲姓名*/
s->link=NULL;
p=s;
}
return(h);
}
main()
{
int number; /*保存人數(shù)的變量*/
stud *head; /*head是保存單鏈表的表頭結點地址的指針*/
number=N;
head=creat(number); /*把所新建的單鏈表表頭地址賦給head*/
}
這樣就寫好了一個可以建立包含N個人姓名的單鏈表了。
寫動態(tài)內存分配的程序應注意，請盡量對分配是否成功進行檢測。