4. Doppelt verkettete Listen, Knoten vertauschen

Doppelt verkettete Listen, Knoten vertauschen

  • K

    Hallo zusammen,

    Thema: Doppelt verkettete Listen.
    Aufgabe: Ich soll eine Funktion schreiben, die zwei beliebige Knoten vertauscht, die davor eingelesen wurden und entsprechend sortiert angelegt worden sind.

    Mir geht es nur um diese Swap Funktion.

    Da mein Programm aus 400+ Zeilen besteht hier die wichtigsten Stellen:

    struct PERSON  struct LISTENKOPF
{
    char vorname[MAX];
    char nachname[MAX];
    char telefon[MAX];
};

struct KNOTEN
{
    struct PERSON *person;
    struct KNOTEN *next;
    struct KNOTEN *prev;
};
struct LISTENKOPF
{
    struct KNOTEN *ersterKnoten;
    struct KNOTEN *letzterKnoten;
};

    Die Funktion "Suche starten" liest den Vor und Nachnamen ein und gibt einen Pointer auf den gesuchten Knoten zurück.

    struct KNOTEN *SucheStarten(struct LISTENKOPF *head)
{
    char vorname[MAX];
    char nachname[MAX];
    struct KNOTEN *returnKnoten;
    /*Einlesen der Werte und Belegen der Person*/
    printf("Vorname:");
    fgets(vorname,MAX,stdin );
    cut_newline_at_end(vorname);

    printf("Nachname:");
    fgets(nachname,MAX,stdin );
    cut_newline_at_end(nachname);

    returnKnoten = findeKnoten(head, vorname, nachname);

    return returnKnoten;
}

    Jetzt meine Funktion, die zwei Knoten vertauschen soll:

    void ListSwap(struct KNOTEN *knoten1,struct KNOTEN *knoten2)
{
    struct KNOTEN *halteknoten;
    /* next und prev Verweise des zweiten Knotens werden gespeichert */
    halteknoten->next=knoten2->next;
    halteknoten->prev=knoten2->prev;

    /* Knoten 2 wird auf ersten Knoten kopiert*/
    knoten2->next=knoten1->next;
    knoten2->prev=knoten1->prev;
    knoten2->next->prev=knoten2;
    knoten2->prev->next=knoten2;

    /* Knoten 1 wird mit Halteknoten auf position des 2ten Knotens kopiert*/
    knoten1->next=halteknoten->next;
    knoten1->prev=halteknoten->prev;
    knoten1->next->prev=knoten1;
    knoten1->prev->next=knoten1;
}

    Der Funktionsaufruf passiert in der Main-Funktion wie folgt(verkürzt):

    struct LISTENKOPF *liste;
struct KNOTEN *kn1;
struct KNOTEN *kn2;

case 5:
                printf("Geben sie die Personen ein, die getauscht werden sollen:\n");
                kn1 = SucheStarten(liste);
                kn2 = SucheStarten(liste);
                ListSwap(kn1,kn2);

    Das Programm funktioniert, bis auf die Swap Funktion. Sobald die Funktion ausgeführt wird, stürzt das Programm ab. Habe ich einen Fehler gemacht bei der verknüpfung der Knoten?

    Über jede Hilfe dankbar. LG

    0
  • Mod

    Zeile 3: Du hast dort einen Zeiger, der auf nichts zeigt. Und dann dereferenzierst du diesen.

    Du willst wohl eher so etwas:

    struct KNOTEN *oldprev, *oldnext;
    /* next und prev Verweise des zweiten Knotens werden gespeichert */
    oldnext=knoten2->next;
    oldprev=knoten2->prev;

    // und so weiter

    Was du aber noch nicht beachtet hast, ist der Fall, dass deine zu vertauschenden Knoten am Anfang oder am Ende stehen. Das überlasse ich aber erst einmal dir als Übung.

    Was mir aber auffällt: Du speicherst die Daten innerhalb der Knoten ja sowieso nur über einen Zeiger. Wieso vertauscht du nicht einfach die beiden Datenzeiger? Geht viel schneller und einfacher!

    0 

  • struct KNOTEN *halteknoten;

    ist dein Problem. Worauf zeigt der Zeiger wenn du ihn dereferenzierst (bei ->)?
    Außerdem solltest du darauf achten, nie NULL-Zeiger an deine Swap Funktion zu übergeben.
    Verkettete Listen sind praktischer Nonsens.

    0
  • K

    Erstmal danke für die Antworten!

    SeppJ, du hast Recht. Ich könnte auch einfach die Nutzdaten der beiden Knoten
    vetauschen, jedoch soll ich, laut Aufgabenstellung, auch die äußere Struktur, also die Knoten Selbst tauschen.

    Du hast von Fällen gesprochen bei denen die Knoten an erster oder lezter Stelle stehen. Hast du dir sowas vorgestellt?

    if(!(knoten2->next)) // Knoten 2 ist letzter Knoten
   {
    oldnext=0;
    oldprev=knoten2->prev;

    knoten2->next=knoten1->next;
    knoten2->prev=knoten1->prev;
    knoten2->next->prev=knoten2;
    knoten2->prev->next=knoten2;

    knoten1->next=0;
    knoten1->prev=oldprev;
    knoten1->prev->next=knoten1;

    knoten1=listenkopf->letzterKnoten;
   }

    Muss ich das für alle Fälle machen, in denen ein Knoten am Ende der Liste steht?
    Da das dann locker 100 Zeilen lang wird, glaube ich ich mach was falsch xD.

    LG

    0
  • Mod

    Kexplx schrieb:

    Denkst du so könnte das funktionieren?

    Noch nicht. Denn beispielsweise könnte knoten1 am Anfang oder Ende stehen und in dienem Code greifst du wieder fröhlich auf dessen Vorgänger und Nachfolger zu.

    Hast du eigentlich schon an die Fälle gedacht, dass die beiden Knoten nebeneinander stehen? Oder man gar zweimal den gleichen Knoten vorliegen hat? Funktioniert dein Code dann noch?

    Muss ich das für alle Fälle machen, in denen ein Knoten am Ende der Liste steht?

    Wenn du das tatsächlich so aufbaust, dann ja.

    Da das dann locker 100 Zeilen lang wird, glaube ich ich mach was falsch xD.

    Kann schon sein (sowohl zu 100 Zeilen als auch zu falsch machen). Ideen:
    -Funktionen? Wenn sich Code zig-mal wiederholt, bloß mit anderen Variablen, dann bietet sich eine Funktion dafür an.
    -Wenn wir schon bei Funktionen sind: Man könnte das Vertauschen von Knoten auch als eine Kombination von Entfernen und Einfügen von Knoten ansehen. Du hast ja sicherlich schon fertige (und hoffentlich funktionierende) Funktionen dafür.
    -Man könnte auch über eine andere Struktur der Liste nachdenken, bei der das alles einfacher ginge. Ich weiß aber nicht, wie viel bei dir Vorgabe ist und wie viel Eigenentwicklung.
    -Oder man denkt wirklich scharf nach und guckt, ob man nicht möglichst alle Fälle mit einem einzigen Algorithmus erwischen kann. Ungetestet würde ich sagen, folgendes sollte funktionieren:

    Swap(Node1, Node2)
{
  Falls Vorgänger von Node1 existiert: Setze Node1->Vorgänger->Nachfolger = Node2
  Falls Vorgänger von Node2 existiert: Setze Node2->Vorgänger->Nachfolger = Node1
  Falls Nachfolger von Node1 existiert: Setze Node1->Vorgänger->Nachfolger = Node2
  Falls Nachfolger von Node2 existiert: Setze Node2->Vorgänger->Nachfolger = Node1

  Tausche Vorgänger von Node1 und Node2
  Tausche Nachfolger von Node1 und Node2
}

    Ich denke, das sollte die Fälle von aufeinander folgenden und gleichen Knoten abdecken (Ich hoffe, ich liege richtig, sonst wär's peinlich 🙂 ). Man hat aber nun ein anderes Problem: Der Listenkopf ist nicht mehr aktuell. Mit der derzeitigen Vorgabe ist dieses Problem nicht zu lösen, es kommt wieder da drauf an, wie viel von dem was du gezeigt hast, durch die Vorgabe gegeben ist und wie viel du selber entwickelt hast (und ggf. geändert werden kann). Zwei Ideen, wie man das Problem lösen könnte:
    -Mache den Listenkopf vom Layout her kompatibel mit den Knoten. Dann kann man sich die gesamte Sonderbehandlung sparen und einfach direkt dessen Zeiger verbiegen.
    -Übergib den Listenkopf mit an die Funktion und ändere die Zeiger falls nötig

    0
  • K

    Nochmal danke dass du mit mir die Nacht bezwingst 😉

    Erster Fall, Knoten liegen nicht nebeneinander und sind weder an letzter noch erster Stelle:

    void ListSwap(struct LISTENKOPF *listenkopf,struct KNOTEN *knoten1,struct KNOTEN *knoten2)
{
struct KNOTEN *oldnext,*oldprev;
if(knoten1->next && knoten2->next && knoten1->prev && knoten2->prev)
{
    knoten1->prev->next=knoten2;
    knoten2->prev->next=knoten1;
    oldprev=knoten2->prev;
    oldnext=knoten2->next;

    knoten2->next=knoten1->next;
    knoten2->prev=knoten1->prev;
    knoten1->next=oldnext;
    knoten1->prev=oldprev;
}

}

    Funktioniert soweit. Weiter gehts 🕶

    0
  • K

    Musterlösung:

    Einfach die Nutzdaten tauschen.
    Ich könnt kotzen! Verdammte Einzeiler als Aufgabenstellung 😡 😡

    Sorry eure Zeit verschwendet zu haben.

    LG

    0
Anmelden zum Antworten