對于線性鏈表可用一維數(shù)組來進行描述，這種描述方法便于在沒有指針類型的高級程序設(shè)計語言中使用鏈表結(jié)構(gòu)，即使用數(shù)組描述的鏈表稱為靜態(tài)鏈表。由于全局?jǐn)?shù)組是存儲在靜態(tài)區(qū)也叫做靜態(tài)鏈表。

C語言具有指針能力使其非常容易地操作內(nèi)存中的地址和數(shù)據(jù)，對于面向?qū)ο蟮恼Z言雖然不使用指針，但因為啟用了對象引用機制，從某種角度也間接實現(xiàn)了指針的某些作用。但對于早期的編程語言，由于沒有指針，鏈表結(jié)構(gòu)等也就無法實現(xiàn)了，怎么辦呢？于是，就有了使用數(shù)組來代替指針來描述單鏈表。使用數(shù)組描述的鏈表叫做靜態(tài)鏈表（static list），又稱為游標(biāo)實現(xiàn)法。

動態(tài)鏈表

靜態(tài)鏈表和動態(tài)鏈表是線性表鏈?zhǔn)酱鎯Φ膬煞N不同的表示方式。

• 在動態(tài)鏈表中，節(jié)點的申請和釋放分別使用內(nèi)存申請函數(shù)，如C語言的malloc()和free()兩個函數(shù)實現(xiàn)。所以鏈表長度沒有限制。由于是動態(tài)申請內(nèi)存，所以每個節(jié)點的物理地址不連續(xù)，要通過指針來順序訪問。
• 在靜態(tài)鏈表中，操作的是數(shù)組，不存在像動態(tài)鏈表的節(jié)點申請和釋放問題，所以需要自己實現(xiàn)這兩個函數(shù)，才可以做插入和刪除操作。靜態(tài)鏈表使用類似于數(shù)組方法實現(xiàn)，是順序的存儲結(jié)構(gòu)，在物理上是連續(xù)的，且需要預(yù)先分配地址空間大小，所以靜態(tài)鏈表的初始長度一般是固定的，在做插入和刪除操作時不需要移動元素，僅需要修改指針。

靜態(tài)鏈表原理

一個數(shù)組的邏輯分為兩部分：空閑鏈表部分和非空閑鏈表部分，它們通過指針來連接，空閑鏈表由空閑頭節(jié)點連接起來，非空閑鏈表由非空閑頭節(jié)點連接起來?？臻e鏈表本質(zhì)上是作為需要管理的內(nèi)存，當(dāng)插入節(jié)點時，向管理的內(nèi)存部分申請空間。當(dāng)刪除節(jié)點時，向管理的內(nèi)存部分釋放內(nèi)存。

空閑鏈表

• 下標(biāo)為0的節(jié)點是空閑鏈表的頭節(jié)點
• 下標(biāo)為1的節(jié)點是非空閑鏈表的頭節(jié)點

首先，讓數(shù)組的元素由兩個數(shù)據(jù)域組成，data和cursor。即數(shù)組的每個下標(biāo)都對應(yīng)一個data和一個cursor。數(shù)據(jù)域data用來存放數(shù)據(jù)元素，游標(biāo)cursor相當(dāng)于單鏈表中的next指針，存放元素后繼在數(shù)組中的下標(biāo)。

/*線性表的靜態(tài)鏈表存儲結(jié)構(gòu)*/
#define MAXSIZE 1000

typedef struct
{
    ElemType data;//數(shù)據(jù)域
    int cursor;//游標(biāo)，為0表示無指向。
} Component, StaticLinkList[MAXSIZE];

StaticLinkList space;

結(jié)構(gòu)體數(shù)組中，space[0]作為備用鏈表的頭指針，space[1]作為鏈表的頭指針。

結(jié)構(gòu)體數(shù)組

初始化數(shù)組狀態(tài)

• 對數(shù)組第一個和最后一個元素作為特殊元素處理，不存數(shù)據(jù)。
• 把未被使用的數(shù)組元素稱為備用鏈表
• 數(shù)組第一個元素即下標(biāo)為0的元素的cursor就存放備用鏈表的第一個節(jié)點的下標(biāo)
• 數(shù)組最后一個元素的cursor則存放第一個有數(shù)值的元素的下標(biāo)，相當(dāng)于單鏈表中的頭節(jié)點作用。
• 當(dāng)整個鏈表為空時則為O^2

image.png

游標(biāo)實現(xiàn)法

線性表的靜態(tài)鏈表

/**
 * 將一維數(shù)組space中各分量鏈成一備用鏈表
 * space[0].cursor 為頭指針，0表示空指針。
 */
Status InitList(StaticLinkList space)
{
    int i;
    for(i=0; i<MAXSIZE; i++){
        space[i].cursor = i+1;
    }
    //靜態(tài)鏈表為空，最后一個元素的游標(biāo)為0
    space[MAXSIZE-1].cursor = 0;
    return OK;
}

假設(shè)已經(jīng)將數(shù)據(jù)存入靜態(tài)鏈表，比如分別存放甲乙丙丁午己庚等數(shù)據(jù)。

靜態(tài)鏈表

存放數(shù)據(jù)

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

靜態(tài)鏈表如何模擬單鏈表進行插入和刪除操作呢？靜態(tài)鏈表要解決的是：如何用靜態(tài)鏈表模擬動態(tài)鏈表結(jié)構(gòu)的存儲空間分配，也就是需要的時候申請，不需要的時候釋放。

為了辨明數(shù)組中那些分量未被使用，解決的辦法是將所有未被使用過的及已被刪除的分量用游標(biāo)鏈成一個備用的鏈表，每當(dāng)進行插入時，便可以從備用鏈表上取得第一個節(jié)點作為待插入的新節(jié)點。

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

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

獲得空閑分量的下標(biāo)

/**
 * 辨明數(shù)組中那些分量未被使用，解決的辦法是將所有未被使用多的及已被刪除的分量用游標(biāo)鏈成一個備用的鏈表。
 * 每當(dāng)進行插入時，便可以從備用鏈表上取得第一個節(jié)點作為待插入的新節(jié)點。
 */
int MallocSLL(StaticLinkList space)
{
    int i = space[0].cursor;//當(dāng)前數(shù)組第一個元素的游標(biāo)，即第一個備用空閑的下標(biāo)。
    //若備用空間鏈表非空則返回分配的節(jié)點的下標(biāo)否則返回0
    if(space[0].cursor){
        //將下一個分量用來做備用
        space[0].cursor = space[i].cursor;
    }
    return i;
}

在靜態(tài)鏈表某個元素之前插入新元素

Status InsertSLL(StaticLinkList L, int i, ElemType e)
{   
    int j,k,l;
    //邊界檢查
    if(i<1 || i>ListLength(L)+1){
        return ERROR;
    }
    //獲得空閑分量的下標(biāo)
    int j = MallocSSL(L);
    if(j){
        //將數(shù)據(jù)賦值給此分量的數(shù)據(jù)域
        L[j].data = e;
        //找到第i個元素之前的位置
        k = MAXSIZE - 1;//最后一個元素
        for(l=1; l<=i-1; l++){
            k = L[k].cursor;
        }
        //將第i個元素之前的游標(biāo)值賦值給新元素的游標(biāo)
        L[j].cursor = L[k].cursor;
        //將新元素的下標(biāo)賦值給地i個元素之前的元素的游標(biāo)
        L[k].cursor = j;
        return OK;
    }
}

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