如何向后显示有序的双链表？[关闭]

Question

这个问题不太可能帮助任何未来的访问者;它只与一个小的地理区域、一个特定的时间时刻或一个特别狭窄的情况有关，而这种情况并不普遍适用于全世界的互联网受众。为了帮助使这个问题更广泛地适用, 访问帮助中心.

已关闭 7年前.

我在挣扎。我已经得到了它来显示大部分列表，但其中一个1没有显示出来，我不能为我的生活弄清楚如何解决它。

这里是相关的代码，我想。

我的插入功能:

 template <class T>
 void DoublyLinkedList<T>::insert(T data)
 {
    DoublyLinkedList<T> *newNode, *tmp, *oneBefore;

    newNode = new DoublyLinkedList(data);

if (mNext == NULL)
    mNext = newNode;

else
{
   oneBefore = mNext;
   tmp = mNext;

    while (tmp != NULL && tmp->mData < data)
    {
        oneBefore = tmp;
        tmp = tmp->mNext;
    }

    if (tmp == mNext)
    {
        newNode->mNext = mNext;
        mNext = newNode;
    }
    else
    {
        oneBefore->mNext = newNode;
        newNode->mNext = tmp;
        newNode->mPrevious = oneBefore;
    }

   }
 }

我的displayBackwards功能:

 void displayBackward(DoublyLinkedList<int> *ptr)
 {
    DoublyLinkedList<int> *tmp;

    tmp = ptr;
    while (tmp != NULL)
    {
       cout << tmp->getData() << endl;
       tmp = tmp->getPrevious();
    }
 }

和我的主要功能的相关部分:

    DoublyLinkedList<int> *ptr, *head, *tail;

    ptr = new DoublyLinkedList<int>;

    cout << "Testing Insert\n";
    ptr->insert(1);
    ptr->insert(2);
    ptr->insert(3);
    ptr->insert(1);

    tail = ptr;
    while (tail->getNext() != NULL)
       tail = tail->getNext();

    cout << "\n\nTesting displayBackward\n";
    displayBackward(tail);

我目前的输出是:

 Testing displayBackward
 3
 2
 1

Answer 1

这段代码是问题所在（在insert函数中）

    if (tmp == mNext)
    {
        newNode->mNext = mNext;
        mNext = newNode;
    }

你需要

    if (tmp == mNext)
    {
        newNode->mNext = mNext;
        mNext->mPrevious = newNode;
        mNext = newNode;
    }

您的原始代码将在某些情况下工作，除非您尝试插入小于或等于当前第一个节点中的数据的数据。

另外，我假设你的构造函数将mNext＆mPrevious初始化为NULL。如果没有，你会有其他问题。

Answer 2

 template <class T>
 void DoublyLinkedList<T>::insert(T data)
 {
    DoublyLinkedList<T> *newNode, *tmp, *oneBefore;

    newNode = new DoublyLinkedList(data);

if (mNext == NULL)
    mNext = newNode;

else

这不是连接新节点的后指针。

你的代码也可能有更多的错误。

---

编写双链表的一个简单方法是

• 区分 名单 和 节点 类型，以及
• 使每个列表始终有一个虚拟节点，称为 头节点.

这样你就没有了 NULL 指针来处理。

它确实简化了事情。