Element aus einfach verketteter Liste löschen

Hallo Leute,

ich habe hier eine einfach verkettete Liste, die aus Objekten vom Typ „Element“ besteht. Ich möchte nun mit Hilfe einer Funktion loescheElement() ein ganz bestimmtes Element aus der Liste entfernen. Leider stürzt mir das Programm immer ab, sobald der delete-Befehl ausgeführt wird - ich bin noch Anfänger was C++ angeht. Hier mein Ansatz der Funktion zum Löschen:

void Liste::loescheElement(Element * a)
{
Element * prev=NULL;
Element * aktuell=listenanker;
while(aktuell!=a)
{
prev=aktuell;
aktuell=aktuell->getNext();
}
if(prev==NULL){listenanker=aktuell->getNext();}
else{prev->setNext(aktuell->getNext());}
delete aktuell;
}
Noch einige Infos:

  • jedes Element besitzt einen Zeiger „next“, der auf das nächste Listenelement zeigt
  • die Liste besitzt einen Zeiger „listenanker“, der auf das erste Listenelement zeigt
  • ich habe die Klassen „Liste“ und „Element“ in getrennten Dateien (falls das irgendwas zur Sache tut)
  • wenn ich den delete-Befehl auskommentiere funktioniert alles, aber dann entstehen doch Speicherlecks…oder?
  • das Element „a“, das als Parameter übergeben, wird ist garantiert in der Liste vorhanden

Ich hoffe ihr könnt mir weiterhelfen. Falls noch weitere Infos benötigt werden, kann ich die gerne Posten.

MfG,
0nyx

Hallo 0nyx

ich habe hier eine einfach verkettete Liste, die aus Objekten
vom Typ „Element“ besteht. Ich möchte nun mit Hilfe einer
Funktion loescheElement() ein ganz bestimmtes Element aus der
Liste entfernen. Leider stürzt mir das Programm immer ab,
sobald der delete-Befehl ausgeführt wird - ich bin noch
Anfänger was C++ angeht. Hier mein Ansatz der Funktion zum
Löschen:

OK

void Liste::loescheElement(Element * a)
{
Element * prev=NULL;
Element * aktuell=listenanker;
while(aktuell!=a)
{
prev=aktuell;
aktuell=aktuell->getNext();
}
if(prev==NULL){listenanker=aktuell->getNext();}
else{prev->setNext(aktuell->getNext());}
delete aktuell;
}

Das sieht unheimlich kompliziert aus,
für so einen einfachen Zweck :wink:

Wo kommen denn die Listenelemente
her? Aus ‚next = new element;‘ ?

Gibt es Konstruktoren oder Destruktoren
für ‚Element‘? Wie sehen die aus?

Kannst Du bitte (neben Deiner Intention
zum Zweck des Programms und seines komplizierten
Designs) alle relevanten Klassendeklarationen
sowie Konstruktoren/Destruktoren posten?

Grüße

CMБ

ich habe hier eine einfach verkettete Liste, die aus Objekten
vom Typ „Element“ besteht. Ich möchte nun mit Hilfe einer
Funktion loescheElement() ein ganz bestimmtes Element aus der
Liste entfernen. Leider stürzt mir das Programm immer ab,
sobald der delete-Befehl ausgeführt wird

Warum implementierst du die Liste selber? Aus Spass an der Freude, oder weil du das für irgendeine (Haus)aufgabe brauchst? Die STL bietet praktisch alle gängigen Datenstrukturen an, unter anderem auch std::list. In C++ gibt es wirklich nur die zwei Gründe, eine Liste selbst zu implementieren.

Dein Code sieht soweit gut aus. Wenn sich delete verabschiedet, dann solltest du - wie in der ersten Antwort erwähnt -, sicherstellen, dass alle Elemente wirklich per new erzeugt werden. Wenn das so ist, dann ist wohl irgendwas im Destruktor von Element falsch.

Lass das Programm mal im Debugger laufen, der sollte bei dem Problem schon einigermaßen informativ sein.

Hallo Semjon!

Zunächst folgendes: Ich habe im ersten Posting versucht das ganze vereinfacht darzustellen und habe dazu „Liste“ und „Element“ als Bezeichnungen gewählt. In der Klassendeklaration weiter unten werden stattdessen die Bezeichnungen „CListe“ und „CStein“ (entspricht dem Element) auftauchen. Ebenfalls heißt „listenanker“ dort „sl“.

Wo kommen denn die Listenelemente
her? Aus ‚next = new element;‘ ?

Die Elemente (Steine) werden in einer Funktion „macheSteine()“ mit „new“ erzeugt und dann über eine Funktion „insertListe()“ an das Ende der Liste geknüpft (d.h. an den „next“-Zeiger des letzten Listenelements).

Gibt es Konstruktoren oder Destruktoren
für ‚Element‘? Wie sehen die aus?

Kannst Du bitte (neben Deiner Intention
zum Zweck des Programms und seines komplizierten
Designs) alle relevanten Klassendeklarationen
sowie Konstruktoren/Destruktoren posten?

Intention: Das Programm ist als Übung gedacht und soll eine Art vereinfachtes Tetris ergeben (ich nehme an du kennst Tetris). Dabei fallen die Steine von oben herab, bis sie unten den Bildschirmrand erreichen, bzw. mit einem anderen Stein kollidieren. Diese Steine (CStein) werden in der einfach verketteten Liste (CListe) gespeichert (Vorgabe!). Wenn bestimmte Bedingungen eintreffen, sollen einzelne Steine wieder gelöscht werden und somit auch nicht mehr auf der Oberfläche dargestellt werden. Die Klasse „View“, die nachfolgend auftaucht, dient zur Prüfung, ob es Kollisionen zwischen den einzelnen Steinen gibt.

Nachfolgend die Headerdateien für CStein und CListe:

class CStein
{
private:
int x;
int y;
int breite;
int hoehe;
char farbe;
CStein * next;
View * v;
public:
CStein();
CStein(int x, int y, int breite, int hoehe, char farbe, View * v);
void setX(int x);
void setY(int y);
void setBreite(int b);
void setHoehe(int h);
void setNext(CStein * n);
void setView(View * v);
int getX() const;
int getY() const;
int getBreite() const;
int getHoehe() const;
int getFarbe() const;
CStein * getNext() const;
void show() const;
void showGUI(HDC hdc) const;
bool kollision(CStein * s) const;
void dropOneLine();
void cutOneLine();
};

= = = = = = = = = =

class CListe
{
private:
CStein * sl;
View * v;
void copy(View * v, CStein * &sl, CListe &original);
void cutLine(int i, HWND hWnd);
void deleteStein(CStein * a);
public:
CListe();
CListe(CListe &original);
CListe & operator=(CListe &original);
~CListe();
void clearListe();
void insertListe(CStein * s);
void showListe(HWND hWnd) const;
int animateListe(HWND hWnd, CStein * s, char richtung);
bool kollision() const;
CStein * const getSL() const;
View * const getView() const;
void checkLines(HWND hWnd);
};
Konstruktoren CStein:
CStein::CStein()
{
x=0;
y=0;
breite=0;
hoehe=0;
farbe=177;
next=NULL;
v=NULL;
}

CStein::CStein(int x, int y, int breite, int hoehe, char farbe, View * v)
{
this->x=x;
this->y=y;
this->breite=breite;
this->hoehe=hoehe;
this->farbe=farbe;
next=NULL;
this->v=v;
} Destruktor CStein:
Ich habe KEINEN Destruktor für CStein implementiert, d.h. ich benutze den Standard-Destruktor der vom Compiler gestellt wird. Mein Gedanke dahinter: obwohl ein Stein Zeiger auf Heap-Objekte enthält (next, v), sollen diese beim Vernichten des Steins nicht gelöscht werden, da sie ja noch vom Programm verwendet werden. (Liegt hier etwa mein Fehler?)

Konstruktor CListe:
CListe::CListe()
{
sl=NULL;
this->v=new View();
v->clear();
} Destruktor CListe:
CListe::~CListe()
{
if(sl!=NULL){clearListe();}
delete v; v=NULL;
}

So, ich hoffe das hilft weiter.

MfG,
0nyx

Hallo!

Warum implementierst du die Liste selber? Aus Spass an der
Freude, oder weil du das für irgendeine (Haus)aufgabe
brauchst? Die STL bietet praktisch alle gängigen
Datenstrukturen an, unter anderem auch std::list. In C++ gibt
es wirklich nur die zwei Gründe, eine Liste selbst zu
implementieren.

Ja, ich mache das ganze für ein Praktikum und muss es dashalb selbst implementieren. Wie gesagt, ich bin noch anfänger.

Dein Code sieht soweit gut aus. Wenn sich delete
verabschiedet, dann solltest du - wie in der ersten Antwort
erwähnt -, sicherstellen, dass alle Elemente wirklich per new
erzeugt werden. Wenn das so ist, dann ist wohl irgendwas im
Destruktor von Element falsch.

Die Elemente werden per „new“ erzeugt…

Hallo 0nyx,

void Liste::loescheElement(Element * a)
{
Element * prev=NULL;
Element * aktuell=listenanker;

Was passiert wohl, wenn „listenanker“ == NULL ist in dem while() ???

while(aktuell!=a)
{
prev=aktuell;
aktuell=aktuell->getNext();
}
if(prev==NULL){listenanker=aktuell->getNext();}
else{prev->setNext(aktuell->getNext());}
delete aktuell;
}

Da du lernen sollst, wie programmiert wird, solltest du mal den Debugger anwerfen und sehen, WAS dein Programm macht.
Dabei lernst du mit dem Debugger umzugehen und wie dein Programm von der CPU verarbeitet wird.

MfG Peter(TOO)

Hallo Peter!

Was passiert wohl, wenn „listenanker“ == NULL ist in dem
while() ???

Dieses Problem habe ich bereits eine Ebene „weiter oben“ abgesichert, d.h. wenn die Variable listenanker NULL ist, dann wird die Funktion loescheElement() gar nicht erst aufgerufen.

Da du lernen sollst, wie programmiert wird, solltest du mal
den Debugger anwerfen und sehen, WAS dein Programm macht.

Den Debugger habe ich schon mehrmals angeworfen. Leider kann ich mit den Meldungen nicht wirklich viel anfangen - was natürlich daran liegen mag, dass ich nicht genau weiß wie man ihn bedient…

MfG,
0nyx

Hallo 0nyx,

Da du lernen sollst, wie programmiert wird, solltest du mal
den Debugger anwerfen und sehen, WAS dein Programm macht.

Den Debugger habe ich schon mehrmals angeworfen. Leider kann
ich mit den Meldungen nicht wirklich viel anfangen - was
natürlich daran liegen mag, dass ich nicht genau weiß wie man
ihn bedient…

Dazu gibts ein Handbuch …

Ich würde als erstes einen Breakpoint auf „loescheElement“ setzen.
Dann kannst du das Programm bis zu diesem Punkt voll durchlaufen lassen.
Dann, wenn das der Debugger nicht automatisch macht, alle lokalen und „listenanker“ anzeigen lassen.
Dann mit Singlestep (modus „Aufrufe überspringen“) durchsteppen, bis zum Fehler. Möglicherweise erkennst du dabei schon das Problem, beim betrachten der aktuellen Werte der Variablen.

MfG Peter(TOO)

Hallo nochmal!

Dazu gibts ein Handbuch …

Habe ich aber nicht. Ich benutze die vorinstallierte Software aus dem Rechner Pool der Hochschule - Handbücher habe ich da noch nie rumfliegen sehen. Und bei Klick auf den Menüpunkt „Hilfe“ kommt sowas wie „MSDN Library nicht installiert“, aber egal - ich weiche vom Thema ab.

Ich würde als erstes einen Breakpoint auf „loescheElement“ setzen.
Dann kannst du das Programm bis zu diesem Punkt voll
durchlaufen lassen.
Dann, wenn das der Debugger nicht automatisch macht, alle
lokalen und „listenanker“ anzeigen lassen.
Dann mit Singlestep (modus „Aufrufe überspringen“)
durchsteppen, bis zum Fehler. Möglicherweise erkennst du dabei
schon das Problem, beim betrachten der aktuellen Werte der
Variablen.

Hab deine kleine Anleitung befolgt und den Fehler gefunden. Das Problem war, dass ich - nach dem „delete“ - an einer anderen Stelle im Programm nochmal auf das gelöschte Objekt zugegriffen habe…

Danke!!

MfG,
0nyx

Hallo Semjon!

Danke für dein Bemühen. Ich habe den Fehler inzwischen gefunden. Es lag nicht am „delete“ oder an der Funktion, sondern daran, dass ich nach dem Löschen nochmal auf das Objekt zugegriffen habe (über Zeiger).

MfG,
0nyx

Hallo 0nyx,

Hab deine kleine Anleitung befolgt und den Fehler gefunden.
Das Problem war, dass ich - nach dem „delete“ - an einer
anderen Stelle im Programm nochmal auf das gelöschte Objekt
zugegriffen habe…

So ein Debugger ist manchmal ganz praktisch :wink:

Lernt man bei euch eigentlich nichts übers Debuggen ??

MfG Peter(TOO)

Hallo Peter

So ein Debugger ist manchmal ganz praktisch :wink:
Lernt man bei euch eigentlich nichts übers Debuggen ??

Ja, in meinem Fall war der Debugger echt praktisch - hatte den Fehler schon nach kurzer Zeit gefunden. In der Vorlesung / im Praktikum haben wir nichts mit dem Debugger gemacht. Wir hatten lediglich die erste Stunde dafür genutzt, um uns die Oberfläche des Programms anzuschauen (d.h. wie legt man ein Projekt an, Einstellungen, etc.) und dann ging schon das „eigentliche“ Programmieren los.
Eigentlich schade, dass wir nichts mit dem Debugger gemacht haben, aber andererseits ist C++ doch sehr umfangreich und ein Semester ist so kurz…

MfG und danke nochmal,
0nyx

Hallo Peter!

Was passiert wohl, wenn „listenanker“ == NULL ist in dem
while() ???

Dieses Problem habe ich bereits eine Ebene „weiter oben“
abgesichert, d.h. wenn die Variable listenanker NULL ist, dann
wird die Funktion loescheElement() gar nicht erst aufgerufen.

„Weiter oben“ ist aber kein guter Stil. Ich wuerde diese function
reparieren, weil sie immer dann Probleme hat, wenn das element,
das du entfernen willst, nicht in der Liste enthalten ist.

Es gibt prinzipiell 2 Möglichkeiten, die ich fuer akzeptabel
halte (die kann man auch kombinieren):
1)
Entferne die Bugs aus der function, d.h. mache sie robust
gegenueber unvorhergesehenen Input.
2)
Stelle klare preconditions auf und ueberpruefe sie am
Anfang der Funktion. zB:

Precondition: „zu entfernendes Element muss in der Listen enhalten sein“
Überpruefen in der Funktion: assert( Liste::enthaelt(a) );