doppelt verkettete liste, 2 elemente vertauschen

minastaros

pImpl schrieb:

Mit der pImpl Lösung kannst du aber aus den Klassen recht einfach Templateklassen machen und später beliebige Objekte mitder Liste verwenden... Das geht jetzt nur durch umprogrammieren.

Ich gebe Dir absolut recht. Es "riecht" etwas nach Studiums-Hausaufgabe mit einer entsprechenden Vorgabe, nämlich dem int -Element. Vermutlich soll das Prinzip der linked list verstanden werden, da ist das Datenobjekt ja zunächst zweitrangig.

Ansonsten ist die Trennung container <--> Datenobjekt natürlich sauberer. Oder eben gleich std::list ...

Belli

Kessl schrieb:

inzwischen vermute ich einfach es führt kein Weg daran vorbei wirklich etliche Sonderfälle abzufangen.

Einer ist das erste Element, oder das letzte, oder die beiden sind benachbart.

Ohne mich jetzt nochmal da hineingedacht zu haben, glaube ich, daß nur der Sonderfall, daß die zu vertauschenden Elemente benachbart sind, ein Problem für die von mir vorgeschlagene Lösung ist.
Das würde ich (ungetestet) so zu lösen versuchen:

void LinkedList::SwitchElements(ListElement* eins, ListElement* zwei)
{
   //Vorgänger und Nachfolger von eins und zwei anpassen
   if(eins->prev)   //Wenn Element einen Vorgänger hat
     if(eins->prev == zwei)  //Wenn der Vorgänger das hier einzusetzende Element ist
        eins->prev->prev->next = eins;  //Dann soll dessen Vorgänger jetzt auf dieses Element zeigen 
     else
        eins->prev->next = zwei;          

   //analog die nächsten drei Instruktionen meines Lösungsvorschlages anpassen

    ...

  //danach weiter wie gehabt

   ListElement* temp;

   //prev von eins und zwei tauschen
   temp = eins->prev;      // '0' speichern
   eins->prev = zwei->prev;
   zwei->prev = temp;

  //next von eins und zwei tauschen
   temp = zwei->next;     // '3' speichern
   zwei->next = eins->next;
   eins->next = temp;  
}

Kessl

[quote="minastaros"]

pImpl schrieb:

Es "riecht" etwas nach Studiums-Hausaufgabe mit einer entsprechenden Vorgabe, nämlich dem int -Element. Vermutlich soll das Prinzip der linked list verstanden werden, da ist das Datenobjekt ja zunächst zweitrangig.

Die Aufgabe war eine einfach verkettete Liste, aber das war mir zu langweilig. Da ist das ganze erheblich leichter, nur die doppelt verkettete Liste bereitet mir noch immer etwas Kopfschmerzen. Das was ich da im 3. Post an Code habe funktioniert ja auch, jedenfalls solange "eins" in der Liste vor "zwei" liegt und da die beiden ja nur Zeiger sind ließen sie sich leicht vertauschen, aber trotzdem wundert es mich wirklich das es scheinbar für ein so triviales Problem nirgends im Internet einen Algorithmus gibt mit dem sich das leicht implementieren ließe. Ich bin mir noch immer nicht sicher ob mein Vertauschen wirklich alle exceptions abfängt und schön ist das mit Sicherheit nicht. Da aber einige der Antworten... sagen wir mal wenigstens nicht vollständig richtig waren scheint dieses einfache vertauschen wohl doch alles andere als einfach zu sein... naja, es ist Wochenende und noch genug Zeit darüber zu grübeln, abgegeben ist es ohnehin schon.

camper

[quote="Kessl"]

minastaros schrieb:

pImpl schrieb:

Es "riecht" etwas nach Studiums-Hausaufgabe mit einer entsprechenden Vorgabe, nämlich dem int -Element. Vermutlich soll das Prinzip der linked list verstanden werden, da ist das Datenobjekt ja zunächst zweitrangig.

Die Aufgabe war eine einfach verkettete Liste, aber das war mir zu langweilig. Da ist das ganze erheblich leichter, nur die doppelt verkettete Liste bereitet mir noch immer etwas Kopfschmerzen. Das was ich da im 3. Post an Code habe funktioniert ja auch, jedenfalls solange "eins" in der Liste vor "zwei" liegt und da die beiden ja nur Zeiger sind ließen sie sich leicht vertauschen, aber trotzdem wundert es mich wirklich das es scheinbar für ein so triviales Problem nirgends im Internet einen Algorithmus gibt mit dem sich das leicht implementieren ließe. Ich bin mir noch immer nicht sicher ob mein Vertauschen wirklich alle exceptions abfängt und schön ist das mit Sicherheit nicht. Da aber einige der Antworten... sagen wir mal wenigstens nicht vollständig richtig waren scheint dieses einfache vertauschen wohl doch alles andere als einfach zu sein... naja, es ist Wochenende und noch genug Zeit darüber zu grübeln, abgegeben ist es ohnehin schon.

Das Vertauschen von Elementen einer Liste ist weder trivial noch elementar.
Einfacher und typischer ist das Verschieben von Elementen oder Teillisten. Hierbei lösen wir das Element aus der Liste und fügen es an der Zielstelle wieder ein (splice).
Das geht einfach und fast ohne Sonderfälle:

void LinkedList::MoveElement(ListElement* src, ListElement* dest)
{
    assert( src != 0 && dest != 0 );
    // Sonderfall: Element ist mit Einfügestelle identisch - dann sind wir bereits fertig
    if ( src == dest )
        return;
    // Element aus der Liste herauslösen
    if ( src->prev ) // Abfrage überflüssig, falls Ringliste
        src->prev->next = src->next;
    if ( src->next ) // Abfrage überflüssig, falls Ringliste
        src->next->prev = src->prev;
    // Element vor Einfügestelle einfügen
    src->prev = dest->prev;
    src->next = dest;
    if ( dest->prev ) // Abfrage überflüssig, falls Ringliste
        dest->prev->next = src;
    dest->prev = src;
}

Was diese Funktion nicht leisten kann, ist das Verschieben ans Ende der Liste (das wäre mit ein bisschen Aufwand auch möglich - wiederum stellt das keine Besonderheit bei einer Ringliste dar, denn die hat kein Ende), für unsere Vertauschenfunktion brauchen wir das nicht unbedingt.

Das Vertauschen von Elementen erreichen wir durch das Verschieben der Elemente

void LinkedList::SwitchElements(ListElement* eins, ListElement* zwei)
{
    if ( eins == zwei )
        return; // nichts zu tun
    // Trick, um die Beschränkung der Verschiebefunktion zu umgehen:
    if ( eins->next == 0 )
        swap( eins, zwei );
    // eins ist nun garantiert nicht am Ende der Liste
    ListElement* eins_einfuegestelle = eins->next;
    MoveElement(eins, zwei);
    MoveElement(zwei, eins_einfuegestelle);
}

das ist also relativ einfach, und die meisten Sonderfälle erledigen sich, wenn man Ringlisten einsetzt.

Kessl

So, hier nun das vorläufige amtliche Endergebnis. Ich habe die SwitchElements für alle Sonderfälle getestet die mir eingefallen sind und bisher hat sie sich gut geschlagen. Es sieht auch langsam halbwegs lesbar aus, jedenfalls sehr viel besser als das gewusel im 3. post. 2 der merken-Zeiger koennte ich evtl. noch einsparen, aber hier ist sicher>schön. Für den Moment finde ich das so ganz ok.

/*Hier werden 2 Listenelemente vertauscht*/
void LinkedList::SwitchElements(ListElement* eins, ListElement* zwei){
  /*erstmal einige Zeiger merken*/
  ListElement* merken1n = eins->next;
  ListElement* merken1p = eins->prev;
  ListElement* merken2n = zwei->next;
  ListElement* merken2p = zwei->prev;
  /*sonderfall eins=zwei. Sollte nie eintreten.*/
  if(eins==zwei) return;
  /*Sonderfall eins vorgaenger von zwei*/
  else if(merken1n==zwei){
    /*Sonderfall eins erster und/oder zwei letzter*/
    if(merken1p!=NULL) merken1p->next=zwei;
    else this->first = zwei;
    if(merken2n!=NULL) merken2n->prev=eins;
    else this->last = eins;
    eins->prev = zwei;
    zwei->next = eins;
    eins->next = merken2n;
    zwei->prev = merken1p;
  }
  /*Sonderfall zwei vorgaenger von eins*/
  else if(merken2n==eins){
    /*Sonderfall eins letzter und/oder zwei erster*/
    if(merken1n!=NULL) merken1n->prev=zwei;
    else this->last=zwei;
    if(merken2p!=NULL) merken2p->next=eins;
    else this->first=eins;
    eins->next=zwei;
    zwei->prev=eins;
    eins->prev=merken2p;
    zwei->next=merken1n;
  }
  /*eins und zwei nicht benachbart*/
  else{
    /*falls einer von beiden das erste Element ist*/
    if(this->first==zwei){
      merken1p->next=zwei;
      this->first=eins;}
    else if(this->first==eins){
      merken2p->next=eins;
      this->first=zwei;}
    else{
      merken2p->next=eins;
      merken1p->next=zwei;}
    /*falls einer von beiden das letzte Element ist*/
    if(this->last==zwei){
      merken1n->prev=zwei;
      this->last=eins;}
    else if(this->last==eins){
      merken2n->prev=eins;
      this->last=zwei;}
    else{
      merken2n->prev=eins;
      merken1n->prev=zwei;}
    /*ganz ohne Sonderfall solange beide nicht benachbart sind*/
    eins->next=merken2n;
    zwei->prev=merken1p;
    eins->prev=merken2p;
    zwei->next=merken1n;
  }
}

Darkstyle

Hi,

ich möchte mich mal hier einklinken, da ich bis vor kurzem mehr oder weniger vor dem selben Problem stand. Und zwar brauchte ich eine Funktion, die in einer beliebigen doppelt verketteten Liste zwei Elemente miteinander vertauschen kann. Meine Listen haben dabei folgenden Aufbau:

struct liste {
    // variable Daten
    struct liste *next;
    struct liste *prev;
};

Von denen habe ich mehrere, aber die Zeiger next und prev sind stehts an der vorletzten bzw. letzten Position. Da ich nicht für jede Liste eine extra Funktion haben wollte, die dann alle jeweils die selbe Aufgabe erfüllen, habe ich eine Funktion universell für alle Listen geschrieben:

void list_swap(void *list1, void *list2, int obj_size, int pnt_size)
{
    void **list1_next_prev, **list1_prev_next, **list2_next_prev, **list2_prev_next;
    void *cache_next, *cache_prev, **list1_next, **list1_prev, **list2_next, **list2_prev;

    // Adressen berechnen für list1->next, list1->prev, list2->next, list2->prev
    list1_next = list1 + obj_size - (pnt_size << 1);
    list1_prev = list1 + obj_size - pnt_size;
    list2_next = list2 + obj_size - (pnt_size << 1);
    list2_prev = list2 + obj_size - pnt_size;

    // Adressen berechnen für list1->prev->next, list1->next->prev, list2->prev->next, list2->next->prev
    list1_prev_next = (*list1_prev != NULL) ? (*list1_prev + obj_size - (pnt_size << 1)) : NULL;
    list1_next_prev = (*list1_next != NULL) ? (*list1_next + obj_size - pnt_size) : NULL;
    list2_prev_next = (*list2_prev != NULL) ? (*list2_prev + obj_size - (pnt_size << 1)) : NULL;
    list2_next_prev = (*list2_next != NULL) ? (*list2_next + obj_size - pnt_size) : NULL;

    // next und prev Zeiger der Nachbarelemente von den auszutauschenden Elementen neu setzen
    if (*list1_prev != NULL)
        *list1_prev_next = list2;
    if (*list1_next != NULL)
        *list1_next_prev = list2;
    if (*list2_prev != NULL)
        *list2_prev_next = list1;
    if (*list2_next != NULL)
        *list2_next_prev = list1;

    // next und prev Zeiger der auszutauschenden Elemente neu setzen
    cache_next = *list1_next;
    cache_prev = *list1_prev;

    *list1_next = *list2_next;
    *list1_prev = *list2_prev;
    *list2_next = cache_next;
    *list2_prev = cache_prev;
}

Der Aufruf dazu:

list_swap(list1, list2, sizeof(struct liste), sizeof(struct liste *));

Nach meinen bisherigen Tests funktioniert sie einwandfrei, also die Elemente können benachbart sein, an erster oder letzter Stelle in der Liste stehen oder kreuz und quer. Sogar ein Element mit sich selbst tauschen funktioniert (die Liste bleibt dann eben unverändert).

Nur mein Problem ist jetzt, dass ich nicht so ganz verstehe, wie das genau funktioniert, insbesondere der Mittelteil. Ich dachte mir nämlich, man könnte die doppelten if-Abfragen einsparen, was dann so aussieht:

...
if (*list1_prev != NULL) {
    list1_prev_next = *list1_prev + obj_size - (pnt_size << 1);
    *list1_prev_next = list2;
}
if (*list1_next != NULL) {
    list1_next_prev = *list1_next + obj_size - pnt_size;
    *list1_next_prev = list2;
}
if (*list2_prev != NULL) {
    list2_prev_next = *list2_prev + obj_size - (pnt_size << 1);
    *list2_prev_next = list1;
}
if (*list2_next != NULL) {
    list2_next_prev = *list2_next + obj_size - pnt_size;
    *list2_next_prev = list1;
}
...

Nach meinem Verständnis habe ich hier nichts wesentliches verändert, sondern lediglich den mittleren Teil zusammengefasst. Allerdings läuft diese Lösung nicht mehr, ich habe dann eine Endlosschleife. Eine Testausgabe hat ergeben, dass der Zeiger next dann auf das Element zeigt, in welchem er sich selbst befindet, sprich das Element zeigt auf sich selbst.
Genau hier stellt sich mir die Frage. Warum funktioniert der Aufbau oben, und dieser hier unten nicht mehr?

camper

Darkstyle schrieb:

Hi,

ich möchte mich mal hier einklinken, da ich bis vor kurzem mehr oder weniger vor dem selben Problem stand. Und zwar brauchte ich eine Funktion, die in einer beliebigen doppelt verketteten Liste zwei Elemente miteinander vertauschen kann. Meine Listen haben dabei folgenden Aufbau:
struct liste {
    // variable Daten
    struct liste *next;
    struct liste *prev;
};
Von denen habe ich mehrere, aber die Zeiger next und prev sind stehts an der vorletzten bzw. letzten Position. Da ich nicht für jede Liste eine extra Funktion haben wollte, die dann alle jeweils die selbe Aufgabe erfüllen, habe ich eine Funktion universell für alle Listen geschrieben:
void list_swap(void *list1, void *list2, int obj_size, int pnt_size)
{
    void **list1_next_prev, **list1_prev_next, **list2_next_prev, **list2_prev_next;
    void *cache_next, *cache_prev, **list1_next, **list1_prev, **list2_next, **list2_prev;

    // Adressen berechnen für list1->next, list1->prev, list2->next, list2->prev
    list1_next = list1 + obj_size - (pnt_size << 1);
    list1_prev = list1 + obj_size - pnt_size;
    list2_next = list2 + obj_size - (pnt_size << 1);
    list2_prev = list2 + obj_size - pnt_size;

    // Adressen berechnen für list1->prev->next, list1->next->prev, list2->prev->next, list2->next->prev
    list1_prev_next = (*list1_prev != NULL) ? (*list1_prev + obj_size - (pnt_size << 1)) : NULL;
    list1_next_prev = (*list1_next != NULL) ? (*list1_next + obj_size - pnt_size) : NULL;
    list2_prev_next = (*list2_prev != NULL) ? (*list2_prev + obj_size - (pnt_size << 1)) : NULL;
    list2_next_prev = (*list2_next != NULL) ? (*list2_next + obj_size - pnt_size) : NULL;

    // next und prev Zeiger der Nachbarelemente von den auszutauschenden Elementen neu setzen
    if (*list1_prev != NULL)
        *list1_prev_next = list2;
    if (*list1_next != NULL)
        *list1_next_prev = list2;
    if (*list2_prev != NULL)
        *list2_prev_next = list1;
    if (*list2_next != NULL)
        *list2_next_prev = list1;

    // next und prev Zeiger der auszutauschenden Elemente neu setzen
    cache_next = *list1_next;
    cache_prev = *list1_prev;

    *list1_next = *list2_next;
    *list1_prev = *list2_prev;
    *list2_next = cache_next;
    *list2_prev = cache_prev;
}
Der Aufruf dazu:
list_swap(list1, list2, sizeof(struct liste), sizeof(struct liste *));
Nach meinen bisherigen Tests funktioniert sie einwandfrei, also die Elemente können benachbart sein, an erster oder letzter Stelle in der Liste stehen oder kreuz und quer. Sogar ein Element mit sich selbst tauschen funktioniert (die Liste bleibt dann eben unverändert).

Nur mein Problem ist jetzt, dass ich nicht so ganz verstehe, wie das genau funktioniert, insbesondere der Mittelteil. Ich dachte mir nämlich, man könnte die doppelten if-Abfragen einsparen, was dann so aussieht:
...
if (*list1_prev != NULL) {
    list1_prev_next = *list1_prev + obj_size - (pnt_size << 1);
    *list1_prev_next = list2;
}
if (*list1_next != NULL) {
    list1_next_prev = *list1_next + obj_size - pnt_size;
    *list1_next_prev = list2;
}
if (*list2_prev != NULL) {
    list2_prev_next = *list2_prev + obj_size - (pnt_size << 1);
    *list2_prev_next = list1;
}
if (*list2_next != NULL) {
    list2_next_prev = *list2_next + obj_size - pnt_size;
    *list2_next_prev = list1;
}
...
Nach meinem Verständnis habe ich hier nichts wesentliches verändert, sondern lediglich den mittleren Teil zusammengefasst. Allerdings läuft diese Lösung nicht mehr, ich habe dann eine Endlosschleife. Eine Testausgabe hat ergeben, dass der Zeiger next dann auf das Element zeigt, in welchem er sich selbst befindet, sprich das Element zeigt auf sich selbst.
Genau hier stellt sich mir die Frage. Warum funktioniert der Aufbau oben, und dieser hier unten nicht mehr?

Das compiliert schon mal nicht.

Darkstyle

Okay, habe gerade gemerkt, dass ich im C++ Bereich bin. Mein Programm ist in reinem C geschrieben, gcc kann es übersetzen, g++ z.B. nicht.
Ich stelle meine Frage wohl besser noch mal im C Unterforum.