单链表 - 弹出函数

Question

我正在尝试编写一个函数，该函数将最后一个元素从列表中弹出，但是我不断收到指向指针的非法de引用的错误。我在这里做错了什么？我的插入函数也出现分段错误，其代码位于底部。任何帮助，不胜感激。

这是我的弹出函数

template < typename T >
void List<T>::PopBack()
{
  if (Empty())
  {
    std::cerr << "** List error: PopBack() called on empty listn";
    return;
  }
  Link *oldLink = last_;
  if (first_ == last_)
    first_ = last_ = 0;
    Link *currLink = GetPred(last_);
    last_ = currLink;
    last_->next_ = nullptr;
    delete oldLink;
} // end PopBack()

这也是我正在调用的函数

template <typename T >
typename List<T>::Link* List<T>::GetPred ( Link* x )
{
  Link* p = first_;
  while ( p != nullptr && p->next_ != x )
    p = p->next_;
  return p;
}

这是我的插入功能

// Insert t at (in front of) i; return i at new element
template < typename T >
ListIterator<T> List<T>::Insert (ListIterator<T> i, const T& t)
{
  if (Empty())  // always insert
  {
    i = End();
  }
  if (!i.Valid()) // null
  {
    std::cerr << " ** cannot insert at position -1n";
    return End();
  }
  Link* newLink = NewLink(t);
  Link* currLink = GetPred(i.curr_);
  // leave i at new entry and return
  newLink = currLink;
  return i;
}

这是我的结束函数

// return iterator "1 past the back"
template < typename T >
ListIterator<T>  List<T>::End()
{
  Iterator i(last_->next_);
  return i;
}

这是我的有效函数

// test cursor for legal dereference
template < typename T >
bool ConstListIterator<T>::Valid() const
{
  return curr_ != nullptr;
}

这是我的空函数

template < typename T >
bool List<T>::Empty()  const
{
  return (first_ == nullptr);
}

检索方法

template < typename T >
T&  ConstListIterator<T>::Retrieve() const
// Return reference to current t
// note conflicted signature - const method returns non-const reference
{
  if (curr_ == nullptr)
  {
    std::cerr << "** Error: ConstListIterator<T>::Retrieve() invalid dereferencen";
    exit (EXIT_FAILURE);
  }
  return curr_->Tval_;
}

Answer 1

如果你的列表有一个元素，我假设first_和last都指向该元素。那么，当 List 只包含一个元素时调用 PopBack 时会发生什么：

template < typename T >
void List<T>::PopBack()
{
  if (Empty())  // Not empty so don't take the if
  {
    std::cerr << "** List error: PopBack() called on empty listn";
    return;
  }
  Link *oldLink = last_;
  // first_ and last_ are the same so set them to 0
  if (first_ == last_)
    first_ = last_ = 0;  // Why 0 instead of nullptr ?
    // GetPred(0) will return nullptr, i.e. currLink  will be nullptr
    Link *currLink = GetPred(last_);
    // Last will be nullptr
    last_ = currLink;
    // Dereference of nullptr !!!!
    last_->next_ = nullptr;
    delete oldLink;
}

也许你可以做到：

template < typename T >
void List<T>::PopBack()
{
  if (Empty())      {
    std::cerr << "** List error: PopBack() called on empty listn";
    return;
  }
  delete last_; // No reason for oldLink - just delete right away
                // as you will not dereference last_ until it has
                // a new value
  if (first_ == last_)
  {
    first_ = last_ = nullptr;
  }
  else
  {
    Link *currLink = GetPred(last_);
    last_ = currLink;
    last_->next_ = nullptr;
  }    
}

Answer 2

方法 PopBack 在 first_ 等于 last_ 的情况下具有未定义的行为，因为起初两个节点都设置为 0

if (first_ == last_)
  first_ = last_ = 0;

然后，您正在尝试访问 alreadt 等于 0 的节点的数据成员next

last_->next_ = nullptr;

函数可以写得更简单

template < typename T >
void List<T>::PopBack()
{
    if ( Empty() )
    {
        std::cerr << "** List error: PopBack() called on empty listn";
        return;
    }
    Link *oldLink = last_;
    Link *currLink = GetPred( last_ );
    last_ = currLink;
    if ( last_ == nullptr )
    {
        first_ = last_;
    }
    else
    {
        last_->next_ = nullptr;
    }
    delete oldLink;
} // end PopBack()

据我所知，方法Insert具有内存泄漏，因为首先分配了一个节点并将其地址分配给newLink

Link* newLink = NewLink(t);

然后重新分配此变量

newLink = currLink;

似乎该方法实际上什么也没插入。

它可以看起来像下面这样

// Insert t at (in front of) i; return i at new element
template < typename T >
ListIterator<T> List<T>::Insert (ListIterator<T> i, const T& t)
{
    if (Empty())  // always insert
    {
        i = End();
    }
    if ( !i.Valid() ) // null
    {
        std::cerr << " ** cannot insert at position -1n";
        return End();
    }
    Link* newLink = NewLink(t);
    newLink->next = i.curr;
    Link* currLink = GetPred( i.curr_ );
    if ( currLink == nullptr )
    {
        first_ = newLink;
    }
    else
    {
        currLink->next = newLink;
    }   
    i.curr = newLink;
    return i;
}