Wie zeige ich eine geordnete doppelt verknüpfte Liste rückwärts an?[geschlossen]

Question

Es ist unwahrscheinlich, dass diese Frage künftigen Besuchern weiterhilft.Es ist nur für ein kleines geografisches Gebiet, einen bestimmten Zeitpunkt oder eine außerordentlich begrenzte Situation relevant, die nicht allgemein auf das weltweite Publikum des Internets anwendbar ist.Wenn Sie Hilfe benötigen, um diese Frage breiter anwendbar zu machen, Besuche das Hilfe Zentrum.

Geschlossen vor 7 Jahren.

Ich habe damit zu kämpfen.Ich habe es so eingestellt, dass es den größten Teil der Liste anzeigt, aber eine der Einsen wird nicht angezeigt, und ich kann beim besten Willen nicht herausfinden, wie ich das Problem beheben kann.

Hier ist der relevante Code, denke ich.

Meine Einfügefunktion:

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

   }
 }

Meine displayBackwards-Funktion:

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

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

Und der relevante Teil meiner Hauptfunktion:

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

Meine Ausgabe ist derzeit:

 Testing displayBackward
 3
 2
 1

Answer 1

Dieser Code ist das Problem (in der Einfügefunktion)

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

Du brauchst

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

Ihr ursprünglicher Code funktioniert in bestimmten Fällen, es sei denn, Sie versuchen, Daten einzufügen, die kleiner oder gleich den Daten in Ihrem aktuellen ersten Knoten sind.

Außerdem gehe ich davon aus, dass Ihr Konstruktor mNext und mPrevious auf NULL initialisiert.Wenn nicht, werden Sie andere Probleme haben.

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

Dadurch wird der Rückzeiger des neuen Knotens nicht verknüpft.

Möglicherweise ist auch noch mehr Fehler in Ihrem Code.

---

Eine einfache Möglichkeit, eine doppelt verknüpfte Liste zu codieren, besteht darin, Folgendes zu tun:

• Unterscheide zwischen Liste Und Knoten Typ und
• Stellen Sie sicher, dass jede Liste immer einen Dummy-Knoten namens a hat Header-Knoten.

Auf diese Weise haben Sie keine NULL Hinweise, mit denen man sich befassen muss.

Es vereinfacht die Dinge wirklich.