1. 靜態(tài)鏈表

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

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

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

圖1 引用自身的結(jié)構(gòu)體

　　例1 一個簡單的鏈表

#include <stdio.h>

struct node
{
  int data;
  struct node *next;
};
typedef struct node NODETYPE;

int main()
{
  //a是頭結(jié)點，b是中間節(jié)點，c是尾節(jié)點
  //h是基類型為NODETYPE的指針，指向頭結(jié)點
  //p是基類型為NODETYPE的指針，用于遍歷鏈表
  NODETYPE a, b, c, *h, *p;
  
  //給變量中的data賦值
  a.data = 10;
  b.data = 20;
  c.data = 30;
  
  //將節(jié)點相連
  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

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

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

　　在此例中，鏈接到一起的每個節(jié)點（結(jié)構(gòu)體變量 a、b、c）都是通過定義，由系統(tǒng)在內(nèi)存中開辟了固定的、不一定連續(xù)的存儲單元。在程序執(zhí)行過程中，不可能人為的再產(chǎn)生新的存儲單元，也不能認為的使已開辟的存儲單元消失。這種鏈表成為“靜態(tài)鏈表”。

圖2 鏈表存儲結(jié)構(gòu)示意圖

2.動態(tài)鏈表的概念

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

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

　　需要強調(diào)的是：動態(tài)鏈表中，每個節(jié)點沒有自己的名字，只能靠指針維系節(jié)點之間的接序關(guān)系。一旦某個節(jié)點的指針“斷開”，后續(xù)節(jié)點就再也無法找尋。

圖3 帶有頭結(jié)點的單向鏈表

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

最新評論