0

!=我目前正在研究以下擦除递归布尔函数，它将 list 和 int 作为参数，如果找到并删除了 int，则返回 true，如果在列表中找不到它，则返回 false。它似乎有效，但问题是它删除了列表中的下一个 int 数字，而不是当前的：

 typedef struct E_Type * List;

 struct E_Type
 {
        int data;
        List next = 0;
 };

bool erase(const List & l, int data){
List current = l;   
if (current == 0)
{
   return false;
 }
else if (current->data == data)
{
      List deleteNode = new E_Type;
     deleteNode = current->next;//probably this causes the error, but how can I point it to the current without crashing the program
     current->next = deleteNode->next;
     delete deleteNode;
     return true;
}

else if (current->data != data)
{
      return erase(current->next, data);
}


}
4

7 回答 7

2

有两种基本类型的列表：

  • 单链表（每个节点都知道它的下一个节点）和
  • 双链表（每个节点都知道它的下一个节点以及它的前一个节点）。

如果像您的情况一样，有一个单链表，则不能检查 CURRENT 节点是否与“数据”相等，因为此时更改最后一个节点的下一个指针为时已晚。所以你总是必须检查 NEXT 指针是否相等，如下所示：

bool erase(const List & l, int data)
{
    List current = l;   
    if (current == 0)
        return false;

    // special case: node to be deleted is the first one
    if (current->data == data)
    {
        delete current;
        return true;
    }

    if (current->next && current->next->data == data) // next exists and must be erased
    {
        List deleteNode = current->next;   // Step 1: save ptr to next
        current->next = deleteNode->next;  // Step 2: reassign current->next ptr
        delete deleteNode;                 // Step 3: delete the node
        return true;
    }

    return erase(current->next, data);
}

注意：我忽略了你最后一个“else if”条件。'else' 因为前一个 if 在其中有一个 return，而 'if' 因为它的条件只是前一个 'if' 的否定，如果程序走到这一步 - 它将永远成立。

问候

于 2012-12-06T14:24:52.897 回答
1

这里有一些指示。

迭代方法

当您遍历列表时，仅维护指向当前元素的指针是不够的。您还需要维护指向前一个previous->next元素的指针，因为如果您删除当前元素，则需要进行修复。

最重要的是，删除列表的第一个元素需要特殊处理。

递归方法

编写一个递归函数，该函数将获取指向列表头的指针，查找并删除所需元素，并返回指向新列表头的指针。为此，您需要：

  1. 定义和实施基本案例。处理单元素列表似乎是一种自然的选择。
  2. 定义递归。有两种情况：要么列表的头部是您要查找的元素，要么不是。弄清楚在这两种情况下你需要做什么，然后从那里开始。
于 2012-12-06T14:04:43.230 回答
1

您正在考虑的唯一节点是当前节点，因此您必须准备好修改l：

if (current->data == data)
{
  l = current->next;
  delete current;
  return true;
}
于 2012-12-06T14:08:00.137 回答
1

你的情况

else if (current->data == data)

将在具有值数据的节点上停止。然后，您继续删除代码中此节点之后的节点。

如果您想保持其余代码相同，则该行应为：

else if ((current->next)->data == data)

进行额外检查，以防第一个元素是列表中的唯一元素。

一种更简单的方法是在当前元素之前保留一个指向该元素的指针，然后删除该指针引用的节点。

于 2012-12-06T14:10:46.110 回答
1

如果你有一个列表：
A --> B --> C --> D
并且你想删除 C，你必须： 将 C
存储在一个临时变量中
Change B->next=C->next
delete C.
所以您需要找到 B 才能对其进行修改。
您当然不应该创建任何 E_type 的新实例。

于 2012-12-06T14:11:09.493 回答
0

从列表中删除节点时，需要将前一个节点指向下一个节点。由于您有一个单链表，因此有 2 个选项：

  1. 在函数中维护指向前一个节点的指针erase。当遇到所需节点时，将前一个节点链接到current->next当前节点并删除当前节点。需要对列表中的第一个节点进行特殊处理。

  2. 当你遇到想要的节点时，复制current->nextinto的内容current，然后删除current->next。这样，您的函数中就不需要额外的参数。需要对列表中的最后一个节点进行特殊处理。

于 2012-12-06T13:55:33.703 回答
0

您将需要更改前一个条目的next指针。所以一切都找到了，但是您必须根据数据检查 current->next->data，而不是 current->data。

如果 current 是列表中的最后一个条目，请务必检查 NULL 指针！

于 2012-12-06T14:08:25.423 回答