c語言鏈表

單鏈表的建立

有了動態內存分配的基礎，要實現鏈表就不難了。鏈表由一系列不必在內存中相連的結構組成。每一個結構均含有表元素和指向包含該元素后繼元的結構指針。我們稱之為next指針。最后一個單元的next指針指向NULL；該值由C定義并且不能與其它指針混淆。ANSI C規定NULL為零。
指針變量是包含存儲另外某個數據的地址的變量。因此，如果P被聲明為指向一個結構的指針，那么存儲在P中的值就被解釋為內存中的一個位置，在該位置能夠找到一個結構。該結構的一個域可以通過P->FileName訪問，其中FileName是我們要考察的域的名字。如圖1所示，這個表含有五個結構，恰好在內存中分配給它們的位置分別是1000，800,712,992和692。第一個結構的指針含有值800，它提供了第二個結構所在的位置。其余每個結構也都有一個指針用于類似的目的。當然，為了訪問該表，我們需要知道在哪里能夠找到第一個單元。

為了執行打印表PrinList（L）或查找表Find（L，key），只要將一個指針傳遞到該表的第一個元素，然后用一些Next指針穿越該表即可。
typedef struct node
{
char name[20];
struct node *link;
}stud;
這樣就定義了一個單鏈表的結構，其中char name[20]是一個用來存儲姓名的字符型數組，指針*link是一個用來存儲其直接后繼的指針。定義好了鏈表的結構之后，只要在程序運行的時候在數據域中存儲適當的數據，如有后繼結點，則把鏈域指向其直接后繼，若沒有，則置為NULL。下面就來看一個建立帶表頭（若未說明，以下所指鏈表均帶表頭）的單鏈表的完整程序。

#include <stdio.h>  

#include <conio.h>  

#include <string.h>  

#include <stdlib.h>

#define N 3 /*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;  //要把s的數據保存到p中，要不下次循環s就又指向一個空的新地址了。

   }

   return(h);

}

int main()

{

   int number; /*保存人數的變量*/

   stud *head; /*head是保存單鏈表的表頭結點地址的指針*/

   number=N;

   head=creat(number); /*把所新建的單鏈表表頭地址賦給head*/

}