如何检查节点是否被删除或没有在链表中

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。