C 語言實作單向鏈結串列：完整資料結構教學與原始碼解析

前言

鏈結串列是資料結構中的核心主題，相較於陣列，它能動態配置記憶體、彈性插入刪除。本文提供一份完整、可編譯執行的 C 語言單向鏈結串列實作，涵蓋初始化、銷毀、清空、查詢、插入、刪除、建立、列印、反轉等核心操作，並附上詳細註解與邏輯解析。

核心資料結構定義

#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW   -2

typedef int ElemType;
typedef int Status;

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

採用帶頭節點的單向鏈結串列設計，頭節點不存放資料，僅作為起始標記，簡化邊界條件處理。

主要功能函式詳解

1. 初始化串列 InitList()

LinkList InitList() {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    if (!L) {
        printf("***** Init Link list failed ! **** \n");
        exit(OVERFLOW);
    }
    L->next = NULL;
    printf("Init Link list ...\n");
    return L;
}

配置頭節點記憶體，next 指向 NULL 代表空串列。

2. 銷毀串列 DestoryList()

void DestoryList(LinkList L) {
    LinkList p = L;
    while (p) {
        L = p->next;
        free(p);
        p = L;
    }
}

從頭節點開始逐一釋放所有節點記憶體，包含頭節點本身。

3. 清空串列 ClearList()

void ClearList(LinkList L) {
    LinkList p = L->next;
    while (p) {
        L->next = p->next;
        free(p);
        p = L->next;
    }
    printf("clear list done !\n");
}

保留頭節點，僅釋放所有資料節點。

4. 判斷空串列 ListEmpty()

Status ListEmpty(LinkList L) {
    if (L->next == NULL) {
        printf("Link is empty !\n");
        return TRUE;  // 此處邏輯：空返回 TRUE
    }
    return FALSE;
}

5. 取得串列長度 ListLength()

int ListLength(LinkList L) {
    int i = 0;
    LinkList p = L->next; // 跳過頭節點
    while (p) {
        p = p->next;
        i++;
    }
    return i;
}

6. 按位置查詢元素 GetElem_L()

Status GetElem_L(LinkList L, int i, ElemType *e) {
    int j = 1;
    LinkList p = L->next; // 第 1 個資料節點
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) return ERROR;
    *e = p->data;
    printf("node %d value : %d\n", i, *e);
    return OK;
}

7. 按值查找位置 LocateElem()

int LocateElem(LinkList L, ElemType e) {
    LinkList p = L->next;
    int i = 1;
    while (p && p->data != e) {
        p = p->next;
        i++;
    }
    if (p) {
        printf("system has found %d in %d node !\n", e, i);
        return i;
    }
    printf("%d is not in Link List !\n", e);
    return 0;
}

8. 尋找前驅節點 PriorElem()

int PriorElem(LinkList L, ElemType cur, ElemType *pre) {
    LinkList p = L->next, q = p;
    if (!p) { printf("link list is empty, no Prior !\n"); exit(-1); }
    while (p->next && p->next->data != cur) p = p->next;
    if (p->next && p->next->data == cur) {
        *pre = p->data;
        printf("prior node value = %d\n", *pre);
    }
    return OK;
}

9. 插入節點 ListInsert_L()

Status ListInsert_L(LinkList L, int i, ElemType e) {
    int j = 1;
    LinkList p = L->next;
    while (p && j < i-1) { p = p->next; j++; }
    if (!p || j > i-1) return ERROR;
    LinkList q = (LinkList)malloc(sizeof(LNode));
    if (!q) return OVERFLOW;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return OK;
}

10. 刪除節點 ListDelete_L()

Status ListDelete_L(LinkList L, int i, ElemType *e) {
    int j = 1;
    LinkList p = L->next;
    while (p && j < i-1) { p = p->next; j++; }
    if (!p || j > i-1) return ERROR;
    LinkList q = p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK;
}

11. 建立串列（尾插法）CreateList_L()

void CreateList_L(LinkList L) {
    int len, e, i, j;
    LinkList p, q = L;
    q->next = NULL;
    printf("please input List len = ");
    scanf("%d", &len);
    for (i = len; i > 0; --i) {
        j = len - i + 1;
        p = (LinkList)malloc(sizeof(LNode));
        if (!p) exit(OVERFLOW);
        printf("please input data for Link list %d: ", j);
        scanf("%d", &e);
        p->data = e;
        q->next = p;
        p->next = NULL;
        q = p;
    }
}

尾插法可保持輸入順序與串列順序一致。

12. 列印串列 Print()

void Print(LinkList L) {
    int i = 1;
    LinkList p = L->next;
    while (p) {
        printf("\n##### No.%d value : %d ####", i, p->data);
        p = p->next;
        i++;
    }
    printf("\n");
}

13. 反轉串列 InvertLink()

void InvertLink(LinkList L) {
    LinkList p = L->next, s;
    L->next = NULL;
    while (p) {
        s = p;
        p = p->next;
        s->next = L->next;
        L->next = s;
    }
}

採用「頭插法」重建串列，原地反轉，空間複雜度 O(1)。

主程式測試流程

int main(void) {
    LinkList S = InitList();
    CreateList_L(S);
    Print(S);
    
    int e;
    GetElem_L(S, 3, &e);
    printf("e : %d\n", e);
    
    int len = ListLength(S);
    printf("List length = %d \n", len);
    
    // 可解開註解測試插入、刪除、反轉等功能
    // ListInsert_L(S, 3, 34); Print(S);
    // InvertLink(S); Print(S);
    
    return 0;
}

學習重點總結

進階建議：嘗試實作雙向鏈結串列、循環鏈結串列，或將 ElemType 改為 void* 實現泛型容器。