c++ - 从 C++ 队列的中间删除一个节点

Question

我有一个带有 c 样式ctor和dtor.

当这个 if 语句决定不测试 true 时，我太沮丧了，让我陷入了无限循环。我不明白为什么它永远不会测试为真。

我正在尝试从我的LinkedList.

也许有人可以帮助我？

Node *Current = first_; // I want this to be my only Node Ptr Varaible Declaration.
if ( NULL == first_ )
std::cout << "Cannot delete from an empty list: \n";


while ( Current != NULL )
{
  if ( first_->data_ == node->data_ ) 
  {
    //check to see if we are deleteing the head.
    first_ = first_->next_;
    --listLen_;
    delete Current;
    std::cout << "Head Deleted!\n";
  }
  if ( Current->data_ == node->data_ ) // FOR SOME REASON this is never true?
  {
    --listLen_;
    node->data_ = NULL;
    Current     = Current->next_;
    node->data_ = Current;
  }
  else  // we must not of found it.  // else should match previous i
  {
    Current->prev_ = Current;// since we are not deleting the first node we are OK here.
    Current        = first_->next_;

    if ( Current->next_ == NULL ) // see if we are at the end of the list.
    {
      first_ = NULL;  
      last_  = Current->prev_;

    }
  }
}
return;

score 2 · Accepted Answer

这真的应该重写，因为它有太多问题......还有为什么不使用STL容器？我认为这是一个家庭作业问题。

无限循环的答案是递增到下一个节点的 else 情况：

Current        = first_->next_;

如果在前两个节点中找不到数据，这将使您永远循环...因为您将始终将下一个测试设置为第一个节点的下一个节点，并且如果有超过 2 个节点，它将永远不会将当前设置为 NULL在列表中。

score 1 · Accepted Answer

我不完全确定您要完成什么，但我确定您做错了。如果你只是想从一个与 node->data_ 匹配的双向链表中删除一个元素，就这么简单：

Node *Current = first_;

while (Current != NULL)
{
  if (Current->data_ == node->_data)
  {
    //If Current isn't the head of the list, set prev to next
    if (Current != first_)
      Current->prev_->next_ = Current->next_
    else
    {
      first_ = Current->next_;
      if (first_ != NULL)
        first_->prev_ = NULL;
    }

    //If Current isn't the tail of the list, set next to prev
    if (Current->next_ != NULL)
      Current->next_->prev_ = Current->prev_
    else if (Current->prev_ != NULL)
      Current->prev_->next_ = NULL;


    delete Current;
    Current = NULL;
  }
  else
  {
    Current = Current->next_;
  }
}
return;

score 0 · Accepted Answer

您没有显示node来自哪里或如何data_定义，但如果它是指针类型，您可能需要比较内容，而不是地址。

假设这data_是一个指向某物的指针，并且它指向的内容已经operator==定义或者是一个内置类型，并且它具有您正在寻找的值，那么您可以这样做：

if ( *Current->data_ == *node->data_ )

score 0 · Accepted Answer

如果first_->data_ == node->data_曾经计算为真，那么第二个 if 语句将始终计算为真，那么第二个 if 条件将始终计算为假Current->data_ == node->data_ ，因为在第一次迭代时first_ == Current，您删除Current而不更新它

要从链表中删除一个节点，您似乎做了太多的工作。

score 0 · Accepted Answer

保持循环小，更容易找出问题所在。假设您的数据比较有意义，请查看以下内容：

curr = first_;
while( curr && (curr->data_ != node->data_) ) { 
  curr = curr->next_; 
}
if (!curr) return   // didnt find it, nothing to remove
if ( curr == first_ )   
  first_ = curr->next_  
else            
  curr->prev_->next_ = curr->next_
curr->next_->prev_ = curr->prev_ // always fix next's prev
delete curr

score 0 · Accepted Answer

对于实际问题，这里并不是真正的答案，而是一个建议。

我永远不会遍历链接列表来删除列表中的条目。每个条目都应该有一个有效的下一个和上一个指针，当您从列表中删除一个条目时，您只需将前一个记录指向下一个，反之亦然，将您自己从列表中删除。一个空列表应该有一个头记录和一个尾记录，它们只是相互指向，并且所有有效的条目都插入到它们之间。

score 0 · Accepted Answer

删除传递值的节点。

void deleteBegin()
{
 Node* temp =Head;
 if(temp==NULL)
     return;
 Head=Head->next;
 free(temp);
}
void deleteMiddle(int _data)
{
 Node* curr = Head;
 Node* prev = Head;

if(curr==NULL)
    return;

if(curr->next==NULL)
  {
    deleteBegin();
    return;
 }

 while(curr->next!=NULL && curr->data!=_data)
 {
    prev=curr;
    curr=curr->next;
 }

 if(curr->data == _data)
 {
     if(prev==curr)
     {
        deleteBegin();
        return;
      }
    prev->next = curr->next;
    free(curr);
 }  
 else
 {
    cout<<"Element Not Found\n";
    return;
 }

}

c++ - 从 C++ 队列的中间删除一个节点

7 回答 7

Related

Reference