Elemente der doppelt verketteten Liste vertauschen

[Allesquatsch]

Hallo DirkB, anonymer12,

Ihr habt nicht daran gedacht, dass es neben den NULL-Pointern noch weitere Sonderfälle gibt, die man unbedingt behandeln muss.
Im anderen Fall macht ihr einen Loop in die Liste, wenn die beiden zu vertauschenden Elementen hintereinander hängen.

Zumindest eine zusätzliche if-Abfrage muss noch in den Code.

Ciao, Allesquatsch

[camper]

Allesquatsch schrieb:

Hallo DirkB, anonymer12,

Ihr habt nicht daran gedacht, dass es neben den NULL-Pointern noch weitere Sonderfälle gibt, die man unbedingt behandeln muss.
Im anderen Fall macht ihr einen Loop in die Liste, wenn die beiden zu vertauschenden Elementen hintereinander hängen.

Zumindest eine zusätzliche if-Abfrage muss noch in den Code.

Ciao, Allesquatsch

Der Fall hintereinander liegender Elemente ist allerdings nur deshalb ein Sonderfall, weil Null-zeiger vorkommen können. Im Fall von doppelt verketteten Listen gibt es fast nie gute Gründe, keine Ringlisten zu verwenden.
Die Invarianten für 0-terminierte Listen sind unnötig komplex und verkomplizieren entsprechend die Algorithmen, die mit diesen arbeiten müssen.

Ansonsten

spielzug* remove(spielzug* p)
{
    spielzug* next = p->next;
    p->prev && ( p->prev->next = p->next );
    p->next && ( p->next->prev = p->prev );
    return next;
}

void insert(spielzug* p, spielzug* prev, spielzug* next)
{
    p->next = next;
    p->prev = prev;
    prev && ( prev->next = p );
    next && ( next->prev = p );
}

spielzug* change_pointer(spielzug* liste, spielzug* change1, spielzug* change2)
{
    spielzug dummy1, dummy2;
    insert( &dummy1, change2->prev, change2 ); // dummy-element, change1 und chnage2 können so nicht mehr unmittelbar benachbart sein
    insert( &dummy2, change2, change2->next );

    spielzug* change1_old = remove( change1 );
    insert( change1, &dummy1, &dummy2 );       // das entfernt gleichzeitig change2, falls change1 != change2
    insert( change2, &dummy1, change1_old );   // hier passiert gar nichts, falls change1 == change2

    remove( &dummy1 );
    remove( &dummy2 );

    return liste->prev == 0 ? liste : liste == q ? p : q; // Falls der Listenanfang getauscht wurde, muss sich hier nat. etwas ändern.
}

[camper]

Im Fall einer Ringliste wird das Ganze erheblich einfacher:

void swap_spielzug(spielzug** p, spielzug** q)
{
    spielzug* t = *p;
    *p = *q;
    *q = t;
}

void intersect(spielzug* p, spielzug* q)
{
    p->prev->next = q;
    q->prev->next = p;
    swap_spielzug( &p->prev, &q->prev );
}

spielzug* change_pointer(spielzug* liste, spielzug* p, spielzug* q)
{
    intersect( p, q );
    intersect( p->next, q->next );
    return liste == p ? q : liste == q ? p : liste;
}

Der Tausch völlig ohne Sonderfälle und if-Orgien. Die Frage, wo der Listenanfang sein soll, muss nat. zusätzlich geklärt werden.

[Allesquatsch]

camper schrieb:

Allesquatsch schrieb:

Hallo DirkB, anonymer12,

Ihr habt nicht daran gedacht, dass es neben den NULL-Pointern noch weitere Sonderfälle gibt, die man unbedingt behandeln muss.
Im anderen Fall macht ihr einen Loop in die Liste, wenn die beiden zu vertauschenden Elementen hintereinander hängen.

Zumindest eine zusätzliche if-Abfrage muss noch in den Code.

Ciao, Allesquatsch

Der Fall hintereinander liegender Elemente ist allerdings nur deshalb ein Sonderfall, weil Null-zeiger vorkommen können.

Meiner Meinung NEIN. Das Problem hintereinanderhängender Elemente ist, dass ein Element gleichzeitig auch der Vorgänger bzw. Nachfolger ist, in dem man die Zeiger anpasst.

Damit sind die zu ändernden Zeiger identisch. Je nachdem in welcher Reihenfolge man arbeitet, überschreibt man den korrekten Wert mit einem Zeiger auf sich selbst.

Ciao, Allesquatsch

[camper]

Allesquatsch schrieb:

camper schrieb:

Der Fall hintereinander liegender Elemente ist allerdings nur deshalb ein Sonderfall, weil Null-zeiger vorkommen können.

Meiner Meinung NEIN. Das Problem hintereinanderhängender Elemente ist, dass ein Element gleichzeitig auch der Vorgänger bzw. Nachfolger ist, in dem man die Zeiger anpasst.

Damit sind die zu ändernden Zeiger identisch. Je nachdem in welcher Reihenfolge man arbeitet, überschreibt man den korrekten Wert mit einem Zeiger auf sich selbst.

Wenn man so vorgeht.
Das Problem mit Nullzeigern ist, dass sie als Indikatoren für eine Position unbrauchbar sind, weil man den Nachfolger (beim Listenanfang) bzw. Vorgänger (am Ende) nicht aus ihnen ableiten kann. Da ein lineare Liste aus N Elementen über N+1 Einfügestelle verfügt, genügt für diese Einfügestellen nicht ein einfacher Verweis auf das Vorgäner- oder Nachfolgerelement. Sonderfälle sind damit unvermeidlich. Welche Form diese Sondefälle haben, hängt nun von der konkreten Strategie ab.
Eine Ringliste hat dieses Problem nicht; eine N-elementige Ringliste verfügt auch nur über N Einfügestellen. Ich denke, mein obiger Code demonstriert das hinreichend.

[Allesquatsch]

camper schrieb:

Allesquatsch schrieb:

Meiner Meinung NEIN. Das Problem hintereinanderhängender Elemente ist, dass ein Element gleichzeitig auch der Vorgänger bzw. Nachfolger ist, in dem man die Zeiger anpasst.

Damit sind die zu ändernden Zeiger identisch. Je nachdem in welcher Reihenfolge man arbeitet, überschreibt man den korrekten Wert mit einem Zeiger auf sich selbst.

Wenn man so vorgeht.
Das Problem mit Nullzeigern ist,

Nochmals NEIN.
Das von mir angesprochene Problem hat nichts mit NULL-Pointern zu tun und tritt auch auf, wenn man mit Ringketten arbeitet.
Es hat damit zu tun, dass man jeweils für die beiden zu vertauschenden Elemente und in ihren Vorgängern/Nachfolgern Zeiger verbiegen muss. Und damit müssen die Sonderfälle berücksichtigt werden, wenn die beiden Elemente schon vorher in einer Vorgänger/Nachfolger-Beziehung stehen.

Einfach mal das Problem auf Papier malen, dann fällt das Nachdenken leichter.

Hängt Element2 hinter Element1 würde das Ändern des Vorgängers von Element2 bedeuten, dass man Element1 auf sich selbst zeigen lässt
Hängt von der Schreibreihenfolge der Zeiger ab, wann man so die Kette korrumpiert.

Ciao, Allesquatsch

[camper]

Allesquatsch schrieb:

Einfach mal das Problem auf Papier malen, dann fällt das Nachdenken leichter.

Danke, und gleich zurück. Ich habe bereits einfachen und funktionierenden Code (für Ringlisten) geliefert. Bei einer linearen Liste funktioniert entsprechend, sofern keine der getauschten Elemente unmittelbar am Anfang oder Ende liegt, also sind das die Spezialfälle.
Ich weigere mich auf eine allgemeine Diskussion einzulassen, solange du kein Beispiel bringst, in dem die Funktion versagt.

Allesquatsch schrieb:

Hängt Element2 hinter Element1 würde das Ändern des Vorgängers von Element2 bedeuten, dass man Element1 auf sich selbst zeigen lässt

Richtig. Ist das ein Problem? An dieser Stelle ist man schließlich noch nicht fertig.

[anonymer12]

Dann dürfte es so funktionieren oder?

if(before2 != NULL && before2 != change1)
	{
    before2->next = change1;
	}

  if(change1 != NULL)
	{ 
	  change1->prev = before2;
    change1->next = after2; 
	}

  if(after2 != NULL && after2 != change2)
	{
    after2->prev = change1;
	}

  if(before1 != NULL && before1 != change2)
	{
    before1->next = change2;
	}

  if(change2 != NULL)
  { 
		change2->prev = before1;
    change2->next = after1; 
	}

  if(after1 != NULL && after1 != change2)
	{
    after1->prev = change2;
	}

  if(before1 == NULL)
	{
    liste=change2;
	}

  if(before2 == NULL)
	{
		liste=change1;
	}

[camper]

anonymer12 schrieb:

Dann dürfte es so funktionieren oder?

if(before2 != NULL && before2 != change1)
	{
    before2->next = change1;
	}

  if(change1 != NULL)
	{ 
	  change1->prev = before2;
    change1->next = after2; 
	}

  if(after2 != NULL && after2 != change2)
	{
    after2->prev = change1;
	}

  if(before1 != NULL && before1 != change2)
	{
    before1->next = change2;
	}

  if(change2 != NULL)
  { 
		change2->prev = before1;
    change2->next = after1; 
	}

  if(after1 != NULL && after1 != change2)
	{
    after1->prev = change2;
	}

  if(before1 == NULL)
	{
    liste=change2;
	}

  if(before2 == NULL)
	{
		liste=change1;
	}

Keine Ahnung. Das ist schlicht zu lang.
Nach ein bisschen mehr Überlegen finde ich, dass auch einfache lineare Listen ohne Sonderfallbehandlung auskommen, ganz analog zu zur Variante für Ringlisten kann man schreiben

void swap_spielzug(spielzug** p, spielzug** q)
{
    spielzug* t = *p;
    *p = *q;
    *q = t;
}

void crosslink_prev(spielzug* p, spielzug* q)
{
    swap_spielzug( &p->prev, &q->prev );
    p->prev && ( p->prev->next = p );
    q->prev && ( q->prev->next = q );
}

void crosslink_next(spielzug* p, spielzug* q)
{
    swap_spielzug( &p->next, &q->next );
    p->next && ( p->next->prev = p );
    q->next && ( q->next->prev = q );
}

spielzug* change_pointer(spielzug* liste, spielzug* p, spielzug* q)
{
    crosslink_prev( p, q );
    crosslink_next( p, q );
    return liste->prev == 0 ? liste : p->prev == 0 ? p : q;
}

Und weils es mir sowieso nicht geglaubt wird, skizziere ich mal die wichtigsten Fälle:

Fall1:
Ausgangssituation:
      p       q
0-->| A |-->| B |-->| C |-->| D |-->0

Zwischenschritt:
      q                               p
0-->| B |-->| C |-->| D |-->0    -->| A |--
                                 |        |
                                 -----<----
2. Schritt:
      q       p
0-->| B |-->| A |-->| C |-->| D |-->0

Fall2:
      p               q
0-->| A |-->| B |-->| C |-->| D |-->0

Zwischenschritt:
      q                       p
0-->| C |-->| D |-->0    -->| A |-->| B |--
                         |                |
                         -------<----------
2. Schritt:
      q               p
0-->| C |-->| B |-->| A |-->| D |-->0

Fall3:
      p                       q
0-->| A |-->| B |-->| C |-->| D |-->0

Zwischenschritt:
      q               p
0-->| D |-->0    -->| A |-->| B |--| C |--
                 |                       |
                 ------------<------------
2. Schritt:
      q                       p
0-->| D |-->| B |-->| C |-->| A |-->0

Fall4:
Ausgangssituation:
              p       q
0-->| A |-->| B |-->| C |-->| D |-->0

Zwischenschritt:
              q                       p
0-->| A |-->| C |-->| D |-->0    -->| B |--
                                 |        |
                                 -----<----
2. Schritt:
              q       p
0-->| A |-->| C |-->| B |-->| D |-->0

[Allesquatsch]

camper schrieb:

Allesquatsch schrieb:

Einfach mal das Problem auf Papier malen, dann fällt das Nachdenken leichter.

Danke, und gleich zurück. Ich habe bereits einfachen und funktionierenden Code (für Ringlisten) geliefert. Bei einer linearen Liste funktioniert entsprechend, sofern keine der getauschten Elemente unmittelbar am Anfang oder Ende liegt, also sind das die Spezialfälle.
Ich weigere mich auf eine allgemeine Diskussion einzulassen, solange du kein Beispiel bringst, in dem die Funktion versagt.

Touchee, habe tatsächlich mehr auf den Text und die Listings im ursprünglichen Stil geachtet und mir Dein Coding nicht genau genug angesehen.

Du hast recht, dass das Problem bei Deinem Code nicht auftritt, da Du das Herauslösen und das Wiedereinfügen in getrennten Schritten machst.
Halte Deine Codierung für handwerklich perfekt.

Es liegt aber an dieser Vorgehensweise und weniger daran, dass die Kette "verringt" ist. Denn auch bei einem Ring bekommt man das Problem, wenn man die Zeigerverbiegerei in einem Schritt für beide Elemente ausführt.

Ciao, Allesquatsch