Ringliste in C++ programmieren

B

bandchef

0
Hi Leute!

Ich will eine Ringliste in C++ programmieren. Bei einer Ringliste muss ja das letzte Element auf das erste Zeigen. Wie aber mach ich das dann?

Ich hab hier schon mal einiges an Code geschrieben:

Code: 
#include<iostream>
#include"ringlist.h"
using namespace std;


ringlist::ringlist()
{
    head = NULL;
    tail = NULL;
}


ringlist::~ringlist()
{

}


void ringlist::Append(int val)
{
    element *elem = new element;

    elem->val = val;
    elem->next = NULL;

    if(tail == NULL)
    {
        head = elem;
        tail = elem;
    }
    else
    {
        tail->next = elem;
        tail = elem;
    }
}


void ringlist::Print()
{
    element *curr = head;

    cout << "Ringliste: ";
    while(curr != NULL)
    {
        cout << curr->val << " ";
        curr = curr->next;
    }
    cout << endl;
}


Code: 
#ifndef RINGLIST__H
#define RINGLIST__H
#include"element.h"

class ringlist
{
private:
    element *head;
    element *tail;

public:
    ringlist();
    ~ringlist();

    void Append(int value);
    void Print();
};

#endif


Code: 
#ifndef ELEMENT__H
#define ELEMENT__H

class element
{
public:
    int val;
    element *next;
};

#endif


Mein Problem ist quasi nun, wie ich in der Methode Append() wissen soll, wann das letzte Element angefügt wird, damit ich den Zeiger des Elements auf das erste Element legen kann... Versteht ihr was ich meine?
 
Zuletzt bearbeitet:
Du müsstest erstens einmal festlegen wie groß die Ringliste ist. Dann kannst du während dem Hinzufügen und Entfernen mitzählen wieviele Elemente enthalten sind und wüsstest somit durch einen einfachen Vergleich, wann die Ringliste voll ist.

mfg benediktibk
 
Ein append() fügt immer hinten an, schafft also ein neues letztes Element. Das bisherige letzte Element zeigt dann auf das neu angehängte, das neu angehängte zeigt auf das erste Element der Liste.
 
Kommt jetzt ganz darauf an, ob man eine Ringliste mit konstanter (bzw. maximaler) Größe hat, oder eine dynamisch wachsende.

mfg benediktibk
 
Es kann ja sowohl dynamische, als auch konstante Ringlisten geben.
Ebenso können Ringlisten doppelt verkettet sein oder nur einfach.

Ein "Problem" bei der Ringliste besteht darin, dass man sich die Anzahl der Elemente extern merken muss, weil man die Elemente nicht zählen kann, wie bei üblichen Listen. Denn dann würde man eine Endlosschleife basteln beim Versuch es zu zählen. :wink:

So gesehen gibt es eigentlich auch kein "Append" (Anhängen), sondern nur ein Insert nach oder vor einem beliebigen Element.
Denn wo ist bei einer Ringliste denn das Ende oder der Anfang? Gibt's nicht.

Selbst, wenn die Ringliste nur ein Element hat, zeigt das Next auf sich selbst, bzw. zusätzlich auch das prev, wenn doppelt verlinkt.

Also: Das da oben ist keine Ringliste.
 
+++ATH0 hat gesagt.:
Ein "Problem" bei der Ringliste besteht darin, dass man sich die Anzahl der Elemente extern merken muss, weil man die Elemente nicht zählen kann, wie bei üblichen Listen. Denn dann würde man eine Endlosschleife basteln beim Versuch es zu zählen. :wink:
Zum Vergrößern anklicken....
Zuminest unter C++ könnte man sich die Speicheradressen ausgeben lassen und so schauen, ob man da schon mal war.
 
Es müsste doch kein Problem sein die Ringliste zu durchlaufen. Er merkt sich doch den head und den tail. Das heißt er setz seine Durchlaufschleife beim head an und durchläuft sie solange bis er bei tail auskommt. Und selbst wenn er sowas nicht hätte bräuchte er sich doch nur die Adresse seinen Startelements merken und beim Durchlaufen einfach jedesmal prüfen ob er die Adresse wieder erreicht hat.
 
Selbst ohne die Adresse des Startelements, also auch in vielen anderen Programmiersprachen wo man gar kein Zugriff darauf hat, würde es funktionieren, wenn man einfach die Identität des Startobjekts immer vergleichen lässt. Vorausgesetzt man hat eine Objektorientierte Programmiersprache und speichert keine primitiven Datentypen ab, wobei die in Java z.B. auch ein äquivalent dafür haben (int und Integer als Beispiel).

Ist jetzt wohl aber auch egal, ich denke es hat jeder kapiert, dass man in einer Ringliste herausbekommt wieviele Elemente enthalten sind :D
 
Identität eines Objekts != Wert eines Objekts.

a == b mag true sein, dennoch können die Identitäten von a und b unterschiedlich sein ;)
 
enkore hat gesagt.:
Identität eines Objekts != Wert eines Objekts.

a == b mag true sein, dennoch können die Identitäten von a und b unterschiedlich sein ;)
Zum Vergrößern anklicken....

Stimmt schon, aber wie t3rr0r.bYt3 bereits andeutete bezog er sich darauf, dass du tatsächlich das selbe Objekt öfter in der Ringliste hast.
Also Objekt A,B,C und eine Ringliste die z.B. (natürlich als "Ring") wie folgt aufgebaut ist: A,C,B,A,B,C,A*..., wobei ab A* jetzt eine Runde vorbei ist.
Dann ist die Identität des ersten und vierten Objekts gleich, weils auch das selbe Objekt ist, aber trotzdem die Ringliste noch nicht zu Ende.
Wobei das gleiche auch für Speicheradressen gelten würde, weil das Objekt A auch an der selben Speicheradresse bleibt.

Daran hatte ich jetzt nicht gedacht, aber...

Was mir dabei auch noch auffällt: Wenn ein Objekt zweimal in einer Ringliste vorkommt muss es auch zwei unterschiedliche Nachfolger haben, denn wenn in jedem Objekt selbst der Nachfolger steht, verändert der sich nicht und daher haben wir eine Runde, und damit die Anzahl, sobald wir einmal das selbe Objekt finden. Ansonsten würde man zweimal den selben Zyklus im Ring haben, was an für sich schon keinen Sinn macht und daher direkt vom Programmierer ausgeschlossen werden sollte.
Heißt also man bräuchte sowas wie ein "Ringlistenelement", dass ein Nachfolger Ringlistenelement hat und eine Referenz auf das tatsächliche Objekt was "drin" sein soll, aber dann kann ich die Identität der Ringlistenelement Objekte überprüfen.
Also wenn meine Überlegungen jetzt nicht falsch sind, bräuchte ich für "zweimal das selbe Objekt in einer Ringliste" sowieso wieder ein zusätzliches Objekt wie Ringlistenelement, dass eindeutig die Position, im Sinne von Nachfolger, weil Positionen gibt es an für sich ja nicht in einer Ringliste, bestimmten kann und damit den Nachfolger.
 
Zuletzt bearbeitet:
Ähm, man kann sich das Leben schon schwerer machen als es ist. :wink:.
Was ist so verkehrt daran entweder mitzuzählen oder die Adressen zu vergleichen? Ist performanter, einfacher zu programmieren und geht nicht von irgendwelchen Annahmen a la nicht zweimal den selben Zyklus im Ring haben aus.

mfg benediktibk
 
benediktibk hat gesagt.:
Was ist so verkehrt daran entweder mitzuzählen [...]
Zum Vergrößern anklicken....

Nix ;-).

benediktibk hat gesagt.:
[...] oder die Adressen zu vergleichen?
Zum Vergrößern anklicken....

Genau das Selbe was t3rr0r.bYt3 zu meinem Vorschlag gesagt hat die ID des Objekts zu vergleichen: "Nur unter der Voraussetzung, dass kein Element mehrfach vorkommt."
Kommt ein Element mehrfach vor wirst du auch zweimal die selbe Speicheradresse haben und damit sind wir wieder bei dem was ich davor geschrieben habe :D
 
Am zuverlässigsten ist es wohl immernoch, intern einen Zähler der Objekte zu haben, denn modifiziert werden kann die Liste ja sowieso nur durch dein Interface.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben