¿Cómo mostrar una lista ordenada doblemente vinculada al revés?[cerrado]

Question

Es poco probable que esta pregunta ayude a futuros visitantes;solo es relevante para un área geográfica pequeña, un momento específico en el tiempo o una situación extraordinariamente limitada que generalmente no es aplicable a la audiencia mundial de Internet.Para obtener ayuda para hacer que esta pregunta sea más ampliamente aplicable, visita el centro de ayuda.

Cerrado hace 7 años.

Estoy luchando con esto.Tengo que mostrar la mayor parte de la lista, pero una de las 1 no aparece, y no puedo por mi vida descubrir cómo solucionarlo.

Aquí está el código relevante, creo.

Mi función de inserción:

 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;
    }

   }
 }

Mi función displayBackwards:

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

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

Y la parte relevante de mi función principal:

    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);

Mi salida actualmente es:

 Testing displayBackward
 3
 2
 1

Answer 1

Este código es el problema (en la función de inserción)

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

Necesitas

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

Su código original funcionará en los casos, excepto cuando intente insertar datos que sean menores o iguales a los datos en su primer nodo actual.

Además, supongo que el constructor inicializa mNext y mPrevious en NULO.Si no, tendrás otros problemas.

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

Esto no está vinculando el puntero hacia atrás del nuevo nodo.

También puede haber más errores con su código.

---

Una forma sencilla de codificar una lista doblemente vinculada es

• diferenciar entre lista y nodo tipo, y
• haga que cada lista siempre tenga un nodo ficticio, llamado a nodo de encabezado.

De esa manera no tendrás NULL indicadores con los que lidiar.

Realmente simplifica las cosas.