c++ - 从链表中删除节点(递归)

Question

!=我目前正在研究以下删除递归 bool 函数，该函数将 list 和 int 作为参数，如果找到并删除了 int 则返回 true，如果未在列表中找到则返回 false。它似乎可行，但问题是它删除了列表中的下一个整数，并且< strong>不是当前的:

 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);
}


}

Answer 1

有两种基本类型的列表:

• 单链表(每个节点都知道它的下一个节点)和
• 双链表(每个节点都知道它的下一个和前一个节点)。

如果像您的情况一样，有一个单链表，则您不能检查 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 有一个返回值，而“if”是因为它的条件只是前面“if”的否定，如果程序走到这一步 - 它将始终成立。

问候