C語言非循環單鏈表遍歷算法完整教程與代碼實現

編輯：關於C語言

前言

鏈表是數據結構中的基石，非循環單鏈表作為最基礎的鏈表形式，其遍歷操作是所有鏈表算法的起點。本文從概念模型、遍歷邏輯、代碼實現、邊界處理到常見錯誤，全方位講解單鏈表遍歷，幫助初學者建立清晰的指鈈操作思維。

核心概念澄清

術語	定義	圖示位置
頭指針	指向鏈表第一個節點（頭節點）的指針變量	`PNODE pHead`
頭節點	不存儲有效數據的哨兵節點，便於統一空表/非空表操作	數據域無意義，指針域指向首元節點
首元節點	鏈表中第一個存儲有效數據的節點	`pHead->next`
尾元節點	最後一個有效節點，指針域為 `NULL`	標誌鏈表結束

遍歷算法邏輯

初始化：定義工作指針 p，指向首元節點 p = pHead->next。
循環條件：當 p != NULL 時繼續，NULL 表示已越過尾元節點。
訪問數據：處理當前節點數據域 p->data（打印、累加、查找等）。
推進指針：p = p->next 移動到下一個節點。
結束：p 變為 NULL，循環退出。

完整可運行代碼 (C99 標準)

#include <stdio.h>
#include <stdlib.h>

// 節點結構定義
typedef struct Node {
    int data;
    struct Node *next;
} Node, *PNode;

// 函數聲明
PNode create_list(void);
void traverse_list(PNode head);
void free_list(PNode head);

int main(void) {
    PNode head = create_list();
    printf("鏈表遍歷結果：");
    traverse_list(head);
    free_list(head);  // 釋放內存，良好習慣
    return 0;
}

// 頭插法/尾插法創建鏈表（此處演示尾插法）
PNode create_list(void) {
    int len, val;
    printf("請輸入節點個數: ");
    if (scanf("%d", &len) != 1 || len < 0) {
        fprintf(stderr, "輸入無效\n");
        exit(EXIT_FAILURE);
    }

    // 分配頭節點
    PNode head = (PNode)malloc(sizeof(Node));
    if (!head) { perror("頭節點分配失敗"); exit(EXIT_FAILURE); }
    head->next = NULL;
    PNode tail = head;

    for (int i = 0; i < len; ++i) {
        printf("第 %d 個節點值: ", i + 1);
        if (scanf("%d", &val) != 1) {
            fprintf(stderr, "輸入錯誤\n");
            free_list(head);
            exit(EXIT_FAILURE);
        }
        PNode new_node = (PNode)malloc(sizeof(Node));
        if (!new_node) { perror("節點分配失敗"); free_list(head); exit(EXIT_FAILURE); }
        new_node->data = val;
        new_node->next = NULL;
        tail->next = new_node;
        tail = new_node;
    }
    return head;
}

// 遍歷並打印
void traverse_list(PNode head) {
    PNode p = head->next;  // 跳過頭節點
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    putchar('\n');
}

// 釋放鏈表所有節點（含頭節點）
void free_list(PNode head) {
    PNode curr = head;
    while (curr) {
        PNode next = curr->next;
        free(curr);
        curr = next;
    }
}

運行示例

請輸入節點個數: 5
第 1 個節點值: 10
第 2 個節點值: 20
第 3 個節點值: 30
第 4 個節點值: 40
第 5 個節點值: 50
鏈表遍歷結果：10 20 30 40 50

關鍵細節與避坑指南

1. 空表處理

head->next == NULL 時，遍歷循環零次，直接打印換行，邏輯天然正確，無需額外判斷。

2. 指針推進順序

必須先保存 p->data 或完成處理，再執行 p = p->next。若先移動指針再訪問，會導致首元節點被跳過或訪問已釋放內存。

3. 內存洩漏預防

創建時每次 malloc 必須檢查返回值。
程序結束前調用 free_list 遞歸釋放所有節點。
刪除節點時：prev->next = curr->next; free(curr); 順序不可顛倒。

4. 常見錯誤示例

// 錯誤 1：未跳過頭節點，打印垃圾值
PNode p = head;  // 應為 head->next

// 錯誤 2：循環條件寫成 p->next != NULL，導致尾節點不被處理
while (p->next != NULL) { ... }

// 錯誤 3：遍歷中修改鏈表結構（如刪除當前節點）未保存 next 指針
while (p) {
    if (p->data == target) free(p);  // 危險！p 已失效
    p = p->next;  // 未定義行為
}
// 正確做法：
while (p) {
    PNode next = p->next;
    if (p->data == target) free(p);
    p = next;
}

進階：遍歷的通用框架化

實際項目中，可將遍歷邏輯封裝為通用迭代器模式：

// 回調函數類型
typedef void (*VisitFunc)(int data);

// 通用遍歷
void list_foreach(PNode head, VisitFunc visit) {
    for (PNode p = head->next; p; p = p->next) {
        visit(p->data);
    }
}

// 使用示例
void print_double(int x) { printf("%d ", x * 2); }
void sum_up(int x) { static int sum = 0; sum += x; printf("Sum: %d\n", sum); }

list_foreach(head, print_double);  // 輸出每個值的兩倍
list_foreach(head, sum_up);        // 累加求和