[GELÖST + FRAGE KORRIGIERT] Liste mit Mehrfach-Zeiger (doppelter Indirektion): Warum?

*amp***null*-*gt*Hallo

Moin,

ich habe gerade ein Beispiel für eine (einfach) verkettete Liste gesehen für beispielsweise diese Struktur:

struct Knoten
{
     Element element;
     struct Knoten* naechster;
};

struct Knoten* Wurzel;

Jetzt haben wir folgende Einfüge-Routine:

void insert(struct Knoten* Start, Element Einf)
{
     struct Knoten** laeufer;
     for(laeufer=&Start;*laeufer;laeufer=&((*laeufer)->naechster))
     {
        /* such-Algo, die Schleife wird verlassen, wenn das Element */
        /* gefunden ist, welches dem einzufügenden Element nachfolgt */
     }

     struct Knoten* n=malloc(struct Knoten);
     n->naechster=*laeufer;
     laeufer=n;
}

Was hat das für einen Nachteil, wenn ich meinen Läufer so abbilde, ohne Doppel**:

void insert(struct Knoten* Start, Element Einf)
{
     struct Knoten* laeufer;
     for(laeufer=Start;laeufer;laeufer=laeufer->naechster)
     {
        /* such-Algo, die Schleife wird verlassen, wenn das Element */
        /* gefunden ist, welches dem einzufügenden Element nachfolgt */
     }

     struct Knoten* n=malloc(struct Knoten);
     n->naechster=laeufer;
     &laeufer=n;
}

Mir fiel als Problem nur ein, wenn ich das Element am Ende einfüge, also wenn laeufer = NULL. Aber auch dann alles i.O.: n->naechster=NULLL, &laeufer selbst ist nicht Null und beschreibbar.

Aber es hieß, man mache das, um ein Memory Leak zu vermeiden. Sehe ich nicht. Die neue Adresse kommt in &laeufer, die identisch ist mit dem in der Schleife vorangegangen laeufer->naechster, welcher über Wurzel erreichbar ist. Das Internet bietet viele schöne Einträge dazu, aber keinen, der mir Klarheit verschafft.

Also bitte warum?

MFK

&(*null)->Hallo schrieb:

Was hat das für einen Nachteil, wenn ich meinen Läufer so abbilde, ohne Doppel**:

Der Nachteil ist, dass der Compiler das nicht akzeptieren wird. Du kannst der Adresse einer Variablen nichts zuweisen.

camper

&(*null)->Hallo schrieb:

Jetzt haben wir folgende Einfüge-Routine:

void insert(struct Knoten* Start, Element Einf)
{
     struct Knoten** laeufer;
     for(laeufer=&Start;*laeufer;laeufer=&((*laeufer)->naechster))
     {
        /* such-Algo, die Schleife wird verlassen, wenn das Element */
        /* gefunden ist, welches dem einzufügenden Element nachfolgt */
     }

     struct Knoten* n=malloc(struct Knoten);
     n->naechster=*laeufer;
     laeufer=n;
}

Das funktioniert schonmal nicht, ganz sicher soll es:

*laeufer=n;

heissen. Mit deiner Deklaration

struct Knoten* laeufer;

würde es dann folglich zu

laeufer=n;

was zwar wohlgeformt ist, aber offensichtlich nicht das tut, was beabsichtigt war.

*amp***null*-*gt*Hallo

Mein Fehler.

Eigentlich wollte ich folgendes abgleichen:

struct Knoten
{
     Element element;
     struct Knoten* naechster;
};

struct Knoten* Wurzel;  

void insert(struct Knoten* Start, Element Einf)
{
     struct Knoten** laeufer;
     for(laeufer=&Start;*laeufer;laeufer=&((*laeufer)->naechster))
     {
        /* such-Algo, die Schleife wird verlassen, wenn das Element */
        /* gefunden ist, welches dem einzufügenden Element nachfolgt */
     }

     struct Knoten* n=malloc(struct Knoten);
     n->naechster=*laeufer;
     *laeufer=n;
}

versus

//dieselbe struct
void insert(struct Knoten* Start, Element Einf)
{
     struct Knoten* laeufer;
     for(laeufer=Start;laeufer;laeufer=laeufer->naechster)
     {
        /* such-Algo, die Schleife wird verlassen, wenn das Element */
        /* gefunden ist, welches dem einzufügenden Element nachfolgt */
     }

     struct Knoten* n=malloc(struct Knoten);
     n->naechster=laeufer;
     laeufer=n;
}

Der Fehler ist laeufer=n, weil laeufer eine lokale Variable ist, die ihren Gültigkeitsbereich wieder verliert . Man kann es aber retten mit (hier vereinfacht mit int x, wenn man ob mit x die Schleifendurchläufe gezählt hat)

struct Knoten** laeufer2;
laeufer2=&Start;
for(i=0;i<x;i++)laeufer2=&((*laeufer2)->nxt);
*lauefer2=n

Das würde funktionieren, gerade probiert , zeigt aber, dass doppelte Indirektion hier effizient ist

Wutz

An verkett. Listen ist überhaupt nichts effizient.

Fricky667

Wutz schrieb:

An verkett. Listen ist überhaupt nichts effizient.

doch, das Einfügen.

Wutz

Du hast keine Ahnung, also halt die Klappe.

Fricky667

Wutz schrieb:

Du hast keine Ahnung, also halt die Klappe.

Füg doch mal was bei einem großen Array ein. DAS ist ineffizient und DU hast keine Ahnung.

Wutz

Arrays sind in ihrer Größe unveränderlich - du hast hast keine Ahnung wovon du sprichst sondern plapperst nur aufgeschnapptes Halbwissen nach - halt die Klappe.

Fricky667

Wutz schrieb:

Arrays sind in ihrer Größe unveränderlich

Na immerhin das weißt du. Und was folgt daraus?
Ich verrate es dir. Du musst ein neues Array anlegen und alles umkopieren, wenn du was einfügen willst.

Und jetzt laber noch mal Blödsinne über Ineffizienz von Listen, du Troll!

Wutz

Dorfdepp. Du hast keine Ahnung. Du weißt nicht, was Arrays sind. Es gibt auch keine großen Arrays.
Halt die Klappe.

Fricky667

Wutz schrieb:

Dorfdepp. Du hast keine Ahnung. Du weißt nicht, was Arrays sind. Es gibt auch keine großen Arrays.
Halt die Klappe.

Hahaha, jetzt dreht der Dummtroll völlig frei,

camper

Da offenbar niemand mehr etwas Nützliches zu sagen hat, schließe ich den Thread.