c++ - 从链表中删除节点

Question

我正在研究从链表中删除节点的迭代删除函数，我认为代码应该可以正常工作，它遍历列表，找到所需的节点，将头指向下一个节点并删除当前节点，但是当我测试运行它时，我得到了无限循环，请你帮我查明错误，这里是函数：

typedef struct E_Type * List;
struct E_Type
{
  int data;
  struct E_Type* next;
};

功能：

 bool erase(List & l, int data){
 List head = l; 
 if (l != 0){
    for(List current = head; current; current = current->next){
    if ( current->data == data )
       head = current->next;
       delete current;
       return true;
     }
   }
 return false;
}

测试程序：

int main()
{
  List l = 0;
  cout << boolalpha << l->data << "went well? "<< (insert(l,73)) << endl;
  cout << boolalpha << l->data << "went well? "<< (insert(l,24)) << endl;
  print(cout,l);
  cout << boolalpha << "Is deleted 24? "<<(erase(l,24)) << endl;    
  cout << boolalpha << "Is deleted 35? "<<(erase(l,35)) << endl;
  print(cout,l);
  cout << endl;
  return 0;
}

插入：

bool insert(List & l, int data)
{   

    List current = l;
    while(current != 0) {
        if (current->data == data)
        return false;
       current = current->next;
    }

    if (l == 0 || l->data > data){
        List new_list = new E_Type;
        new_list->data = data;
        new_list->next = l;
        l = new_list;
    return true;
    }

    else if(l->data < data){
    insert(l->next, data);
    return true;
    }

}

Answer 1

您还需要在 for 循环中跟踪前一个节点并执行以下操作：

prev->next = current->next;
delete current;

您还需要处理已删除元素是列表的第一个元素的情况，在这种情况下，您需要设置l为l->next

 bool erase(List & l, int data){
 if (l != 0){
    for(List current = head, prev = 0; current; prev = current, current = current->next){
    if ( current->data == data )
    {
       if (prev)
       {
           prev->next = current->next;
       }
       else
       {
            l = current->next;
       }
       delete current;
       return true;

     }
   }
 return false;
}

您的第一个擦除可能正在创建一个循环列表。

Answer 2

正如 Andreas Brinck 已经指出的那样，您还需要更新“上一个”链接。但是，您不需要为此使用专用变量，只需使用指向指针的指针：

bool erase(List & l, int data){
  List *it = &l;
  while ( *it ) {
    if ( (*it)->data == data ) {
      List next = (*it)->next;
      delete *it;
      *it = next;
      return true;
     }
     it = &(*it)->next;
  }
  return false;
}

这还负责处理所有“特殊情况”，例如从空列表中删除、删除列表中的第一个元素或删除列表中的最后一个元素。

Answer 3

我们可能还需要查看您的插入方法。

有没有可能

current == current->next

如果是这样，可能会导致无限循环。