【文章內(nèi)容簡介】 在函數(shù)的執(zhí)行部分干預(yù)存儲單元的分配和釋放 。 這樣的存儲分配叫固定內(nèi)存分配 ， 又叫系統(tǒng)存儲分配 。 ② 動態(tài)內(nèi)存分配 C語言允許程序員在函數(shù)執(zhí)行部分使用動態(tài)存儲分配函數(shù)開辟或回收存儲單元，這樣的存儲分配叫動態(tài)內(nèi)存分配。動態(tài)內(nèi)存分配使用自由、節(jié)約內(nèi)存。 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 (2) 鏈表的概念 ① 結(jié)點 組成鏈表的基本存儲單元叫結(jié)點 ， 該存儲單元存有若干數(shù)據(jù)和指針 ， 由于存放了不同數(shù)據(jù)類型的數(shù)據(jù) ， 它的數(shù)據(jù)類型應(yīng)該是結(jié)構(gòu)體類型 。 在結(jié)點的結(jié)構(gòu)體存儲單元中 ， 存放數(shù)據(jù)的域叫數(shù)據(jù)域 ， 存放指針的域叫指針域 ， 簡單結(jié)點的形式如圖所示 。 數(shù)據(jù)域 指針域 結(jié)點類型定義的一般形式為： struct 類型名 {數(shù)據(jù)域定義； struct 類型名 * 指針域名 。 }。 例如有如下結(jié)點類型的定義： struct student {int num。 float score。 struct student *next。 } 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 ② 鏈表 若有一些結(jié)點，每一個結(jié)點的指針域存放下一個結(jié)點的地址，因此就指向下一個結(jié)點， 這樣就首尾銜接形成一個鏈狀結(jié)構(gòu)，稱為鏈表。用上面的結(jié)構(gòu)體類型建立的有 4個結(jié)點的鏈表如圖所示。 (2) 鏈表的概念 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 頭結(jié)點： 指向鏈表中第一個包含有用數(shù)據(jù)的結(jié)點 ， 本身不包含有用數(shù)據(jù) ， 用于對鏈表的訪問 。 尾結(jié)點： 不指向其他結(jié)點的結(jié)點。尾結(jié)點的指針域存放的地址為 NULL（或 0，或 39。\039。）。 (2) 鏈表的概念 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 相同點：它們均由同類型的存儲單元組成 。 不同點： 數(shù)組由固定分配的連續(xù)的存儲單元組成，定義后存儲單元不可增加或減少，對數(shù)組元素的訪問為隨機訪問。 鏈表可由不連續(xù)的存儲單元（結(jié)點）組成，結(jié)點一般為動態(tài)分配存儲單元，可隨時增、刪。只能順序訪問鏈表中的結(jié)點。 鏈表與數(shù)組 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 =15。=NULL。 p=head。 while(p!=NULL) {printf(%d,pdata)。 p=pnext。 } printf(NULL\n)。 } 【 例 911】 以三個結(jié)構(gòu)體變量為結(jié)點建立一個簡單的鏈表并輸出。 struct node {int data。 struct node *next。 }。 main() {struct node a,b,c,*head,*p。 head=amp。a。 =5。 =amp。b。 =10。 =amp。c。 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 2. C 動態(tài)存儲分配函數(shù) C動態(tài)存儲分配函數(shù)有： malloc、 calloc、 free、 realloc，函數(shù)定義包含在頭文件 。 (1)malloc函數(shù) void *malloc(unsigned int size) 調(diào)用形式為： (類型 *) malloc(size) 例如： int *pi。 float *pf。 pi=(int *)malloc(2)。 pf=(float *)malloc(4)。 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 【 例 912】 動態(tài)開辟一組字符型存儲單元，用于存放字符串，然后輸出。 include include main( ) {char *str。 if((str=(char *) malloc(50))==NULL) { printf(No enough memory to allocata for the string. )。 exit(1)。 } printf(Input the string: )。 gets(str)。 printf(The string is:%s\n,str)。 free(str)。 } 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 (2) calloc函數(shù) void *calloc(unsigned n, unsigned size) 調(diào)用形式為： (類型 *) calloc(n, size) 如： char *ps。 ps=(char *)calloc(10, sizeof(char))。 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 【 例 913】 動態(tài)開辟可存放 100個 float型數(shù)據(jù)的存儲單元。 include main() {float *p。 p=(float *)calloc(100,sizeof(float))。 if(p==NULL) printf(Allocation is failed.\n )。 else printf(Allocation is successful.\n )。 free(p)。 } 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 (3)realloc函數(shù) void *realloc(void *ptr, unsigned newsize) 調(diào)用形式為： (類型 *) realloc(ptr, newsize) (4)free函數(shù) void free(void *) 調(diào)用形式為： free(p)。 其中指針變量 p是由 malloc、 calloc、 realloc函數(shù)分配存儲單元存放首地址的指針變量，作用是收回由 p指向的動態(tài)分配的存儲單元。該函數(shù)無返回值。 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 【 例 914】 利用 realloc函數(shù)重新分配動態(tài)存儲空間。 include include include main() {char *str。 str=(char *)malloc(10)。 if(!str) {printf(Allocation is failed.\n )。 exit(1)。 } printf(Input the string: )。 gets(str)。 str=(char *)realloc(str,20)。 if(!str) {printf(Allocation is failed.\n )。 exit(1)。 } strcat(str, **********)。 printf(The final string is:%s\n,str)。 free(str)。 } 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 由包含一個指針域的結(jié)點組成的鏈表為單向鏈表。 鏈表的基本操作： ①建立并初始化鏈表 ②遍歷訪問鏈表（包括查找、輸出結(jié)點等） ③刪除鏈表中的結(jié)點 ④在鏈表中插入結(jié)點 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 (1) 建立單向鏈表 建立單向鏈表的步驟如下： ① 建立頭結(jié)點 （ 或定義頭指針變量 ） ； ② 讀取數(shù)據(jù)； ③ 生成新結(jié)點； ④ 將數(shù)據(jù)存入結(jié)點的數(shù)據(jù)域中； ⑤ 將新結(jié)點連接到鏈表中 （ 將新結(jié)點地址賦給上一個結(jié)點的指針域 ） 。 ⑥ 重復(fù)步驟 ② ～ ⑤ ， 直到輸入結(jié)束 。 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 【 例 915】 建立帶有頭結(jié)點的單向鏈表，當(dāng)輸入 1時結(jié)束。 include struct node {int data。 struct node *next。 }。 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 main() {int x。 struct node *h, *s, *r。 h=(struct node *)malloc(sizeof(struct node))。 r=h。 scanf(%d,amp。x)。 while(x!=1) {s=(struct node *)malloc(sizeof(struct node))。 sdata=x。 rnext=s。 r=s。 scanf(%d,amp。x)。 } rnext=NULL。 } 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 (2) 輸出鏈表 輸出鏈表即順序訪問鏈表中各結(jié)點數(shù)據(jù)域，方法是：從頭結(jié)點開始，不斷讀取數(shù)據(jù)和下移指針變量，直到尾結(jié)點為止。 【 例 916】 編寫單向鏈表的輸出函數(shù)。 void print_slist(struct node *h) {struct node *p。 p=hnext。 if(p== NULL) printf(Linklist is null!\n)。 else{ printf(head)。 while(p!= NULL) {printf(%d, pdata)。 p=pnext。 } printf(end\n)。 } } 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 （ 3）刪除單向鏈表中的一個結(jié)點 刪除單向鏈表中一個結(jié)點的方法步驟如下 : ① 找到要刪除結(jié)點的前驅(qū)結(jié)點； ②將要刪除結(jié)點的后繼結(jié)點的地址賦給要刪除結(jié)點的前驅(qū)結(jié)點的指針域； ③將要刪除結(jié)點的存儲空間釋放。 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 【 例 917】 編寫函數(shù)，在單向鏈表中刪除值為 x的結(jié)點 void delete_node(struct node *h, int x) {struct node *p,*q。 q=h。 p=hnext。 if(p!= NULL) {while((p!=NULL) amp。amp。 (pdata!=x)) {q=p。 p=pnext。} if(pdata==x) {qnext=pnext。 free(p)。} } } 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 （ 4）在單向鏈表的某結(jié)點前插入一個結(jié)點 在單向鏈表的某結(jié)點前插入一個結(jié)點的步驟如下： ①開辟一個新結(jié)點并將數(shù)據(jù)存入該結(jié)點的數(shù)據(jù)域； ②找到插入點結(jié)點； ③將新結(jié)點插入到鏈表中：將新結(jié)點的地址賦給插入點上一個結(jié)點的指針域，并將插入點的地址存入新結(jié)點的指針域 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 【 例 918】 編寫函數(shù)，在單向鏈表中值為 x的結(jié)點前插入值為 y的結(jié)點，若值為 x的結(jié)點不存在，則插在表尾。 分析 :本例結(jié)合了查找和插入兩種功能，可能遇到三種情況： ① 鏈表非空 ,值為 x的結(jié)點存在 ,則插在值為 x的結(jié)點之前； ② 鏈表非空 ,值為 x的結(jié)點不存在 ,則插在表尾； ③ 鏈表為空 ,也相當(dāng)于值為 x的結(jié)點不存在 ,則插在表尾。 安 慶 師 范 學(xué) 院 計 算 機 與 信 息 學(xué) 院 函數(shù)編寫如下： void insert_node(struct node *h, int x, int y) { struct node *s,*p,*q。 s