Doppelt verketteter Ring - Zeigersetzung beim Hinzufügen von Elementen

[wisdomsoz]

Hallo Leute,

und zwar habe ich eine Frage zum doppelt verketteten Ring in C bzw. C++.
Zunächst möchte ich dem Ring ein neues Element hinzufügen.

Wir gehen davon aus, dass wie bei einem Ring üblich, das letzte Element gleichzeitig auch mit dem ersten Element verbunden ist und nicht wie bei einer Liste, ein Anfang und Ende existiert.

Konkret besteht mein Problem darin, die Zeiger der Elemente (*next und *prev) umzustellen, sobald dem Ring ein neues Element hinzugefügt wird.

Konkret geht es um die Methode "Hinzufügen", bei der ich die Zeigersetzung nicht verstehe.

void einfuegen(wert_typ **s1, wert_typ **w)
  {//uebergebener Block wird am Anfang des Ringes eingefuegt
  if(*s1==NULL)// Leere Liste?
    *s1=*w;//Zeitpunkt 2
  else//Einfuegen am Anfang der Liste
    {
    //Next-Verkettung #########################################
    (*w)->next = *s1;
    *s1=(*w);
    (*w)=(*s1)->next;
    (*w)=(*w)->prev;
    (*w)->next=(*s1);  //Zeitpunkt 3
    //Prev-Verkettung#############################################
    (*w)=(*s1);
    (*w)=(*w)->next;//auf 2.Block
    (*s1)->prev=(*w)->prev;
    (*w)->prev = (*s1);
    }//Zeitpunkt 4
  *w=NULL;
  }//einfuegen

Jedes Element (Node) hat ja einen previous Zeiger auf das vorherige Element und einen next Zeiger auf das folgende Element.

Ich verstehe allerdings die Zeigersetzung in der obigen Methode "Hinzufügen" nicht.

Kann mir hier jemand die Zusammenhänge erklären, wieso diese Zeiger so gesetzt wurden?

Bei **s1 handelt es sich um den Startzeiger und bei '**w um den Zeiger auf das Element, welches neu hinzugefügt werden soll.

[wisdomsoz]

Mein Vorgehen wäre wie folgt:

Der next-Zeiger von Start müsste auf das neue Element zeigen. Der prev-Zeiger von dem neuen Element auf Start. Der next-Zeiger vom neuen Element muss somit wieder auf start zeigen und der prev-Zeiger von Start auf das neue Element.

Aber ich weiß nicht, wo ich da falsch liege um ehrlich zu sein. Vielleicht bin ich mittlerweile auch so verwirrt, weil ich mir seit Stunden einen Reim draus versuche zu machen..

[Whiz-zarD]

Woher stammt der Code? Stammt er von dir? Funktioniert er oder wo liegen konkret deine Fragen?

Meine C-Kenntnisse sind auch schon sehr stark angerostet, aber der Code ist auch recht schwierig zu lesen, weil s1 und w ständig getauscht werden. Schauen wir uns aber mal den Code an:

1     //Next-Verkettung #########################################
2     (*w)->next = *s1;
3     *s1=(*w);
4     (*w)=(*s1)->next;
5     (*w)=(*w)->prev;
6     (*w)->next=(*s1);  //Zeitpunkt 3
7     //Prev-Verkettung#############################################
8     (*w)=(*s1);
9     (*w)=(*w)->next;//auf 2.Block
10    (*s1)->prev=(*w)->prev;
11    (*w)->prev = (*s1);

Wir haben folgende Ausgangssituation:

e0 ←→ e1 ←→ e2
↑           ↑
└───────────┘

Wir haben also ein Ring. Bestehend aus e0, e1 und e2. Der Code fügt nun zwischen e0 und e1 ein neues Element (e3) hinzu. *w zeigt auf e3 und *s1 auf e1. e3 hat erstmal keine Verbindung in den Ring.

e3              *w  = e3
                *s1 = e1

e0 ←→ e1 ←→ e2
↑           ↑
└───────────┘

In der zweiten Zeile wird *w->next auf s1 gesetzt:

e3────┐         *w  = e3
      │         *s1 = e1
      ↓
e0 ←→ e1 ←→ e2
↑           ↑
└───────────┘

In Zeile 3 wird *s1 mit *w ersetzt und in zeile 4 *w wird ersetzt mit *s1->next. Damit werden beide getauscht und der Ring hat einen neuen "Anfang":

e3────┐        *w  = e1
      │        *s1 = e3
      ↓
e0 ←→ e1 ←→ e2
↑           ↑
└───────────┘

In zeile 5 wird wiederum *w mit *w->prev getauscht und zeigt somit auf e0.

e3────┐        *w  = e0
      │        *s1 = e3
      ↓
e0 ←→ e1 ←→ e2
↑           ↑
└───────────┘

Nun wird *w->next auf *s1 gesetzt und somit ist e3 schon mal in eine Richtung in den Ring integriert:

e3────┐        *w  = e0
↑     │        *s1 = e3
│     ↓
e0 ←- e1 ←→ e2
↑           ↑
└───────────┘

Allerdings zeigt der prev-Zeiger von e1 noch auf e0 und e3 hat noch kein Prev-Zeiger auf e0. Dies geschieht nun im Prev-Block. *w wird in Zeile 8 und 9 auf e1 gesetzt:

e3────┐        *w  = e1
↑     │        *s1 = e3
│     ↓
e0 ←- e1 ←→ e2
↑           ↑
└───────────┘

Nun wird *s1->prev auf *w-prev gesetzt:

e3────┐        *w  = e1
↑     │        *s1 = e3
↓     ↓
e0 ←- e1 ←→ e2
↑           ↑
└───────────┘

Und zum Schluss *w->prev auf *s1:

e3←───┐        *w  = e1
↑     │        *s1 = e3
↓     ↓
e0    e1 ←→ e2
↑           ↑
└───────────┘

Und der Ring ist fertig.

Allerdings halte ich den Code für zu viel, denn im Grunde ist das ja nur ein Umbiegen der Zeiger. Wir kennen doch den "Anfang" des Ringes (*s1) und das Element (*w), was hinzugefügt werden soll. Dann kann man doch im ersten Schritt

*w->next auf *s1 und
*w->prev auf *s1->prev

setzen.

w─────┐
│     │ 
↓     ↓
s0 ←→ s1 ←→ s2
↑           ↑
└───────────┘

Und im zweiten Schritt 

*w->prev->next auf *w und
*w->next->prev auf *w

w←────┐
↑     │ 
↓     ↓
s0    s1 ←→ s2
↑           ↑
└───────────┘

Das wären dann 4 Zeilen Code.

[wisdomsoz]

Guten Abend,

also erstmal einen herzlichen Dank für die wirklich ausführliche Erklärung.
Nein, der Code stammt nicht von mir, sondern von einem Lehrer, der sie uns zur Verfügung gestellt hat. Ich wollte mir den Code anschauen, um die bekannte Theorie, auch in C++ nachvollziehen zu können. Ich dachte mir anfangs auch, dass man doch nicht so viele Zeiger umbiegen muss, um das neue Element einzufügen, nur dachte ich mir, dass mein Lehrer das wohl schon auf die am wenig verwirrenste und unkomplizierteste Art umsetzt.

Danke nochmal!

[Whiz-zarD]

Ist schon ein bisschen länger her, dass ich mit C einen doppeltverketteten Ring implementiert habe aber so kompliziert habe ich das nicht gemacht. Wie gesagt. Mehr als die vier Zeilen, die ich da schrieb, braucht man nicht. Letzen Endes müsste der Algorithmus genauso aussehen, wie beim Einfügen in eine doppeltverkettete Liste und da braucht man nur die vier Zielen, die ich schrieb:

https://de.wikibooks.org/wiki/Algorithmen_und_Datenstrukturen_in_C/_Listen#Einfügen

In einem Ring hat man ja nicht die Ausnahmen, dass next oder prev NULL sein kann.