Как отобразить упорядоченный двусвязный список в обратном порядке?[закрыто]

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 указатели, с которыми нужно иметь дело.

Это действительно упрощает ситуацию.