Doppelt verkettete Listen in C++

Question

Ich habe eine Aufgabe, bei der wir eine Klasse mit doppelt verknüpften Listen implementieren müssen. Aus irgendeinem Grund definierten sie den Knoten struct wie folgt:

struct node {
  node   *next;
  node   *prev;
  T      *o;
};

Es scheint mir, dass es viel einfacher wäre, die Klasse zu schreiben, wenn das Strukturmitglied "data" kein Zeiger wäre. Unnötig zu sagen, dass ich es nicht ändern kann, also werde ich es einfach umgehen müssen. Ich habe versucht, die Methode, die ein Element an den Anfang der Liste hinzufügt, wie folgt zu implementieren:

template <typename T>
void Dlist<T>::insertFront(T *o) {
    node *np = new node;
    T val = *o;

    np->o = &val;
    np->prev = NULL;
    np->next = first;

    if (!isEmpty()) {
        first->prev = np;
    } else {
        last = np;
    }
    first = np;
}

Während ich ddd zum Debuggen benutzte, stellte ich fest, dass alles beim ersten Mal, wenn man eine Zahl einfügt, gut funktioniert, aber beim zweiten Mal wird alles durcheinander gebracht, denn sobald man 'val' auf das neue Element setzt, wird das erste Element "überschrieben", da die Speicheradresse von val verwendet wurde. Ich habe versucht, andere Dinge zu tun, wie z.B. anstatt nur die Variable 'val' zu haben, folgendes zu tun:

T *valp = new T;
T val;
valp = &val;
val = *o;

np->o = valp

Auch das schien nicht zu funktionieren. Ich denke, das ist, weil es ziemlich viel nur eine kompliziertere Form von dem, was ich oben nur mit einem zusätzlichen Speicherleck :)

Jede Idee/jeder Hinweis in die richtige Richtung wäre großartig.

Answer 1

Die T val die Sie erstellen, ist eine automatische Variable. Ihr Fehler besteht darin, die Adresse dieser Stack-Variablen zu speichern.

Sie sollten Folgendes verwenden new um Platz auf dem Heap zuzuweisen, wie Sie vermuten, aber Ihr Datenzeiger muss direkt auf die Adresse zeigen, die von new .

Ihr Fehler bei Ihrem letzten Versuch liegt hier:

valp = &val;

Sie verändern sich valp a auf etwas anderes zeigen (die Adresse von val), wenn Sie wahrscheinlich versuchen Val's Daten kopieren und nicht seine Adresse.

Die an Ihre Funktion übergebenen Daten sollten in den neuen Speicher kopiert werden, wo valp Punkte.

Answer 2

Ich denke nicht, dass Sie das tun sollten:

T val = *o;

Da die o Mitglied in der Knotenstruktur ist ein Zeiger, und der Parameter für insertFront auch ein Zeiger ist, beabsichtigt Ihr Lehrer wahrscheinlich, dass Sie den Zeiger, den Sie erhalten, in der Liste speichern und nicht eine Kopie des Objekts erstellen und einen Zeiger darauf speichern. Speichern Sie einfach den o Zeiger übergeben in insertFront als die o Mitglied des Knotens und es sollte alles in Ordnung sein.

Answer 3

 T val = *o;

    np->o = &val;

Dieser Teil ist verdächtig. Der Hinweis ist, dass der in einer Funktion auf dem Stack zugewiesene Speicher nicht mehr zur Verfügung steht, sobald die Funktion den Anwendungsbereich verlässt.

Answer 4

Ihr Code passt nicht zu Ihrer Definition von node -- in node definieren Sie eine data Mitglied, aber in Ihrem Code verwenden Sie o stattdessen.

In jedem Fall müssen Sie zwei dynamische Zuweisungen vornehmen, um jeden Knoten hinzuzufügen - eine für den Knoten selbst und eine für das Datenobjekt, auf das er zeigen soll. Wenn Sie das Datenobjekt zuordnen, können Sie auch den Rückgabewert von new direkt auf den Zeiger in Ihrem Knoten. Dann müssen Sie das Datenobjekt, dessen Zeiger übergeben wurde, in das Datenobjekt kopieren, das Sie gerade zugewiesen haben und auf das der Zeiger im Knoten zeigt.

Answer 5

Sie t die Zeiger-Nutzlast ist unpraktisch. Aber vielleicht soll die Liste ja dazu dienen, einen Link zu erstellen oben auf bestehende Objekte, wie in:

struct A { int i; };
A as[10] = { 1,2,3,4,5,6,7,8,9,10 };

LinkedList primes_in_my_data;
insertFront( primes_in_my_data, &as[1] );
insertFront( primes_in_my_data, &as[2] );
insertFront( primes_in_my_data, &as[3] );
insertFront( primes_in_my_data, &as[5] );
insertFront( primes_in_my_data, &as[7] );

// now I have a linked list of primes, and caused no extra memory allocation
// (except for the list overhead)