Re: Dynamische Speicherverwaltung "doppelt verkettete Liste" - C++ (German)

C++Talk.NET
C++ language newsgroups

Archives

FAQ

Memberlist

Usergroups

Profile

Re: Dynamische Speicherverwaltung "doppelt verkettete Liste"

C++Talk.NET Forum Index -> C++ (German)

View previous topic :: View next topic

Author

Message

Werner Salomon
Guest

Posted: Mon Sep 27, 2004 9:13 am Post subject: Re: Dynamische Speicherverwaltung "doppelt verkettete Liste"

"Dieter Dannerbeck" <dannerbeck_dieter (AT) web (DOT) de> wrote

Quote:

Hallo
Vorweg ich lese seit ein paar Tagen mit und bin begeistert. Hier bin ich mir
sicher kann ich gut lernen...
Ich hab da mehr eine Unklarheit als ein Problem. Ich soll aus einer "Einfach
verketteten Liste" eine "doppelt verkettete Liste" basteln.
Code:

#include <iostream.h

Hallo Dieter,

Du solltest wissen, dass es von den STL-Headern zwei Varianten gibt.
Die 'alte' - zu erkennenn am .h am Ende - und die 'neue' (ohne .h).
Letztere ist die, die standardisiert ist, und immer benutzt werden
sollte. Alle Definitionen daraus befinden sich dann im namespace
'std'.

Also:
#include // und z.B.:
std::cout << "Hallo Welt" << std::endl;

Quote:

struct listenelement
{
char daten[30];
Felder dieser Art sollten vermieden werden. Dafür gibt es den

'string':
std::string daten; // notwendig: #include

Quote:

listenelement *next;
listenelement *last;
};
Es gibt natürlich eine fertige und doppelt verkettete Liste. Für Deine

Anwendung wäre das
std::list< std::string > // notwendig: #include <list>

... aber egal

Quote:

listenelement *listenanfang;
Globale Vartiablen sind zu 99,9% ein Problem oder ein Fehler oder

beides. Als die Schlange aus dem Paradies zu den Programmierern
sprach: "trennt Daten und Funktionen", da bissen sie zu - und es
begann eine Reise durch ein großes ödes Jammertal. Erst die
Objektorientierung brachte Besserung, aber unter den Folgen leiden wir
noch immer.
Besser Du baust eine eigene Klasse für eine Liste.

class List {
listenelement* m_listenanfang; // Markiere die Member z.B.: mit
'm_'

Quote:

listenelement *hilfszeiger;
Diese Variable brauchst Du nur lokal und da sollte sie auch hin.

Quote:

void einfuegen(char datenneu[30])
Aus dem unten stehenden Code sieht man, dass hier nicht eingefügt,

sondern angehängt wird (C++-Standard: push_back). Dann solltest Du
Deine Daten, falls sie größer als ein paar Byte sind, nicht per Value,
sondern per const Referenz übergeben.
Tipp: besorge Dir die Bücher von Scott Meyers - Effektiv C++ ..
Und bitte std::string benutzen
void anhaengen( const std::string& datenneu )

Quote:

{
hilfszeiger=listenanfang;
listenelement* hilfszeiger = m_listenanfang; // (s.o.)

while (hilfszeiger->next!=NULL)
{
hilfszeiger=hilfszeiger->next;
}
Mit dieser Konstruktion ist die Komplexität des Anlegens einer Liste

mit N Elementen N*N. Also angenommen es dauert 2ms eine Liste mit 10
Elementen zu erstellen (10 x anhaengen). Dann würde es 100*100 also
10000 mal so lange dauern, eine Liste mit 100 mal so viel Elementen zu
erzeugen. -> 20 s Sad

Sowas sollte höchsten die Komplexität N haben. Das erreicht man, indem
man dafür sorgt, dass die Laufzeit der Methode 'anhaengen' unabhängig
von der Anzahl der bereits vorhandenen Elemente ist. In diesem Fall
einfach den Zeiger auf das zuletzt eingefügte Element merken.
class List {
listenelement* m_listenanfang;
listenelement* m_listenende; // zeigt auf das letzte Element

void List::abhaengen( const std::string& datenneu ) {
// leere Liste beachten !
m_listenende->next = new listenelement;

Quote:

hilfszeiger->next=new(listenelement);

hilfszeiger=hilfszeiger->next;

strcpy(hilfszeiger->daten,datenneu);
hilfszeiger->next=NULL;
}
auch hier ist die Initialisierung der Daten von der Struktur

'listenelement' getrennt. Besser ist ein Konstruktor für Listenelement
struct listenelement {
listenelement( const std::string& str, listenelement* last )
: m_daten(str )
, m_next( 0 )
, m_last( last )
{}
std::string m_daten;
listenelement *m_next;
listenelement *m_last;
};
Dann wird 'anhaengen' zu - jetzt gleich doppelt verkettet:
void List::abhaengen( const std::string& datenneu ) {
// leere Liste beachten !
m_listenende->next = new listenelement( datenneu, m_listenende );
m_listenende = m_listenende->next;
} // fertig

Quote:

void ausgeben()
{
hilfszeiger=listenanfang;

cout<
while (hilfszeiger->next!=NULL)
{
hilfszeiger=hilfszeiger->next;
cout< }
}
Solange Deine Liste keine Iteratoren besitzt, ist wohl eine

(friend-)Funktion für List die bevorzugte Lösung:
std::ostream& operator<<( std::ostream& out, const List& l ) {
// usw. im Prinzip wie oben - Anwendung siehe unten: main()

Quote:

void init()
{
listenanfang=new(listenelement);
listenanfang->next=NULL;
strcpy(listenanfang->daten,"Element 0");
}

void ende()
{
while (listenanfang!=NULL)
{
hilfszeiger=listenanfang;
listenanfang=listenanfang->next;
delete(hilfszeiger);
}
}
Das 'init' gehört in den Konstruktor und das 'ende' in den Destruktor.

Immerhin löblich, dass Du überhaupt ein 'ende' vorgesehen hast. Wink

class List {
public:
List();
~List();
void anhaengen( const std::string& datenneu ); // s.o.
friend
std::ostream& operator<<( std::ostream& out, const List& l );

private:
listenelement* m_listenanfang;
listenelement* m_listenende; // zeigt auf das letzte Element
};

List::List()
: m_listenanfang( 0 ) // die Liste ist am Anfang leer
, m_listenende( 0 )
{}

List::~List() {
// (s.o) wie ende()

Quote:

void main()
{
init();
einfuegen("Element 1");
einfuegen("Element 2");
ausgeben();
ende();

/*char p[50];
cin.getline(p,50);*/
}
Tja - und das main sieht dann so aus:

int main() {
using namespace std; // spart im folgenden Prefix std::
List s;
s.anhaengen( "Element 0" );
s.anhaengen( "Element 1" );
s.anhaengen( "Element 2" );
cout << s << endl; // List ausgeben
return 0;
}

Quote:

Für mich ist das alles noch schwer nachvollziehbar.
Das ist verständlich, da hilft üben, üben, Scott Meyers und diese ng

lesen.

Quote:

Ich will das ganze mit
einem neuen Zeiger *last lösen der auf das letzte Element zeigt. Wie genau
weiss ich noch nicht. Meine Frage ist wie packe ich so etwas an?
Na ja - das hat sich ja fast von selbst erledigt (s. anhaengen). Nur

eine leere Liste muss noch berücksicht werden.
void List::abhaengen( const std::string& datenneu ) {
if( m_listenanfang ) {
m_listenende->next = new listenelement( datenneu, m_listenende
);
m_listenende = m_listenende->next;
}
else {
m_listenanfang = new listenelement( datenneu, 0 );
m_listenende = m_listenanfang;
}
}

Gruß
Werner

--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de

Christoph Rabel
Guest

Posted: Mon Sep 27, 2004 9:27 am Post subject: Re: Dynamische Speicherverwaltung "doppelt verkettete Liste"

Dieter Dannerbeck wrote:

Quote:

Vorweg ich lese seit ein paar Tagen mit und bin begeistert. Hier bin ich mir
sicher kann ich gut lernen...
Ich hab da mehr eine Unklarheit als ein Problem. Ich soll aus einer "Einfach
verketteten Liste" eine "doppelt verkettete Liste" basteln.

Generell, auch wenn du es vermutlich schon weist, gibt es in C++ schon
die Klasse std::list, die man statt etwas selbstgestricktem verwenden
sollte.

Obigen bzw. einen analogen Hinweis wirst du vermutlich öfter bekommen
wenn du etwas existierendes nachstrickst, meist ist hilfreich sowas wie:
"Ich mach das zur Übung." dazuzuschreiben

Quote:

#include <iostream.h

iostream.h ist ein veralteter Header, der offiziel auch gar nicht mehr
existiert. Bitte verwende den neuen.

#include
Da danach alle Funktionen im Namespace std sind, musst du entweder
explizit qualifizieren oder durch using Deklarationen/Direktiven
bekanntmachen.

Ich bin jetzt mal faul und mache alles aus dem Namespace std bekannt:

using namespace std;

Quote:

struct listenelement
{
char daten[30];

Hier solltest du std::string verwenden. Oder falls es wirklich Daten und
keine Texte sind std::vector

Quote:

listenelement *next;
listenelement *last;

previous wäre vermutlich ein besserer Name.
Warum verwendest du eigentlich Deutsch/Englische Namen gemischt?

Du wirst feststellen, dass es günstiger ist bei einer Sprache und einer
Namenskonvention zu bleiben.

Weiters solltest du listenelement einen Konstruktor spendieren, der next
und last mit korrekten Werten füllt.

Quote:

listenelement *listenanfang;

Das hier ist strategisch falsch!

Du solltest eine Klasse liste machen, die den Listenanfang und die
Listanfunktionen als Member hält:

class liste
{
listenelement *listenanfang;

public:
liste(); // Konstruktor
~liste(); // Destruktor
void einfügen(char datenneu[30]);
void ausgeben();
// usw.

}

Quote:

listenelement *hilfszeiger;

Hilfszeiger solltest du global überhaupt nicht benötigen, erzeug diesen
Pointer am besten immer lokal in jeder Funktion.

Quote:

void einfuegen(char datenneu[30])
{
hilfszeiger=listenanfang;

Hier könntest du z.B. hilfszeiger lokal erzeugen, du brauchst ihn nicht
global.

Quote:

while (hilfszeiger->next!=NULL)
{
hilfszeiger=hilfszeiger->next;
}

hilfszeiger->next=new(listenelement);

Warum klammerst du hier? new ist keine Funktion.

Quote:

hilfszeiger=hilfszeiger->next;

strcpy(hilfszeiger->daten,datenneu);

Hier würde ich eher strncpy verwenden um Bufferüberfläufe zu vermeiden.
(Oder noch besser wie schon gesagt überhaupt std::string nehmen)

Quote:

hilfszeiger->next=NULL;
}

void ausgeben()
{
hilfszeiger=listenanfang;

cout<
while (hilfszeiger->next!=NULL)
{
hilfszeiger=hilfszeiger->next;
cout< }

Ich würde obiges so implementieren:

listenelement * hilfszeiger = listenanfang;

while(hilfszeiger)
{
cout << hilfszeiger->daten << 'n;
hilfszeiger=hilfszeiger->next;
}

Quote:

void init()
{
listenanfang=new(listenelement);
listenanfang->next=NULL;
strcpy(listenanfang->daten,"Element 0");
}

Statt dieser init Funktion solltest du einen Konstruktor verwenden.

Quote:

void ende()
{
while (listenanfang!=NULL)
{
hilfszeiger=listenanfang;
listenanfang=listenanfang->next;
delete(hilfszeiger);
}
}

Und ende sollte der Destruktor der Funktion sein.

Quote:

void main()
{
init();
einfuegen("Element 1");
einfuegen("Element 2");
ausgeben();
ende();

/*char p[50];
cin.getline(p,50);*/
}
Für mich ist das alles noch schwer nachvollziehbar. Ich will das ganze mit
einem neuen Zeiger *last lösen der auf das letzte Element zeigt. Wie genau
weiss ich noch nicht. Meine Frage ist wie packe ich so etwas an? Hat jemand
einen Tipp für mich?

Solltest du diesen Code im Rahmen eines C++ Kurses erhalten haben, so
würde ich nicht viel auf diesen Kurs geben.

Dieser Code ist vom Stil her C, und für C auch halbwegs ok. Aber er ist
schlechtes C++.

Zu deinem direkten Problem:

Beim Erzeugen eines neuen listenelements musst du einfach dem last
Pointer immer das vorhergehende Element zuweisen. Und damit bist du
schon fertig, es sei denn du möchtest weitere Funktionen schreiben, die
von einer doppelt verketteten Liste provitieren. z.B. Daten von hinten
nach vorn ausgeben.

mfg

Christoph

--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de

Nicolas Pavlidis
Guest

Posted: Mon Sep 27, 2004 9:40 am Post subject: Re: Dynamische Speicherverwaltung "doppelt verkettete Liste"

"Dieter Dannerbeck" <dannerbeck_dieter (AT) web (DOT) de> writes:

Quote:

#include Ohne .h, diese Headers sind veraltet.

Quote:

struct listenelement
{
char daten[30];
listenelement *next;
listenelement *last;
};

Du willst nicht den letzten Knoten wissen sondern den Vorgaenge nur
Nachfolger.

Quote:

listenelement *listenanfang;

listenelement *hilfszeiger;

Globale Vraiablen sind nie gut, ganz egal wo Smile

, vorallem in C++.

Quote:

void einfuegen(char datenneu[30])
{
hilfszeiger=listenanfang;

while (hilfszeiger->next!=NULL)
{
hilfszeiger=hilfszeiger->next;
}

hilfszeiger->next=new(listenelement);

new listenelement nicht new(listenelement), das sind zwei verschiedene
Operatoren.

Quote:

void main()

Main retuniert immer int, ganz egal was manche Leute oder Buecher sagen
Smile

Quote:

Für mich ist das alles noch schwer nachvollziehbar. Ich will das ganze mit
einem neuen Zeiger *last lösen der auf das letzte Element zeigt. Wie genau
weiss ich noch nicht. Meine Frage ist wie packe ich so etwas an? Hat jemand
einen Tipp für mich?

Wie gesagt bei einer doppelt verketteten Liste muss jedes Listenelement
seinen Vorgaenger und seinen Nachfolger sowie die Daten kennen die es
haelt.

Noch was ganz anderes:
bevor du das angehst setz dich mal Klassen, Mehtoden, Datenkapselung
usw. auseinander. Grad in C++ macht das sehr viel Sinn Wink

.

Google mal nach "Thinking in C++" von "Bruce Eckel". Das Buch ist zwar
in englisch, ist baer gratis zum download, und fuer den Einstieg
wirklich gut.

HTH
Nicolas
--

Quote:

Nicolas Pavlidis | Elvis Presly: | |__ |
Student of SE & KM | "Into the goto" | |__| |
[email]pavnic (AT) sbox (DOT) tugraz.at[/email] | ICQ #320057056 | |
-------------------University of Technology, Graz----------------|

--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de

Karl Heinz Buchegger
Guest

Posted: Mon Sep 27, 2004 3:39 pm Post subject: Re: Dynamische Speicherverwaltung "doppelt verkettete Liste"

Dieter Dannerbeck wrote:

Quote:

[snip]

Quote:

Das wichtigste bei der Arbeit mit dynamischen Datenstrukturen ist es:
Papier und Bleistift bereit zu halten und die Datenstruktur aufzuzeichnen!

jedes Objekt (Variable) wird zu einem Rechteck auf Deinem Papier. Wenn es
sich dabei um eine benannte Variable handelt, dann schreibst Du den Namen
der Variablen ueber das Rechteck. Den Wert der Variablen schreibst Du
in das Rechteck. Handelt es sich bei der Variablen um einen Pointer, so
kommt da kein Zahlenwert oder String hinein, sondern ein Pfeil. Der Pfeil
'zeigt' dann auf das Objekt, auf das auch der Pointer in Deinem Program
zeigt.
Handelt es sich bei dem Objekt selbst wieder um eine struct oder eine class,
dann machst Du ganz einfach eine innere Struktur in das Rechteck hinein.

Nun eine einfach verkette Liste sieht dann zB. so aus:

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+ +---------------+

Quote:

Hier siehst Du also die visuelle Darstellung Deiner Liste im Speicher.
Was bringts?
Ganz einfach. Du kannst das benutzen um graphisch zu pruefen, was denn
Deine Programanweisungen tatsaechlich machen.
zB. Was macht

listenanfang->next->next = NULL;

Denk nicht lange nach und arbeite Dich durch die Anweisung und male
in der Graphik mit:

listenanfang suche das Rechteck auf, das 'listenanfang heist'

listenanfang
+------------+

Quote:

|
+------------+

listenanfang-> von diesem Rechteck muss ein Pfeil wegfuehren, wenn
nicht, dann hast Du schon einen Programfehler.
Folge diesem Pfeil

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

listenanfang->next Der Pfeil hat Dich zu einem Rechteck gebracht. Suche dort
das next Feld auf:

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+

Quote:

daten: "Juhu" |
next: <--- Hier ist es
+---------------+

listenanfang->next-> Von dort muss wieder ein Pfeil weggehen. Folge ihm

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+

Quote:

daten: "Juhu" |
next: o--------
+---------------+

listenanfang->next->next Im Rechteck in dem dieser Pfeil endet, suche das next Feld

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+ +---------------+

Quote:

daten: "Juhu" | | daten: "noch" |
next: o-------->| next: <--- Da ist es
+---------------+ +---------------+

listenanfang->next->next = NULL; Genau dieses Feld wird auf NULL gesetzt. Damit wird
der Pfeil der bisher von diesem Feld ausging
geloescht.

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+ +---------------+

Quote:

+---------------------+

Quote:

daten: "mehr daten" |
next: NULL |
+---------------------+

und wir sehen:
zum Einen ist die Liste kuerzer geworden, das letzte Element wurde abgehaengt.
zum Anderen gibt es da jetzt ein Rechteck (sprich ein Listenelement) zu dem kein
Pfeil mehr hinfuehrt. Dieses Rechteck hat auch keinen Namen. Daher ist es vom
Program aus unmoeglich geworden auf dieses Objekt zuzugreifen, es fuehrt kein
Pfad mehr dorthin. Du hast ein Speicherleck produziert.

Nun. Ich habe die Anweisung mal einfach so hingeschrieben um Dir zu zeigen, wie man
die Anweisung in der Graphik verifizieren kann. Aber jetzt drehen wir den Spiess
mal um. Angenommen wir wollen tatsaechlich das 2. Element loeschen (und wir wissen
bereits dass es existiert, etc.) wie muesste man das in einem Program schreiben.
Welche Anweisungen braucht man?
Fang wieder mit der Graphik an.
Wie sieht die Liste zur Zeit aus? So:

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+ +---------------+

Quote:

Und wie muss sie nach der Operation aussehen? So:

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+

Quote:

Nachdem wir das Ergebnis jetzt kennen, koennen wir uns ueberlegen, welche Schritte
dazu notwendig sind. Noch immer schreibst Du keine einzige Zeile Code, sondern machst
das ganze zunaechst mal am Papier, und zwar solange, bis Du eine Sequenz hast, die
am Papier funktioniert.

Also. Am Anfang war:

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+ +---------------+

Quote:

Durch Vergleich mit dem Endzustand ist klar, das der rechte Knoten weg muss. Nun, das geht
aber jetzt noch nicht. Er enthaelt eine Information die wir brauchen, naemlich den Pfeil
auf den nachfolgenden Knoten. Also koennten wir mal damit beginnen, im ersten Knoten
den Pfeil auf den dritten Knoten zu verbiegen:

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+ +---------------+

Quote:

Und dann koennten wir den zweiten Knoten loeschen. Hmm. Koennten wir. Aber
in der Graphik sieht man, dass es keinen Pfeil mehr gibt, der zum zweiten Knoten
fuehrt. Damit ist er unerreichbar geworden.
So gehts also nicht.
Was wir brauchen ist eine Hilfsvariable, die zB. einen Pfeil auf den zweiten Knoten
kriegt und dafuer sorgt, dass es auch nach der Pfeilverbiegerei noch einen Weg zum
zweiten Knoten gibt.
zB. so

Ausgangsssituation:

listenanfang
+------------+

Quote:

o-------------------+
+------------+ |

v

+---------------+ +---------------+

Quote:

Einfuehren einer Hilfsvariablen:

listenanfang
+------------+ tmp

Quote:

o-------------------+ +-----------------+
+------------+ | | |
+-----------------+
v

+---------------+ +---------------+

Quote:

Die Hilfsvariable auf den zweiten Knoten zeigen lassen:

listenanfang
+------------+ tmp

Quote:

o-------------------+ +-----------------+
+------------+ | | o |
+--------|--------+
v v

+---------------+ +---------------+

Quote:

Dann den Zeiger im ersten Knoten verbiegen, so dass er auf den dritten Knoten
zeigt:

listenanfang
+------------+ tmp

Quote:

o-------------------+ +-----------------+
+------------+ | | o |
+--------|--------+
v v

+---------------+ +---------------+

Quote:

Und schliesslich ueber die Hilfsvariable den zweiten Knoten loeschen:

listenanfang
+------------+ tmp

Quote:

o-------------------+ +-----------------+
+------------+ | | o |
+--------|--------+
v v

+---------------+

Quote:

Wenn dann die Hilfsvariable beim Verlassen der Funktion (ich nehme mal an, dass
das ganze in eine Funktion gepackt wird) zerstoert wird, dann entspricht obiges
genau dem geforderten Verhalten.
Beachte: Bis jetzt haben wir keine einzige Zeile Code geschrieben, und haben trotzdem
schon einiges an Klarheit gewonnen welche Operationen notwendig sind um die
Aktion: 'loesche zweiten Knoten' durchzufuehren. Genau so soll's auch sein!

Jetzt beginnen wir, das was wir an der Graphik gelernt haben in tatsaechlichen Code
um zusetzen:
Das Einfuehren der Hilfsvariablen ist leicht:

listenelement* tmp

aber worauf muss er zeigen. Schau auf die Graphik. Was wir brauchen ist einen Weg
ausgehend von benannten Rechtecken zum zweiten Knoten der Liste.

listenanfang
+------------+ tmp

Quote:

o-------------------+ +-----------------+
+------------+ | | |
+-----------------+
v

+---------------+ +---------------+

Quote:

listenanfang

ist schon mal klar. Dort beginnt der Weg. Danach musst Du einem Pfeil folgen um
zum Rechteck "Juhu" zu gelangen:

listenanfang->

In diesem Rechteck brauchst Du offensichtlich das next Feld, den dort beginnt
der Pfeil der zum gesuchten Ziel fuehrt:

listenanfang->next

Damit haben wir aber einen Pfeil der zum zweiten Knoten fuehrt. tmp soll auch dorthin
zeigen, kriegt also genau diesen Wert. Damit schreiben wir:

listenelement* tmp = listenanfang->next;

(und zur Sicherheit zeichnen wir auch gleich mit:

listenanfang
+------------+ tmp

Quote:

o-------------------+ +-----------------+
+------------+ | | o |
+-------|---------+
v v

+---------------+ +---------------+

Quote:

siehst Du's? listenanfang->next und tmp zeigen beide auf das gleiche Rechteck.)

Wie gehts weiter? Ach ja der Pfeil im ersten Knoten muss so verbogen werden, dass
er auf das dritte Rechteck zeigt. D.h der Pfeil in listenelement->next wird
um geleitet. Aber wohin? Wo gibt es noch einen Pfeil, der auf den dritten Knoten
zeigt. Was wir brauchen ist eine komplette Kette die bei einer benannten Variablen
beginnt und beim gesuchten Ziel endet. Na zb.

tmp->next

ist so ein Pfeil (Stelle hier absolut sicher, das Du verstehst warum das so ist.
Benutze die Zeichnung um Dich davon zu ueberzeugen, dass das so ist).

Damit ist unsere naechste Anweisung:

listenanfang->next = tmp->next;

und wir landen bei:

listenanfang
+------------+ tmp

Quote:

o-------------------+ +-----------------+
+------------+ | | o |
+--------|--------+
v v

+---------------+ +---------------+

Quote:

Soweit so gut. Jetzt benutzen wir noch

delete tmp;

um den Knoten auf den tmp zeigt zu zerstoeren:

listenanfang
+------------+ tmp

Quote:

o-------------------+ +-----------------+
+------------+ | | o |
+--------|--------+
v v

+---------------+

Quote:

Beachte: Du darfst am Papier nur das machen, was auch Dein Program macht. Die letzte
Anweisung zB. hat den Knoten zerstoert. Aber das heist nicht, das tmp geaendert wird.
Konsequenterweise habe ich den Pfeil in tmp in Ruhe gelassen. Der Zeiger zeigt jetzt
ins Nirwana, aber das ist genau das was auch in Deinem Program passiert!

So. Soviel zur Technik, wie man Operationen auf dynamische Datenstrukturen ausknobelt
und auch debuggt. Zurueck zu Deiner doppelt verketteten Liste:
So eine Liste sieht zb so aus:

listenanfang listenende
+-------------+ +-------------+

Quote:

o | | o---------------------+
+------|------+ +-------------+ |

v v
+--------------+ +---------------+ +------------+

Quote:

daten: "1" | | daten: "2" | | daten: "3" |
next: o------------->| next: o-------------->| next: NULL |
last: NULL |<---+ | last: o |<---+ | last: o |
+--------------+ | +--------|------+ | +---------|--+

+------------+ +-------------+

Siehst Du wie sich die Knoten gegenseitig referenzieren? Jeder Knoten (mit Ausnahme
des ersten und des letzten) hat jeweils einen Pfeil, der auf den vorhergehenden bzw.
nachfolgenden Knoten zeigt.

Die Aufgabe sei jetzt zb. hinter dem letzten Knoten einen Knoten "4" einzuhaengen.
(Ich machs jetzt mal im Schnelldurchlauf)
Zunaechst mal muss der Knoten erzeugt werden. Dazu brauchen wir wieder eine Hilfsvariable
die einen Pfeil auf diesen Knoten haelt (tmp = new listenelement; ... )

listenanfang listenende
+-------------+ +-------------+

Quote:

o | | o---------------------+
+------|------+ +-------------+ |

v v
+--------------+ +---------------+ +------------+

Quote:

+------------+ +-------------+

tmp
+------+

Quote:

o---------------->+---------------+
+------+ | daten: "4" |
next: NULL |
last: NULL |
+---------------+

Danach muss der next Pointer im letzten Knoten verbogen werden:

listenanfang listenende
+-------------+ +-------------+

Quote:

o | | o---------------------+
+------|------+ +-------------+ |

v v
+--------------+ +---------------+ +------------+

Quote:

daten: "1" | | daten: "2" | | daten: "3" |
next: o------------->| next: o-------------->| next: o-------+
last: NULL |<---+ | last: o |<---+ | last: o | |
+--------------+ | +--------|------+ | +---------|--+ |

+------------+ +-------------+ |

Quote:

+----------------------------------------------+

tmp |

+------+ v

Quote:

o---------------->+---------------+
+------+ | daten: "4" |
next: NULL |
last: NULL |
+---------------+

Und schliesslich muss noch der Rueckwaertspfeil in den Knoten "4" rein:

listenanfang listenende
+-------------+ +-------------+

Quote:

o | | o---------------------+
+------|------+ +-------------+ |

v v
+--------------+ +---------------+ +------------+

Quote:

+------------+ +-----^-------+ |

Quote:

|
+------------------------------|---------------+
|
tmp | |

+------+ v |

Quote:

Tja. Und nachdem es nun einen neuen 'letzten' Knoten gibt, sollte 'listenende'
das auch dokumentieren:

listenanfang listenende
+-------------+ +-------------+

Quote:

o | | o--------------------------------------------------+
+------|------+ +-------------+ |

v |
+--------------+ +---------------+ +------------+ |

Quote:

daten: "1" | | daten: "2" | | daten: "3" | |
next: o------------->| next: o-------------->| next: o-------+ |
last: NULL |<---+ | last: o |<---+ | last: o | | |
+--------------+ | +--------|------+ | +---------|--+ | |

+------------+ +-----^-------+ | |

Quote:

| |
+------------------------------|---------------+ |
| |
tmp | +-----------------------------------------------------+

+------+ v v |

Quote:

Wenn die lokale Variable 'tmp' wieder zwegfaellt, dann landen wir bei einer Graphik
die richtig aussieht. Alle Knoten verweisen korrekt auf den nachfolgenden bzw. den
vorhergehenden Knoten. listenanfang und listenende zeigen auf die korrekten Knoten,
d.h. Der obige Weg sieht brauchbar aus um einen Knoten ans Ende der Liste anzufuegen.

Das Ganze nun in Code umzusetzen ist jetzt Deine Aufgabe. Aber mit den bisherigen
Hinweisen wie man mit solchen Graphiken arbeitet sollte das kein grosses Problem
mehr sein.

--
Karl Heinz Buchegger
[email]kbuchegg (AT) gascad (DOT) at[/email]

--
de.comp.lang.iso-c++ - Moderation: mailto:voyager+mod (AT) bud (DOT) prima.de
FAQ: http://www.voyager.prima.de/cpp/ mailto:voyager+send-faq (AT) bud (DOT) prima.de

Display posts from previous:

	C++Talk.NET Forum Index -> C++ (German)	All times are GMT
Page 1 of 1

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum