靜態鏈表完整實現：帶空間檢測的插入刪除遍歷（C語言）

編輯：關於C語言

靜態鏈表完整實現：帶空間檢測的插入刪除遍歷（C語言）

靜態鏈表用數組模擬鏈表，結構體包含 data 和 cur（游標/下標）。本文實現帶剩余空間判斷的完整操作集：初始化、插入、刪除、求長、遍歷顯示，並附帶交互式測試主程序。

數據結構設計

#define MAXSIZE 7
typedef int ElemType;

typedef struct {
    ElemType data;
    int cur;        // 下一個節點下標，0 表示空
} StaticList;

StaticList L[MAXSIZE];

L[0].cur：備用鏈表頭，指向第一個空閒下標。
L[MAXSIZE-1].cur：數據鏈表頭，指向第一個有效數據下標。
數據節點下標範圍：1 ~ MAXSIZE-2。

核心操作實現

初始化

void InitList(StaticList *space) {
    for (int i = 0; i < MAXSIZE-1; i++) {
        space[i].data = 0;
        space[i].cur = i+1;      // 串聯備用鏈表
    }
    space[MAXSIZE-1].cur = 0;    // 數據鏈表為空
    space[MAXSIZE-1].data = 0;
}

分配節點 `Malloc_SL`

int Malloc_SL(StaticList *space) {
    int i = space[0].cur;        // 取第一個空閒
    if (space[0].cur) space[0].cur = space[i].cur; // 從備用鏈摘除
    return i;                    // 返回下標，0 表示滿
}

釋放節點 `Free_SL`

void Free_SL(StaticList *space, int k) {
    space[k].cur = space[0].cur; // 插入備用鏈表頭
    space[0].cur = k;
}

插入 `ListInsert(L, i, e)`

檢查位置合法性：1 <= i <= ListLength(L)+1。
檢查空間：ListLength(L) >= MAXSIZE-2 則滿。
分配節點，填數據，修改前驅 cur 指向新節點，新節點 cur 指向原後繼。

刪除 `ListDelete(L, i)`

檢查位置合法性：1 <= i <= ListLength(L)。
找到前驅，修改 cur 跳過被刪節點，釋放節點歸還備用鏈。

遍歷顯示 `show(L)`

打印數組下標、data、cur 三行，再按鏈表順序輸出 data->data->^ 形式。

交互式測試主程序

int main() {
    StaticList L[MAXSIZE];
    InitList(L);
    int choice, x, pos;
    while (1) {
        printf("1:插入 2:刪除 3:輸出 0:退出\n");
        scanf("%d", &choice);
        if (choice == 0) break;
        switch (choice) {
            case 1:
                printf("輸入要插入的數字和位置\n");
                scanf("%d %d", &x, &pos);
                ListInsert(L, pos, x);
                break;
            case 2:
                printf("輸入要刪除的位置\n");
                scanf("%d", &pos);
                ListDelete(L, pos);
                break;
            case 3:
                show(L);
                break;
        }
    }
    return 0;
}

優勢總結

特性	動態鏈表	靜態鏈表
內存分配	malloc/free 頻繁調用	數組預分配，O(1) 分配釋放
空間檢測	malloc 失敗才知	`Malloc_SL` 返回 0 即滿
適用場景	長度不確定、頻繁增刪	嵌入式、長度有上限、實時系統