Verkettete Liste

Stromberg

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

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

Werner Salomon

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.
Mit

m_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.

Stromberg

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

Stromberg

Werner biste noch da?

MfG
Stromberg

Werner Salomon

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

Th

Hallo Stromberg, dein Schleifenbedingung ist falsch:

while(temp->m_next!=0) // <- falsch

Du ü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.

Stromberg

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) // <- falsch

sowas fällt mir aber irgendwie nie selber auf :).

MfG
Stromberg

Stromberg

Wie kann ich den überprüfen ob alles korrekt gelöscht wird, und nix überig bleibt und eventuell Speicherlücken entstehen?

MfG
Stromberg

oelsni

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.

Werner Salomon

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 = 0

Wenn 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