您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言基礎

C語言鏈表實戰：創建、刪除、插入與遍歷完整教程

編輯：C 語言基礎

前言

鏈表是動態數據結構的基石，掌握其增刪改查操作是 C 語言進階的必經之路。本文通過一個完整的學生信息管理案例，演示單向鏈表的創建、節點查找、刪除、插入與打印，並深度解析指針操作的內存邏輯。

數據結構定義

#define NULL 0
#define TYPE struct Stu
#define LEN sizeof(struct Stu)

struct Stu {
    int num;        // 學號
    int age;        // 年齡
    struct Stu *next; // 指針域，指向下一節點
};

核心操作函數

1. 創建鏈表 `creat`

TYPE *creat(int n) {
    TYPE *head = NULL, *pf = NULL, *pb = NULL;
    for (int i = 0; i < n; ++i) {
        pb = (TYPE *)malloc(LEN);           // 分配新節點
        printf("輸入學號和年齡：");
        scanf("%d%d", &pb->num, &pb->age);  // 填充數據域

        if (i == 0) {
            pf = head = pb;                 // 首節點：head 與 pf 同指向它
        } else {
            pf->next = pb;                  // 非首節點：前一節點指向當前
        }
        pb->next = NULL;                    // 當前節點指針域置空
        pf = pb;                            // pf 後移，備戰下一輪
    }
    return head;                            // 返回頭指針
}

關鍵點：pf（previous front）始終指向已建鏈表的尾節點，pb（previous back）指向新分配節點。循環結束時，head 指向首節點，鏈表串聯完畢。

2. 刪除節點 `delete`

TYPE *delete(TYPE *head, int num) {
    TYPE *pf = NULL, *pb = head;

    if (!head) { printf("\n空鏈表！\n"); return head; }

    // 尋找目標節點：pb 指向目標，pf 指向其前驅
    while (pb->num != num && pb->next != NULL) {
        pf = pb;
        pb = pb->next;
    }

    if (pb->num == num) {           // 找到
        if (pb == head) {
            head = pb->next;        // 刪除頭節點：head 後移
        } else {
            pf->next = pb->next;    // 刪除中間/尾節點：前驅跳過目標
        }
        free(pb);                   // 釋放內存
        printf("節點已刪除\n");
    } else {
        printf("未找到節點 %d\n", num);
    }
    return head;                    // 可能新頭指針
}

3. 插入節點 `insert`（按學號升序）

TYPE *insert(TYPE *head, TYPE *pi) {
    TYPE *pf = NULL, *pb = head;

    if (!head) {                    // 空鏈表
        head = pi;
        pi->next = NULL;
        return head;
    }

    // 尋找插入位置：pi->num <= pb->num 時插在 pb 前
    while (pi->num > pb->num && pb->next != NULL) {
        pf = pb;
        pb = pb->next;
    }

    if (pi->num <= pb->num) {       // 插在 pb 之前
        if (head == pb) {           // 插在頭部
            head = pi;
        } else {
            pf->next = pi;          // 插在中間
        }
        pi->next = pb;
    } else {                        // 插在尾部
        pb->next = pi;
        pi->next = NULL;
    }
    return head;
}

4. 遍歷打印 `print`

void print(TYPE *head) {
    printf("學號\t年齡\n");
    while (head) {
        printf("%d\t%d\n", head->num, head->age);
        head = head->next;   // 注意：這會改變 head，調用端若需保留頭指針請傳副本
    }
}

主函數測試流程

int main() {
    TYPE *head = NULL, *pnew = NULL;
    int n, num;

    printf("輸入節點數："); scanf("%d", &n);
    head = creat(n);
    print(head);

    printf("輸入要刪除的學號："); scanf("%d", &num);
    head = delete(head, num);
    print(head);

    printf("輸入要插入的學號和年齡：");
    pnew = (TYPE *)malloc(LEN);
    scanf("%d%d", &pnew->num, &pnew->age);
    head = insert(head, pnew);
    print(head);

    return 0;
}

運行示例

輸入節點數：3
輸入學號和年齡：103 20
輸入學號和年齡：105 22
輸入學號和年齡：108 19
學號	年齡
103	20
105	22
108	19

輸入要刪除的學號：103
節點已刪除
學號	年齡
105	22
108	19

輸入要插入的學號和年齡：106 21
學號	年齡
105	22
106	21
108	19

聯合體補充

文末介紹了聯合體（union）：多成員共享同一塊內存，長度等於最大成員長度。適用於「同一時刻只存一種數據」的場景，如教師/學生的「單位」字段（教研室字串 vs 班級整數）。

總結

鏈表核心是指針域串聯堆上節點，動態分配/釋放實現靈活增減。
增刪操作本質是修改前驅節點的 next 指針，務必處理頭節點、尾節點、空鏈表等邊界情況。
print 遍歷時修改了頭指針，實際項目中應使用臨時變量 TYPE *p = head; while(p) { ... p = p->next; } 保護原頭指針。
聯合體節省空間但犧牲同時存儲能力，結構體可嵌套聯合體實現變體記錄。