1. 靜態(tài)鏈表

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

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

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

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

　　例1 一個(gè)簡(jiǎn)單的鏈表

#include <stdio.h>

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

int main()
{
  //a是頭結(jié)點(diǎn)，b是中間節(jié)點(diǎn)，c是尾節(jié)點(diǎn)
  //h是基類型為NODETYPE的指針，指向頭結(jié)點(diǎn)
  //p是基類型為NODETYPE的指針，用于遍歷鏈表
  NODETYPE a, b, c, *h, *p;
  
  //給變量中的data賦值
  a.data = 10;
  b.data = 20;
  c.data = 30;
  
  //將節(jié)點(diǎn)相連
  h = &a;
  a.next = &b;
  b.next = &c;
  c.next = '\0';
  
  //移動(dòng)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 共有兩個(gè)成員：成員 data 是整型；成員 next 是指針類型，其基類型是 NODETYPE 類型。

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

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

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

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

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

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

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

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

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

最新評(píng)論