資料結構教材實作：擴展線性鏈表歸並演算法

資料結構教材實作：擴展線性鏈表歸並演算法

背景

本範例在教材基礎單鏈表之上，引入尾指標與長度欄位，構成「擴展線性鏈表」，使尾部插入、長度查詢均為 O(1)，歸並效率進一步提升。

擴展結構定義 (ExtenLinkedList.c)

typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

typedef struct {
    LinkList head, tail;  // 頭、尾指標
    int len;              // 長度
} ExtList;

歸並核心邏輯 (MergeEList.c)

void MergeExtList(ExtList &La, ExtList &Lb, ExtList &Lc) {
    LinkList pa = La.head->next, pb = Lb.head->next;
    Lc.head = Lc.tail = (LinkList)malloc(sizeof(LNode));
    Lc.len = 0;
    while (pa && pb) {
        if (pa->data <= pb->data) {
            Lc.tail->next = pa; Lc.tail = pa; pa = pa->next;
        } else {
            Lc.tail->next = pb; Lc.tail = pb; pb = pb->next;
        }
        ++Lc.len;
    }
    Lc.tail->next = pa ? pa : pb;
    while (Lc.tail->next) { Lc.tail = Lc.tail->next; ++Lc.len; }
    free(Lb.head);  // 釋放 Lb 頭節點
}

測試資料與結果

• TestData_La.txt、TestData_Lb.txt：兩有序鏈表輸入資料

優勢總結

• 尾指標讓歸並過程無需額外掃描即可接上剩餘段
• 長度欄位即時維護，避免事後遍歷統計
• 介面封裝良好，便於上層邏輯複用

此模式廣泛應用於需要高效尾部操作的鏈表場景（如訊息佇列、日誌緩衝區）。