靜態鏈表和動態鏈表，靜態動態

靜態鏈表和動態鏈表，靜態動態

1. 靜態鏈表

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

　　　　struct link

　　　　{

　　　　　　char ch;

　　　　　　struct link *p;

　　　　} a;

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

圖1 引用自身的結構體

　　例1 一個簡單的鏈表

1 #include <stdio.h> 2 3 struct node 4 { 5 int data; 6 struct node *next; 7 }; 8 typedef struct node NODETYPE; 9 10 int main() 11 { 12 //a是頭結點，b是中間節點，c是尾節點 13 //h是基類型為NODETYPE的指針，指向頭結點 14 //p是基類型為NODETYPE的指針，用於遍歷鏈表 15 NODETYPE a, b, c, *h, *p; 16 17 //給變量中的data賦值 18 a.data = 10; 19 b.data = 20; 20 c.data = 30; 21 22 //將節點相連 23 h = &a; 24 a.next = &b; 25 b.next = &c; 26 c.next = '\0'; 27 28 //移動p，使之依次指向a、b、c,輸出它們data中的值 29 p = h; 30 while (p) 31 { 32 printf("%d\t", p->data); 33 p = p->next; //p順序後移 34 } 35 printf("\n"); 36 return 0; 37 } 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) 值，標志著鏈表的結束。上述鏈表的每個節點都只有一個指針域，每個指針域存放著下一個節點的地址。因此，這種鏈表只能從當前節點找到後繼節點，故稱為“單向鏈表”。