資料結構 C 語言實作：單向鏈表完整原始碼與詳解

編輯：關於C語言

前言

單向鏈表是資料結構入門的核心主題。本文提供一套完整、可編譯執行的 C 語言實作，包含標頭檔、函式庫與主程式，並詳細解析關鍵演算法（建立、插入、刪除、查詢、合併）與指標操作細節。

模組架構

declaration.h：型別定義、常數、結構體
function.h：介面宣告
function.c：核心演算法實作
main.c：測試驅動程式

核心原始碼

declaration.h

#ifndef DECLARATION_H_INCLUDED
#define DECLARATION_H_INCLUDED

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

typedef int ElemType;
typedef ElemType* Triplet;
typedef int Status;

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

#endif

function.h

#ifndef FUNCTION_H_INCLUDED
#define FUNCTION_H_INCLUDED

void CreateList_L(LinkList* L, int n);                    // 逆序建立帶頭節點單鏈表
Status ListInsert_L(LinkList* L, int i, ElemType e);      // 第 i 位置前插入
Status ListDelete_L(LinkList* L, int i, ElemType* e);     // 刪除第 i 個元素
Status GetElem_L(LinkList L, int i, ElemType* e);         // 取第 i 個元素值
Status MergeList_L(LinkList* La, LinkList* Lb, LinkList* Lc); // 歸併兩有序表
void PrintList_L(LinkList L);                             // 列印鏈表

#endif

function.c 關鍵演算法解析

1. 逆序建表 CreateList_L

void CreateList_L(LinkList* L, int n) {
    *L = (LinkList)malloc(sizeof(LNode));
    (*L)->next = NULL;
    for (int i = n; i > 0; --i) {
        LinkList p = (LinkList)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = (*L)->next;  // 头插法：新節點指向原第一個
        (*L)->next = p;        // 頭節點指向新節點
    }
}

重點：頭插法導致輸入順序與鏈表順序相反。若需正序，請使用尾插法（維護尾指標）。

2. 插入 ListInsert_L

Status ListInsert_L(LinkList* L, int i, ElemType e) {
    LinkList p = *L, s;
    int j = 0;
    while (p && j < i - 1) { p = p->next; ++j; } // 尋找第 i-1 個節點
    if (!p || j > i - 1) return ERROR;           // 位置非法
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;  // 先連後段
    p->next = s;        // 再連前段
    return OK;
}

核心：s->next = p->next; p->next = s; 兩步驟不可顛倒，否則斷鏈。

3. 刪除 ListDelete_L

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

4. 歸併有序表 MergeList_L

Status MergeList_L(LinkList* La, LinkList* Lb, LinkList* Lc) {
    LinkList pa = (*La)->next, pb = (*Lb)->next;
    *Lc = (LinkList)malloc(sizeof(LNode));
    LinkList pc = *Lc;
    while (pa && pb) {
        if (pa->data <= pb->data) {
            pc->next = pa; pc = pa; pa = pa->next;
        } else {
            pc->next = pb; pc = pb; pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb; // 連接剩餘段
    return OK;
}

技巧：直接重用原節點，無需新建，O(1) 空間複雜度。

main.c 測試驅動

int main() {
    ElemType e;
    LinkList *La = malloc(sizeof(LinkList));
    LinkList *Lb = malloc(sizeof(LinkList));
    LinkList *Lc = malloc(sizeof(LinkList));
    
    printf("Input 5 numbers for La: "); CreateList_L(La, 5);
    printf("La: "); PrintList_L(*La);
    printf("3rd elem: %d\n", GetElem_L(*La, 3, &e));
    printf("Deleted 1st: %d\n", ListDelete_L(La, 1, &e));
    printf("La after delete: "); PrintList_L(*La);
    
    printf("Input 4 numbers for Lb: "); CreateList_L(Lb, 4);
    printf("Lb: "); PrintList_L(*Lb);
    ListInsert_L(Lb, 2, 3);
    printf("Lb after insert 3 at pos2: "); PrintList_L(*Lb);
    
    if (MergeList_L(La, Lb, Lc) == OK) {
        printf("Merged Lc: "); PrintList_L(*Lc);
    }
    return 0;
}

指標傳遞深度解析

為何 CreateList_L 接受 LinkList* L（二級指標）？

C 語言參數為值傳遞。傳遞一級指標 LinkList L 只能修改節點內容，無法修改主調函數中的頭指標本身。
傳遞 LinkList* L，函數內透過 *L = malloc(...) 修改指標指向的記憶體位址，修改對主調可見。
同理 ListInsert_L、ListDelete_L 可能改變頭節點（如在位置 1 插入/刪除），故同樣需二級指標。

常見坑與避坑指南

野指標：MergeList_L 中忘記為 *Lc 配置記憶體，導致 pc 成野指標，程式崩潰。鐵律：指標使用前必須初始化。
記憶體洩漏：測試程式未釋放鏈表節點。生產代碼需提供 DestroyList_L 遞歸釋放所有節點。
邊界條件：插入/刪除位置 0、超過長度、空表操作均需防禦性檢查。
輸入緩衝：scanf("%d", &p->data) 留下換行符，後續 scanf("%c") 會讀到換行。建議統一用 fgets + sscanf。