Liste

babuschka

Top Contributor
Hallo, ich will gerade für eine doppelt verkettete Ringliste eine Methode schreiben, die die Listenelemente zählt, wobei man das Ankerelement nicht mitzuzählen hat.

Dabei gibt es jeweils als Attribute Daten und eine Referenz auf das nächste Listenelement, die heißt n. Und natürlich eine Referenz aufs Vorgängerelement, p genannt.

Ich stecke irgendwie fest.

Also man kann bei irgendeinem Listeneintrag anfangen zu zählen und man zählt, bis man diesen Listeneintrag wieder erreicht hat. So weit ist es mir klar.


Aber die Umsetzung...

Java:
public int size(){
int counter=0;
RList e = this;

[...]

Weiter komme ich irgendwie partout nicht...
 
F

Firephoenix

Gast
Zeig doch bitte mal den kompletten Code der Ringliste, mit den 3 Zeilen lässt sich schwer arbeiten.

Ansonsten sollte das umsetzen doch nicht allzu schwer sein oder?

Du musst dir nur raussuchen
-Wie du auf das nächste Element zugreifst
-Wie du 2 Objekte der Liste vergleichst

Und dann nur noch deinen Satz in Codeform bringen:
bei irgendeinem Listeneintrag anfangen zu zählen und man zählt, bis man diesen Listeneintrag wieder erreicht hat

(nur irgendeinem Listeneintrag sollte man evtl durch Anker ersetzen ;) )
Gruß
 

babuschka

Top Contributor
Java:
@file RList.java Listenverwaltung  in Form einer <b>doppelt
 *  verketteten Ringliste</b>.
 *
 *   <ul>
 *    <li> Jedes Listenelement m ist mit einer Referenz m.n auf den
 *          Nachfolger und einer Referenz  m.p auf den Vorgänger versehen
 *         (sog. doppelte Verkettung).
 *    <li> Jede Liste enthält immer ein sog. <b>Ankerelement</b>.
 *          Dieses  trägt niemals
 *          Nutzdaten (Komponente 'data' ist die null-Referenz).
 *    <li> Die leere Liste wird allein durch das Ankerelement
 *          repräsentiert, bei dem Nachfolger
 *          und Vorgänger auf sich selbst zeigen.
 *    <li> Bei einer nicht leeren Liste ist der Nachfolger
 *          des Ankerelementes der <b>Listenkopf</b>, d.h.
 *          das erste Nutzdaten tragende Element der Liste. Der
 *          Vorgänger des Ankerelementes ist das <b>letzte Element</b>
 *          der Liste. Umgekehrt hat der Listenkopf immer das
 *          Ankerelement als Vorgänger, und das letzte Element der
 *          Liste hat immer das Ankerelement als Nachfolger.
 *    </ul>
 *
 *  Der Vorteil einer doppelt verketteten Ringliste besteht darin, 
 *  dass Einfüge- und Löschoperationen, sowie Konkatenation 
 *   ohne spezielle Fallunterscheidungen
 *  "Liste leer/nicht leer", "Löschen des letzten Elementes" etc.
 *  auskommen.
 */

/**
 *  Aus der Klasse Rlist werden einzelne Listenelemente instanziiert.
 *  Gleichzeitig repräsentiert das Ankerelement der Liste die
 *  gesamte Liste, denn vom Ankerelement aus lässt sich jedes 
 *  Listenelement erreichen.
 */
class Rlist<T extends Comparable<T>> {
    
    /** Jeder Listeneintrag hat ein Objekt vom Typ T als Nutzdaten.
     *  Das Ankerelement l der Liste ist durch die Bedingung
     *  
     *  <code>l.data == null</code>
     *
     *  eindeutig gekennzeichnet.
     */
    private T data;
    
    /** Referenz auf das Nachfolger-Listenelement */
    private Rlist<T> n;
    
    /** Referenz auf das Vorgänger-Listenelement */
    private Rlist<T> p;
    
    /**
     *  Konstruktor Rlist() erzeugt eine neue leere
     *  Liste.
     *
     *  @return Korrekt initialisiertes Ankerelement und damit
     *           eine leere Liste, die allein durch das Ankerelement
     *           repräsentiert ist.
     */
     
     public RList(){
    	 data = null;
    	 n = this;
    	 p = this;
     }
    
     /**
     *  Methode isEmpty() prüft, ob eine Liste 
     *  leer ist.
     *
     *
     *  @return Gibt genau dann true zurück, wenn die Liste leer ist,
     *          d.h. wenn Vorgänger und Nachfolger wieder
     *          auf das Listenelement zeigen, auf dem empty()
     *          aufgerufen wird: Damit ist nachgewiesen, dass
     *          die Liste allein aus dem Ankerelement besteht.
     *  
     */
    public boolean isEmpty() {
		return ( n = this && p = this);
    }
    
    /**
     *  Methode size() berechnet die Länge
     *  einer Liste. Das Ankerelement wird 
     *  dabei <b>nicht</b> mit gezählt.
     *
     *  @return Anzahl der Listenelemente,
     *          abzüglich des Ankerelements.
     *
     *  @note Wegen der Ringverkettung kann die Methode auf ein
     *        beliebiges Listenelement aufgerufen werden.
     *        Die Zählung endet, wenn bei der Traversion der List wieder
     *        das Ursprungselement erreicht wurde.
     *  
     */
    public int size() {
		int counter=0;
		RList e = this;
		
				
		while(e.n != this){
				counter++;
				e = e.n;
			}
		return counter;
    }
    
    /**
     *  Methode clear() löscht den Listeninhalt, so dass
     *  die leere Liste zurück bleibt.
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     */
    public void clear() {
    }
    
    /**
     * Methode add() fügt ein neues Listenelement
     * <b>hinter</b>  dem Element ein, auf welchem 
     * die Methode aufgerufen wurde.
     *
     *  @param d Einzufügendes Nutzdatenobjekt.
     *
     *  @note Die Operation lässt sich ohne ein
     *        einziges if-statement realisieren.
     *
     *  @note add(null) ist nicht zulässig,
     *        weil ansonsten das Ankerelement nicht eindeutig
     *        bestimmbar wäre.
     *
     */
    public void add(T d) {
    }
    
    /**
     * Methode insert() fügt ein neues Listenelement
     * <b>vor</b> demjenigen ein, auf welchem die Operation
     * aufgerufen wird.
     *
     *  @param d Nutzdaten für das neu
     *         anzulegende Listenelement.
     *
     *  @note Die Operation lässt sich ohne ein
     *        einziges if-statement realisieren.
     *
     *  @note insert(null) ist nicht zulässig,
     *        weil ansonsten das Ankerelement nicht eindeutig
     *        bestimmbar wäre.
     */
    public void insert(T d) {
    }
    
    
    /**
     * Methode get() gibt den Inhalt (Nutzdaten) des
     * Listenelements zurück, auf dem die Operation
     * aufgerufen wird.
     *
     *  @return Referenz auf die Nutzdaten (kann null sein,
     *  falls es sich um das Ankerelement handelt)
     *
     */
    public T get() {
		return null;
    }
    
    /**
     * Methode next() gibt die Referenz auf 
     * den Nachfolger des Listenelements l zurück,
     * auf dem die Methode aufgerufen wird.
     *
     *  @return Nachfolger l.n von l.
     *
     */
    public Rlist<T> next() {
        return null;
    }
    
    /**
     * Methode prev() gibt die Referenz auf 
     * den Vorgänger des Listenelements l zurück, auf dem
     * die Methode aufgerufen wird.
     *
     *  @return Vorgänger l.p von l.
     *
     */
    public Rlist<T> prev() {
		return null;
    }
    
    /**
     * Methode find() sucht nach einem Listenelement l,
     * welches ein vorgegebenes Nutzdatenelement enthält,
     * und gibt die Referenz auf dieses Element l zurück,
     * falls vorhanden.  
     *
     *  @param d Nutzdatenobjekt, das unter den Listenelementen
     *           gesucht werden soll.
     *  @return null, falls d bei keinem Element als Nutzdaten
     *          eingetragen ist.
     *  @return Referenz auf das erste gefundene Listenelement sonst.
     *
     *  @note Zum Vergleich der Nutzdaten wird die Methode equals()
     *        verwendet.
     */
    public Rlist<T> find(T d) {
		return null;
    }
    
    
    
    /**
     * Methode remove() löscht das Listenelement aus der Liste,
     * auf welchem die Methode aufgerufen wurde. 
     * Wirkungslos, wenn auf dem Ankerelement aufgerufen.
     *
     *
     *  @note Diese Operation benötigt eine if-Abfrage.
     *        Warum?
     */
    public void remove() {
    }
    
    
    /**
     * Methode toString() gibt den Nutzdateninhalt der Liste als String zurück.
     *
     * Der String ist eine durch spitze Klammern eingefasste und durch Komma
     * separierte Auflistung der einzelnen Nutzdaten in der entsprechenden
     * Reihenfolge. Die einzelnen Elemente werden selbst wieder mit der
     * Methode toString() formatiert.
     * Beispielrückgabe: "<1, 2, 4, 3>"
     *
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     * @return Der String.
     */
    public String toString() {
		return null;
    }
    
    
    /**
     * Methode equals() vergleicht zwei Listen auf
     * inhaltliche Gleichheit.
     *
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     *  @param o Referenz auf Ankerelement der zweiten Liste.
     *         Die Liste darf leer sein.
     *
     *  @return false, wenn o nicht vom Typ RList ist.
     *  @return false, wenn die Listen unterschiedliche Länge haben.
     *  @return false, wenn sich die Listen bei mindestens einem Element
     *           in den Nutzdaten unterscheiden.
     *  @return true, falls die Listen dieselbe Länge, dieselben
     *          Nutzdaten und dieselbe Sortierung besitzen.
     */
    public boolean equals(Object o) {
		return false;
    }
    
    
    /**
     *  Methode addSorted() fügt das Element d in die Liste
     *  ein, so dass eine vorher aufsteigend sortierte Liste
     *  nach  Ausführung von addSorted() immer noch aufsteigend 
     *  sortiert ist.
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     * @param d Das einzufügende Element.
     * 
     * @note Nutzdaten werden mit der Funktion compareTo() verglichen.
     */
    public void addSorted(T d) {
    }

    /**
     * Methode isSorted() überprüft, ob die Liste aufsteigend
     * sortiert ist. Diese Methode darf nur auf das
     * Ankerelement aufgerufen werden.
     *
     * @return Gibt genau dann true zurück, wenn die Liste sortiert ist.
     * 
     * @note Nutzdaten werden mit der Funktion compareTo() verglichen.
     */
    public boolean isSorted() {
		return false;
    }
}

Aufgabe ist es, die Methoden zu implementieren.

Ich habe mich schon an dem Konstruktor und isEmpty() versucht.


Nun wollte ich size() probieren.


Nur: So, wie es jetzt dort steht, zählt man ein Element zu wenig... oder
 
F

Firephoenix

Gast
Ein paar Fehler könntest du vermeiden wenn du einfach eine IDE wie Eclipse verwenden würdest :)

-Im Konstruktor: RList und Rlist sind nicht identisch!
-bei isEmpty vergleichst du mit == , = ist eine Zuweisung
-Und bei size() gehört ebenfalls Rlist und nicht RList hin.

Ob die size-Methode funktioniert müsstest du Testen, dafür benötigst du aber erstmal eine Methode mit der du einfügen kannst :) sonst haben deine Testlisten wohl immer größe 0 :)

Gruß
 

babuschka

Top Contributor
Danke für die Hinweise. Das ist wirklich schlampig von mir.

Tests stehen noch aus, ich wollte nur gerne wissen, ob das Bisherige okay ist oder ob ich (schon wieder) auf dem falschen Dampfer bin.

Was würdest Du sagen? Sieht size() ganz gut aus (wenn ich die Schreibfehler berichtige)?





PS. Zur der IDE: Sicher wäre es nicht verboten, so eine zu verwenden, aber richtig vorgestellt soll eine IDE erst im nächsten Semester werden (PI 2, so weit ichs mitbekommen habe).


Dann habe ich nochmal eine Frage zu der zu implementierenden Methode clear():

Diese darf nur auf das Ankerelement angewandt werden, meine Idee ist ganz grundsätzlich (da das Ankerelement keine Nutzdatan trägt, was es m.E. von allen anderen Listenelementen unterscheidet):

Java:
public void clear() {
    
if( this.data == null ){
    n = this;
    p = this;
    data = null;
}
}

Das heißt, wenn man diese Methode auf ein vom Ankerelement verschiedenes Element anwendet, hat sie keinerlei Wirkung. Wobei ich nicht weiß, ob nicht auch andere Elemente der Liste data == null erfüllen können.

Ist das korrekt?
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
Die Methode size() an sich sieht erstmal nicht schlecht aus.
Ist die Liste leer kriegst du eine 0 raus - das ist trivial.
Ansonsten hangelst du dich Element für Element durch die Liste und zählst mit.
Wie gesagt - testen - insbesondere die Randfälle wie leere liste und liste nach löschen/einfügen.

Bei der clear-Methode klingt der Ansatz auch gut, spontan fällt mir auch keine andere Möglichkeit ein den Anker zu erkennen, allerdings solltest du dir da nochmal anschauen ob so etwas sinn macht:
Java:
if( this.data == null ){
    [...]
    data = null;
}

Gruß
 

babuschka

Top Contributor
Vielen lieben Dank für die Reaktion!

Ansonsten hangelst du dich Element für Element durch die Liste und zählst mit.

Zählt man auch die richtige Anzahl? Meine Gedanken hierzu:
Man hört ein Element vor dem Element, bei man zu zählen anfing, auf zu zählen. Das müsste mit der Anzahl hinkommen (das Ankerelement zählt man so nämlich nicht mit).

Beispiel:

Anker - Element 1 - Element 2

Ich fange an zu zählen bei Element 1: Schritt von Element 1 nach Element 2 (Zähler geht auf 1), Schritt von Element 2 zum Anker (Zähler geht auf 2). Ende des Zählens und das kommt ja auch hin, da man das Ankerelement nicht mitzählen soll.

Wenn ich bei Element 2 anfange zu zählen, komme ich auch auf die Anzahl 2.

Ebenso, wenn ich beim Anker beginne zu zählen.


Und das mit dem Testen werde ich machen, das ist nämlich sowieso dann noch eine weiterführende Aufgabe. :)

Bei der clear-Methode klingt der Ansatz auch gut, spontan fällt mir auch keine andere Möglichkeit ein den Anker zu erkennen, allerdings solltest du dir da nochmal anschauen ob so etwas sinn macht:
Java:
if( this.data == null ){
    [...]
    data = null;
}

Gruß

Okay, das ist natürlich doppelt & dreifach, da dann data ohnehin null ist.
Es reicht, die Referenzen auf this zu setzen.


Ich habe oben in der Beschreibung noch gelesen, daß das Ankerelement durch data == null eindeutig identifiziert sein soll; demnach müsste die Methode wohl so okay sein.
 
Zuletzt bearbeitet von einem Moderator:

babuschka

Top Contributor
Hallo!

Ich befasse mich nun gerade mit der Methode add(T d).

Dort steht, daß man kein einziges if-statement benötigt. Das ist mir unklar, wie das funktionieren kann.

Ich habe bisher nur Folgendes hinbekommen:

1. Fall: leere Menge, d.h. Anwenden der Methode auf das Ankerelement

Java:
public void add(T d){
if(d != null){

this.n = d;
this.p = d;
d.n = this;
d.p = this;
}
}

2. Fall: Anwenden der Methode auf ein Element bei nicht leerer Menge (das Element auf das die Methode angewandt wird ist nicht das letzte Element)

Java:
public void add(T d){
if(d != null){

this.n = d;
d.p = this;
d.n = this.n;
this.n.p = d;
}
}

3. Fall: Anwenden der Methode auf das letzte Element

Java:
public void add(T d){
if( d!= null){

this.n = d;
d.p = this;
d.n = this.n;
}
}


Ich habe hierzu also 2 Fragen:

1.) Stimmen die Einzelfälle?

2.) Wie kann man das nun zusammen und ohne if-statement(s) realisieren?



Besten Dank!



Edit:
Ich glaube, ich habe nicht gut genug überlegt.
Wenn ich mir das recht ansehe, kommt das Folgende doch für alle 3 Fälle hin:

Java:
public void add(T d){
 if(d != null){
   this.n = d;
   d.p = this;
   d.n = this.n;
   this.n.p = d;
  }
}

Stimmt's?

Jetzt müsste ich bloß noch das eine if-statement wegbekommen. :)
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
Schau dir dazu mal den Kommentar der Methode an und überleg dir was genau dein if-statement abfängt.
Gruß
 

babuschka

Top Contributor
Ich bin gerade ein bisschen irritiert, weil der Parameter d gar kein Element, sondern nur die Nutzdaten (also data) eines hinzuzufügenden Elements sein soll?

Verstehe ich da was falsch?



Edit: Quatsch: d soll ein Nutzdatenobjekt sein, also Listenelement, aber kein Ankerelement...

Dann würde ich zumindest verbessern:

Java:
if(d.data != null){...}

Aber das if-statement kreucht da dann immer noch rum.


Edit 2:

Nee, das ist doch nicht so toll.

Ich bleibe bei if(d != null), weiß aber leider noch immer nicht, wie ich das wegbekomme. :rtfm:

Also Du hast mir den Tipp gegeben, mal zu überlegen, was ich mit diesem if-statement abfange.

Ich würde meinen, den Fall, daß das hinzuzufügende Nutzdatenobjekt auf nichts verweist...
 
Zuletzt bearbeitet von einem Moderator:

babuschka

Top Contributor
Also nochmal ein bisschen geordneter. Ich fange schon wieder an, die Hinweise zu überlesen, sorry. Das soll nicht wieder passieren, also konkret zu Deinem Hinweis:


Was fange ich mit dem if-statement ab.
Den Fall, daß man ein Listenelement einfügt, das auf nichts verweist. (null verweist doch auf nichts)

Kann man über diese Überlegung darauf kommen, wie man das if-statement da wegbekommen kann?



Edit:

Achso, eine Überlegung: Als Parameter soll man ja ein Nutzdatenobjekt übergeben und das zeichnet sich ja dadurch aus, daß es Nutzdaten und eine Referenz auf Vorgänger bzw. Nachfolger hat.

Und null hat ja diese Referenzen nicht, von daher kann man das if-statement einfach weglassen, weil sowieso eine Fehlermeldung kommt, wenn man null als Parameter der Methode übergibt?

(Nur eine Idee.)
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
@note add(null) ist nicht zulässig,
* weil ansonsten das Ankerelement nicht eindeutig
* bestimmbar wäre.

Add(null) ist nicht erlaubt, da man ohne if-Bedingungen auskommen soll würde ich daraus folgern, dass man diesen fall auch nicht prüfen muss.
Gruß
 

babuschka

Top Contributor
Also tatsächlich nur:

Java:
public void add(T d) {
    	this.n = d;
    	d.p = this;
    	d.n = this.n;
    	this.n.p = d;
   }

und das ist schon die ganze Methode?



----------------------

Macht es eigentlich einen Unterschied, daß bei der Methode insert(T d) bei der Beschreibung steht, daß d hier die Nutzdaten sind? (Bei add(T d) ist d ja das Nutzdatenobjekt).

Im Grunde sind die Methoden doch aber sehr ähnlich, nur, daß man einmal davor und einmal danach einfügt, deswegen verstehe ich nicht ganz, wieso der Parameter d unterschiedliche Bedeutungen haben soll.


Ich würde einfach meinen:

Java:
public void insert(T d){
   this.p = d;
   d.n. = this;
   d.p = this.p;
   this.p.n = d;
}

---------------------------

Dann nochmal ein paar Methoden, die ich wohl meine zu haben und gern kontrolliert hätte:

Java:
public T get() {
		return this.data;
    }

sowie

Java:
public Rlist<T> next() {
        return this.n;
    }

sowie

Java:
public Rlist<T> prev() {
		return this.p;
    }
 
Zuletzt bearbeitet von einem Moderator:

babuschka

Top Contributor
Und noch eine Methode (ergänzend zum letzten Post), von der ich gern wüsste, ob's okay ist:

Java:
public Rlist<T> find(T d) {
    	Rlist e = this;
    	do {
            if ( e.data.equals(d) ) {
                return e;
            }
            e = e.n;
        } while ( e != this );
        return null;       
    }
 
F

Firephoenix

Gast
Überleg dir mal was bei dem 1. Durchlauf passiert wenn e.data.equals(d) ausgewertet wird.
Gruß
 

babuschka

Top Contributor
Hm, ich würde sagen: Wenn eine Übereinstimmung vorliegt, wird e ausgegeben, sonst e um eine Position weiterverschoben.

Stimmt daran etwas nicht?


(Bestimmt, sonst würdest Du nicht drauf hinweisen...)


Hm, ich sehe da nichts Falsches. :bahnhof:


Kannst Du noch einen Hinweis geben? :oops:
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
Was passiert denn wenn du am Anker anfängst und loslegst?

Java:
Rlist e = this;
e ist jetzt dein Listenanker. Bei dem ist data ja bekanntlich null.

Jetzt prüfst du
Java:
f ( e.data.equals(d) )

also if null.equals(d)

und sobald du per Punkt-Notation Aufrufe auf einer null-referenz durchführst fliegt eine Nullpointer-Exception.

Bei solchen Fehlern bist du aber wirklich schneller wenn du dir einfach mal eine Main-Methode anlegst, dir eine Testliste erstellst (z.b. eine Liste die Strings speichert) und einfach mal deine Methoden aufrufst und mit ein paar println prüfst ob auch das herauskommt was du erwartest.

Bzw Falls ihr schon eine Testumgebung wie JUnit hattet kannst du auch dort direkt Tests für deine Liste anlegen und einfach mal prüfen ob das herauskommt was du erwartest.

Das macht es einfacher und ist schneller als nach jedem Stück Code einen Post zu erstellen ;)

Gruß
 

babuschka

Top Contributor
Diese fiese NullPointerException immer.
Die habe ich noch nie so richtig verstanden.

Aber wenn ich so frage, lerne ich am meisten. Aber ich werde versuchen, weniger zu posten und mehr zu testen.


Ich würde dann also am liebsten sowas vorschlagen:

Java:
public Rlist<T> find(T d) {
    	Rlist e = this;
    	do {
            if ( e.data != null && e.data.equals(d) ) {
                return e;
            }
            e = e.n;
        } while ( e != this );
        return null;       
    }

:toll: oder :mad: ?

---------------------------

Ich hoffe, es nervt Dich nicht allzu sehr, aber hier ist noch eine Methode, auf die Du vllt. mal ein Auge werfen kannst, wenn Du Lust hast. Das ist meine Idee zur Methode remove():

Java:
public void remove() {
    	if(this.data != null){
    		this.p.n = this.n;
    		this.n.p = this.p;
    	}
    }

Im Kommentarteil ist gefragt, wieso man hier ein if-statement braucht.
Meine Antwort ist: Damit man ausschließen kann, daß man die Methode auf das Ankerelement anwendet (s. Code, Zeile 2). Wäre das die richtige Antwort?
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
Klingt doch brauchbar, wie siehts denn mit deiner Ausgabe aus wenn du die Methoden einfach mal laufen lässt?

Müsst ihr für die Klasse eigentlich eine Testsuite mit z.B. JUnit einrichten um zu prüfen ob eure Methoden auch der Funktion entsprechen oder wird das später erst bei der Abgabe von demjenigen gemacht der das ganze bewertet?

Gruß
 

babuschka

Top Contributor
Wenn Du mit Ausgabe das Kompilieren meinst, so bekomme ich die Fehlermeldungen, die ich als Screenshot angefügt habe und nicht gut verstehe.


Ja, wir sollen mit JUnit eine Testsuite schreiben, das ist Aufgabe Nr. 2.

--------------------------------------

Nochmal eine weitere Frage:

Meine Idee zu toString():

Java:
public String toString() {
    	if(this.data == null){
    	
		    String s = new String();
		    for(Rlist e = this.n; e != this; e.next() ){
		    	s += e.get().toString() + "\n";
		    }
    		  return s;
    		}
    }


Allerdings weiß ich nicht, wie ich die gewünschte Ausgabe mit den eckigen Klammern und den Kommata realisieren kann, jetzt habe ich ja nur, daß die Listenelemente (abzüglich des Ankerlements)untereinander ausgegeben werden oder?


Es soll ja aber <Element 1, Element 2,...> sein.

Wie macht man sowas?
 
F

Firephoenix

Gast
Erstmal die aktuellen Fehler raus bevor du weitere Methoden schreibst, Java ist bei den Fehlermeldungen auch relativ freundlich (ich erinner mich da nur an meine Assembler-Versuche: 200 Zeilen Registermatsch und als Fehlermeldung kommt: Segmentation Fault :applaus:)

Der erste Fehler tritt bei dir in Zeile 139 auf, hier hast du offenbar eine Zuweisung und versuchst ein Objekt vom Typ T in ein Objekt vom Typ Rlist<T> zu packen -> das geht logischerweise schief.
Vermutlich musst du hier erst das T-Objekt in ein neues Rlist-Objekt stecken.

Bei den nächsten 2 Fehlermeldungen in Zeile 140/141 hast du ein ähnliches Problem, diese sind vom Typ T implements Comparable und nicht vom Typ Rlist<T> , du kannst hier nicht auf .n oder .p zugreifen.

142 und 161 sind das gleiche Problem wie in Zeile 139

162 und 163 das gleiche wie 140/141

und 164 wieder das gleiche wie 139

Die Mal beheben und neu versuchen, falls neue Fehler finden erstmal das neue Wissen anwenden und schauen ob du sie beheben kannst (die meisten lösen sich auf wenn man sich nur den Text anschaut und dann die Zeile, gerade sowas wie incompatible types findet man in einer Zeile x = y sehr schnell wenn man sich einfach überlegt welchen Typ x und y haben können)
Gruß
 

babuschka

Top Contributor
Kurze Zwischenfrage zur Fehlerbehebung Zeile 139 nach Deinem Vorschlag:

Um ein neues Rlist - Objekt zu erzeuge, das das T - Objekt enthält, muss ich erst einen zusätzlichen Konstruktor schreiben, oder? Bisher habe ich ja nur einen, der die leere Menge erzeugt, aber keinen, der dafür sorgt, daß eine Liste erzeugt wird, die ein als Parameter übergebenes Element enthält.

Mein erster Gedanke war, eine leere Liste zu erzeugen und dann mit add(d) das Element d hinzuzufügen, aber das geht ja nicht, weil der Fehler gerade im Rumpf der Methode add(T d) auftaucht.


Wenn ja, wie könnte dieser Konstruktor aussehen?
Bin da gerade ein bisschen ratlos.
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
du willst ja auch keine Leere Liste erzeugen und dann add an die Leere Liste hängen und die einfügen, dann kriegst du ja sowas:

Anker(data = null) - Leere Liste (data = null) - data
(was von den Typen her auch nicht geht)

Besser wäre statdessen:

Anker(data=null)
->
Anker(data=null) - Leere Liste (data = null)
->
Anker(data = null) - Leere Liste (data = d)

Natürlich kannst du auch erst die data setzen und dann anhängen, wichtig ist, dass du am Ende eine Ringliste bekommst die um 1 größer ist und bei der hinter deinem aktuellem Element ein neues eingefügt wurde dessen data-feld das einzufügende data-feld speichert.

Gruß
 

babuschka

Top Contributor
Oh, das habe ich nicht verstanden.

Anker - Leere Liste

Das ist der 1. Schritt. Also mit dem Konstruktor eine leere Liste erzeugen. Und noch eine leere Liste erzeugen. Und die an die erste dranhängen.

Und dann bei der zweiten Liste data=d setzen und die entsprechenden Referenzen, dann hat man eine Liste Anker - Element 1 mit data==d



So?

Was ich aber, wie gesagt, nicht verstanden habe: Wie kann ich das denn anhängen? Add kann ich ja nicht benutzen,wenn ich da den Fehler habe?


EDIT: Ich hab Dich doch richtig verstanden, daß Du mir beschrieben hast, wie man den Konstruktor schreiben muss? Und darf ich den Konstruktor, der die leere Liste erzeugt, ínnerhalb dieses Konstruktors verwenden??

Dann würde ich es glaube ich verstanden haben.

Der Konstruktor wäre dann nach meiner Idee:

Java:
public Rlist(T d){

Rlist<T> l = new Rlist<T>();
Rlist<T> m = new Rlist<T>();
m.data = d;
m.n = l;
m.p =l;
l.n = m;
l.p =m;
}

Ich hoffe, das ist okay! Ansonsten habe ich wieder Murks produziert...
 
Zuletzt bearbeitet von einem Moderator:

babuschka

Top Contributor
Ich hoffe, mein Edit im letzten Post gleicht die blöde Frage davor wieder aus.

(Wenn das stimmt. Bin mir nämlich (wie immer) nicht sicher.)
 
F

Firephoenix

Gast
Java:
Rlist<T> m = new Rlist<T>();
m.data = d;

Damit kriegst du doch genau das was du willst - eine Liste die die neuen Daten enthält die du einfügen willst.
Jetzt musst du die Liste nur noch richtig in die andere Liste hängen, der richtige Ort dafür ist genau die add()-Methode (kein neuer Konstruktor ;))
Gruß
 

babuschka

Top Contributor
Achso!

Java:
public void add(T d){
Rlist<T> m = new Rlist<T>();
m.data = d;

this.n = m;
m.p = this;
m.n = this.n;
this.n.p = m;
}

Kompilieren zeigt:

Die Fehleranzahl hat sich auf 4 reduziert, also kann's so verkehrt nicht sein. :toll:


Jetzt hab ichs auch kapiert!

Danke hoch drei!

:idea:



Um die restlichen Fehler kümmere ich mich später, für heute ist Feierabend.
 

babuschka

Top Contributor
Hallo und guten "Morgen",

ich habe jetzt die Fehler, wie ich sie als Screenshot gepostet hatte beseitigt, es bleibt noch folgende Konsolenausgabe übrig (s. Screenshot).

Was hat das zu bedeuten bzw. wie behebe ich das?

----------------------

Dann kann ich ja jetzt mit der Methode toString() weitermachen.
Da habe ich folgenden Code:

Java:
public String toString() {
    	String s = new String();
    	
    	if(this.data == null){
	      for(Rlist e = this.n; e != this; e.next() ){
		    	s += e.get().toString() + "\n";
		    }
    	}
   
    	return s;		
    }

Ich weiß allerdings nicht, wie ich die gewünschte Ausgabe machen kann, also in spitzen Klammern und die Listeneinträge mit Kommata voneinander getrennt...

Könnte ich da einen Tipp bekommen?



LG
 
F

Firephoenix

Gast
Zeig mal den Code von der kompletten Klasse wegen der unchecked-Meldung.

Für die toString:
Am Anfang und am Ende steht immer ein "<" und ein ">".
Warum fügst du dann nicht einfach am Anfang und am Ende der Methode die Zeichen an den String an?
Dann musst du nur noch einmal über die Liste laufen und den rest in den String packen.
Gruß
 

babuschka

Top Contributor
Java:
public String toString() {
    	String s = new String();
    	
    	if(this.data == null){
	      for(Rlist e = this.n; e != this; e.next() ){
		    	s += e.get().toString() + ",";
		    }
    	}
   
    	return "<" + s + ">";		
    }

Meinst Du das so?

----------------------

Okay, hier ist die ganze Klasse:

Java:
/** 
 *  @file RList.java Listenverwaltung  in Form einer <b>doppelt
 *  verketteten Ringliste</b>.
 *
 *   <ul>
 *    <li> Jedes Listenelement m ist mit einer Referenz m.n auf den
 *          Nachfolger und einer Referenz  m.p auf den Vorgänger versehen
 *         (sog. doppelte Verkettung).
 *    <li> Jede Liste enthält immer ein sog. <b>Ankerelement</b>.
 *          Dieses  trägt niemals
 *          Nutzdaten (Komponente 'data' ist die null-Referenz).
 *    <li> Die leere Liste wird allein durch das Ankerelement
 *          repräsentiert, bei dem Nachfolger
 *          und Vorgänger auf sich selbst zeigen.
 *    <li> Bei einer nicht leeren Liste ist der Nachfolger
 *          des Ankerelementes der <b>Listenkopf</b>, d.h.
 *          das erste Nutzdaten tragende Element der Liste. Der
 *          Vorgänger des Ankerelementes ist das <b>letzte Element</b>
 *          der Liste. Umgekehrt hat der Listenkopf immer das
 *          Ankerelement als Vorgänger, und das letzte Element der
 *          Liste hat immer das Ankerelement als Nachfolger.
 *    </ul>
 *
 *  Der Vorteil einer doppelt verketteten Ringliste besteht darin, 
 *  dass Einfüge- und Löschoperationen, sowie Konkatenation 
 *   ohne spezielle Fallunterscheidungen
 *  "Liste leer/nicht leer", "Löschen des letzten Elementes" etc.
 *  auskommen.
 */

/**
 *  Aus der Klasse Rlist werden einzelne Listenelemente instanziiert.
 *  Gleichzeitig repräsentiert das Ankerelement der Liste die
 *  gesamte Liste, denn vom Ankerelement aus lässt sich jedes 
 *  Listenelement erreichen.
 */
class Rlist<T extends Comparable<T>> {
    
    /** Jeder Listeneintrag hat ein Objekt vom Typ T als Nutzdaten.
     *  Das Ankerelement l der Liste ist durch die Bedingung
     *  
     *  <code>l.data == null</code>
     *
     *  eindeutig gekennzeichnet.
     */
    private T data;
    
    /** Referenz auf das Nachfolger-Listenelement */
    private Rlist<T> n;
    
    /** Referenz auf das Vorgänger-Listenelement */
    private Rlist<T> p;
    
    /**
     *  Konstruktor Rlist() erzeugt eine neue leere
     *  Liste.
     *
     *  @return Korrekt initialisiertes Ankerelement und damit
     *           eine leere Liste, die allein durch das Ankerelement
     *           repräsentiert ist.
     */
     
     public Rlist(){
    	 data = null;
    	 n = this;
    	 p = this;
     }
    
     
     
     /**
     *  Methode isEmpty() prüft, ob eine Liste 
     *  leer ist.
     *
     *
     *  @return Gibt genau dann true zurück, wenn die Liste leer ist,
     *          d.h. wenn Vorgänger und Nachfolger wieder
     *          auf das Listenelement zeigen, auf dem empty()
     *          aufgerufen wird: Damit ist nachgewiesen, dass
     *          die Liste allein aus dem Ankerelement besteht.
     *  
     */
    public boolean isEmpty() {
		return ( n == this && p == this);
    }
    
    /**
     *  Methode size() berechnet die Länge
     *  einer Liste. Das Ankerelement wird 
     *  dabei <b>nicht</b> mit gezählt.
     *
     *  @return Anzahl der Listenelemente,
     *          abzüglich des Ankerelements.
     *
     *  @note Wegen der Ringverkettung kann die Methode auf ein
     *        beliebiges Listenelement aufgerufen werden.
     *        Die Zählung endet, wenn bei der Traversion der List wieder
     *        das Ursprungselement erreicht wurde.
     *  
     */
    public int size() {
		int counter=0;
		Rlist<T> e = this;
		
		while(e.n != this){
				counter++;
				e = e.n;
			}
		return counter;
    }
    
    /**
     *  Methode clear() löscht den Listeninhalt, so dass
     *  die leere Liste zurück bleibt.
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     */
    public void clear() {
	    if(this.data==null){
		    n = this;
		    p = this;
   }
}
    /**
     * Methode add() fügt ein neues Listenelement
     * <b>hinter</b>  dem Element ein, auf welchem 
     * die Methode aufgerufen wurde.
     *
     *  @param d Einzufügendes Nutzdatenobjekt.
     *
     *  @note Die Operation lässt sich ohne ein
     *        einziges if-statement realisieren.
     *
     *  @note add(null) ist nicht zulässig,
     *        weil ansonsten das Ankerelement nicht eindeutig
     *        bestimmbar wäre.
     *
     */
    public void add(T d){
    	Rlist<T> m = new Rlist<T>();
    	m.data = d;
    	this.n = m;
    	m.p = this;
    	m.n = this.n;
    	this.n.p = m;
   }
    
    /**
     * Methode insert() fügt ein neues Listenelement
     * <b>vor</b> demjenigen ein, auf welchem die Operation
     * aufgerufen wird.
     *
     *  @param d Nutzdaten für das neu
     *         anzulegende Listenelement.
     *
     *  @note Die Operation lässt sich ohne ein
     *        einziges if-statement realisieren.
     *
     *  @note insert(null) ist nicht zulässig,
     *        weil ansonsten das Ankerelement nicht eindeutig
     *        bestimmbar wäre.
     */
    public void insert(T d) {
    	Rlist<T> m = new Rlist<T>();
    	m.data = d;
    	this.p = m;
    	m.n = this;
    	m.p = this.p;
    	this.p.n = m;
    }
    
    
    /**
     * Methode get() gibt den Inhalt (Nutzdaten) des
     * Listenelements zurück, auf dem die Operation
     * aufgerufen wird.
     *
     *  @return Referenz auf die Nutzdaten (kann null sein,
     *  falls es sich um das Ankerelement handelt)
     *
     */
    public T get() {
		return this.data;
    }
    
    /**
     * Methode next() gibt die Referenz auf 
     * den Nachfolger des Listenelements l zurück,
     * auf dem die Methode aufgerufen wird.
     *
     *  @return Nachfolger l.n von l.
     *
     */
    public Rlist<T> next() {
        return this.n;
    }
    
    /**
     * Methode prev() gibt die Referenz auf 
     * den Vorgänger des Listenelements l zurück, auf dem
     * die Methode aufgerufen wird.
     *
     *  @return Vorgänger l.p von l.
     *
     */
    public Rlist<T> prev() {
		return this.p;
    }
    
    /**
     * Methode find() sucht nach einem Listenelement l,
     * welches ein vorgegebenes Nutzdatenelement enthält,
     * und gibt die Referenz auf dieses Element l zurück,
     * falls vorhanden.  
     *
     *  @param d Nutzdatenobjekt, das unter den Listenelementen
     *           gesucht werden soll.
     *  @return null, falls d bei keinem Element als Nutzdaten
     *          eingetragen ist.
     *  @return Referenz auf das erste gefundene Listenelement sonst.
     *
     *  @note Zum Vergleich der Nutzdaten wird die Methode equals()
     *        verwendet.
     */
    public Rlist<T> find(T d) {
    	Rlist e = this;
    	do {
            if ( e.data != null && e.data.equals(d) ) {
                return e;
            }
            e = e.n;
        } while ( e != this );
        return null;       
    }
    
    
    
    /**
     * Methode remove() löscht das Listenelement aus der Liste,
     * auf welchem die Methode aufgerufen wurde. 
     * Wirkungslos, wenn auf dem Ankerelement aufgerufen.
     *
     *
     *  @note Diese Operation benötigt eine if-Abfrage.
     *        Warum?
     */
    public void remove() {
    	if(this.data != null){
    		this.p.n = this.n;
    		this.n.p = this.p;
    	}
    }
    
    
    /**
     * Methode toString() gibt den Nutzdateninhalt der Liste als String zurück.
     *
     * Der String ist eine durch spitze Klammern eingefasste und durch Komma
     * separierte Auflistung der einzelnen Nutzdaten in der entsprechenden
     * Reihenfolge. Die einzelnen Elemente werden selbst wieder mit der
     * Methode toString() formatiert.
     * Beispielrückgabe: "<1, 2, 4, 3>"
     *
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     * @return Der String.
     */
    public String toString() {
    	String s = new String();
    	
    	if(this.data == null){
	      for(Rlist e = this.n; e != this; e.next() ){
		    	s += e.get().toString() + ",";
		    }
    	}
   
    	return "<" + s + ">";		
    }
    
    	
    /**
     * Methode equals() vergleicht zwei Listen auf
     * inhaltliche Gleichheit.
     *
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     *  @param o Referenz auf Ankerelement der zweiten Liste.
     *         Die Liste darf leer sein.
     *
     *  @return false, wenn o nicht vom Typ RList ist.
     *  @return false, wenn die Listen unterschiedliche Länge haben.
     *  @return false, wenn sich die Listen bei mindestens einem Element
     *           in den Nutzdaten unterscheiden.
     *  @return true, falls die Listen dieselbe Länge, dieselben
     *          Nutzdaten und dieselbe Sortierung besitzen.
     */
    public boolean equals(Object o) {
		return false;
    }
    
    
    /**
     *  Methode addSorted() fügt das Element d in die Liste
     *  ein, so dass eine vorher aufsteigend sortierte Liste
     *  nach  Ausführung von addSorted() immer noch aufsteigend 
     *  sortiert ist.
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     * @param d Das einzufügende Element.
     * 
     * @note Nutzdaten werden mit der Funktion compareTo() verglichen.
     */
    public void addSorted(T d) {
    }

    /**
     * Methode isSorted() überprüft, ob die Liste aufsteigend
     * sortiert ist. Diese Methode darf nur auf das
     * Ankerelement aufgerufen werden.
     *
     * @return Gibt genau dann true zurück, wenn die Liste sortiert ist.
     * 
     * @note Nutzdaten werden mit der Funktion compareTo() verglichen.
     */
    public boolean isSorted() {
		return false;
    }
}
 
F

Firephoenix

Gast
Bin mal drüber gegangen bzgl des unchecked:
aus der Methode find:

Java:
public Rlist<T> find(T d) {
        Rlist e = this;
        do {
            if ( e.data != null && e.data.equals(d) ) {
                return e;
            }
            e = e.n;
        } while ( e != this );
        return null;       
    }

e ist nur eine Rlist ohne generische Typisierung, zurückliefern willst du aber eine Rlist<T>, hier musst du korrekt typisieren (gleiches typproblem auch in der toString)

Und in der toString hast du auch noch einen anderen kleinen Fehler eingebaut, den findest du aber sofort wenn du toString mal auf einer nicht-leeren Liste ausführst ;)

Gruß
 

babuschka

Top Contributor
Was ein fehlendes <T> alles auslösen kann...

Also da habe ich jetzt:

Java:
public Rlist<T> find(T d) {
    	Rlist<T> e = this;
    	do {
            if ( e.data != null && e.data.equals(d) ) {
                return e;
            }
            e = e.n;
        } while ( e != this );
        return null;       
    }

Es kommt auch beim Kompilieren keine Fehlermeldung bzw. auch sonst keine Ausgabe mehr.

-----------------

Bei toString() sehe ich jedoch nicht, wo etwas falsch ist.
Ich glaube nur, daß das Komma da falsch steht.

Wenn ich zum Beispiel eine Liste habe, die ein Element hat, also

Anker - Element 1

so wäre die Ausgabe wohl nicht

<Element 1>, sondern <Element 1,>...
 
F

Firephoenix

Gast
Java:
public static void main( String[] args )
    {
        Rlist<String> rlist = new Rlist<String>();
        System.out.println(rlist.toString());
        rlist.add( "Hello" );
        System.out.println(rlist.toString());
        rlist.add( "World" );
        System.out.println(rlist.toString());
    }

Meine Ausgabe (mit meiner Version):
<>
<Hello>
<World, World>

Bekommst du eine identische Ausgabe?
(sowas ist auch eine gute Gelegenheit direkt mit den Tests anzufangen - hier sei dir nochmal zu eclipse geraten - da schreibste die tests in JUnit, drückst auf den run-test button und kriegst nen schicken grünen balken wenns geht ;) )
Gruß
 
F

Firephoenix

Gast
Methode toString() gibt den Nutzdateninhalt der Liste als String zurück. Der String ist eine durch spitze
* Klammern eingefasste und durch Komma separierte Auflistung der einzelnen Nutzdaten in der entsprechenden
* Reihenfolge. Die einzelnen Elemente werden selbst wieder mit der Methode toString() formatiert. Beispielrückgabe:
* "<1, 2, 4, 3>" Diese Methode darf nur auf das Ankerelement aufgerufen werden.

Der Fehler der dafür sorgt, dass deine Liste leer bleibt kann auch gut in deiner add-Methode liegen.

Mal dir mal auf einem Papier auf was du für Elemente hast (jeweils mit data, next und prev-teil) und geh dann den Code per Hand durch um zu prüfen ob am Ende auch das herauskommt was du willst:

Java:
Rlist<T> m = new Rlist<T>();
        m.data = d;
        this.n = m;
        m.p = this;
        m.n = this.n;
        this.n.p = m;

Gruß
 

babuschka

Top Contributor
Für mich ist bei der Methode add() so alles okay.

Habe es mal durchgespielt...





Das verwirrt mich jetzt dann doch ein bisschen.
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
Sicher?

Gruß

Edit: 333 Posts sehe ich gerade - Schnapszahl :)
 
Zuletzt bearbeitet von einem Moderator:

babuschka

Top Contributor
Ich habe wohl den Fehler gemacht, daß ich Werte zuweise und später diese Variablen wieder verwende.

Nützt es was die Reihenfolge zu ändern?

Ich habe jetzt dies überlegt an der Skizze von Dir:

Java:
public void add(T d){
    	Rlist<T> m = new Rlist<T>();
    	m.data = d;
    	m.n = this.n;
             m.p = this;
             this.n = m;
             m.n.p = m;

   }


Edit: Nee, das ändert auch nix, ich glaube ich habe den gleichen Fehler wieder gemacht.
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
Rlist<T> newElement = new Rlist<T>();
newElement.data = d;
newElement.n = this.n;
this.n.p = newElement;
this.n = newElement;
newElement.p = this;


Geh doch einfach mal Schritt für Schritt drüber :)

1. Neues Element erzeugen und data setzen.
Jetzt willst du die 2 Elemente verbinden.
Was du direkt kennst, ohne etwas kaputt zu machen ist, das du den Vorgänger des neuen Elementes setzt, das ist ja dein aktuelles Element.
das nächste Element hinter deinem aktuellem Kennt allerdings das neue als vorgänger nicht nicht, also teilst du diesem jetzt mit, dass es einen neuen Vorgänger hat.

Jetzt hast du das neue und dein voriges folgeElement verknüpft.
Was noch fehlt ist das neue Element mit dem aktuellem,
Also hängst du das neue an dein aktuelles und dann dein aktuelles element noch als vorgänger an das neue element.

Wenn du den Vorgang einfach mal auf dem Papier aufmals (auch mal mit mehr Elementen) kommst du da wesentlich schneller drauf ;)
15 Minuten Papier und Zeichnen können 2-3 Stunden probieren und Fehlersuche vermeiden.
Gruß
 

babuschka

Top Contributor
Jetzt habe ich es verstanden.

Aber auch damit wird immer nur noch <> ausgegeben.


:noe:


Edit: Achso und was ich noch dazu sagen sollte:

Wenn ich also java Rlist eingebe...

Erscheint <> und dann kann man nichts mehr machen, so, als wenn es laden und laden und laden würde.
 
Zuletzt bearbeitet von einem Moderator:

babuschka

Top Contributor
Da ich mir jeden noch so blöden Fehler zutraue...

Mal eine Frage... habe ich die main-Methode denn überhaupt richtig eingefügt...

Vielleicht liegt die komische Ausgabe einfach daran, daß ich das wieder falsch gemacht habe?!


Ich habe die main-methode einfach unten an die Klasse gemacht:

Java:
/** 
 *  @file RList.java Listenverwaltung  in Form einer <b>doppelt
 *  verketteten Ringliste</b>.
 *
 *   <ul>
 *    <li> Jedes Listenelement m ist mit einer Referenz m.n auf den
 *          Nachfolger und einer Referenz  m.p auf den Vorgänger versehen
 *         (sog. doppelte Verkettung).
 *    <li> Jede Liste enthält immer ein sog. <b>Ankerelement</b>.
 *          Dieses  trägt niemals
 *          Nutzdaten (Komponente 'data' ist die null-Referenz).
 *    <li> Die leere Liste wird allein durch das Ankerelement
 *          repräsentiert, bei dem Nachfolger
 *          und Vorgänger auf sich selbst zeigen.
 *    <li> Bei einer nicht leeren Liste ist der Nachfolger
 *          des Ankerelementes der <b>Listenkopf</b>, d.h.
 *          das erste Nutzdaten tragende Element der Liste. Der
 *          Vorgänger des Ankerelementes ist das <b>letzte Element</b>
 *          der Liste. Umgekehrt hat der Listenkopf immer das
 *          Ankerelement als Vorgänger, und das letzte Element der
 *          Liste hat immer das Ankerelement als Nachfolger.
 *    </ul>
 *
 *  Der Vorteil einer doppelt verketteten Ringliste besteht darin, 
 *  dass Einfüge- und Löschoperationen, sowie Konkatenation 
 *   ohne spezielle Fallunterscheidungen
 *  "Liste leer/nicht leer", "Löschen des letzten Elementes" etc.
 *  auskommen.
 */

/**
 *  Aus der Klasse Rlist werden einzelne Listenelemente instanziiert.
 *  Gleichzeitig repräsentiert das Ankerelement der Liste die
 *  gesamte Liste, denn vom Ankerelement aus lässt sich jedes 
 *  Listenelement erreichen.
 */
class Rlist<T extends Comparable<T>> {
    
    /** Jeder Listeneintrag hat ein Objekt vom Typ T als Nutzdaten.
     *  Das Ankerelement l der Liste ist durch die Bedingung
     *  
     *  <code>l.data == null</code>
     *
     *  eindeutig gekennzeichnet.
     */
    private T data;
    
    /** Referenz auf das Nachfolger-Listenelement */
    private Rlist<T> n;
    
    /** Referenz auf das Vorgänger-Listenelement */
    private Rlist<T> p;
    
    /**
     *  Konstruktor Rlist() erzeugt eine neue leere
     *  Liste.
     *
     *  @return Korrekt initialisiertes Ankerelement und damit
     *           eine leere Liste, die allein durch das Ankerelement
     *           repräsentiert ist.
     */
     
     public Rlist(){
    	 data = null;
    	 n = this;
    	 p = this;
     }
    
     
     
     /**
     *  Methode isEmpty() prüft, ob eine Liste 
     *  leer ist.
     *
     *
     *  @return Gibt genau dann true zurück, wenn die Liste leer ist,
     *          d.h. wenn Vorgänger und Nachfolger wieder
     *          auf das Listenelement zeigen, auf dem empty()
     *          aufgerufen wird: Damit ist nachgewiesen, dass
     *          die Liste allein aus dem Ankerelement besteht.
     *  
     */
    public boolean isEmpty() {
		return ( n == this && p == this);
    }
    
    /**
     *  Methode size() berechnet die Länge
     *  einer Liste. Das Ankerelement wird 
     *  dabei <b>nicht</b> mit gezählt.
     *
     *  @return Anzahl der Listenelemente,
     *          abzüglich des Ankerelements.
     *
     *  @note Wegen der Ringverkettung kann die Methode auf ein
     *        beliebiges Listenelement aufgerufen werden.
     *        Die Zählung endet, wenn bei der Traversion der List wieder
     *        das Ursprungselement erreicht wurde.
     *  
     */
    public int size() {
		int counter=0;
		Rlist<T> e = this;
		
		while(e.n != this){
				counter++;
				e = e.n;
			}
		return counter;
    }
    
    /**
     *  Methode clear() löscht den Listeninhalt, so dass
     *  die leere Liste zurück bleibt.
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     */
    public void clear() {
	    if(this.data==null){
		    n = this;
		    p = this;
   }
}
    /**
     * Methode add() fügt ein neues Listenelement
     * <b>hinter</b>  dem Element ein, auf welchem 
     * die Methode aufgerufen wurde.
     *
     *  @param d Einzufügendes Nutzdatenobjekt.
     *
     *  @note Die Operation lässt sich ohne ein
     *        einziges if-statement realisieren.
     *
     *  @note add(null) ist nicht zulässig,
     *        weil ansonsten das Ankerelement nicht eindeutig
     *        bestimmbar wäre.
     *
     */
    public void add(T d){
    	Rlist<T> m = new Rlist<T>();
    	m.data = d;
    	m.n = this.n;
    	this.n.p = m;
    	this.n = m;
    	m.p = this;
    	
    }
    
    /**
     * Methode insert() fügt ein neues Listenelement
     * <b>vor</b> demjenigen ein, auf welchem die Operation
     * aufgerufen wird.
     *
     *  @param d Nutzdaten für das neu
     *         anzulegende Listenelement.
     *
     *  @note Die Operation lässt sich ohne ein
     *        einziges if-statement realisieren.
     *
     *  @note insert(null) ist nicht zulässig,
     *        weil ansonsten das Ankerelement nicht eindeutig
     *        bestimmbar wäre.
     */
    public void insert(T d) {
    	Rlist<T> m = new Rlist<T>();
    	m.data = d;
    	m.p = this.p;
    	this.p.n = m;
    	this.p = m;
    	m.n = this;
    }
    
    
    /**
     * Methode get() gibt den Inhalt (Nutzdaten) des
     * Listenelements zurück, auf dem die Operation
     * aufgerufen wird.
     *
     *  @return Referenz auf die Nutzdaten (kann null sein,
     *  falls es sich um das Ankerelement handelt)
     *
     */
    public T get() {
		return this.data;
    }
    
    /**
     * Methode next() gibt die Referenz auf 
     * den Nachfolger des Listenelements l zurück,
     * auf dem die Methode aufgerufen wird.
     *
     *  @return Nachfolger l.n von l.
     *
     */
    public Rlist<T> next() {
        return this.n;
    }
    
    /**
     * Methode prev() gibt die Referenz auf 
     * den Vorgänger des Listenelements l zurück, auf dem
     * die Methode aufgerufen wird.
     *
     *  @return Vorgänger l.p von l.
     *
     */
    public Rlist<T> prev() {
		return this.p;
    }
    
    /**
     * Methode find() sucht nach einem Listenelement l,
     * welches ein vorgegebenes Nutzdatenelement enthält,
     * und gibt die Referenz auf dieses Element l zurück,
     * falls vorhanden.  
     *
     *  @param d Nutzdatenobjekt, das unter den Listenelementen
     *           gesucht werden soll.
     *  @return null, falls d bei keinem Element als Nutzdaten
     *          eingetragen ist.
     *  @return Referenz auf das erste gefundene Listenelement sonst.
     *
     *  @note Zum Vergleich der Nutzdaten wird die Methode equals()
     *        verwendet.
     */
    public Rlist<T> find(T d) {
    	Rlist<T> e = this;
    	do {
            if ( e.data != null && e.data.equals(d) ) {
                return e;
            }
            e = e.n;
        } while ( e != this );
        return null;       
    }
    
    
    
    /**
     * Methode remove() löscht das Listenelement aus der Liste,
     * auf welchem die Methode aufgerufen wurde. 
     * Wirkungslos, wenn auf dem Ankerelement aufgerufen.
     *
     *
     *  @note Diese Operation benötigt eine if-Abfrage.
     *        Warum?
     */
    public void remove() {
    	if(this.data != null){
    		this.p.n = this.n;
    		this.n.p = this.p;
    	}
    }
    
    
    /**
     * Methode toString() gibt den Nutzdateninhalt der Liste als String zurück.
     *
     * Der String ist eine durch spitze Klammern eingefasste und durch Komma
     * separierte Auflistung der einzelnen Nutzdaten in der entsprechenden
     * Reihenfolge. Die einzelnen Elemente werden selbst wieder mit der
     * Methode toString() formatiert.
     * Beispielrückgabe: "<1, 2, 4, 3>"
     *
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     * @return Der String.
     */
    public String toString() {
    	String s = new String();
    	
    	if(this.data == null){
	      for(Rlist e = this.n; e != this; e.next() ){
		    	s += e.get().toString() + ",";
		    }
	      return "<" + s + ">";
    	}
    	
    	return "<" + s + ">";
   
    			
    }
    
    	
    /**
     * Methode equals() vergleicht zwei Listen auf
     * inhaltliche Gleichheit.
     *
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     *  @param o Referenz auf Ankerelement der zweiten Liste.
     *         Die Liste darf leer sein.
     *
     *  @return false, wenn o nicht vom Typ RList ist.
     *  @return false, wenn die Listen unterschiedliche Länge haben.
     *  @return false, wenn sich die Listen bei mindestens einem Element
     *           in den Nutzdaten unterscheiden.
     *  @return true, falls die Listen dieselbe Länge, dieselben
     *          Nutzdaten und dieselbe Sortierung besitzen.
     */
    public boolean equals(Object o) {
		return false;
    }
    
    
    /**
     *  Methode addSorted() fügt das Element d in die Liste
     *  ein, so dass eine vorher aufsteigend sortierte Liste
     *  nach  Ausführung von addSorted() immer noch aufsteigend 
     *  sortiert ist.
     *  Diese Methode darf nur auf das Ankerelement aufgerufen
     *  werden.
     *
     * @param d Das einzufügende Element.
     * 
     * @note Nutzdaten werden mit der Funktion compareTo() verglichen.
     */
    public void addSorted(T d) {
    }

    /**
     * Methode isSorted() überprüft, ob die Liste aufsteigend
     * sortiert ist. Diese Methode darf nur auf das
     * Ankerelement aufgerufen werden.
     *
     * @return Gibt genau dann true zurück, wenn die Liste sortiert ist.
     * 
     * @note Nutzdaten werden mit der Funktion compareTo() verglichen.
     */
    public boolean isSorted() {
		return false;
    }
    
    public static void main( String[] args )
    {
        Rlist<String> rlist = new Rlist<String>();
        System.out.println(rlist.toString());
        rlist.add( "Hello" );
        System.out.println(rlist.toString());
        rlist.add( "World" );
        System.out.println(rlist.toString());
    }
}


Ist das vllt. der Fehler??
 

babuschka

Top Contributor
Nee, also im Moment sehe ich weder einen Fehler in add(), noch einen in toString() und kann das Verhalten daher nicht nachvollziehen. :bahnhof:


Kannst Du mir einen Hinweis geben?

--------------------------

Ich mache derweil weiter mit der Methode equals(Object o), hier meine Idee:

Java:
public boolean equals(Object o) {
		if( ! (o instanceof Rlist)) return false;
		
		Rlist lAux = (Rlist)o;
        Rlist l;
        
        if( this.size() != lAux.size() ) return false;
        
        
        for(l=this.n; l != this; l=l.next(), lAux=lAux.next()){
        	if( ! l.get().equals(lAux.get()) ) return false;
        }
    	
    return true;
    }

Auch hier würde ich mich über ein Feedback freuen.
 
Zuletzt bearbeitet von einem Moderator:

babuschka

Top Contributor
Und weiter geht's. Hier meine Idee zu addSorted(T d):

Java:
public void addSorted(T d) {
    	Rlist<T> m = new Rlist<T>();
    	m.data = d;
    	
    	if( this.isEmpty() ) {
    		m.p = this;
    		m.n = this;
    		this.n = m;
    		this.p = m;
    	}
    
         Rlist<T> prev = this;
         for( Rlist<T> l = this.next(); l != this; l = l.next(), prev = prev.next() ){
        	 if( l.get().compareTo(m.data) >= 0){
        		 m.n = l;
        		 m.p = prev;
        		 prev.n = m;
        		 l.p = m;
        	 }
         }
    
        m.p = this.n;
        m.n = this;
        this.p.n = m;
    
    
    }


EDIT:

Oder muss es in Zeile 14 heißen:

Java:
if( l.get().compareTo(m.data) >= 0 && prev.get().compareTo(m.data) <= 0 ){

? (Es muss ja auch größer gleich dem vorherigen Listeneintrag sein...

Feedback erwünscht. ;)

-------------------------------

Und dann auch noch zur Methode isSorted():

Java:
public boolean isSorted() {
		Rlist<T> prev = this;
		Rlist<T> l;
		
		for( l = this.next(); l != this; l = l.next(), prev = prev.next() ){
			if( prev.get().compareTo(l.get()) > 0 ) return false;
		}
  
       return true;
    }

Auch hier: Feedback erbeten.
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
Shame on me :) ich sehe gerade meine Ausgabe bzgl der Main war falsch (copy-paste fehler :D)

Java:
public static void main( String[] args )
    {
        Rlist<String> rlist = new Rlist<String>();
        System.out.println(rlist.toString());
        rlist.add( "Hello" );
        System.out.println(rlist.toString());
        rlist.add( "World" );
        System.out.println(rlist.toString());
    }

muss folgenden output produzieren:
<>
<Hello>
<World, Hello>

Was auch Sinn macht, denn das World wird nach Hello eingefügt, rückt also zwischen Anker und Hello.
Bei der Ausgabe fängt man nach dem Anker an, kommt zuerst zu World und dann zu Hello.
Deine Main ist aber korrekt.

Die Ausgabe "<>" produziert deine fehlerhafte toString(), den Fehler findest du sobald du dir einfach mal in die for-schleife ein sysout einbaust.


Edit:
Ich würde dir übrigens gerade in Hinsicht auf Aufgabe 2 dringend raten dir mal eclipse zu besorgen, das Programm beißt nicht und die Einarbeitungszeit hält sich in Grenzen.
Auf dem Javavideokurs von hdi sind die ersten 6 Videos übrigens frei und dort beschreibt er sehr gut wie du dir eclipse besorgst und ein erstes Projekt einrichtest, JUnit dann in das Projekt zu bekommen sind auch nur 3-4 klicks - das kann man schnell machen.
Java Video Kurs - Java Video Tutorials - Online Java lernen! (Video 1/2 müssten das sein).
Falls es dir die 50€ Wert ist kann ich den kurs übrigens sehr empfehlen - Videomaterial von der Qualität dürfte man in der Form nur schwer finden.

Sobald du das Eingerichtet hast kannst du nämlich dein Projekt mit einem Button ausführen, anstatt jedes mal per Konsole zu Compilen und dort auszuführen.
Gerade wenn man viel ausprobiert kommt doch oft die Idee "ach das wird schon gehen, ich schreib noch etwas mehr bevor ich wieder 2 Minuten in Konsole und Konsorten verblase" und nach ner halben Stunde Coden am Stück kommt dann eine Fehlerpalette die so lang ist wie dein Screen von Seite 2 ;)

Die meisten Fehler kannst du auch direkt vermeiden, weil Eclipse so nett ist dir syntaktisch falsche Stellen anzustreichen.

Außerdem lernst du gleich noch etwas wichtiges mit wenn du Tests schreibst bevor der Code funktioniert :) Du musst dir nämlich Gedanken darüber machen was dein Code tun soll, ohne ihn zu kennen.
Ein Beispiel dafür ist die kleine main die ich dir gegeben habe.
Die kann man ohne weiteres in einen Testfall packen und hat eine schöne prüfung dafür ob add in Kombination mit toString() das produziert was sie tut.
Und statt konsole ablesen ein assertEquals(..) darum zu klatschen kostet wirklich wenig Zeit ;)



Gruß
 
Zuletzt bearbeitet von einem Moderator:

babuschka

Top Contributor
Okay, ich habe den Fehler entdeckt, es muss bei der Inkrementierung der for-Schleife lauten:

Code:
e = e.next()

Die Ausgabe ist dann nicht so wie Deine, sondern so, wie es in folgendem Screenshot zu sehen ist:



EDIT: Wenn ich das System.out von oben wieder rausnehme, komme ich dann auch auf das, was bei Dir ausgegeben wird.
 
Zuletzt bearbeitet von einem Moderator:
F

Firephoenix

Gast
Ich war etwas langsam mit dem Editieren - bitte nochmal meinen vorigen Post durchlesen :)

Deine Ausgabe ist relativ ähnlich, ich vermute, dass du irgendwo nochmal s direkt ausgibst oder?
Außerdem fehlen dir noch Leerstellen hinter den Daten und du solltest hinter den letzten Eintrag kein Komma mehr schreiben ;)
Gruß
 

babuschka

Top Contributor
Ich habe das verbessert: Ja, ich hatte ja ein System.out.println(s) eingeführt um den Fehler zu entdecken und jetzt habe ich das wieder entfernt und bekomme auch nur die Ausgaben mit den eckigen Klammern.



Die Leerzeilen nach den Kommata habe ich jetzt auch.

Aber zwei Fragen bleiben bei mir doch noch:

1. Wie kann man bei dem letzten Eintrag das Komma wegbekommen.

2. Soll nicht <Hello, World> ausgegeben werden? Ich habe oben gelesen, wo Du erklärst, wie <World, Hello> zustande kommt, aber soll nicht idealerweise doch <Hello, World> ausgegeben werden?
 
F

Firephoenix

Gast
zu 1.
In der for-schleife unterscheiden, was machst du bei jedem durchlauf, was nur bei bestimmten durchläufen (z.b. alle außer dem letzten) und wie erkennst du den letzten durchlauf?

2.
Du kannst die Strings auch durch "Blau" und "Magentacyan" ersetzen,
wenn du zuerst Blau einfügst und dann Magentacyan bekommst du als Ausgabe <Magentacyan, Blau>

3.
Edit oben -> eclipse :)

Gruß
 

babuschka

Top Contributor
Tipp 1.) und 3.) behalte ich im Hinterkopf.


Aber zu 2.)

Möchte man denn nicht aber bei add() daß das Element 1 (also das, was man zuerst einfügt, z.B. "Blau") auch als erstes in der Liste steht?..




EDIT: Zu 1.)

Hab es hinbekommen.

Java:
for(Rlist e = this.n; e != this; e=e.next() ){
		    	if(e.n != this) s += e.get().toString() + ", ";


		    	else s += e.get().toString();


EDIT2:

Achso... rlist wird ja neu erzeugt als leere Liste. Dann wird darauf add() angewandt, damit rückt das HELLO hinter den Anker, also rlist.. Dann wird nochmal add() auf rlist angewandt und damit rückt world zwischen anker (rlist) und HELLO.

Alles klar!! :toll:
 
Zuletzt bearbeitet von einem Moderator:

Neue Themen


Oben