靜態(tài)鏈表是使用順序存儲(chǔ)結(jié)構(gòu)來實(shí)現(xiàn)的鏈表。嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)（C語言版）》在介紹靜態(tài)鏈表時(shí)使用的是一個(gè)姓氏列表。

圖1是書本上的靜態(tài)鏈表示例，圖（a）是初始化后插入了8個(gè)姓氏的鏈表，圖（b）是在第5個(gè)元素前插入了“SHI”而刪除了“WANG”的結(jié)果。

圖1：靜態(tài)鏈表示例

（a）修改前的狀態(tài)；（b）修改后的狀態(tài)

現(xiàn)在，我們就來實(shí)現(xiàn)一下這個(gè)靜態(tài)鏈表。實(shí)際上靜態(tài)鏈表與一般含有指針的鏈表沒有太大的差別，只是靜態(tài)鏈表的結(jié)點(diǎn)存放的空間不是在使用時(shí)臨時(shí)分配的，而是在一開始就分配了固定的一些，一般是用數(shù)組。同時(shí)一般的鏈表使用指針來指向下一個(gè)結(jié)點(diǎn)而在靜態(tài)鏈表中則使用數(shù)組下標(biāo)了。大家如果看嚴(yán)蔚敏的書會(huì)發(fā)現(xiàn)書上的算法還是有些問題的。下面我就直接給大家展示一種靜態(tài)鏈表的實(shí)現(xiàn)算法。

最重要的是模擬系統(tǒng)分配內(nèi)存的過程?？梢灶A(yù)先定義一個(gè)全局?jǐn)?shù)組（space）作為后面分配的空間，然后再初始化這個(gè)數(shù)組，為以后分配做準(zhǔn)備，如圖2。初始化后，這個(gè)數(shù)組中的狀態(tài)應(yīng)該如圖3(a)一樣。這樣，數(shù)組的第0個(gè)節(jié)點(diǎn)就是用來標(biāo)識(shí)哪個(gè)結(jié)點(diǎn)可用來存儲(chǔ)數(shù)據(jù)的。那么如果是含有頭結(jié)點(diǎn)的靜態(tài)鏈表，則一般開始時(shí)數(shù)組的第1個(gè)節(jié)點(diǎn)就是用來存放頭結(jié)點(diǎn)的，此時(shí)數(shù)組第0個(gè)結(jié)點(diǎn)標(biāo)識(shí)第2個(gè)結(jié)點(diǎn)可以用來存儲(chǔ)數(shù)據(jù)，而第1個(gè)結(jié)點(diǎn)（靜態(tài)鏈表的頭結(jié)點(diǎn)）的下一個(gè)結(jié)點(diǎn)下標(biāo)為0，標(biāo)識(shí)著這個(gè)靜態(tài)鏈表為空，如圖3(b)。靜態(tài)鏈表的初始化以及插入刪除各種算法與一般的鏈表是相似的。具體描述如下：

圖2：類型定義、用來模擬內(nèi)存的數(shù)組定義以及初始化

圖3：模擬內(nèi)存的數(shù)組狀態(tài)。(a)初始化后的狀態(tài)，(b)給靜態(tài)鏈表分配頭結(jié)點(diǎn)后的狀態(tài)

圖4：在靜態(tài)鏈表中查找元素在space中的位置（相當(dāng)于地址）

圖5：給靜態(tài)鏈表中的結(jié)點(diǎn)分配存儲(chǔ)空間，實(shí)際上返回的是數(shù)組中可用的結(jié)點(diǎn)下標(biāo)

圖6：釋放靜態(tài)鏈表中結(jié)點(diǎn)的存儲(chǔ)空間

靜態(tài)鏈表的存儲(chǔ)空間（圖2中的space）始終只有11個(gè)節(jié)點(diǎn)，起始為空表。insert a e代表在第a個(gè)姓氏前插入姓氏e；delete a代表刪除第a個(gè)姓氏；search e代表查找姓氏e的位置；show代表輸出靜態(tài)鏈表存儲(chǔ)空間的狀態(tài)。輸入保證操作都合法。

只遇到search和show時(shí)才輸出。當(dāng)遇到search時(shí)輸出姓氏e在space中的位置；當(dāng)遇到show時(shí)輸出這11個(gè)結(jié)點(diǎn)的狀態(tài)。姓氏占8個(gè)字符而數(shù)字占2個(gè)字符，姓氏左對齊。每個(gè)指令輸出后面跟著含有20個(gè)星號(hào)的行。

show
insert 1 ZHAO
show
insert 2 QIAN
show
insert 3 SUN
show
insert 4 LI
insert 5 ZHOU
insert 6 WU
insert 7 ZHENG
insert 8 WANG
show
insert 1 ZHANG
show
search LI
show

         2
         0
         3
         4
         5
         6
         7
         8
         9
        10
         0
********************
         3
         2
ZHAO     0
         4
         5
         6
         7
         8
         9
        10
         0
********************
         4
         2
ZHAO     3
QIAN     0
         5
         6
         7
         8
         9
        10
         0
********************
         5
         2
ZHAO     3
QIAN     4
SUN      0
         6
         7
         8
         9
        10
         0
********************
        10
         2
ZHAO     3
QIAN     4
SUN      5
LI       6
ZHOU     7
WU       8
ZHENG    9
WANG     0
         0
********************
         0
        10
ZHAO     3
QIAN     4
SUN      5
LI       6
ZHOU     7
WU       8
ZHENG    9
WANG     0
ZHANG    2
********************
 5
********************
         0
        10
ZHAO     3
QIAN     4
SUN      5
LI       6
ZHOU     7
WU       8
ZHENG    9
WANG     0
ZHANG    2
********************

零基礎(chǔ)的同學(xué)可以先學(xué)習(xí)基礎(chǔ)，教程見:  C語言教程、C++教程、編譯器教程、數(shù)據(jù)結(jié)構(gòu)教程、Python教程、單片機(jī)教程等

視頻教學(xué)見視頻網(wǎng)課