Ring

[emulb]

Aufgrund meiner Krankheit und der langen Krankenhaus besuche hinke ich mit dem Stoff sehr weit hinterher. Muss mir gerade alles selber beibringen und muss außerdem 5 Blätter bis morgen abgeben mit jeweils 4 Aufgaben. Dies ist die einzige Aufgabe die ich nicht habe und die ich eigenlich auch nicht verstehe. Ich hab zwar etwas ausprobiert aber ich bin mit meinen Kräften nun vollkommen am Ende. Kann mir jemand bitte helfen, dass ich endlich schlafen kann.
Hier die Aufgabe und im Anschluss meine hingeknetete Lösung.

Eine lineare Liste wird zu einem Ring geschlossen, indem das erste Element der Liste als
Nachfolger des letzten Elements gesetzt wird. Der Anfang der Ringliste wird dann durch
eine Referenz auf ein beliebiges Element des Rings gesetzt. Dieses Element des Rings sei
im folgenden als aktuelles Element bezeichnet.
Implementieren Sie eine Klasse Ring mit Elementen vom Typ Element .
Implementieren Sie für die Klasse Ring Methoden mit folgender Funktionalität:

1. Ring(): Konstruktor, generiert leeren Ring.
2. Ring(int n): Konstruktor, generiert Ring mit n Elementen mit den Werten 1 bis
n aufsteigend. Aktuelles Element hat den Wert 1.
3. next(): Die Referenz auf den Ring (d. h. das aktuelle Element) wird um ein
Element weiter bewegt.
4. back(): Das aktuelle Element wird um ein Element zurück bewegt.
5. insert(int d): Es wird ein Element in den Ring einfügt. Das neue Element soll
vor dem aktuellen Element eingefügt werden.
6. print(): Die Werte der Elemente des Rings werden auf dem Bildschirm ausgegeben.
7. remove(): Das aktuelle Element wird aus dem Ring gelöscht. Das nachfolgende
Element wird aktuelles Element (oder null falls der Ring leer wird).
8. Ein bekannter Auszählreim für Kinder ist „Ene mene muh und raus bis Du!“,
d. h. die siebte Person ist „raus“. Unter den verbleibenden Kindern wird wiederum
ausgezählt bis am Ende ein Gewinner übrig bleibt.
everyNth(int n): Solange möglich, wird jedes n-te (n >=2) Element gelöscht. Für
einen nichtleeren Ring bleibt genau ein Element (der Gewinner) übrig.
Testens Sie ihre Implementierung!

public class Ring<T> {
private final T[] buffer;
private final int capacity;
private int next = 0;
private int used;

public Ring(int c) {
capacity = c;
buffer = (T[])new Object[c];
used = 0;
}


public void push(T t) {
buffer[next] = t;
next++;
if(next >= capacity)
next = 0;
if(used < capacity)
used++;

Das wars auch mit meinem Teil ;( ;( ;(

Ich kann nicht mehr :autsch:

 

[HimBromBeere]

Next soll nicht den Inhalt des nächsten Elementes ausgeben, sondern nur eine Referenz auf dasselbe. Also:

private T next = null;

 

[Marcinek]

Das ist ja tragisch... Fast garnicht in Worte zu fassen. Bemerkenswert tragisch ist auch, dass es mich in keinster Weise interessiert, wie dein Gesundheitlicher Zustand aussieht.

~~~

Also für mich sieht das aus wie eine klassische Aufgabe für die Listenimplementierung mit Elementen, die dann

"data" haben und einen vorgänger und nachfolger.

Und nicht "einfach" ein Array mit T Objekten. Natürlich kann man das so machen aber denke nicht, dass es Sinn der Aufgabe ist.

 

[Firephoenix]

Hier findest du auch einen recht ausführlichen Thread über eine (sogar doppelt verkettete) Ringliste:
http://www.java-forum.org/hausaufgaben/130135-liste.html
Gruß

 

[Kevin94]

Wenn du eigentlich soweit hinterher hinkst, hab ich ehrlichgesagt keine Ahnung wie du auf die Anwendung von Generics kommst, das ist wenn ich die Aufgabe richtig verstanden habe gar nicht gefordert, sodern nur für den Datentyp int (s. 5. insert(int d)). Und das bei dieser Aufgabe keine Arraybasierte Lösung gefordert ist, sondern eine doppletverkettete Liste, halte ich eigentlich für selbstverständlich. Dafür braucht man dann auch eine zweite Klasse (Element).

 

[HimBromBeere]

Kleiner Hinweis:
die Klasse Element besitzt die Eigenschaften Element next und int data. In next ist der Nachfolger dieses Elementes drin, in data der Inhalt des Elementes...

 

[emulb]

ich habs mit google probiert

 

[emulb]

Mein neuer code:

public class Element {
private Object value;
private Element next;
public Element(Object value, Element next) {
this.next = next;
this.value = value;
}
public void setNext(Element next) {
this.next = next;
}
public Element getNext() {
return next;
}
public Object getValue() {
return value;
}
}
public class Ring {
private Element position;
public Ring() {
position = null;
}
}

public void insert(Object v) {
if (position == null) {
position = new Element(v,null);
position.setNext(position);
}
else {
Element e = new Element(v,position.getNext());
position.setNext(e);
public void delete() {
if (position != null) {
if (position.getNext() == position) position = null;
else {
Element prev = position;
while (prev.getNext() != position) prev = prev.getNext();
position = position.getNext();
prev.setNext(position);
}
}
}

 

[Firephoenix]

Ich weiß nicht wo du den jetzt wieder gefunden hast, aber nur mit Code aus google wirst du die Aufgabe nicht lösen.

Den Beitrag von Kevin94 hast du wohl auch hart überlesen oder?

Gruß

 

[HimBromBeere]

Also funktionieren sollte der Code, aber ich denke, er ist etwas unglücklich formuliert.

Deine Element-Klasse sieht aber erstmal ganz OK aus (abgesehen davon, dass in der Aufgabe nur von Integer-Werten für die Daten die Rede war, nicht von (beliebigen) Objekten).

Die Ring-Klasse ist dagegen noch ein wenig unklar, eine Methode insert() sollte auch Elemente EINFÜGEN und nicht anhängen (du brauchst also noch die Information, an welche Stelle das Element soll). Dort musst du dann erstmal mit deinem internen Elementezeiger an die richtige Stelle vorrücken.

 

[Firephoenix]

Wundert mich, dass der Thread jetzt erledigt ist - fertig ist der Code nämlich noch nicht,
wenigstens eine nicht-generische Version die mit int statt object arbeitet hätte ich eigentlich schon erwartet.

Und die Bewegungsmethode back() ist auch relativ schnell umgesetzt, man muss nur solange nach vorne gehen bis das nächste element das element ist bei dem man angefangen hat - so kann man auch ohne doppelverkettung in dem Ring (uneffizient) rückwärts laufen.

Gruß

 

[Firephoenix]

Kann den vorigen Beitrag leider nicht mehr Editieren, hier trotzdem noch ein Vorschlag wie das Ding aussehen könnte, ich hab mich bewusst um spielzeuge wie überladene Konstruktoren etc gedrückt um mit möglichst wenig Methoden auszukommen (gerade im Element nur die getter/setter) um es möglichst überschaubar zu halten.

Klasse für ein Element (daten und Zeiger auf das nächste Element)

public class RingElement
{

    private int data;
    
    private RingElement nextElement;


    public int getData()
    {
        return data;
    }


    public void setData( int data )
    {
        this.data = data;
    }


    public RingElement getNextElement()
    {
        return nextElement;
    }

    public void setNextElement( RingElement nextElement )
    {
        this.nextElement = nextElement;
    }
    
}

Klasse Ring mit Feld für das aktuelle Element und Manipulationsmethoden.

public class Ring
{

    private RingElement aktuellesElement;

    public Ring()
    {
        // Leerer konstruktor, aktuellesElement ist null
    }

    public Ring( int n )
    {
        // Anfang des Rings erstellen
        aktuellesElement = new RingElement();
        aktuellesElement.setData( 1 );
        // Als vorgänger für die neuen Elemente merken
        RingElement vorgänger = aktuellesElement;
        for ( int i = 2; i <= n; i++ )
        {
            // RingElement erzeugen das angehängt wird
            RingElement neuesElement = new RingElement();
            neuesElement.setData( i );
            // Element an den Vorgänger hängen
            vorgänger.setNextElement( neuesElement );
            // Das neue Element wird selbst zum vorgänger
            vorgänger = neuesElement;
        }
        // Am Ende den Ring schließen
        vorgänger.setNextElement( aktuellesElement );
    }

    public void next()
    {
        // Das aktuelle Element ist jetzt der nachfolger
        aktuellesElement = aktuellesElement.getNextElement();
    }

    public void back()
    {
        // Start des Ringes merken
        RingElement start = aktuellesElement;
        // Solange das nächste Element nicht der Start ist
        while ( aktuellesElement.getNextElement() != start )
        {
            // Einen Schritt weiter gehen
            next();
        }
        // Anmerkung: Entspricht einem Autobahnkreuz: Statt einmal Links fahre 3 mal rechts,
        // bzw statt einmal nach hinten, gehe solange nach vorne, bis du hinten bist
    }

    public void insert( int d )
    {
        // Falls der Ring leer ist anfangselement erzeugen und Ring schließen
        if ( aktuellesElement == null )
        {
            aktuellesElement = new RingElement();
            aktuellesElement.setData( d );
            aktuellesElement.setNextElement( aktuellesElement );
        }
        else
        {
            // Element erzeugen das Angefügt wird
            RingElement element = new RingElement();
            element.setData( d );
            // Ein Element zurückgehen und vorgänger merken
            back();
            RingElement vorgaenger = aktuellesElement;
            // Wieder nach vorne gehen zum aktuellen Element
            next();
            // Das neue Element an den vorgänger hängen
            vorgaenger.setNextElement( element );
            // Und das aktuelleElement an das neue anbinden
            element.setNextElement( aktuellesElement );
        }
    }

    public void print()
    {
        // Ausgabe für leeren Ring
        if ( aktuellesElement == null )
        {
            System.out.println( "Der Ring ist leer" );
        }
        else
        {
            // Aktuelles Element merken
            RingElement actual = aktuellesElement;
            do
            {
                // Ausgabe des aktuellen Elementes
                System.out.print( actual.getData() + " " );
                // Ein Element weitergehen
                actual = actual.getNextElement();
            }
            // Solange das aktuelle Element nicht wieder am Anfang angekommen ist
            while ( actual != aktuellesElement );
            // Am Ende noch eine Leerzeile ausgeben
            System.out.println();
        }
    }

    public void remove()
    {
        // Wenn der Ring nur ein Element enthält aktuellesElement auf null setzen
        if ( aktuellesElement.getNextElement() == aktuellesElement )
        {
            aktuellesElement = null;
        }
        else
        {
            // Ansonsten den Nachfolger merken
            RingElement nachfolger = aktuellesElement.getNextElement();
            // Zum vorigen Element laufen
            back();
            // Voriges Element auf Nachfolger des alten aktuellenElementes setzen
            aktuellesElement.setNextElement( nachfolger );
            // Und wieder nach vorne gehen
            next();
        }
    }

    public void everyNth( int n )
    {
        // Solange entfernen bis der Ring nur ein Element enthält
        while ( aktuellesElement.getNextElement() != aktuellesElement )
        {
            // Bei 1 Anfangen zu zählen falls das aktuelle Element mitgezähtl werden soll, andernfalls auf 0 ändern
            for ( int i = 1; i < n; i++ )
            {
                next();
            }
            remove();
        }
    }

}

Gruß