从链接列表中删除节点 [英] Delete node from Linked List

问题描述

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

I am working on iterative delete function that deletes node from a linked list, I think that the code is supposed to work fine, it traverses through the list, finds the needed node, points the head to the next node and deletes the current, but when I test run it I get infinite loop, could you please help me to pinpoint the error, here is the function:

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

}

推荐答案

正如Andreas Brinck指出的那样，您还需要更新上一个"链接.但是，您不需要为此使用专用变量，只需使用指向指针的指针即可:

As Andreas Brinck already points out, you need to update the 'previous' link as well. However, you don't need a dedicated variable for this, just use a pointer to a pointer:

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

这还可以处理所有特殊情况"，例如从空列表中删除，删除列表中的第一个元素或删除列表中的最后一个元素.

This also takes care of handling all the "special cases" such as deleting from an empty list, deleting the first element in the list or deleting the last element in the list.

这篇关于从链接列表中删除节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！