對于線性鏈表，也可用一維數(shù)組來進行描述。這種描述方法便于在沒有指針類型的高級程序設計語言中使用鏈表結(jié)構(gòu)。用數(shù)組描述的鏈表，即稱為靜態(tài)鏈表。

靜態(tài)鏈表示意圖

線性表的靜態(tài)鏈表存儲結(jié)構(gòu)

#define MAXSIZE 1000
typedef struct{
  ElemType data;//數(shù)據(jù)
  int cur;//游標(Cursor)
}Component,StaticLinkList[MAXSIZE]

靜態(tài)鏈表進行初始化相當于初始化數(shù)組

Status InitList(StaticLinkList space){
  int I;
  for(I = 0;i < MAXSIZE - 1;I++){
   space[I].cur = I+1;
   space[MAXSIZE-1].cur = 0;
   return OK;
  }
}

說明

• 對數(shù)組的第一個和最后一個元素做特殊處理,他們的data不存放數(shù)據(jù)
• 我們通常把未使用的數(shù)組元素稱為備用鏈表
• 數(shù)組的第一個元素,即小標為0的那個元素的cur就存放備用鏈表的第一個結(jié)點的下標
• 數(shù)組的最后一個元素,即下標為MAXSIZE-1的cur則存放第一個有數(shù)值的元素的下標,相當于單鏈表中頭結(jié)點作用

• 最后一個數(shù)據(jù)的游標指向0 ;!!!圖片有誤

  
  

靜態(tài)鏈表中主要解決的是:如何用靜態(tài)模擬動態(tài)鏈表結(jié)構(gòu)的存儲空間分配,也就是需要的時候申請,不需要的時候釋放.
在動態(tài)鏈表中,結(jié)點申請和釋放分別借用C語言的malloc()和free()兩個函數(shù)來實現(xiàn)
在靜態(tài)鏈表中,操作的是數(shù)組,不存在像動態(tài)鏈表的結(jié)點申請和釋放的問題,所以需要自己實現(xiàn)這兩個函數(shù),才可以做到插入和刪除的操作

靜態(tài)鏈表的插入操作

為了辨明數(shù)組中哪些分量未被使用,解決的方法是將所有未被使用過的及已被刪除的分量用游標鏈成一個備用的鏈表
每當進行插入時,便可以從備用鏈表上取得第一個結(jié)點作為待插入的新結(jié)點,這里假設在A后邊插入B

代碼實現(xiàn)

• 首先是獲取空閑分量的下標

int Malloc_SLL(StaticLinkList space){
  int I space[0].cur;
  if(space[0].cur)
  space[0].cur = space[I].cur;//把它的下一個分量用來作為備用
  return i;   
}

Status ListInsert( StaticLinkList L, int I, ElemType e){
 
 int j ,k,l;
 k = MAX_SIZE - 1;
 if(I <1 || I> ListLength(L) + 1){
 return ERROR
 }
 
 j  = Malloc_SLL(L);

if(j){
  L[j].data = e;
for(l = 1; l <= I-1;l++){
  k = L[k].cur;
  L[j].cur = L[k].cur;
  L[k].cur = j;
  return OK;
} 
  return ERROR;
}
}

靜態(tài)鏈表的刪除操作

Status ListDelete(StaticLinkList L , int i){

 int j ,k;

 if(I <1 || I> ListLength(L)){
 return ERROR
 }
 k = MAX_SIZE - 1;

for (j = 1;j <= I-1;j++){
  
  k =L[k].cur;

}
j = L[k].cur;
L[k].cur = L[j].cur;
Free_SLL(L,j);
return OK
}

//將小標為k的空閑結(jié)點回收到備用鏈表
void Free_SLL (StaticLinkList space ,int k){

  space[k].cur = space[0].cur;
  space[0].cur = k;
}

// 返回L中數(shù)據(jù)元素個數(shù)
int ListLength(StaticLinkList L){

int j = 0;
int I = L[MAXSIZE - 1].cur;
while(i){
   
  I = L[I].cur;
  j++;
  
}
return j;

}

靜態(tài)鏈表

優(yōu)點:在插入和刪除操作時,只需要修改游標,不需要移動元素,從而改進了在順序存儲結(jié)構(gòu)中的插入和刪除操作需要移動大量元素的缺點

缺點:
沒有解決連續(xù)存儲分配(數(shù)組)帶來的表長難以確定的問題
失去了順序存儲結(jié)構(gòu)隨機存取的特征

總的來說,靜態(tài)鏈表其實是為了給沒有指針的編程語言設計的一種實現(xiàn)單鏈表共的方法,一般情況我們可以用單鏈表就不用靜態(tài)鏈表了

面試題:如何快速找到未知長度單鏈表的中間節(jié)點

普通方法:首先遍歷一遍單鏈表以確定單鏈表的長度L.然后再次從頭結(jié)點出發(fā)循環(huán)L/2次找到單鏈表的中間節(jié)點 ; 算法復雜度為:O(L+L/2) = O(3L/2)

利用快慢指針原理實現(xiàn): 設置兩個指針 search mid 都是指向單鏈表的頭結(jié)點 其中search的移動速度是mid 的2倍. 當*search指向末尾結(jié)點時候mid正好就在中間了.這也是標尺的思想

 Status GetMIdNode(LinkList L, ElemType *e){
  LinkList search,mid;
  mid = search =L
  while(search->next ! = NULL){
    
    if(search->next->next != NULL){
     search = search->next->next;
     mid = mid->next;
    }else{
     search = search->next;
    }

 }

*e = mid->data;
return OK;
}