Verkettete Liste
-
Folgenden Code von hier http://c-plusplus.net/forum/viewtopic-var-p-is-1324660.html#1324660 check ich irgendwie nicht, und zwar:
#include <iostream> using namespace std; class SList //1 { public: typedef int value_type; private: class Node // Listenelement 2 { public: explicit Node( const value_type& x, Node* next = 0 ) :m_next( next ), m_value( x ) { cout << "Node\n"; } Node* m_next; value_type m_value; }; public: SList() // ersetzt das init() : m_kopf( value_type() ) , m_ende( &m_kopf ) {cout << "SList\n";} ~SList() { clear(); } // immer schön wieder aufräumen void push_back( const value_type& x ) // ersetzt das einfuegen() was ein anhaengen() ist { m_ende->m_next = new Node( x ); m_ende = m_ende->m_next; } void clear() // ersetzt das ende() { for( Node* p = m_kopf.m_next; p; ) { Node* tmp = p; p = p->m_next; delete tmp; } m_kopf.m_next = 0; m_ende = &m_kopf; } // -- Ausgabe std::ostream& ausgeben( std::ostream& out, const char* delim = "" ) { for( Node* p = m_kopf.m_next; p; p = p->m_next ) { out << p->m_value << delim; } return out; } private: // Kopieren z.Zt. nicht vorgesehen; -> "Regel der drei" SList( const SList& ); SList& operator=( const SList& ); // -- Member Node m_kopf; Node* m_ende; }; int main() { SList A; A.push_back(20); A.push_back(200); return 0; }Es gibt anfangs ein "m_kopf" Node Objekt, und einen Node Zeiger namens "m_ende".
"m_kopf" wird mit 0 initialisiert, m_ende zeigt auf m_kopf.// m_kopf --> a --> b --> c --> d --> m_ende
// ^-----------------------------------------------|Doch jetzt wenn ich zur Funktion push_back() gehe, dann blick ich nicht mehr durch.
void push_back( const value_type& x ) // ersetzt das einfuegen() was ein anhaengen() ist { m_ende->m_next = new Node( x ); m_ende = m_ende->m_next; }Der Node Zeiger "m_next" aus "m_kopf" hat nun ein neus Node Objekt auf dem HEap erstelle und Zeigt darauf:
m_kopf.m_next --> neues Objekt
Und die Elementvariable "m_next" vom Zeiger "m_next" zeigt auf NULL. (konstruktor)
Dann übernimmt m_ende die Adresse von dem neuen Objekt (m_next).
Trotzdem check ich net was das nun alles bringt. Da soll sich doch so eine Zeigerkettet ergeben....mh ich hab glaub irgendwas nicht richtig verstanden!? Kann mir jemand des alles nochmal n bissel erklären, den irgendwas mach ich ziemlich falsch in meinem Kopf.http://www.pictureupload.de/originals/pictures/041107125828_mein_gehirn.JPG
MfG
Stromberg
-
Hallo Stromberg,
mal angenommen, die Liste ist leer. Dann haben wir folgende Situation:
m_ende | v +-------+ | m_kopf| | 0 | +-------+Also es gibt ein Node-Element m_kopf, dessen Member m_next den Wert 0 (bzw. NIL Not In List) hat und der Member m_ende der Liste zeigt auf eben dieses Node-Objekt m_kopf.
Jetzt wird z.B. push_back( x1 ) aufgerufen. In der ersten Zeile geschieht
m_ende->m_next = new Node( x );Dann ergibt sich folgendes Bild
m_ende | v +-------+ +->+-------+ | m_kopf| | | x1 | | p1-------+ | 0 | +-------+ +-------+'new Node( x )' legt ein Knotenobjekt auf dem Heap in diesem Fall mit dem Value x1. Beachte nun, dass m_ende auf m_kopf zeigt und m_ende->m_next der Member m_next von m_kopf ist. Diesem m_next wird die Adresse (p1) des Nodes von x1 zugewiesen.
In der zweiten Zeile geschieht
m_ende = m_ende->m_next;Also m_ende bekommt jetzt den Wert der Adresse des neuen Knoten zugewiesen - also zeigt m_ende auf den neuen Knoten
m_ende | v +-------+ +->+-------+ | m_kopf| | | x1 | | p1-------+ | 0 | +-------+ +-------+Beim nächsten push_back (z.B. push_back( x2 )) geht es genauso weiter. Nach der ersten Zeile ist die Situation
m_ende | v +-------+ +->+-------+ +->+-------+ | m_kopf| | | x1 | | | x2 | | p1-------+ | p2-------+ | 0 | +-------+ +-------+ +-------+.. und mit der zweiten Zeile wird m_ende auf den nächsten Knoten verschoben - also immer auf den Letzten.
m_ende | v +-------+ +->+-------+ +->+-------+ | m_kopf| | | x1 | | | x2 | | p1-------+ | p2-------+ | 0 | +-------+ +-------+ +-------+An dieser push_back-Methode sieht man auch den Vorteil des Dummy-Kopf-Elements, welches kein Element der eigentlichen Liste ist. Wenn man statt des Elements m_kopf nur einen Pointer auf das erste Element hat - also Node* m_head; - so hätte m_ende den Wert 0 (bzw. NIL), wenn die Liste leer wäre. Also müsste man innerhalb von push_back diesen Fall immer abfragen. Also so etwa
void push_back( const value_type& x ) { if( m_head ) // Node* m_head; { // Liste ist nicht leer -> m_ende ist garantiert belegt // Code wie oben m_ende->m_next = new Node( x ); m_ende = m_ende->m_next; } else { // Liste ist leer also Sonderbehandlung m_head = new Node( x ); m_ende = m_head; } }So eine Konstruktion mit dem Dummy-Element nennt man auch ein Sentinel (engl. Wächter) (siehe auch bei Wiki)
Gruß
Werner
-
Könntest du mir auch noch die clear() Funktion erklären, weil diese for-Schleife versteh ich mal gar nicht, warum ist die 3te Lücke leer.
void clear() // ersetzt das ende() { for( Node* p = m_kopf.m_next; p; ) { Node* tmp = p; p = p->m_next; delete tmp; } m_kopf.m_next = 0; m_ende = &m_kopf; }Das "m_ende=&m_kopf" ist aber dann doch nicht mehr wichtig zum schluss oder?
MfG
Stromberg
-
Noch was, was hältst du von dieser Lösung, weil deine versteh ich (noch) nicht.
List::~List() { cout << "Destruktor List\n"; Node *temp=&m_kopf; Node *save; while(temp->m_next!=0) { cout << "Entferne Node Objekt\n"; save=temp->m_next; delete temp; temp=0; temp=save; } m_ende=&m_kopf; }MfG
Stromberg
-
Hallo Stromberg,
zur clear-Methode: mal angenommen die Liste hat 2 Elemente und es wird clear() aufgerufen. Die Ausgangssituation ist wieder
m_ende | v +-------+ +->+-------+ +->+-------+ | m_kopf| | | x1 | | | x2 | | p1-------+ | p2-------+ | 0 | +-------+ +-------+ +-------+void clear() { for( Node* p = m_kopf.m_next; p; ) { Node* tmp = p; p = p->m_next; delete tmp;Die Variable 'p' wird mit m_kopf.m_next initialisiert - enthält also den Wert 'p1' - ungleich 0, also wird die Schleife nicht abgebrochen. In Zeile 5 wird der Zeiger in 'tmp' gemerkt und anschließend in Zeile 6 die Variable p auf den nächsten Knoten gesetzt. Vor der Zeile 7 haben wir dann folgendes:
tmp p m_ende | | | v v v +-------+ +->+-------+ +->+-------+ | m_kopf| | | x1 | | | x2 | | p1-------+ | p2-------+ | 0 | +-------+ +-------+ +-------+jetzt geschieht 'delete tmp' - d.h. der Knoten mit x1 wird gelöscht. 'p' ist immer noch ungleich 0 - sie hat ja den Wert 'p2' - die Schleife wird erneut betreten und vor der Zeile 7 sieht es jetzt so aus
tmp m_ende p == 0 | | v v +-------+ +->? +-------+ | m_kopf| | | x2 | | p1-------+ | 0 | +-------+ +-------+Durch das 'Weiterschalten' von 'P' hat diese Variable den Wert 0 angenommen - von p2->m_next. Vorher wurde 'p' nach 'tmp' kopiert, die jetzt immer noch auf den Knoten mit x2 zeigt.
In Zeile 7 wird mit 'delete tmp' der Knoten mit x2 gelöscht.
Übrig bleiben jetzt zwei 'hängende Zeiger' nämlich m_kop.m_next der auf ein p1 zeigt wo kein Knoten x1 mehr ist und 'm_ende' der auf ein nicht mehr vorhandenes x2 zeigt.
Mitm_kopf.m_next = 0; m_ende = &m_kopf;wird das bereinigt und das ist auch notwendig, denn mit dem nächsten push_back z.B. wird ja auf m_ende->m_next also dann auf den Next-Pointer in m_kopf zugegriffen und das natürlich definiert sein.
Jetzt zu Deinem Code
Stromberg schrieb:
Noch was, was hältst du von dieser Lösung, weil deine versteh ich (noch) nicht.
List::~List() { cout << "Destruktor List\n"; Node *temp=&m_kopf; Node *save; while(temp->m_next!=0) { cout << "Entferne Node Objekt\n"; save=temp->m_next; delete temp; temp=0; temp=save; } m_ende=&m_kopf; }Angenommen wir beginnen wieder mit der Liste mit den beiden Elementen x1 und x2 dann erhält man vor Zeile 10 diese Situation
temp save m_ende | | | v v v +-------+ +->+-------+ +->+-------+ | m_kopf| | | x1 | | | x2 | | p1-------+ | p2-------+ | 0 | +-------+ +-------+ +-------+Dann rufst Du 'delete temp' versuchst also das Kopf-Element vom Heap zu entfernen. Dies ist aber ein Member der Liste und im besten Fall beendet Dein Memory-Management hier das Programm.
Stromberg schrieb:
... weil diese for-Schleife versteh ich mal gar nicht, warum ist die 3te Lücke leer.
nun warum nicht - was sollte darin stehen?
Gruß
Werner
-
Wow Werner
Hast dir ja viel Mühe dabei gegeben, vllt sollte das in die FAQ gesetzt werden.
-
Aber wenns so ist, dann gehts doch:
List::~List() { cout << "Destruktor List\n"; Node *temp=m_head.m_next; Node *save; while(temp->m_next!=0) { cout << "Entferne Node Objekt\n"; save=temp->m_next; delete temp; temp=0; temp=save; } m_end=&m_head; }??? Also wenn das erste "Node *temp=m_head.m_next;" ist.
http://www.pictureupload.de/pictures/051107153523_mein_gehirn.JPG <-- so stell ich mir das vor.Jetzt schau ich mir mal deine Erklärung an.
Schon mal im Voraus ein Dankeschön für die große Mühe.MfG
Stromberg
-
Werner biste noch da?
MfG
Stromberg
-
Stromberg schrieb:
Werner biste noch da?
Öh - ja klar - nicht ständig aber immer wieder.
Erwartest Du eine Antwort? ... ich sehe keine Frage
Gruß
Werner
-
Hallo Stromberg, dein Schleifenbedingung ist falsch:
while(temp->m_next!=0) // <- falschDu überprüfst nur, ob der Member 'next' 0 ist, aber nicht ob die eigentliche Variable 'temp' 0 ist.
Wenn du die for-Schleife von Werner eigenartig findest, dann kann man sie auch als while-Schleife formulieren:
Node* p = m_kopf.m_next; while(p) // entspricht: p != 0 { Node* tmp = p; p = p->m_next; delete tmp; }Der Vorteil mit der for-Schleife bezieht sich auf das automatische Löschen der Variable p nach der Schleife (und nicht erst am Ende des umgebenden Blocks).
Eigentlich würde man ja die "Inkrementieranweisung" als 3. Parameter der for-Schleife angeben, aber da evtl. nach dem Löschen von 'tmp' der Inhalt schon wieder anderweitig verwendet sein könnte (in Multithreading/-tasking-Systemen) muß zuerst 'p' auf den neuen Wert gesetzt werden und danach erst das Objekt in 'tmp' löschen.
-
Ich hab Werner's Beispiel jetzt schon verstanden. War bloß anfangs verwirrt, weil ich immer so nä standard for schleife benutze und zwar:
(int i=0;i<X;i++)...deshalb hat mich des anfangs bissel verwirrt, weil mir mein "++" gefehlt hat
Aber jetzt is alles klar.Bei meinem Beispiel müsste es dann aber doch dann so gehen:
List::~List() { cout << "Destruktor List\n"; Node *temp=m_head.m_next; Node *save; while(temp!=0) { cout << "Entferne Node Objekt\n"; save=temp->m_next; delete temp; temp=0; temp=save; } m_end=&m_head; }????????
Das hier war natürlich unsinnig:
while(temp->m_next!=0) // <- falschsowas fällt mir aber irgendwie nie selber auf :).
MfG
Stromberg
-
Wie kann ich den überprüfen ob alles korrekt gelöscht wird, und nix überig bleibt und eventuell Speicherlücken entstehen?
MfG
Stromberg
-
nur durch nen test, also meines wissens nach. und zwar ist es nen doppelter test (so mache ich es immer). erstens nen event ect reindrücken ob mit scanf oder wer weis, das löst das erstellen von x elementen in der kette aus (sollten genug sein das auch ordentlich speicher drauf geht). alle listenelemte als extrapointer wo speichern nach der erstellung und taskmgr aufmachen. dann geht es los prog starten im task speicher anschauen, dann erstellung auslösen und schauen wieviel speicher extra gefressen wird. danach löschen auslösen am ende muss wieder gleicher speicherwert im tastmgr stehen, desweiteren kannst dann in dem extraarray der pointer prüfen ob an einer speicheradresse wirklich noch ein element liegt oder nicht. gibt sicher eine wesentlich bessere methode aber die ist mir nicht bekannt
. Nichts desto trotz ist dennoch mit meiner methode wirklich feststellbar ob wirklich alles wieder gelöscht wurde, bis auf jedes einzellne element ist es so nachprüfbar. das mit den extra pointerarray kannst weglassen wenn dich das nicht so genau interessiert der task zeigt ja die kb an also ziemlich genau wodurch du erkennen kannst ob dein prog nach dem löschen mehr speicher benutzt als vor der erstellung.
-
Stromberg schrieb:
Wie kann ich den überprüfen ob alles korrekt gelöscht wird, und nix überig bleibt und eventuell Speicherlücken entstehen?
Es gibt dafür Tools - z.B. Boundschecker - oder selbst die MS-Visual-Studio-Umgebung oder boost.test können Speicherlücken detektieren. Ansonsten kann man sich auch selbst mit einer Testklasse behelfen.
Zunächst muss man aus der Liste ein Template machen ..
template< typename T > class SList { public: typedef T value_type;dann kann man sich ein eigenes Testprogramm schreiben
#include "List.h" #include <iostream> class LifeCtrl { public: LifeCtrl() { ++m_cnt; } ~LifeCtrl() { --m_cnt; } LifeCtrl( const LifeCtrl& ) { ++m_cnt; } static int m_cnt; // Zähler für alle aktuell existierenden LifeCtrl-Objekte }; int LifeCtrl::m_cnt = 0; int main() { using namespace std; { SList< LifeCtrl > l; for( int i=0; i<3; ++i ) l.push_back( LifeCtrl() ); l.clear(); cout << "nach clear: Anzahl LifeCtrl-Objekte = " << LifeCtrl::m_cnt << endl; for( int i=0; i<3; ++i ) l.push_back( LifeCtrl() ); // weiter Aktionen auf der Liste ... oder weitere Listen } // damit sollte der Destruktor aufgerufen werden cout << "Ende: Anzahl LifeCtrl-Objekte = " << LifeCtrl::m_cnt << endl; return 0; }Die erwartete Ausgabe wäre:
nach clear: Anzahl LifeCtrl-Objekte = 1 Ende: Anzahl LifeCtrl-Objekte = 0Wenn die Liste mit clear() gelöscht wird, so bleibt das Sentinel-Objekt zurück, da die Liste selbst noch existiert. Wird der Destruktor der Liste aufgerufen - mit Verlassen des Scopes - so darf kein LifCtrl-Objekt mehr übrig bleiben - d.h. die Anzahl muss 0 sein.
Gruß
Werner
