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

Я борюсь с этим. У меня есть это, чтобы отобразить большую часть списка, но один из 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

0

Решение

Этот код является проблемой (в функции вставки)

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

Тебе нужно

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

Ваш оригинальный код будет работать в тех случаях, за исключением случаев, когда вы пытаетесь вставить данные, которые меньше или равны данным в вашем текущем первом узле.

Кроме того, я предполагаю, что вы конструктор инициализирует mNext & mПредусмотрено в NULL. Если нет, у вас будут другие проблемы.

0

Другие решения

 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 указатели для решения.

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

0

По вопросам рекламы [email protected]