Doppelt verkettete Listen

Schnelle objektorientierte, kompilierende Programmiersprache.
Antworten
Xeon
Beiträge: 169
Registriert: So Dez 17, 2017 4:10 pm

Doppelt verkettete Listen

Beitrag von Xeon » Mi Okt 24, 2018 2:19 pm

Hallo zusammen,

einen Teil verstehe ich nicht bei den Doppelt verkettete Listen. Ich habe den Code nach geschrieben.

Code: Alles auswählen

void eingabe_sortiert(char *nname, char *vname)
{
    struct angestellt *zeigerA, *zeigerB;

    if(NULL == anfang)
    {
        anhaengen(nname, vname);
    }
    else
    {
        zeigerA = anfang;
        while(zeigerA != NULL && (strcmp(zeigerA->name, n) < 0))
        {
            zeigerA = zeigerA->next;
        }
					//Element ist das größte, es wird hinten angehängt
        if(NULL == zeigerA)
        {
            anhaengen(nname, vname);
        }
					//Element ist das kleinste, es wird ganz an den anfang plaziert
        else if(zeigerA == anfang)
        {
            anfang = malloc(sizeof(struct angestellt));

            strcpy(anfang->name, nname);
            strcpy(anfang->vorname, vname);

            anfang->next = zeiger;
            anfang->previous = NULL;
        }
        else
        {
					//Element wird in die mitte eingefügt
            zeigerB = anfang;
            while(zeigerB->next != zeigerA)
            {
                zeigerB = zeigerB->next;
            }
            zeigerA = malloc(sizeof(struct angestellt));

            strcpy(zeiger->name, nname);
            strcpy(zeiger->vorname, vname);

            zeigerA->next = zeigerB->next;
            zeigerA->previous = zeigerB;
            zeigerB->next = zeigerA;
            zeigerB->next->previous = zeigerA;
        }
    }
}
Hier ist das Original mit Grafiken:
http://openbook.rheinwerk-verlag.de/c_v ... 9e396d6fd8

Meine Frage ist jetzt: Ich verstehe nicht die Logik von der letzten Zeile.

Code: Alles auswählen

zeigerB->next->previous = zeigerA;
Danke im Voraus

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Doppelt verkettete Listen

Beitrag von Xin » Mi Okt 24, 2018 2:30 pm

Die Zeile kommt vor, wenn Dein ZeigerA-Element mittig eingefügt wird.

ZeigerB ist das element hinter dem eingefügt werden soll. Die Zeile sagt nun, dass das Listenelement, welches sich nach ZeigerB befindet einen neuen Vorgänger bekommt: ZeigerA.

Da in Deinem Code aber steht:

Code: Alles auswählen

            zeigerA->next = zeigerB->next;
            zeigerA->previous = zeigerB;
            zeigerB->next = zeigerA;
            zeigerB->next->previous = zeigerA;
ist zeigerB->Next an der Stelle schon zeigerA. Also sprichst Du mit ZeigerB->next wieder zeigerA an und sagst damit zeigerA, dass es als Vorgänger sich selbst eintragen soll. Das ist vermutlich nicht gewünscht.

Ich würde schonmal beginnen, mir sprechendere Namen einfallen zu lassen: previous und current beispeilsweise, statt zeigerA und zeigerB.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Xeon
Beiträge: 169
Registriert: So Dez 17, 2017 4:10 pm

Re: Doppelt verkettete Listen

Beitrag von Xeon » Do Okt 25, 2018 1:34 pm

Verstehe ich dich richtig dass diese Zeile überflüssig ist?

Code: Alles auswählen

zeigerB->next->previous = zeigerA;

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Doppelt verkettete Listen

Beitrag von Xin » Do Okt 25, 2018 1:47 pm

Xeon hat geschrieben:
Do Okt 25, 2018 1:34 pm
Verstehe ich dich richtig dass diese Zeile überflüssig ist?

Code: Alles auswählen

zeigerB->next->previous = zeigerA;
Nein.
Sie ist quasi falsch.

Du möchtest dem Nachfolger von zeigerB sagen, dass sein Vorgänger zeigerA ist.
In der Zeile davor hast Du aber gesagt, dass der Nachfolger von ZeigerB jetzt zeiger A ist.
Damit hast Du den ursprünglichen Nachfolger von ZeigerB verloren, weil der jetzige Nachfolger von B ist jetzt A.
Anschließend überschreibst Du mit der Zeile das, was Du zwei Zeilen davor festgelegt hast.

Du musst die Reihenfolge beachten!

Am besten schnappst Du Dir mal ein Blatt Papier und zeichnest Dir das Schritt für Schritt auf, was Du da tust.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Xeon
Beiträge: 169
Registriert: So Dez 17, 2017 4:10 pm

Re: Doppelt verkettete Listen

Beitrag von Xeon » Mo Okt 29, 2018 4:58 pm

Ich habe es erst heute ausprobiert mit der Zeichnung auf einem Blatt Papier.
Sicher bin ich mir nicht ob es so stimmt:

Code: Alles auswählen

zeigerA->next = zeigerB->next;
zeigerA->previous = zeigerB;
zeigerA = zeigerB->next->previous;
zeigerB->next = zeigerA;
Mit den neuen Bezeichnungen previous und current, die du vorgeschlagen hast, habe ich es noch nicht probiert.



Liebe Grüße Xeon

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Doppelt verkettete Listen

Beitrag von Xin » Mo Okt 29, 2018 5:20 pm

Xeon hat geschrieben:
Mo Okt 29, 2018 4:58 pm
Ich habe es erst heute ausprobiert mit der Zeichnung auf einem Blatt Papier.
Sicher bin ich mir nicht ob es so stimmt:

Code: Alles auswählen

zeigerA->next = zeigerB->next;
Nachfolger von neuem Element wird zugewiesen mit dem, was der Vorgänger als Nachfolger definiert.

Code: Alles auswählen

zeigerA->previous = zeigerB;
Der Vorgänger vom neuen Element wird auf den Vorgänger gesetzt.

Code: Alles auswählen

zeigerA = zeigerB->next->previous;
Das neue Element wird zu dem, was der Nachfolger vom Vorgänger als Vorgänger definiert hat.
Damit ist unser neues Element weg und zeigerA ist jetzt der Nachfolger von zeigerB.

Code: Alles auswählen

zeigerB->next = zeigerA;
Der Nachfolger vom Vorgänger ist jetzt der Vorgänger vom Nachfolger von Vorgänger.
Xeon hat geschrieben:
Mo Okt 29, 2018 4:58 pm
Mit den neuen Bezeichnungen previous und current, die du vorgeschlagen hast, habe ich es noch nicht probiert.
Mach das mal... ^^

Du hast eine Vorgänger (previous) und ein neues Element (current).
previous ist in einer Liste, hat also einen Nachfolger und einen Vorgänger. current ist noch nicht beschrieben. Current wird nach previous eingehängt.

Code: Alles auswählen

current->previous = previous;    // der Vorgänger vom Neuen ist previous
current->next = previous->next; // der Nachfolger vom Neuen ist der Nachfolger vom vorherigen.
Also current weiß jetzt schonmal, wer vor oder nach ihm ist. Der Vorgänger und der Nachfolger weiß aber noch nichts von current.
Ich muss also den Vorgänger und den Nachfolger noch überarbeiten.

Code: Alles auswählen

previous->next = current;
current->next->previous = current;
Und das zeichne mal.
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Xeon
Beiträge: 169
Registriert: So Dez 17, 2017 4:10 pm

Re: Doppelt verkettete Listen

Beitrag von Xeon » Mi Okt 31, 2018 4:47 pm

Vielen Dank Xin, du hast mir sehr geholfen.

mfro
Beiträge: 346
Registriert: Mi Jan 16, 2013 4:58 pm

Re: Doppelt verkettete Listen

Beitrag von mfro » Sa Nov 10, 2018 9:09 am

Xeon hat geschrieben:
Mi Okt 24, 2018 2:19 pm
Hier ist das Original mit Grafiken:
http://openbook.rheinwerk-verlag.de/c_v ... 9e396d6fd8
Das genannte "Buch" hat schon bei vielen Anfängern für Konfusion gesorgt (weil es eine Unzahl von Fehlern enthält) und ist allgemein als Mist anerkannt.
Mir ist schleierhaft, warum die das nicht korrigieren oder wenigstens vom Netz nehmen - keine gute Werbung für den Verlag.

Tu' dir einen Gefallen und nimm' was anderes.
It's as simple as that. And remember, Beethoven wrote his first symphony in C.

Benutzeravatar
Xin
nur zu Besuch hier
Beiträge: 8858
Registriert: Fr Jul 04, 2008 11:10 pm
Wohnort: /home/xin
Kontaktdaten:

Re: Doppelt verkettete Listen

Beitrag von Xin » Sa Nov 10, 2018 9:38 am

Ich habe das Buch nicht, aber von dem Autor ein anderes Werk, was ich ganz okay fand, aber auch nicht Seite für Seite gelesen habe. Die Kritik habe ich aber auch schon häufig gehört.

Hast Du ein Beispiel?
Merke: Wer Ordnung hellt ist nicht zwangsläufig eine Leuchte.

Ich beantworte keine generellen Programmierfragen per PN oder Mail. Dafür ist das Forum da.

Antworten