資料結構教材實作：靜態鏈表（游標實作鏈表）

資料結構教材實作：靜態鏈表（游標實作鏈表）

核心概念

靜態鏈表以陣列模擬動態記憶體管理，用整數游標取代指標，在不支援指標的語言（如早期 BASIC、Fortran）或嵌入式環境極具價值。它結合了順序表的隨機存取與鏈表的彈性插刪。

儲存結構與機制示意

型別定義 (StaticLinkedList.h)

#define MAXSIZE 100
typedef int ElemType;
typedef struct { ElemType data; int cur; } Component;
typedef Component StaticLinkList[MAXSIZE];

此處巧用 typedef 將整個結構陣列定義為新型別 StaticLinkList，簡化參數傳遞。

關鍵操作：空間分配與回收

int Malloc_SLL(StaticLinkList space) {
    int i = space[0].cur;  // 備用鏈表首節點
    if (i) space[0].cur = space[i].cur;
    return i;  // 返回可用索引，0 表示滿
}

void Free_SLL(StaticLinkList space, int k) {
    space[k].cur = space[0].cur;
    space[0].cur = k;  // 歸還備用鏈表頭部
}

插入與刪除操作

插入：先 Malloc_SLL 取得索引，填入資料，修改前驅游標指向新節點，新節點游標指向原後繼。
刪除：修改前驅游標跳過被刪節點，呼叫 Free_SLL 回收索引。

測試結果

教學價值

靜態鏈表揭示了動態記憶體分配器（malloc/free）的內部原理：維護一個空閒塊鏈表，分配時摘除，釋放時歸還。是理解作業系統記憶體管理的絕佳切入點。