1. 靜態鏈表

　　結構體中的成員可以是各種類型的指針變量，當一個結構體中有一個或多個成員的基類型是本結構體類型時，則稱這種結構體為“引用自身的結構體”。如：

　　　　struct link　　　　{　　　　　　char ch;　　　　　　struct link *p;　　　　} a;

　　p是一個可以指向 struct link 類型變量的指針成員。因此，a.p = &a 是合法的表達式，由此構成的存儲結構如圖1所示。

圖1 引用自身的結構體

　　例1 一個簡單的鏈表

#include <stdio.h>struct node{  int data;  struct node *next;};typedef struct node NODETYPE;int main(){  //a是頭結點，b是中間節點，c是尾節點  //h是基類型為NODETYPE的指針，指向頭結點  //p是基類型為NODETYPE的指針，用于遍歷鏈表  NODETYPE a, b, c, *h, *p;    //給變量中的data賦值  a.data = 10;  b.data = 20;  c.data = 30;    //將節點相連  h = &a;  a.next = &b;  b.next = &c;  c.next = '/0';    //移動p，使之依次指向a、b、c,輸出它們data中的值  p = h;  while (p)  {    printf("%d/t", p->data);    p = p->next;  //p順序后移  }  printf("/n");  return 0;}STRUCT_LIST

STRUCT_LIST

　　以上程序中所定義的結構體類型 NODETYPE 共有兩個成員：成員 data 是整型；成員 next 是指針類型，其基類型是 NODETYPE 類型。

　　a、b、c 是 NODETYPE 結構體類型變量，h 和 p 是指向 NODETYPE 結構體類型的指針變量。執行程序后，形成如圖2所示的存儲結構體：指針 h 中存放變量 a 的地址，變量 a 的成員 a.next 中存放變量 b 的地址……，最后一個變量 c 的成員 c.next 置為 '/0'(NULL)。這樣就把同一類型的結構體變量 a、b、c “鏈接”到一起，形成所謂的“鏈表”，變量 a、b、c 稱為鏈表的節點。

　　在此例中，鏈接到一起的每個節點（結構體變量 a、b、c）都是通過定義，由系統在內存中開辟了固定的、不一定連續的存儲單元。在程序執行過程中，不可能人為的再產生新的存儲單元，也不能認為的使已開辟的存儲單元消失。這種鏈表成為“靜態鏈表”。

圖2 鏈表存儲結構示意圖

2.動態鏈表的概念

　　到目前為止，凡是遇到處理“批量”數據時，我們都是利用數組來存儲。定義數組必須（顯式的或隱含的）指明元素的個數，從而也就限定了一個數組中存放的數據量。在實際應用中，一個程序在每次運行時要處理的數據的數目通常并不確定。如果數組定義的小了，就沒有足夠的空間存放數據，定義大了又浪費存儲空間。

　　對于這種情況，如果能在程序執行過程中，根據需要隨時開辟存儲空間，不需要時再隨時釋放，就能比較合理的使用存儲空間。C 語言的動態存儲分配提供了這種可能性。每次動態分配的存儲單元，其地址不一定是連續的，而所需處理的批量數據往往是一個整體，各數據之間存在著接序關系。鏈表的每個節點中，除了要有存放數據本身的數據域外，至少還需要有一個指針域，用它來存放下一個節點元素的地址，以便通過這些指針把各節點連接起來（如圖3）。由于鏈表每個存儲單元都由動態存儲分配獲得，故稱這樣的鏈表為“動態鏈表”。

　　需要強調的是：動態鏈表中，每個節點沒有自己的名字，只能靠指針維系節點之間的接序關系。一旦某個節點的指針“斷開”，后續節點就再也無法找尋。

圖3 帶有頭結點的單向鏈表

　　每個鏈表都用一個“頭指針”變量來指向鏈表的開始，如圖3中的 head。也就是說，在 head 中存放了鏈表的第一個節點的地址。在這個鏈表中，我們設置了一個“頭結點”，這個節點的數據域中不存放數據（根據需要也可以不設頭結點）。鏈表最后一個節點的指針域不存放地址，置為 '/0'(NULL) 值，標志著鏈表的結束。上述鏈表的每個節點都只有一個指針域，每個指針域存放著下一個節點的地址。因此，這種鏈表只能從當前節點找到后繼節點，故稱為“單向鏈表”。