在前面章節(jié)中，講解了順序表和鏈表兩種存儲(chǔ)結(jié)構(gòu)各自的特點(diǎn)。那么，是否存在一種存儲(chǔ)結(jié)構(gòu)，可以融合順序表和鏈表各自的優(yōu)點(diǎn)，從而既能快速訪問元素，又能快速增加或刪除數(shù)據(jù)元素。

靜態(tài)鏈表，也是線性存儲(chǔ)結(jié)構(gòu)的一種，它兼顧了順序表和鏈表的優(yōu)點(diǎn)于一身，可以看做是順序表和鏈表的升級(jí)版。

使用靜態(tài)鏈表存儲(chǔ)數(shù)據(jù)，數(shù)據(jù)全部存儲(chǔ)在數(shù)組中（和順序表一樣），但存儲(chǔ)位置是隨機(jī)的，數(shù)據(jù)之間"一對(duì)一"的邏輯關(guān)系通過一個(gè)整形變量（稱為"游標(biāo)"，和指針功能類似）維持（和鏈表類似）。

例如，使用靜態(tài)鏈表存儲(chǔ)?{1,2,3}?的過程如下：

創(chuàng)建一個(gè)足夠大的數(shù)組，假設(shè)大小為 6，如圖?1 所示：

接著，在將數(shù)據(jù)存放到數(shù)組中時(shí)，給各個(gè)數(shù)據(jù)元素配備一個(gè)整形變量，此變量用于指明各個(gè)元素的直接后繼元素所在數(shù)組中的位置下標(biāo)，如圖 2 所示：

通常，靜態(tài)鏈表會(huì)將第一個(gè)數(shù)據(jù)元素放到數(shù)組下標(biāo)為 1 的位置（a[1]）中。

圖 2 中，從 a[1] 存儲(chǔ)的數(shù)據(jù)元素 1 開始，通過存儲(chǔ)的游標(biāo)變量 3，就可以在 a[3] 中找到元素 1 的直接后繼元素 2；同樣，通過元素 a[3] 存儲(chǔ)的游標(biāo)變量 5，可以在 a[5] 中找到元素 2 的直接后繼元素 3，這樣的循環(huán)過程直到某元素的游標(biāo)變量為 0 截止（因?yàn)?a[0] 默認(rèn)不存儲(chǔ)數(shù)據(jù)元素）。

類似圖 2 這樣，通過 "數(shù)組+游標(biāo)" 的方式存儲(chǔ)具有線性關(guān)系數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)就是靜態(tài)鏈表。

靜態(tài)鏈表中的節(jié)點(diǎn)

通過上面的學(xué)習(xí)我們知道，靜態(tài)鏈表存儲(chǔ)數(shù)據(jù)元素也需要自定義數(shù)據(jù)類型，至少需要包含以下 2 部分信息：

• 數(shù)據(jù)域：用于存儲(chǔ)數(shù)據(jù)元素的值；

• 游標(biāo)：其實(shí)就是數(shù)組下標(biāo)，表示直接后繼元素所在數(shù)組中的位置；

因此，靜態(tài)鏈表中節(jié)點(diǎn)的構(gòu)成用 C 語言實(shí)現(xiàn)為：

備用鏈表

圖 2 顯示的靜態(tài)鏈表還不夠完整，靜態(tài)鏈表中，除了數(shù)據(jù)本身通過游標(biāo)組成的鏈表外，還需要有一條連接各個(gè)空閑位置的鏈表，稱為備用鏈表。

備用鏈表的作用是回收數(shù)組中未使用或之前使用過（目前未使用）的存儲(chǔ)空間，留待后期使用。也就是說，靜態(tài)鏈表使用數(shù)組申請(qǐng)的物理空間中，存有兩個(gè)鏈表，一條連接數(shù)據(jù)，另一條連接數(shù)組中未使用的空間。

通常，備用鏈表的表頭位于數(shù)組下標(biāo)為 0（a[0]） 的位置，而數(shù)據(jù)鏈表的表頭位于數(shù)組下標(biāo)為 1（a[1]）的位置。

靜態(tài)鏈表中設(shè)置備用鏈表的好處是，可以清楚地知道數(shù)組中是否有空閑位置，以便數(shù)據(jù)鏈表添加新數(shù)據(jù)時(shí)使用。比如，若靜態(tài)鏈表中數(shù)組下標(biāo)為 0 的位置上存有數(shù)據(jù)，則證明數(shù)組已滿。

例如，使用靜態(tài)鏈表存儲(chǔ)?{1,2,3}，假設(shè)使用長度為 6 的數(shù)組 a，則存儲(chǔ)狀態(tài)可能如圖 3 所示：

圖 3 中，備用鏈表上連接的依次是 a[0]、a[2] 和 a[4]，而數(shù)據(jù)鏈表上連接的依次是 a[1]、a[3] 和 a[5]。

靜態(tài)鏈表的實(shí)現(xiàn)

假設(shè)使用靜態(tài)鏈表（數(shù)組長度為 6）存儲(chǔ)?{1,2,3}，則需經(jīng)歷以下幾個(gè)階段。

在數(shù)據(jù)鏈表未初始化之前，數(shù)組中所有位置都處于空閑狀態(tài)，因此都應(yīng)被鏈接在備用鏈表上，如圖 4 所示：

當(dāng)向靜態(tài)鏈表中添加數(shù)據(jù)時(shí)，需提前從備用鏈表中摘除節(jié)點(diǎn)，以供新數(shù)據(jù)使用。

備用鏈表摘除節(jié)點(diǎn)最簡單的方法是摘除 a[0] 的直接后繼節(jié)點(diǎn)；同樣，向備用鏈表中添加空閑節(jié)點(diǎn)也是添加作為 a[0] 新的直接后繼節(jié)點(diǎn)。因?yàn)?a[0] 是備用鏈表的第一個(gè)節(jié)點(diǎn)，我們知道它的位置，操作它的直接后繼節(jié)點(diǎn)相對(duì)容易，無需遍歷備用鏈表，耗費(fèi)的時(shí)間復(fù)雜度為?O(1)。

因此，在圖 4 的基礎(chǔ)上，向靜態(tài)鏈表中添加元素 1 的過程如圖 5 所示：

在圖 5 的基礎(chǔ)上，添加元素 2 的過程如圖 6 所示：

在圖 6 的基礎(chǔ)上，繼續(xù)添加元素 3 ，過程如圖 7 所示：

由此，靜態(tài)鏈表就創(chuàng)建完成了。

下面給出了創(chuàng)建靜態(tài)鏈表的 C 語言實(shí)現(xiàn)代碼：

代碼輸出結(jié)果為：

靜態(tài)鏈表為：
1,2
2,3
3,0

由此，我們就成功創(chuàng)建了一個(gè)不帶頭結(jié)點(diǎn)的靜態(tài)鏈表（如圖 7 所示），感興趣的讀者可自行嘗試創(chuàng)建一個(gè)帶有頭結(jié)點(diǎn)的靜態(tài)鏈表。