Elemente der doppelt verketteten Liste vertauschen

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.

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