doppelt verkettete liste, 2 elemente vertauschen

...<->obj0<->obj1<->obj2<->obj3<->...

private void TauscheObjekte(obj1, obj2) {
   obj2.prev = obj1.prev
   obj1.prev = obj2
   obj1.next = obj2.next
   obj2.next = obj1
}

Kessl

Aber nicht anfangen zu lachen ~

Das ganze ist ziemlich wirr und ich habe es 100 mal verbessert und wieder verschlimmert und langsam zeigt der Zeiger nur noch richtung Bett. Vermutlich schaue ich morgen noch einmal drauf und frage mich was zum geier ich mir dabei gedacht habe ¨ Entsprechend dem steigenden Koffeeinespiegel wurden vermutlich auch die Kommentare nicht besser... aber eigentlich will ich ja nicht meinen Code verbessert, sondern so etwas wie eine Musterlösung in Pseudocode, oder auch gerne java oder so, hauptsache es werden die Zeiger umgebogen und nicht der Inhalt vertauscht...

class ListElement{
  int value;
  ListElement* prev;
  ListElement* next;};
class LinkedList{
  ListElement* first;
  ListElement* last;
  void addElement(int value);
  void switchElement(ListElement*, ListElement*);};

LinkedList hat noch etwas mehr, aber das wird vom vertauschen nicht verwendet.

void LinkedList::SwitchElements(ListElement* eins, ListElement* zwei){
  /*sonderfall eins=zwei/
  if(eins==zwei) return;
  /*erstmal die Zeiger auf das erste und letzte Element richten/
  if(this->first==zwei) this->first=eins;
  else if(this->first==eins) this->first=zwei;
  if(this->last==zwei) this->last=eins;
  else if(this->last==eins) this->last=zwei;
  /*hier koennte vermutlich die haelfte in den muell, aber
   ich will mir tauschen noch einmal ansehen/
  ListElement* merken1n = eins->next;
  ListElement* merken1p = eins->prev;
  ListElement* merken2n = zwei->next;
  ListElement* merken2p = zwei->prev;
  /*sonderfall wenn erstes, oder letztes element/
  if(eins->prev!=NULL){
    eins->prev->next=zwei;//ziemlich sicher
  }
  if(zwei->next!=NULL){
    zwei->next->prev=eins;//ziemlich sicher
  }
  eins->next=zwei->next;//ziemlich sicher
  zwei->prev=eins->prev;//ziemlich sicher
  /*geht so weil eins immer kleiner ist, irgendwie dachte ich nicht
   das es so happig waere eine verlinkte liste mit zeigern zu
   vertauschen./
  if(merken1n!=zwei){
    eins->prev=merken2p;
    zwei->next=merken1n;
    merken2p->next=eins;
    merken1n->prev=zwei;
  }
  else{
    eins->prev=zwei;
    zwei->next=eins;
  }

So aufwendig ist es übrigens wenn man den Inhalt vertauschen darf:

int merken = eins->value;
  eins->value = zwei->value;
  zwei->value = merken;

Der Code von Pseudo geht übrigens nicht, zum einen fehlt da der Nachfolger des Vorgängers vom Element eins, der soll ja jetzt auf zwei zeigen und nicht weiter auf eins, und zum anderen muessen die elemente ja nicht benachbart sein, dann waere es natürlich fatal fuer die liste wenn eins.next auf einmal auf zwei zeigt. Aber ehrlich gesagt war das auch ungefähr womit ich angefangen habe.

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?

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

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