doppelt verkettete liste, 2 elemente vertauschen

[BigNeal]

Ich beziehe mich mal auf folgende Darstellung:

| 0->n | p<-1->n | p<-2->n | p<-3 |

Die zahlen stehen für die Reihenfolge der Elemente in der Liste.
Die zu tauschenden Elemente sind '1' und '2'.

es müsste doch ungefähr so funktionieren.
es ist nicht getestet und sonderfälle habe ich auch nicht beachtet.

void LinkedList::SwitchElements(ListElement* eins, ListElement* zwei)
{
   // 0->n und p<-3 setzen falls vorhanden
   if(eins->prev) eins->prev->next = zwei;          
   if(zwei->next) zwei->next->prev = eins;

   ListElement* temp;

   // p<-1 und p<-2 setzen
   temp = eins->prev;      // '0' speichern
   eins->prev = zwei;
   zwei->prev = temp;

  // 1->n und 2->n setzen
   temp = zwei->next;     // '3' speichern
   zwei->next = eins;
   eins->next = temp;   
}

wenn ich das richtig überlegt habe, wurden sämtliche 6 Zeiger getauscht.
keine garantie

[Belli]

BigNeal schrieb:

void LinkedList::SwitchElements(ListElement* eins, ListElement* zwei)
{
   // 0->n und p<-3 setzen falls vorhanden
   if(eins->prev) eins->prev->next = zwei;          
   if(zwei->next) zwei->next->prev = eins;

   ListElement* temp;

   // p<-1 und p<-2 setzen
   temp = eins->prev;      // '0' speichern
   eins->prev = zwei;
   zwei->prev = temp;

  // 1->n und 2->n setzen
   temp = zwei->next;     // '3' speichern
   zwei->next = eins;
   eins->next = temp;   
}

Auf der Grundlage dieses Vorschlages würde ich folgendes tun:

void LinkedList::SwitchElements(ListElement* eins, ListElement* zwei)
{
   //Vorgänger und Nachfolger von eins und zwei anpassen
   if(eins->prev) eins->prev->next = zwei;          
   if(eins->next) eins->next->prev = zwei;
   if(zwei->prev) zwei->prev->next = eins;
   if(zwei->next) zwei->next->prev = eins;

   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;   
}

[BigNeal]

ich habe gerade noch gesehen, dass der temp-pointer ja überflüssig ist.

void LinkedList::SwitchElements(ListElement* eins, ListElement* zwei)
{
   // 0->n und p<-3 setzen falls vorhanden
   if(eins->prev) eins->prev->next = zwei;          
   if(zwei->next) zwei->next->prev = eins;

   // p<-1 und p<-2 setzen
   zwei->prev = eins->prev;   
   eins->prev = zwei;

  // 1->n und 2->n setzen
   eins->next = zwei->next;   
   zwei->next = eins;
}

war gestern wohl etwas spät.
Was Belli geändert hat, verstehe ich nicht ganz.
Wenn ich es durchdenke klappt es nicht.

[Belli]

Wenn ich zwei Elemente einer Liste vertauschen will, dann ist doch die Ausgangssituation folgende:

Elemente - eins - Elemente - zwei - Elemente

wobei Elemente für viele Elemente steht, eins und zwei für die beiden, die vertauscht werden sollen.

@BigNeal:
Nach Deiner letzten Instruktion:

zwei->next = eins;

sieht das aber doch so aus:

Elemente - ... zwei - eins - ... Elemente

denn Du machst eins zum direkten Nachfolger von zwei ...

Es sollte aber so aussehen:

Elemente - zwei - Elemente - eins - Elemente

BigNeal schrieb:

wenn ich das richtig überlegt habe, wurden sämtliche 6 Zeiger getauscht.

Es müssen acht Zeiger getauscht werden:
eins hat einen Vorgänger und einen Nachfolger, die müssen künftig nicht mehr auf eins, sondern auf zwei zeigen --> zwei Zeiger.
Dasselbe gilt für zwei, dessen Nachbarn müssen künftig auf eins zeigen --> zwei weitere Zeiger.
Dann hat noch eins einen Zeiger auf den Vorgänger und einen auf den Nachfolger --> wieder zwei Zeiger.
Schließlich gilt Letzteres auch noch für zwei, macht insgesamt acht.

[BigNeal]

du hast einen denkfehler drin.
schaut dir die definition der klasse genau an:

class ListElement{
  int value;
  ListElement* prev;
  ListElement* next;};

http://de.wikipedia.org/wiki/Liste_(Datenstruktur)
"eins" und "zwei" sind jeweils einen Datensatz in der Liste.
->next und ->prev sind jeweils ein zeiger der auf den nächsten Datensatz zeigt.

[Belli]

Das ist mir schon bewußt. Aber es bleibt doch ein Fakt, daß

zwei->next = eins;

das Element "eins" zum direkten Nachfolger von Element "zwei" macht, oder nicht?

[pImpl]

Wenn er die Klassenstruktur anpasst mit einen pImpl, dann müsste das Ganze vertauschen doch viel einfacher und schneller funktionieren als jetzt?

class ListElement{
ListDaten* daten;
ListElement* prev;
ListElement* next;};

class ListDaten{...};

Er müsste also nur die ListDaten-Zeiger swappen und an der Liste nichts ändern.

[BigNeal]

Edit: gelöscht wegen geistiger verwirrung, siehe unten.

[Belli]

Wo steht denn, daß Element eins gegen Element zwei getauscht werden soll? Die Funktion soll nach meinem Verständnis in der Lage sein, zwei beliebige Elemente aus der Liste zu vertauschen.
Ich muß also auch zB das dritte Element und das achte Element in die Funktion geben können, ohne daß sie am Ende der Funktion direkt hintereinander angeordnet sind.

Beispiel:
Ele1 - Ele2 - Ele3 - Ele4 - Ele5

Wenn nun die Funktion mit tausche(Ele2, Ele4) aufgerufen wird, dann muß daß Ergebnis so aussehen:
Ele1 - Ele4 - Ele3 - Ele2 - Ele5

[BigNeal]

ach scheisse, jetzt hats klick gemacht. Ich depp...
doch noch zu früh..

ähm ja, jetzt verstehe ich was du meinst. habe mich zufest in "eins" und "zwei" reingesteigert

edit: sorry, wegen meiner verwirrung. Die Lösung von Belli müsste aber funktionieren

[Belli]

Immerhin hast Du mich zu dem Schluß gebracht, daß für genau den (Sonder)fall, daß die in die Funktion eingegebenen Elemente direkte Nachbarn sind, meine ersten vier Instruktionen ein Durcheinander erzeugen.
Man muß also auch dort mit einer temporären Variablen arbeiten, denke ich.

[Kessl]

Hrhr....

Nicht böse gemeint, aber nachdem ich gestern fast daran verzweifelt bin freut es mich schon etwas das dieses Problem wohl doch nicht ganz so trivial ist wie ich ursprünglich angenommen habe. Ich dachte zwischenzeitlich echt ich stehe vor'm Berg, 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.

Etwas einfacher, weil einfach übersichtlicher, könnte es auch sein etwas anders an die Sache ranzugehen und die Elemente nicht zu vertauschen, sondern erst beide zu löschen (also beide Vorgänger erstmal auf die Nachfolger zeigen zu lassen) und dann an der richtigen Stelle wieder einzufügen. Ich glaube durch diese kleineren Schritte entsteht weit weniger Chaos und es könnte sein das sich einige Sonderfälle dann ohnehin in Wohlgefallen auflösen.

Naja, ich habe noch das ganze Wochenende darüber zu grübeln, wenn ich etwas halbwegs elegantes zusammenbekomme werde ich es mal posten.

Trotzdem Danke schonmal an alle

Gruss

[SeppJ]

Kannst du noch einmal erläutern, wieso du nicht einfach die Inhalte vertauscht? Du sagst, du willst die Liste sortieren, aber ich sehe da keinen Zusammenhang.

[Nick Unbekannt]

Vermutlich wird die Kopie etwas aufwendiger, als ein paar Pointer zu tauschen. Ich würde aber im Listenelement einfach auch einen Pointer auf die Daten machen und schon kann man den Inhalt tauschen.

Aber wäre das nicht eine Lösung?

swap(*left, *right)
{
    *l_prev = left->prev;
	*l_next = left->next;

	*r_prev = right->prev;
	*r_next = right->next;

	if (l_prev)
		l_prev->next = right;
	right->prev = l_prev; 
	right->next = l_next;
	if (l_next)
		l_next->prev = right;

	if (r_prev)
		r_prev->next = left;
	left->prev = r_prev;
	left->next = r_next;
	if (r_next)
		r_next->prev = left;
}

Wenn die Elemente direkt nebeneinander liegen müsste man jetzt noch Sonderfälle einführen, aber so viel komplexer dürfte das auch nicht werden.

[minastaros]

Vorsicht, die Pointer first und last der LinkedList brauchen evtl. auch etwas Nachbesserung, wenn die prev - und next -Pointer der Elemente vertauscht werden.

@SeppJ: Je nach Größe der Member halt. Bei einem int sollte es kein Problem sein, einfach den Wert zu tauschen. Bei komplexeren List-Elementen schaut's anders aus. Oder eben die pImpl-Lösung mit Pointer, dann geht es auch mit Polymorphie (aber man hat noch eine extra Klasse...).

[pImpl]

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.

[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.