c++ - 反向双向链表会导致正向互惠失败

我正在使用一个名为Reverse()的函数，因为我仅使用两个链接来反转列表中元素的顺序。我已经搜索了许多方法来执行此操作，但始终以“分段错误”结尾。我有一个方法可以帮助您确定出了什么问题，但是最多可以告诉我的是，当我创建一个包含五个元素(不包括头部和尾部)的列表时，“在位置0处存在正向互惠失败”。请记住，我不想给我代码，而只是给您关于出问题的意见。

void List<T>::Reverse ()
{
  //make sure that the list is long enough
  if( this->Empty())
    return;

  Link * link = this->head_;
  Link * temp = NULL;

  while( link != NULL )
  {
    temp = link->next_;
    link->next_ = link->prev_;
    link->prev_ = temp;

    if( link->prev_ == NULL )
      head_ = link;

    link = link->prev_;
  }
  CheckLinks();
 }

最佳答案

您的算法工作正常。该错误位于代码中的其他位置。

我创建了自己的(非常快速又肮脏的)双向链接列表来进行测试。
我在一个文件中做了所有这些。

我的链接结构与您的结构略有不同:

#include <iostream>

template <typename T>
struct Link
{
    Link (const T &data, Link <T> *prev = NULL, Link <T> *next = NULL) ;

    T data ;
    Link <T> *next_ ;
    Link <T> *prev_ ;
};

template <typename T>
Link <T>::Link (const T &data, Link <T> *prev, Link <T> *next) : data (data), prev_ (prev), next_ (next)
{
}

然后这是我的测试列表结构:

template <typename T>
struct List
{
    List () ;

    bool IsEmpty () const ;
    void Reverse () ;
    void CheckLinks () const ;

    Link <T> *head_ ;
};

template <typename T>
List <T>::List () : head_ (NULL)
{
}

template <typename T>
bool List <T>::IsEmpty () const
{
    return head_ == NULL ;
}

template <typename T>
void List <T>::Reverse ()
{
    if (this->IsEmpty () == true) {
        return ;
    }

    Link <T> *link = head_ ;
    Link <T> *temp = NULL ;

    while (link != NULL) {
        temp = link->next_ ;
        link->next_ = link->prev_ ;
        link->prev_ = temp ;

        if (link->prev_ == NULL) {
            head_ = link ;
        }

        link = link->prev_ ;
    }
}

template <typename T>
void List <T>::CheckLinks () const
{
    Link <T> *link = head_ ;

    while (link != NULL) {
        std::cout << link->data << " " ;
        link = link->next_ ;
    }

    std::cout << std::endl ;
}

这些是我为确保其正确性而进行的测试。

// Null List
void Test0 ()
{
    List <int> list ;

    list.CheckLinks () ;
    list.Reverse () ;
    list.CheckLinks () ;
}

// List with 1 node
void Test1 ()
{
    Link <int> n1 (1) ;

    List <int> list ;
    list.head_ = &n1 ;

    list.CheckLinks () ;
    list.Reverse () ;
    list.CheckLinks () ;
}

// List with 2 nodes
void Test2 ()
{
    Link <int> n1 (1) ;
    Link <int> n2 (2) ;

    n1.next_ = &n2 ;
    n2.prev_ = &n1 ;

    List <int> list ;
    list.head_ = &n1 ;

    list.CheckLinks () ;
    list.Reverse () ;
    list.CheckLinks () ;
}

// List with 3 nodes
void Test3 ()
{
    Link <int> n1 (1) ;
    Link <int> n2 (2) ;
    Link <int> n3 (3) ;

    n1.next_ = &n2 ;

    n2.prev_ = &n1 ;
    n2.next_ = &n3 ;

    n3.prev_ = &n2 ;

    List <int> list ;
    list.head_ = &n1 ;

    list.CheckLinks () ;
    list.Reverse () ;
    list.CheckLinks () ;
}

// List with 4 nodes
void Test4 ()
{
    Link <int> n1 (1) ;
    Link <int> n2 (2) ;
    Link <int> n3 (3) ;
    Link <int> n4 (4) ;

    n1.next_ = &n2 ;

    n2.prev_ = &n1 ;
    n2.next_ = &n3 ;

    n3.prev_ = &n2 ;
    n3.next_ = &n4 ;

    n4.prev_ = &n3 ;

    List <int> list ;
    list.head_ = &n1 ;

    list.CheckLinks () ;
    list.Reverse () ;
    list.CheckLinks () ;
}

这是我的主要内容:

int main (void)
{
    Test0 () ;
    Test1 () ;
    Test2 () ;
    Test3 () ;
    Test4 () ;

    return 0 ;
}

希望这足以使您相信您的错误在其他地方。

关于c++ - 反向双向链表会导致正向互惠失败，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/21288990/