資料結構筆記：靜態鏈表（C 語言實作）

緣起

動態鏈表靠 malloc/free 向系統申請/釋放記憶體，靈活但有管理開銷。靜態鏈表則在固定大小的陣列中模擬「申請」與「釋放」，適合嵌入式或不支援動態記憶體的環境。

核心設計

1. 節點結構

#define MAXSIZE 1000
typedef int ElemType;

typedef struct {
    ElemType data;  // 資料域
    int cur;        // 指標域：儲存下一個節點的陣列索引
} StaticLinkList;

2. 陣列佈局

• List[0]：備用鏈表頭，cur 指向第一個空閒節點索引。
• List[MAXSIZE-1]：資料鏈表頭，cur 指向第一個有效資料節點索引（0 表空）。
• List[1] ~ List[MAXSIZE-2]：實際資料與備用節點共用區。

3. 初始化：建構備用鏈表

void CreateList(StaticLinkList *L) {
    for (int i = 0; i < MAXSIZE - 1; ++i)
        L[i].cur = i + 1;          // 串成 1→2→3→…→MAXSIZE-1
    L[MAXSIZE - 1].cur = 0;        // 資料鏈表為空
}

4. 申請節點（模擬 malloc）

int Malloc_SLL(StaticLinkList *L) {
    int i = L[0].cur;              // 取得第一個空閒索引
    if (i) L[0].cur = L[i].cur;    // 備用鏈表頭前移
    return i;                      // 0 表示已無空間
}

5. 釋放節點（模擬 free）

void Free_SLL(StaticLinkList *L, int k) {
    L[k].cur = L[0].cur;           // 將釋放節點插入備用鏈表頭
    L[0].cur = k;
}

6. 插入與刪除

插入時先呼叫 Malloc_SLL 取得索引，再修改前驅節點的 cur；刪除時先將目標節點從資料鏈表摘除，再呼叫 Free_SLL 歸還備用區。遍歷則從 List[MAXSIZE-1].cur 起沿 cur 走訪。

完整範例程式

#include <stdio.h>
#define MAXSIZE 1000
typedef int ElemType;
typedef struct { ElemType data; int cur; } StaticLinkList;

StaticLinkList L[MAXSIZE];

void CreateList(StaticLinkList *L) { /* ... */ }
int Malloc_SLL(StaticLinkList *L) { /* ... */ }
void Free_SLL(StaticLinkList *L, int k) { /* ... */ }
void ListInsert(StaticLinkList *L, int pos, ElemType val) { /* ... */ }
void ListDelete(StaticLinkList *L, int pos) { /* ... */ }
void PrintList(StaticLinkList *L) { /* ... */ }

int main() {
    CreateList(L);
    ListInsert(L, 1, 10);
    ListInsert(L, 2, 20);
    ListInsert(L, 2, 15);   // 10, 15, 20
    PrintList(L);
    ListDelete(L, 2);       // 刪除 15
    PrintList(L);
    return 0;
}

優缺點總結

靜態鏈表以空間換時間，是資料結構教學與資源受限系統的經典選擇。