在沒有指針的時代，要描述靜態(tài)鏈表是比較困難的桩警，前人想到了使用數組與游標來表示單鏈表的方法可训，如下圖
在靜態(tài)鏈表中，數組第一位的游標存放第一位沒有數據的元素的下標捶枢，數組最后一位的游標存放第一位有數據的元素的下標握截。
這種用數組描述的鏈表叫做靜態(tài)鏈表，這種描述方法叫做游標實現法烂叔。
1. 線性表的靜態(tài)鏈表存儲結構及初始化
typedef struct {
ElemType data;//數據
int cur;//游標(Cursor)
}Component,StaticLinkList[MAXSIZE];
Status InitList(StaticLinkList L)
{
for (int i = 0; i < MAXSIZE-1; i++) {
//初始化的時候除了最后一位谨胞，前面的游標都指向下一位，這樣就串聯成了備用鏈表
L[i].cur = i+1;
}
//最后一位游標為0蒜鸡，因為沒有有數據的項
L[MAXSIZE-1].cur = 0;
return OK;
}
靜態(tài)鏈表備忘錄
- 數組的第一個和最后一個元素做特殊處理胯努，他們的data不存放數據
- 通常把未使用的數組元素成為備用鏈表
- 數組的第一個元素昼牛，即下標為0的那個元素的cur就存放備用鏈表的第一個結點的下標
- 數組的最后一個元素，即下標為MAXSIZE-1的cur則存放第一個有數值的元素的下標康聂，相當于單鏈表中的頭結點作用
2.獲取靜態(tài)鏈表的長度
int ListLength(StaticLinkList L){
//獲取第一個有值結點的下標 如果沒有有值的結點贰健，那么i是0
int i = L[MAXSIZE-1].cur;
int sum = 0;
while (i > 0) {
sum++;
//一直遍歷，因為最后一個有值結點的游標一定是0
i = L[i].cur;
}
return sum;
}
3.靜態(tài)鏈表獲取操作
Status GetElem(StaticLinkList L,int i,ElemType *e){
//超出范圍 直接報錯
if (i < 0 || i > ListLength(L)) {
return ERROR;
}
//獲取第一個有值結點的下標 如果沒有有值的結點恬汁，那么i是0
int j = L[MAXSIZE-1].cur;
//空表直接返回錯誤
if (j == 0) {
return ERROR;
}
int order = 1;
//不斷遍歷伶椿，獲取到第i個位置的下標
while (order < i) {
order++;
j = L[j].cur;
}
//返回值
*e = L[j].data;
return OK;
}
4.靜態(tài)鏈表的插入操作
靜態(tài)鏈表中要實現元素的插入，需要解決的是:如何用靜態(tài)模擬動態(tài)鏈表結構的存儲空間分配氓侧，也就是需要的時候申請脊另，不需要的時候釋放
在動態(tài)鏈表中，結點的申請和釋放分別借用C語言的malloc()和free()兩個函數來實現
在靜態(tài)鏈表中约巷，操作的是數組偎痛，不存在像動態(tài)鏈表的結點申請和釋放的問題，所以我們需要自己實現這兩個函數独郎，才可以做到插入和刪除操作踩麦。
另外，我們需要辨明數組中哪些分量未被使用氓癌，解決的方法是講所有未被使用過的及已被刪除的分量用游標鏈成一個備用的鏈表谓谦，每當進行插入時，便可以從備用鏈表上取得第一個節(jié)點作為待插入的新結點贪婉，如圖所示反粥，我們要在A后面插入B：
//獲取空閑分量的下標
int Malloc_SLL(StaticLinkList L)
{
int i = L[0].cur;
if (i != 0) {
//如果不是空鏈表,那么把備用鏈表的下一個分量作為備用鏈表的起始
L[0].cur = L[i].cur;
}
//返回獲取到的下標
return i;
}
Status ListInsert(StaticLinkList L,int i,ElemType e){
if (i < 1 || i < ListLength(L)) {
return ERROR;
}
//獲取備用鏈表的第一個分量下標
int j = Malloc_SLL(L);
//如果備用鏈表的第一個分量下標為0，表示鏈表已滿疲迂，返回錯誤
if (j == 0) {
return ERROR;
}
//賦值
L[j].data = e;
//獲取鏈表的第一個分量的下標
int k = L[MAXSIZE-1].cur;
int order = 1;
//不斷遍歷才顿，獲取到第i-1個分量的下標
while (order < i-1) {
order++;
k = L[k].cur;
}
L[j].cur = L[k].cur;
L[k].cur = j;
return OK;
}
5.靜態(tài)鏈表的刪除操作操作
刪除如圖示：
刪除操作我們需要實現Free()函數，在調用Free()函數之前尤蒿，將刪除位置直接前驅結點的游標指向刪除位置直接后繼結點郑气。
//釋放結點
void Free_SLL(StaticLinkList space,int k){
//讓此結點游標指向備用鏈表的開始結點
space[k].cur = space[0].cur;
//備用鏈表的頭指針指向此結點
space[0].cur = k;
}
Status ListDelete(StaticLinkList L,int i,ElemType *e)
{
if (i < 1 || i > ListLength(L)) {
return ERROR;
}
//獲取鏈表的第一個分量的下標
int j = L[MAXSIZE-1].cur;
if (j == 0) {
return ERROR;
}
int order = 1;
//通過遍歷，獲取到第i-1個元素的下標
while (order < i - 1) {
order++;
j = L[j].cur;
}
//k就是第i個結點的下標
int k = L[j].cur;
L[j].cur = L[k].cur;
Free_SLL(L, k);
return OK;
}
6.靜態(tài)鏈表優(yōu)缺點總結
.優(yōu)點
— 在插入和刪除操作時优质，只需要修改游標竣贪，不需要移動元素，從而改進了在順序存儲結構中的插入和刪除操作需要移動大量元素的缺點
.缺點
— 沒有解決連續(xù)存儲分配(數組)帶來的表長難以確定的問題
— 失去了順序存儲結構隨機存取的特性
.總的來說巩螃，靜態(tài)鏈表其實是為了給沒有指針的編程語言設計的一種實現單鏈表功能的方法
.盡管我們可以用單鏈表就不用靜態(tài)鏈表了演怎，但這樣的思考方式是非常巧妙的，應該理解其思想避乏，以備不時之需
