如何檢查節點是否被刪除或沒有在鏈表中

Question

嘿請別人清除我的疑問，如果我刪除了一個節點，後來我嘗試打印該節點的數據應該是什麼輸出？如何檢查節點是否被刪除？

在這個程序中，我試圖刪除重複節點以及如何知道我是否正確刪除它們！如果我試圖訪問刪除節點的數據，我想在刪除節點後，如果一切正常，我會得到零！但是這裏就是這種情況，所以我試着重新計算節點，這很好。數數是檢查的唯一方法嗎？

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

typedef struct dll { 
    int data; 
    struct dll* next; 
} dll; 

int main() { 
    dll* p1, *p2, *p3, *p4, *p5, *temp, *head, *todel, *cur, *fwd, *dup; 
    int count = 0, i = 0, j = 0; 

    p1 = (dll*)malloc(sizeof(dll)); 
    p2 = (dll*)malloc(sizeof(dll)); 
    p3 = (dll*)malloc(sizeof(dll)); 
    p4 = (dll*)malloc(sizeof(dll)); 
    p5 = (dll*)malloc(sizeof(dll)); 

    p1->data = 1; 
    p1->next = p2; 

    p2->data = 2; 
    p2->next = p3; 

    p3->data = 3; 
    p3->next = p4; 

    p4->data = 2; 
    p4->next = p5; 

    p5->data = 1; 
    p5->next = NULL; 

    head = p1; 

    printf("p1::%p\n", p1); 
    printf("p2::%p\n", p2); 
    printf("p3::%p\n", p3); 
    printf("p4::%p\n", p4); 
    printf("p5::%p\n", p5); 
    printf("head::%p\n", head); 

    for (temp = head; temp != NULL; temp = temp->next) { 
     count++; 
    } 
    printf("no of nodes %d\n", count); 

    temp = head; 

    cur = temp; 

    while (cur) { 
     for (fwd = cur->next; fwd != NULL; fwd = fwd->next) { 
      if (cur->data == fwd->data) { 
       cur->next = fwd->next; 
       // fwd->next=fwd->next->next; 
       todel = fwd; 
       free(todel); 
       fwd = cur; 
      } 
     } 
     cur = cur->next; 
    } 

    printf("p1::%p\n", p1); 
    printf("p2::%p\n", p2); 
    printf("p3::%p\n", p3); 
    printf("p4::%p\n", p4); 
    printf("p5::%p\n", p5); 

    printf("p1->data::%d\n", p1->data); 
    printf("p2 data::%d\n", p2->data); 
    printf("p3->data::%d\n", p3->data); 
    printf("p4->data::%d\n", p4->data); 
    printf("p5->data::%d\n", p5->data); 

    return 0; 
} 

輸出：

p1::0x8728008 
p2::0x8728018 
p3::0x8728028 
p4::0x8728038 
p5::0x8728048 
head::0x8728008 
no of nodes 5 
temp::0x8728008 
cur::0x8728008 
no of nodes 1 
p1::0x8728008 
p2::0x8728018 
p3::0x8728028 
p4::0x8728038 
p5::0x8728048 
p1->data::1 
p2 data::2 
p3->data::3 
p4->data::2 
p5->data::0 

通過觀察輸出（無節點：1）我知道節點刪除了，但它不是那麼清楚，我甚至不知道哪個節點刪除了，仍然p2到p4給出相同的舊數據值，我怎麼知道？

Answer 1

您擦除不正確的節點，在for循環內的同時fwd變量包含重複節點和cur變量包含原始節點（即重複的）。您正在清除原始節點和重複節點之間的節點。對於只擦除重複節點您需要在此之前維護節點並設置last_fwd->next = fwd->next;，這將只擦除重複的節點（例如：p4 and p5，而不是p1 or p2如果您需要擦除這個更多的工作）。

另一個問題是您正在使用指針打印節點，而不是創建的linked list。在這種情況下，當你擦除p4和p5並嘗試打印它們的值是未定義行爲（任何事情都可能發生，工作，打印垃圾，重啓機器：D等等）。

使用更新代碼，使用列表的鏈接進行打印。在這種情況下，擦除的節點不會觸摸。

代碼：

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

typedef struct dll { 
    int data; 
    struct dll* next; 
} dll; 

int main() { 
    dll* p1, *p2, *p3, *p4, *p5, *temp, *head, *todel, *cur, *fwd, *dup, *last_fwd; 
    int count = 0, i = 0, j = 0; 

    p1 = (dll*)malloc(sizeof(dll)); 
    p2 = (dll*)malloc(sizeof(dll)); 
    p3 = (dll*)malloc(sizeof(dll)); 
    p4 = (dll*)malloc(sizeof(dll)); 
    p5 = (dll*)malloc(sizeof(dll)); 

    p1->data = 1; 
    p1->next = p2; 

    p2->data = 2; 
    p2->next = p3; 

    p3->data = 3; 
    p3->next = p4; 

    p4->data = 2; 
    p4->next = p5; 

    p5->data = 1; 
    p5->next = NULL; 

    head = p1; 

    printf("p1::%p\n", p1); 
    printf("p2::%p\n", p2); 
    printf("p3::%p\n", p3); 
    printf("p4::%p\n", p4); 
    printf("p5::%p\n", p5); 
    printf("head::%p\n", head); 

    for (temp = head; temp != NULL; temp = temp->next) { 
     count++; 
    } 
    printf("no of nodes %d\n", count); 

    temp = head; 

    cur = temp; 

    while (cur) { 
     last_fwd = cur; 
     for (fwd = cur->next; fwd != NULL; fwd = fwd->next) { 
      if (cur->data == fwd->data) { 
       last_fwd->next = fwd->next; 
       todel = fwd; 
       free(todel); 
      } 
      last_fwd = fwd; 
     } 
     cur = cur->next; 
    } 

    for (count = 0, temp = head; temp != NULL; temp = temp->next, count++) { 
     printf("p%d::%p\n", count, temp); 
     printf("p%d->data::%d\n", count, temp->data); 
    } 

    return 0; 
} 

Answer 2

你最後在做什麼，釋放整個鏈表？這不是你應該實現它的方式。實際上沒有辦法查看堆中的塊是否被分配（實際上存在，但依賴於編譯器和髒）。不要以這種方式維護鏈表。

free只是把內存放回堆中，它不會改變指針的值。作爲一名C程序員，你應該支付動態分配的內存是否被釋放，因爲沒有標準的方法來幫助你。

如果要刪除剛剛走出列表的第一個環節

，你應該做的：

head = cur.next; 
free(cur); 

然後忘掉cur，你永遠不應該使用它。

，如果你想cur後刪除的鏈接，它大致有云：

dll *tmp = cur->next; 
cur->next = tmp->next; 
free(tmp); 

此後再也沒有引用tmp。