doppelt verkettete liste, 2 elemente vertauschen

Kessl

Hi

(gehört eigentlich nicht wirklich nach c++, aber ein Forum für Datenstrukturen habe ich nicht gefunden)

Ich klebe den halben Tag schon über einem Probelm das keines ist und bekomme es irgendwie nicht recht in den Griff. Leider schweigt sich Tante Google dazu auch ziemlich deutlich aus. Ziel ist es mir Objekten eine doppelt verlinkte Liste zu erstellen (soweit kein Problem) und nun: Diese zu sortieren. Der Sortieralgorithmus ist das kleinere Problem, das vertauschen in der doppelt verketteten Liste bringt mich dagegen um. Dabei sollen nämlich die Zeiger umgebogen werden und nicht die Elemente vertauscht.

Kennt jemand zufällig eine Seite auf der das ganze als Pseudocode steht? Ich habe bei mir etwa 100 exceptions die ich abfangen muss, wenn a->prev nicht existiert, wenn a und b benachbart sind, nochmal andersrum wenn b vor a liebt.... ich komme inzwischen auf ~3 Seiten Code nur fürs vertauschen.

Das kann es doch irgendwie nicht sein, kennt jemand für dieses Problem so etwas wie eine Musterlösung? Danke schonmal

Gruss

Michael E.

Kessl schrieb:

ich komme inzwischen auf ~3 Seiten Code nur fürs vertauschen.

Zeigst du sie uns? Dann können wir mal schauen, was man vereinfachen kann

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