C 語言實現單鏈表核心操作完整指南

編輯：關於C語言

C 語言實現單鏈表核心操作完整指南

鏈表作為數據結構中的基石，其靈活的動態內存管理特性使其在演算法設計中佔據重要地位。本文將系統講解如何使用 C 語言實現單鏈表的各項基本操作，涵蓋節點定義、初始化、創建、遍歷、銷毀、長度計算、查找、修改、插入與刪除等核心功能，並提供完整可編譯的代碼示例。

一、節點結構定義

單鏈表的每個節點包含數據域與指針域。數據域存儲實際數據，指針域指向下一個節點。通過 typedef 簡化類型聲明，提升代碼可讀性。

typedef int ElemType;                 // 元素類型別名
typedef struct ListNode {
    ElemType element;                 // 數據域
    struct ListNode *next;            // 指針域
} Node;                               // 節點類型別名

二、鏈表初始化

初始化即將頭指針置為 NULL，表示空表。注意傳遞指針的指針或返回新頭指針，以便在調用處生效。

void initList(Node **pHead) {
    *pHead = NULL;
    printf("%s: 初始化成功\n", __FUNCTION__);
}

三、鏈表創建（尾插法）

採用尾插法依次讀取用戶輸入，直到遇到非正整數停止。動態分配節點內存，並維護尾指針實現 O(1) 尾部插入。

Node* createList(Node *pHead) {
    Node *pTail = NULL;
    ElemType val;
    printf("請輸入整數（輸入 0 或負數結束）：\n");
    while (scanf("%d", &val) == 1 && val > 0) {
        Node *newNode = (Node*)malloc(sizeof(Node));
        if (!newNode) { perror("內存分配失敗"); exit(EXIT_FAILURE); }
        newNode->element = val;
        newNode->next = NULL;

        if (!pHead) {
            pHead = newNode;          // 首節點
        } else {
            pTail->next = newNode;    // 尾部追加
        }
        pTail = newNode;              // 更新尾指針
    }
    printf("%s: 創建完成\n", __FUNCTION__);
    return pHead;
}

四、鏈表遍歷打印

從頭節點出發，順著 next 指針逐個訪問並打印數據域，直到遇到 NULL。

void printList(const Node *pHead) {
    if (!pHead) {
        printf("%s: 鏈表為空\n", __FUNCTION__);
        return;
    }
    while (pHead) {
        printf("%d ", pHead->element);
        pHead = pHead->next;
    }
    putchar('\n');
}

五、銷毀鏈表（釋放所有節點）

依次釋放每個節點佔用的內存，防止內存洩漏。釋放前需保存下一節點地址。

void clearList(Node **pHead) {
    Node *curr = *pHead;
    while (curr) {
        Node *next = curr->next;
        free(curr);
        curr = next;
    }
    *pHead = NULL;
    printf("%s: 鏈表已銷毀\n", __FUNCTION__);
}

六、獲取鏈表長度

遍歷計數，時間複雜度 O(n)。

int sizeList(const Node *pHead) {
    int len = 0;
    while (pHead) { ++len; pHead = pHead->next; }
    printf("%s: 長度 = %d\n", __FUNCTION__, len);
    return len;
}

七、判斷鏈表是否為空

int isEmptyList(const Node *pHead) {
    int empty = (pHead == NULL);
    printf("%s: %s\n", __FUNCTION__, empty ? "空表" : "非空");
    return empty;
}

八、按位置查找元素

位置從 1 開始計數。超出範圍或空表時給出提示。

void getElement(const Node *pHead, int pos) {
    if (pos < 1) { printf("位置非法\n"); return; }
    int i = 0;
    while (pHead && ++i < pos) pHead = pHead->next;
    if (!pHead) printf("位置超出長度\n");
    else printf("第 %d 個元素 = %d\n", pos, pHead->element);
}

九、按值查找節點地址

返回首個匹配值的數據域地址，未找到返回 NULL。

ElemType* getElemAddr(const Node *pHead, ElemType x) {
    while (pHead && pHead->element != x) pHead = pHead->next;
    if (!pHead) { printf("未找到值 %d\n", x); return NULL; }
    printf("值 %d 的地址 = %p\n", x, (void*)&pHead->element);
    return &pHead->element;
}

十、修改指定位置元素值

成功返回 1，失敗返回 0。

int modifyElem(Node *pHead, int pos, ElemType x) {
    if (pos < 1) return 0;
    int i = 0;
    while (pHead && ++i < pos) pHead = pHead->next;
    if (!pHead) return 0;
    pHead->element = x;
    return 1;
}

十一、頭插法插入節點

新節點成為新頭節點，需修改頭指針本身，故傳遞二級指針。

int insertHead(Node **pHead, ElemType x) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return 0;
    newNode->element = x;
    newNode->next = *pHead;
    *pHead = newNode;
    return 1;
}

十二、尾插法插入節點

遍歷至尾部追加，若原表為空則同頭插處理。

int insertTail(Node **pHead, ElemType x) {
    Node *newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) return 0;
    newNode->element = x;
    newNode->next = NULL;

    if (!*pHead) { *pHead = newNode; return 1; }
    Node *tail = *pHead;
    while (tail->next) tail = tail->next;
    tail->next = newNode;
    return 1;
}

十三、綜合測試主函數

int main(void) {
    Node *list = NULL;
    initList(&list);
    printList(list);

    list = createList(list);
    printList(list);
    sizeList(list);

    isEmptyList(list);
    getElement(list, 3);
    getElemAddr(list, 5);
    modifyElem(list, 4, 1);
    printList(list);

    insertHead(&list, 5);
    printList(list);
    insertTail(&list, 10);
    printList(list);

    clearList(&list);
    printList(list);
    return 0;
}

本文完整展示了單鏈表在 C 語言中的標準實現方式，代碼結構清晰、錯誤處理完善，適合作為數據結構學習與工程參考的基礎模板。