靜態(tài)鏈表

對(duì)于沒(méi)有指針的語(yǔ)言，通過(guò)數(shù)組表示鏈表，數(shù)組每個(gè)元素由data和cur組成。data保存數(shù)組元素?cái)?shù)據(jù)，cur相當(dāng)于next，用于保存下一個(gè)數(shù)組元素下標(biāo)。

靜態(tài)鏈表

靜態(tài)鏈表結(jié)構(gòu)的代碼表示

#define MAX_SIZE 1000
typedef int ElemType;
typedef struct {
    ElemType data;
    int cur;
}Component, StaticLinkList[MAX_SIZE];

靜態(tài)鏈表的初始化

void InitLinkList (StaticLinkList space) {
    int i;
    for(int i = 0; i < MAX_SIZE; i++){
        space[i].cur = i + 1;
    }
    space[i - 1].cur = 0;//0表示無(wú)指向

}

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

需要模擬動(dòng)態(tài)分配內(nèi)存。
因此還需要準(zhǔn)備一個(gè)備用鏈表，用于存放空的和已經(jīng)刪除的位置，每次需要插入時(shí)則選取備用列表的第一個(gè)位置所記錄的位置進(jìn)行插入。

模擬動(dòng)態(tài)分配內(nèi)存

int malloc_SLL(StaticLinkList space) {
    int i = space[0].cur;//第一個(gè)元素的備用空閑的下標(biāo)
    if (space[0].cur)
    {
        space[0].cur = space[i].cur;//拿出她的下一個(gè)cur作為備用
    }
    return i;
}

插入

int ListLength(StaticLinkList array)
{
    int i = array[MAX_SIZE - 1].cur;
    int j = 0;
    while (i)
    {
        i = array[i].cur;
        ++j;
    }
    return j;
}

void ListInsert(StaticLinkList L, int i, ElemType e){
    int j, k, l;
    k = MAX_SIZE - 1;
    if (i<1 || i > ListLength(L) + 1)
        exit(0);
    j = malloc_SLL(L);
    if (j) {
        L[j].data = e;
        for (l = 1; 1 <= i - 1; l++) {
            k = L[k].cur;
        }
        L[j].cur = L[k].cur;
        L[k].cur = j;
    }
    else
    {
        exit(0);
    }
}

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

void ListDelete(StaticLinkList L, int i) {
    int j, k;
    if (i < 1 || i > ListLength(L))
    {
        exit(0);
    }
    k = MAX_SIZE - 1;
    for (j = 1; j <- i-1; j++)
    {
        k = L[k].cur;
    }
    j = L[k].cur = L[j].cur;
    Free_SSL(L, j);

}

void Free_SSL(StaticLinkList space, int k) {
    space[k].cur = space[0].cur;
    space[0].cur = k;
}