C語言鏈表核心操作（四）：查找、刪除、插入完整實現

鏈表查找：按學號定位節點

TYPE *search(TYPE *head, int num) {
    TYPE *p = head;
    while (p && p->num != num) {
        p = p->next;
    }
    if (p) return p;           // 找到，返回節點指針
    printf("節點 %d 未找到\n", num);
    return NULL;
}

• 時間複雜度 O(n)，單向鏈表只能線性查找。
• 返回節點指針而非數據，便於後續操作（修改、刪除）。

鏈表刪除：三種情況統一處理

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

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

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

    if (!pb) {                 // 遍歷結束未找到
        printf("節點 %d 不存在\n", num);
        return head;
    }

    // 找到 pb，分情況斷鏈
    if (pb == head) {
        head = pb->next;       // 刪除頭節點：head 後移
    } else {
        pf->next = pb->next;   // 刪除中間/尾節點：前驅跳過
    }

    free(pb);                  // 釋放內存
    printf("節點 %d 已刪除\n", num);
    return head;               // 可能新 head
}

關鍵點

• 統一用 pf/pb 雙指針，自然覆蓋頭節點、中間節點、尾節點三種情況。
• 刪除頭節點時 head 改變，必須返回新 head 給調用者。
• free(pb) 在斷鏈後，防止訪問已釋放內存。

鏈表插入：按學號升序插入（四種情況）

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

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

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

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

四種情況圖解

// 1. 空表
head -> NULL
插入 pi -> head = pi -> NULL

// 2. 頭部插入 (pi->num 最小)
head -> A -> B
插入 pi -> head = pi -> A -> B

// 3. 中間插入
A -> B -> C
插入 pi (值在 A,B 之間) -> A -> pi -> B -> C

// 4. 尾部插入 (pi->num 最大)
A -> B -> NULL
插入 pi -> A -> B -> pi -> NULL

完整測試主函數

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

    printf("節點數: "); scanf("%d", &n);
    head = create(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);

    // 釋放整個鏈表（良好習慣）
    while (head) {
        TYPE *tmp = head;
        head = head->next;
        free(tmp);
    }
    return 0;
}

打印函數 print（不修改 head）

void print(TYPE *head) {
    printf("學號\t年齡\n");
    for (TYPE *p = head; p; p = p->next) {
        printf("%d\t%d\n", p->num, p->age);
    }
}

• 用臨時指針 p 遍歷，保護原 head 不被修改。

總結

• 查找：單指針線性掃描，返回節點指針。
• 刪除：雙指針 pf/pb 統一處理頭/中/尾，返回新 head。
• 插入：雙指針尋找位置，四種情況（空/頭/中/尾）統一邏輯，返回新 head。
• 所有修改鏈表結構的操作必須返回頭指針，調用者必須接收：head = insert(head, pnew);。
• 程序結束前遍歷 free 所有節點，養成內存管理閉環習慣。