計算機等級考試二級C語言單鏈表的建立與算法

　　一、單鏈表的建立

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

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

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

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

　　例：

typedef struct node { 　char name[20]; 　struct node *link; }stud;

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

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

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

#include ＜stdio.h＞ #include ＜malloc.h＞ /*包含動態(tài)內存分配函數的頭文件*/ #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]='\0'; /*把表頭結點的數據域置空*/ 　h-＞link=NULL; /*把表頭結點的鏈域置空*/ 　p=h; /*p指向表頭結點*/ 　for(i=0;i＜n;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的數據域中存儲姓名*/ 　　s-＞link=NULL; 　　p=s; 　} 　return(h); } main() { 　int number; /*保存人數的變量*/ 　stud *head; /*head是保存單鏈表的表頭結點地址的指針*/ 　number=N; 　head=creat(number); /*把所新建的單鏈表表頭地址賦給head*/ }

　　這樣就寫好了一個可以建立包含N個人姓名的單鏈表了。寫動態(tài)內存分配的程序應注意，請盡量對分配是否成功進行檢測。