Kopie einer Liste!

Thes-One

Versteh ich das richtig das ich eine Kopie einer Liste nur richtig erstellen kann wenn man jedes Element was in der Liste enthalten ist in der neuen Liste Speichert?

Wenn man nämlcih direkt die beiden Listen = setzt und dann in der kopierten Liste etwas löscht es auch gleichzeitig in der neuen Liste entfernt wurde!!

Oder gibt es noch einen anderen weg??

mcr

Hi,

du siehst das richtig. I.A. musst du jedes Element kopieren und in
der neuen Liste anordnen.

I.A. schreibt man sich dafür eine Funktion, die direkt auf der
Struktur arbeitet und nicht vorhandene Funktionen wie insert() oder so
verwendet.

Gruß mcr

Thes-One

Wieso insert() nicht nutzen, wenn man die Funktionen doch hat???

mcr

Kommt drauf an, wie die Funktion implementiert ist.

Z.B. Wenn du eine einfach verkettete Liste hast und insert() das
neue Element immer an das Ende der Liste anhängt, dann muss bei
jedem insert() die gesamte Liste durchlaufen werden.

Beim Kopieren kannst du dir, den Pointer aufs letzte Element merken
und dadurch geht es schneller.

Oder wenn die insert()-Funktion das Element am Anfang der Liste
einfügt, ist die Reihenfolge umgekehrt, was auch nicht im Sinne einer
Kopierfunktion ist. Um das zu umgehen, müsste man die Elemente
in umgekehrter Reihenfolge einfügen, was bei einer einfach-verketteten
Liste auch nicht schnell geht.

Wenn du in deiner Liste stets einen Pointer aufs erste und aufs letzte
Element hast, dann kann man die insert()-Funktion effizient programmieren.
Aber das bedeutet auch, dass du ein wenig mehr Speicher spendieren mußt.

Ich würde daher die insert()-Funktion vermeiden und direkt die Liste
erzeugen.

Gruß mcr

supertux

Thes-One schrieb:

Wenn man nämlcih direkt die beiden Listen = setzt und dann in der kopierten Liste etwas löscht es auch gleichzeitig in der neuen Liste entfernt wurde!!

kommt auf den Aufbau der Liste an. Wenn du Listen mit Zeigern erstellt hast, dann musst du bei der Kopie für jedes Element neuen Speicher allozieren und das Element kopieren. Wenn du mit mit = eine Kopie erstellst, dann wird nur bitweise kopiert, d.h. die Zeiger der Kopie zeigen auf die originalen Elemente und wenn diese freigegeben/verändert werden, sind die Elemente der Kopie ebenso freigegeben/verändert. Dir sollte klar sein, dass eine Kopie eines Zeiger (zeiger2 = zeiger1; ) keinen neuen Speicher reserviert oder so.

@mcr: was meinst du mit deinem zweiten Absatz? Ich kann nicht verstehen, was du da meinst.

// edit: @mcr: hab zu lange für meine Antowrt gebraucht eine insert() Funktion durchläuft nicht immer die gesammte Liste: Wenn der Kopf der Liste einen Zeiger auf das letzte Element hat, kann man in O(1) Elemente ans Ende der Liste einfügen.

mcr

Es gibt zwei trivale Möglichkeiten insert() für einfach verkettete
Listen zu implementieren.

1. insert() fügt das neue Element ans Ende der Liste an.
Wenn du diesen Pointer nicht hast, musst du durch die gesamte Liste laufen.

2. insert() fügt das neue Element an den Anfang der Liste an.
Dann ist die Reihenfolge der kopierten Liste umgekehrt zur original Liste,
was auch i.d.R. nicht gewünscht ist.
Eine Lösung dafür: Die Elemente werden in umgekehrter Reihenfolge eingefügt.
Aber i.d.R. hat man dann auch nicht den Pointer aufs letzte Element
einer einfach verketteten Liste, also muss man jedes mal wieder durch die
Liste durch.

Daher ist das folgende *Pseudocode* einfacher:

liste copy_list (liste orig) {
    liste neu = NULL, tmp = NULL;
    while (!orig) {
        liste el = malloc(sizeof(*el));
        kopiere die Eintraege des Elements orig (*el = *orig)
        next-Pointer von el initialisieren (mit NULL z.B.)
        if (!tmp) {
            neu = el;
            tmp = neu;
        } else {
            tmp->next = el;
            tmp = el;
        }
        orig = orig->next;
    }
    return neu;
}

Dies sollte im groben funktionieren.

Gruß mcr

//edit: diesmal war ich auch zu langsam: Wenn man ein Listen-Kopf hat, stimmt
das. Aber wenn du eine Liste ohne explizites Kopf-Element hast, dann nicht.