# 11.C語言鏈表的概念 在【例7-8】中采用了動態分配的辦法為一個結構分配內存空間。每一次分配一塊空間可用來存放一個學生的數據，我們可稱之為一個結點。有多少個學生就應該申請分配多少塊內存空間，也就是說要建立多少個結點。當然用結構數組也可以完成上述工作，但如果預先不能準確把握學生人數，也就無法確定數組大小。而且當學生留級、退學之后也不能把該元素占用的空間從數組中釋放出來。 用動態存儲的方法可以很好地解決這些問題。有一個學生就分配一個結點，無須預先確定學生的準確人數，某學生退學，可刪去該結點，并釋放該結點占用的存儲空間。從而節約了寶貴的內存資源。另一方面，用數組的方法必須占用一塊連續的內存區域。而使用動態分配時，每個結點之間可以是不連續的（結點內是連續的）。結點之間的聯系可以用指針實現。 即在結點結構中定義一個成員項用來存放下一結點的首地址，這個用于存放地址的成員，常把它稱為指針域。 可在第一個結點的指針域內存入第二個結點的首地址，在第二個結點的指針域內又存放第三個結點的首地址，如此串連下去直到最后一個結點。最后一個結點因無后續結點連接，其指針域可賦為0。這樣一種連接方式，在數據結構中稱為“鏈表”。 下圖為最一簡單鏈表的示意圖。  圖中，第0個結點稱為頭結點，它存放有第一個結點的首地址，它沒有數據，只是一個指針變量。以下的每個結點都分為兩個域，一個是數據域，存放各種實際的數據，如學號num，姓名name，性別sex和成績score等。另一個域為指針域，存放下一結點的首地址。鏈表中的每一個結點都是同一種結構類型。 例如，一個存放學生學號和成績的結點應為以下結構： ~~~ struct stu{ int num; int score; struct stu *next; } ~~~ 前兩個成員項組成數據域，后一個成員項next構成指針域，它是一個指向stu類型結構的指針變量。 鏈表的基本操作對鏈表的主要操作有以下幾種： * 建立鏈表； * 結構的查找與輸出； * 插入一個結點； * 刪除一個結點。 下面通過例題來說明這些操作。 【例11-9】建立一個三個結點的鏈表，存放學生數據。為簡單起見， 我們假定學生數據結構中只有學號和年齡兩項。可編寫一個建立鏈表的函數creat。程序如下： ~~~ #define NULL 0 #define TYPE struct stu #define LEN sizeof (struct stu) struct stu{ int num; int age; struct stu *next; }; TYPE *creat(int n){ struct stu *head,*pf,*pb; int i; for(i=0;i<n;i++){ pb=(TYPE*) malloc(LEN); printf("input Number and Age\n"); scanf("%d%d",&pb->num,&pb->age); if(i==0) pf=head=pb; else pf->next=pb; pb->next=NULL; pf=pb; } return(head); } ~~~ 在函數外首先用宏定義對三個符號常量作了定義。這里用 TYPE表示struct stu，用LEN表示sizeof(struct stu)主要的目的是為了在以下程序內減少書寫并使閱讀更加方便。結構stu定義為外部類型，程序中的各個函數均可使用該定義。 creat函數用于建立一個有n個結點的鏈表，它是一個指針函數，它返回的指針指向stu結構。在creat函數內定義了三個stu結構的指針變量。head為頭指針，pf為指向兩相鄰結點的前一結點的指針變量。pb為后一結點的指針變量。