Doppelt verknüpfte Listen in C++

Ich habe eine Zuordnung, die erfordert, dass wir eine doppelt verknüpfte List-Klasse implementieren. Aus irgendeinem Grunde definierte sie den Knoten struct wie folgt:Doppelt verknüpfte Listen in C++

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

Es scheint mir, dass es viel einfacher sein würde, um die Klasse zu schreiben, wenn die struct Mitglied ‚Daten‘ kein Zeiger sind. Unnötig zu sagen, dass ich es nicht ändern kann, also werde ich es einfach umgehen müssen. Ich habe versucht, das Verfahren implementiert, die ein Element an den Anfang der Liste hinzufügt, wie folgt:

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 debuggen ddd Verwendung erkannte ich, dass alles funktioniert das erste Mal, wenn Sie eine Nummer einfügen, aber beim zweiten Mal wird alles verschraubt, seit du 'val' auf das neue Element gesetzt hast, "überschreibt" es das erste, da die Speicheradresse von val benutzt wurde. Ich habe versucht, andere Dinge zu tun, wie, anstatt nur die ‚val‘ Variable, die Sie folgendermaßen vorgehen:

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

np->o = valp

Dies nicht zu funktionieren schien. Ich denke, das liegt daran, dass es nur eine kompliziertere Form dessen ist, was ich oben nur mit einem zusätzlichen Speicherleck gemacht habe :)

Irgendwelche Ideen/Zeiger in die richtige Richtung wären toll.

Quelle

2009-12-11 blcArmadillo

+1 für die ehrenvollen Hausaufgaben Haftungsausschluss. –

Werfen Sie einen Blick darauf, die erste Antwort kann Ihnen helfen, das Problem zu verstehen: http://stackoverflow.com/questions/5727/what-are-the-barriers-to-understanding-pointers-and-what-can-be -done-to-overover – Dan

Wenn Sie eine Chance bekommen, werfen Sie einen Blick auf diese auch: http://StackOverflow.com/Questions/599308/proper-Stack-and-Heap-usage-in-C - Unterschied zwischen Stack und Heap-Zuweisung. – Dan

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

Sie sollten new verwenden, um Speicherplatz auf dem Heap zuzuweisen, wie Sie vermuten, aber Ihr Datenzeiger muss direkt auf die Adresse verweisen, die von new zurückgegeben wird.

Ihr Fehler in Ihrem letzten Versuch ist hier:

valp = &val;

Sie wechseln valp zu Punkt woanders (die Adresse von val), wenn Sie wahrscheinlich Daten Kopie val versuchen, nicht seine Adresse.

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

Quelle

2009-12-11 05:11:55

Ahh. Das macht Sinn, warum ich Werte zurück -1074723840 bekam, als ich versuchte, die Werte zu lesen. Das hilft, obwohl ich denke, dass ich immer noch nicht ganz sicher bin, wie ich das beheben soll? Können Sie mir Stichworte geben, die mir bei meiner Suche helfen könnten? Vielen Dank. – blcArmadillo

Nur pingelig: val ist keine temporäre. Es ist eine "automatische" Variable, auch bekannt als Stapelvariable. Ansonsten, gute Antwort. – Dan

http://en.wikipedia.org/wiki/Automatic_variable – Dan

T val = *o; 

    np->o = &val;

Dieser Teil ist verdächtig. Der Hinweis ist, dass der auf dem Stapel in einer Funktion zugewiesene Speicher nicht verfügbar ist, sobald die Funktion den Gültigkeitsbereich verlässt.

Quelle

2009-12-11 05:13:55

Ich glaube nicht, sollten Sie dies tun:

in der Knotenstruktur

T val = *o;

Da das o Mitglied ein Zeiger ist, und der Parameter auf insertFront ist wahrscheinlich auch ein Zeiger, Ihr Lehrer für Sie beabsichtigt um den angegebenen Zeiger zu übernehmen und in der Liste zu speichern, erstellen Sie keine Kopie des Objekts und speichern Sie einen Zeiger darauf. Speichern Sie einfach den o Zeiger, der in insertFront als o Mitglied des Knotens übergeben wurde, und Sie sollten OK sein.

Quelle

2009-12-11 05:15:21 Wyzard

stimme ich voll und ganz zu. Es sollte eher 'np-> data = o;' –

Nicht unbedingt sein. Es sollte einige Kommentare geben, die erklären, ob das übergebene T * dynamisch zugewiesen wurde oder nicht und ob der DList das Eigentum übernehmen soll oder ob es eine Kopie machen soll. Wenn Sie die Antworten auf diese Fragen nicht kennen, können Sie sie möglicherweise nur mit etwas Glück umsetzen. – Dan

@Sammy, woher weißt du, dass es nicht 'np-> data = new (* o);'? – Dan

Ihr Code paßt nicht Ihre Definition von node - in node Sie ein data Mitglied sind definiert, aber in Ihrem Code sind Sie o stattdessen verwenden.

In jedem Fall müssen Sie zwei dynamische Zuordnungen vornehmen, um jeden Knoten hinzuzufügen - einen für den Knoten selbst und einen für das Datenobjekt, auf das er zeigen wird. Wenn Sie dieses Datenobjekt zuordnen, können Sie den Rückgabewert von new direkt dem Zeiger in Ihrem Knoten zuweisen. Dann müssen Sie das Datenobjekt kopieren, dessen Zeiger an das gerade zugewiesene Datenobjekt übergeben wurde, auf das der Zeiger im Knoten zeigt.

Quelle

2009-12-11 05:17:11

Guter Fang. Ich habe die Struktur nach dem Kopieren in SO modifiziert und vergessen, sie an anderen Stellen zu ändern. – blcArmadillo

Sie denken die Zeiger Nutzlast ist unbequem. Aber vielleicht ist die Liste gemeint verwendet werden, um einen Link oben auf vorhandene Objekte zu erstellen, 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)

Quelle

2009-12-11 06:51:31 xtofl

Doppelt verknüpfte Listen in C++

Antwort

Verwandte Themen