删除链表中的节点会导致输出看似随机的节点

Question

我正试图使用以下函数从链表中删除一个节点：

void del_node(int del_data)
{
node* temp = NULL;
node* trail = NULL;
node* del_ptr = NULL;
temp = head;
trail = head;
while (temp != NULL && temp->data != del_data)
{
trail = temp;
temp = temp->next;
}
if (temp != NULL) {
del_ptr = temp;
temp = temp->next;
trail->next = temp;
delete(del_ptr);
}
}

它似乎删除它很好，直到我打印链接列表使用这个：

void print()
{
node* temp = NULL;
temp = head;
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}

它开始输出看似随机的数字，有人能帮我吗，真的很困惑，因为这段代码来自教程。

Answer 1

您的算法无论如何都无法正确管理头指针。任何最终应该修改头指针的更改都不会，这是一个巨大的问题。指针对指针算法不仅解决了这个问题，还提供了一个相当简洁的解决方案：

void del_node(int del_data)
{
struct node **pp = &head;
while (*pp && (*pp)->data != del_data)
pp = &(*pp)->next;
if (*pp)
{
node *tmp = *pp;
*pp = tmp->next;
delete tmp;
}
}

这将适用于任何列表条件，包括：

1. 一个空列表。即CCD_ 1为空
2. 单个节点列表。如果该值与head->data匹配，它将正确删除并重置节点指针
3. 多节点列表。第一个匹配的节点将被删除，如果头节点指针是匹配的位置，它将正确地修复它
4. 以上所有内容，在没有匹配节点的情况下，列表保持不变

在这么短的算法+实现中实现所有这些都是有益的。

Answer 2

我将在内联中评论您的代码：

void del_node(int del_data)
{
node* temp = NULL;
node* trail = NULL;
node* del_ptr = NULL;
temp = head;
trail = head;
// This is fine, but recommend you use nullptr instead of NULL.
// This will find the first instance of data matches del_data,
// But if you are trying to delete all instances of del_data,
// You'll need to do this a little differently.
while (temp != NULL && temp->data != del_data)
{
trail = temp;
temp = temp->next;
}
// This if is fine, but see previous comment about using nullptr
// instead of NULL.
if (temp != NULL) {
del_ptr = temp;
temp = temp->next;
// Problematic: What if trail is null?
trail->next = temp;
delete(del_ptr);
}
}

你的代码还不错。我不会完全这样写，但我将取代你的if语句：

if (temp != nullptr) {
// If trail is nullptr, then we're deleting from the head
if (trail == nullptr) {
head = temp->next;
}
else {
trail->next = temp->next;
}
delete(temp);
}

不需要临时的。只需在if-else块中指出温度，然后删除温度。