Jump to content
  • 0
Melde dich an, um diesem Inhalt zu folgen  

Doppelt verketteter Ring - Zeigersetzung beim Hinzufügen von Elementen

Frage

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.

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen

4 Antworten auf diese Frage

Empfohlene Beiträge

  • 0

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

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
  • 0

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.

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
  • 0

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!

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
  • 0

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.

Diesen Beitrag teilen


Link zum Beitrag
Auf anderen Seiten teilen
Gast
Du kommentierst als Gast. Wenn du bereits einen Account hast kannst du dich hier anmelden.
Diese Frage beantworten...

×   Du hast formatierten Text eingefügt.   Formatierung jetzt entfernen

  Only 75 emoji are allowed.

×   Dein Link wurde automatisch eingebettet.   Einbetten rückgängig machen und als Link darstellen

×   Dein vorheriger Inhalt wurde wiederhergestellt.   Clear editor

×   Du kannst Bilder nicht direkt einfügen. Lade Bilder hoch oder lade sie von einer URL.

Melde dich an, um diesem Inhalt zu folgen  

Fachinformatiker.de, 2018 SE Internet Services

fidelogo_small.png

if_icon-6-mail-envelope-closed_314900.pnSchicken Sie uns eine Nachricht!

Fachinformatiker.de ist die größte IT-Community
rund um Ausbildung, Job, Weiterbildung für IT-Fachkräfte.

Fachinformatiker.de App


Get it on Google Play

Kontakt

Hier werben?
Oder senden Sie eine E-Mail an

Social media u. feeds

Jobboard für Fachinformatiker und IT-Fachkräfte

×

Wichtige Information

Fachinformatiker.de verwendet Cookies. Mehr dazu in unserer Datenschutzerklärung