鏈表的 C 語言實現（五）：單鏈表刪除操作

單鏈表刪除操作

刪除節點 p 需知其前驅節點。操作步驟：

1. 前驅節點 link 指向 p 的後繼（x->link = y->link）
2. 釋放 p 佔用的記憶體（free(p)）

查找前驅節點函數

stud *search2(stud *h, char *x) {  // 返回目標節點的前驅
    stud *p, *s;
    char *y;
    
    p = h->link;  // 當前節點
    s = h;        // 前驅節點（初始為表頭）
    
    while (p != NULL) {
        y = p->name;
        if (strcmp(y, x) == 0)
            return s;       // 找到，返回前驅
        else {
            p = p->link;    // 同步前進
            s = s->link;
        }
    }
    if (p == NULL)
        printf("沒有找到該資料！\n");
    return NULL;
}

刪除函數

void del(stud *x, stud *y) {  // x: 前驅, y: 待刪除節點
    stud *s = y;
    x->link = y->link;  // 旁路 y
    free(s);            // 釋放記憶體
}

主程式

int main() {
    int number = N;
    char fullname[20];
    stud *head, *searchpoint, *forepoint;
    
    head = creat(number);
    printf("請輸入要刪除的姓名: ");
    scanf("%s", fullname);
    
    searchpoint = search(head, fullname);   // 找到目標節點
    forepoint = search2(head, fullname);    // 找到前驅節點
    
    if (searchpoint && forepoint)
        del(forepoint, searchpoint);        // 執行刪除
    return 0;
}

關鍵點總結

• 單鏈表刪除必須知道前驅節點（雙向鏈表則不需要）
• search 返回目標節點，search2 返回前驅節點
• 刪除時先斷開鏈接再 free，避免記憶體洩漏
• 若刪除第一個實際節點，前驅即為表頭 h