Datentyp Ring - zyklisch doppelt verkettete Liste - HILFE!

Status
Nicht offen für weitere Antworten.

rydnic

Mitglied
Hallo :D ,

hab ein Aufgabenblatt mit folgender Fragestellung, sitze schon den ganzen Tag dran, aber bin echt noch nicht so weit das zu lösen, muß aber morgen testieren lassen und brauche die Lösung um zur Klausur zugelassen zu werden :( !
Ich wäre euch super dankbar, wenn Ihr mir einen Tipp geben könntet!!!

Folgende Fragestellung:

Datentyp Ring

Betrachten sie folgende Modifikation der Liste:

Stellen sie sich eine doppelt verkettete Liste vom Typ Item vor, die an den Enden "zusammengeklebt" ist. Man hat also keine Liste mehr, sondern einen doppelt verketteten Ring mit einem Item das als oldest deklariert ist, also das älteste Item im Ring ist.
Definieren sie eine Klasse Ring unter Verwendung der unten angegebenen Klasse Item. Implementieren sie die Einfügeoperation void Ring.insert(Item i) die ein neues Item in den Ring einfügt, und die Entfernungsoperation Item Ring.extract(Item i) die das älteste Item aus dem Ring entfernt und zurück liefert.

Die Klasse sollte außerdem eine Variable haben die die momentane Anzahl von Items enthält.


Code:
public class Item {
    protected Item next = null;
    protected Item prev = null;
    public Object data = null;
    public Item(Object o) {
        this.data = o;
    }
}

und das Klassengerüst:

Code:
public class Ring {
    private int size = 0;
    private Item oldest;
    [...]
    public void insert(Item i) {
       [...]
    }
    public Item extract() {
       [...]
    }
}
 
G

Guest

Gast
Wenn du dein Problem ein weing genauer definieren koenntest waere es auch einfacher dir zu helfen.

Ich finde die Fragestellung recht straig forward.

Also wie die Datenstrucktur aussehen soll ist dir klar?

So und die zwei Funktionen insert und extract sind halt eigentlich ganz einfache Operationen auf dieser Datenstruktur. Um ein Objekt einzufuegen, sucht man sich die entsprechende Stelle raus und setzt die Pointer dann dementsprechend wie man die haben will, meistens so:

Code:
public void insert(item i)
{
   item before = //suche das Objekt hinter dem es eingefuegt werden soll;
   item after = before.next;

   before.next = i;
   after.prev = i;
   i.next = after;
   i.prev = before;
}

Und das mit dem loeschen macht in der Aufgabenstellung fuer mich nicht 100% Sinn, weil da steht es soll das aelteste Element der Liste entfernt werden, jedoch wird der Funktion auch ein Objekt uebergeben --> wozu? Wenn ich das aelteste loeschen soll?

Naja, dass sollte halt ungefaehr so aussehen:

Code:
public void delete()
{
   oldest.next.prev = oldest.prev;
   oldest.prev.next = oldest.next;
}

Das sollte es schon gewesen sein, da wir in java ja nen Garbage Collector haben(oder?).

Bei der insert Funktion muss man noch den Zaehler fuer die Laenge der Liste(Ringes) erhoehen und so nen paar Kleinigkeiten einbauen../

Hoffe hat dir geholfen,

MfG && Greets

tj[/code]
 

AlArenal

Top Contributor
Wenn du nen insert machst, ist es schonmal logisch, dass sich die Anzahl der Items im Ring um 1 erhöht, oder? Den Sonderfall, dass ein schlauer Fuchs ein bereits vorhandenes Item added, klammern wir mal aus.

Dem einzufügenden Item musste eben noch seinen prev und next setzen. Für das erste Item ist das das Item selbst. Danach ist next immer auf oldest zu setzen und der vorige prev von oldest wird prev von i. Der next des ehem. prev von oldest ist dann auf i zu setzen, usw.

extract ist dann irgendwie das gleiche in grün, nur rückwärts ;)

Zeichne dir mal nen Ring auf, inkl. Pfeile für next und prev und dann zeichne Schritt für Schritt was passiert, wenn du was einfügst (wohin muss dann wessen next und prev zeigen?) oder entfernst. Etwas aufpassen muss man bei der Reihenfolge, in der man die Zeiger verbiegt...
 

semi

Top Contributor
@Gast
Das geht aber mächtig in die Hose. Ziemlich viele unbehandelte Fälle. :wink:

@rydnic
Zeichne es auf ein Blatt Papier aus. Mit den "prev" und "next" Pfeilen und überlege Dir,
wie Du die Items entfernen bzw. einfügen kannst, ohne das der Ring unterbrochen
wird.
Eingefügt wird immer vor das älteste Item (wenn vorhanden). Beim Entfernen wird
der Nachfolger des ältesten Items (wenn vorhanden) zum ältesten Item.

Beim Einfügen drei Fälle

1: Noch nix drin
2: Nur ein Item drin
3: Mehr als ein Item drin

Beim Löschen

1: Nichts drin
2: Nur ein Item drin (eine Person steht alleine, hält niemanden)
3: Zwei Items drin (zwei Personen halten sich an den Händen)
4: Mehr als zwei Items drin (mehr als zwei Personen bilden einen Kreis)

Zeichne diese sieben Szenarios auf.
 
G

Guest

Gast
@semi, wie gesagt, nen paar Kleingkeiten fehlen da noch und das wird einem beim ersten Ausfuehren schon auffallen, dass da irgendwann NullExceptions rumfliegen, aber wer solche AUfgaben zu loesen hat sollte auch solche Probleme loesen koennen... ;-p
 

rydnic

Mitglied
Hi,
hier ist meine Lösung, wenn ich mir alles so durchlese ist es der falsche Lösungsansatz.
Werde wohl nochmal beim Urschleim anfangen müssen, bekomm es nicht mal gebacken eine einfache Test-Klasse dafür zu schreiben die funktioniert.

Code:
public class Ring {
    private int size = 0;
    private Item oldest;
    private Item first;
        
  //  [...]
   public void insert(Item i) {
    	if (oldest == null){
    		oldest = new Item(i);
    		first = oldest;
    		oldest.next = oldest;
    		oldest.prev = oldest;
    	   	size++;}
    	else {if (size==1){
    	 oldest.next = new Item(i);
         oldest = oldest.next;
         oldest.prev = oldest.next;
    	}
    	else {oldest.next = new Item(i);
    	 oldest.prev = oldest;
    	 oldest = oldest.next;
    	 oldest.next.next = first;}
    	}
}
    public Item extract() {
       [...]
    }
}
 

Bert Brenner

Bekanntes Mitglied
so weit ist das doch garr nicht mehr von der richtigen lösung entfernt. die new Item(i) kannst du aber weglassen und durch i ersetzen.
 

semi

Top Contributor
Code:
public void insert(Item i)
 {
   if(size==0)
   {
     [...] Fall 1: Noch nichts drin
   }
   else if(size==1)
   {
     [...] Fall 2: Bereits ein Item drin
   }
   else
   {
     [...] Fall 3: Mehr als ein Item drin
   }
   size++;
 }

 public Item extract() {

   if(size==0)  // Fall 4: Nichts drin
     return null;

   Item result;

   if(size==1)
   {
     [...] Fall 5: Ein Item drin
   }
   else if(size==2)
   {
     [...] Fall 6: Zwei Items drin
   }
   else
   {
     [...] Fall 7: Mehr als zwei Items drin
   }

   result.prev = null;
   result.next = null;
   size--;
   return result;
 }
Ich gehe davon aus, dass ein Element nicht auf sich selbst zeigen soll.
 

rydnic

Mitglied
hi,
wie kann ich die klasse testen...das mit dem item bringt mich total durcheinander...wieso kann das nicht einfach ein Object sein?
Wolte hiermit testen, geht aber nicht:
Code:
public class RingTest {

	public static void main(String[] args) {
		Ring erster = new Ring().insert(Irgendetwas);
	}
}

Gibt eclipse eine Fehlermeldung aus(Irgendetwas cannot be resolved) Wie kann ich denn ein Item in den Ring einfügen?Was ist ein Item?
 

semi

Top Contributor
Code:
public class RingTest
{
  public static void main(String args[])
  {
    Ring ring = new Ring();
    ring.insert(new Item());
    ring.insert(new Item());
    ring.insert(new Item());
  
    ring.extract();
    ring.extract();
    ring.extract();
    ring.extract(); // :-)
  }
}

PS: Lauter Sch... Hobbydozenten hier, was? Statt die Lösung zu nennen, quälen wir Dich. :lol:
Es macht aber wenig Sinn eine Lösung zu nennen, ohne das Du sie auch verstehst, daher
die harte Tour. :wink:
 

AlArenal

Top Contributor
Ich würde Item erweitern um

Code:
public void toString() {
  if (data == null) return null;
  return data.toString();
}

Dann kann semis Testcode nämlich umgestellt werden :

Code:
public class RingTest
{
  public static void main(String args[])
  {
    Ring ring = new Ring();
    ring.insert(new Item("eins"));
    ring.insert(new Item("zwei"));
    ring.insert(new Item("drei"));
  
    System.out.println(ring.extract().toString());
    System.out.println(ring.extract().toString());
    System.out.println(ring.extract().toString());
    System.out.println(ring.extract().toString()); // :-)
  }
}

Ansonsten testet man ja im leeren Raum und das bringts nicht wirklich ;)
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
F Datentypen Wertebereiche passender Datentyp Java Basics - Anfänger-Themen 5
K Warum wird mir hier nach dem ersten Durchlauf zwei mal "welchen Datentyp wollen sie übergeben?" ausgegeben ? Java Basics - Anfänger-Themen 1
MiMa Probleme mit Datentyp long ?? Java Basics - Anfänger-Themen 2
D Arraylist mit Komplexen Datentyp Java Basics - Anfänger-Themen 3
Igig1 Welche Werte sind als default Werte in einem Array, der als Datentyp eine Klasse hat? Java Basics - Anfänger-Themen 1
B Datentyp für Einzelnes Objekt oder Liste Java Basics - Anfänger-Themen 9
C initialisieren eines arrays richtiger Größe und mit geeignetem Datentyp Java Basics - Anfänger-Themen 26
H Datentyp mit 3 Zuständen Java Basics - Anfänger-Themen 42
javaluke Erste Schritte Array nach Datentyp sortieren Java Basics - Anfänger-Themen 16
Kanaska Datentyp für Zahlenbereiche Java Basics - Anfänger-Themen 7
A Datentyp char Java Basics - Anfänger-Themen 27
I Klassen als Datentyp nutzen? Java Basics - Anfänger-Themen 11
C unverständlicher Code Attribute ohne Datentyp, wie geht das? Java Basics - Anfänger-Themen 8
T Datentyp mit Anführungszeichen drinnen Java Basics - Anfänger-Themen 3
R Datentypen Datentyp String lenght & charAT Java Basics - Anfänger-Themen 4
M Array mit eigenem Datentyp probleme beim übergeben Java Basics - Anfänger-Themen 6
C Interface als Datentyp eines Attributes? Java Basics - Anfänger-Themen 6
B Datentypen Datentyp welcher den gleichen Namen wie die Klasse trägt? Java Basics - Anfänger-Themen 1
D Datentypen Welcher ist der beste Datentyp? Java Basics - Anfänger-Themen 28
F Datentypen Missverständnis Datentyp Java Basics - Anfänger-Themen 2
D Rechnen mit numerischen Datentyp Frage Java Basics - Anfänger-Themen 16
E Klassename als Datentyp??? Java Basics - Anfänger-Themen 4
F Wertebereich/Datentyp Java Basics - Anfänger-Themen 26
M Datentypen Java Datentyp Definition Java Basics - Anfänger-Themen 6
MiMa Datentyp Short Wert zuweisen über Methode Java Basics - Anfänger-Themen 2
Z Was habe ich davon mit einem Datentyp verschiedene Instanzen zu haben? Java Basics - Anfänger-Themen 6
D Klassen Gesucht: Einfache Beispiel-Klasse für einen Datentyp Java Basics - Anfänger-Themen 7
E Datentypen Benutzerdefinierten Datentyp verwenden Java Basics - Anfänger-Themen 1
ms_cikar Java Datentyp unwandlung Java Basics - Anfänger-Themen 7
G Datentypen Tipps, Ratschläge erwünscht bzgl. Datentyp bestimmen über Wertebereich Java Basics - Anfänger-Themen 5
Y Warum void statt Datentyp + return Java Basics - Anfänger-Themen 4
M Interface als Datentyp Java Basics - Anfänger-Themen 12
R Variablen Datentyp erst während Laufzeit festlegen Java Basics - Anfänger-Themen 6
1 Neuen Datentyp für rationale Zahlen als Klasse entwickeln Java Basics - Anfänger-Themen 20
R Datentypen Datentyp eines Werts in einer Textdateizeile abfragen und ändern Java Basics - Anfänger-Themen 4
R Interface Datentyp bei Erzeugung eines Objekts, dessen Klasse eine Schnittstelle implementiert Java Basics - Anfänger-Themen 18
B Collections Collection soll nur einen bestimmten Datentyp aufnehmen Java Basics - Anfänger-Themen 12
V Datentypen Frage zum Datentyp Byte Java Basics - Anfänger-Themen 11
B datentyp in binär umwandeln Java Basics - Anfänger-Themen 5
S Primitiver Datentyp Short , Vorteil/Nachteil Betrachtung Java Basics - Anfänger-Themen 6
J Field auf Datentyp prüfen Java Basics - Anfänger-Themen 8
D Datentyp Object Java Basics - Anfänger-Themen 2
A Datentypen Mehrdimensionaler Datentyp gesucht Java Basics - Anfänger-Themen 4
D Datentypen Abstrakter Datentyp lässt sich nicht casten Java Basics - Anfänger-Themen 7
F Klassenorganisation: Datentyp in Datentyp anlegen Java Basics - Anfänger-Themen 3
N Unerklärlich: Rekursiver Algorithmus gibt falschen Datentyp zurück... Java Basics - Anfänger-Themen 4
J Datentypen Was ist der Sinn vom Datentyp "char" ? Java Basics - Anfänger-Themen 11
G Eigener Autoboxing Datentyp Java Basics - Anfänger-Themen 3
Binary.Coder Welcher Datentyp für den Simplex Algorithmus Java Basics - Anfänger-Themen 3
Guybrush Threepwood Effizientester Datentyp zur Speicherung einer ungeordneten Menge von ints Java Basics - Anfänger-Themen 8
B Datentyp für +,-,*,/ Java Basics - Anfänger-Themen 5
D Datentypen Rekursiver Datentyp Java Basics - Anfänger-Themen 8
GianaSisters Auf Datentyp überprüfen Java Basics - Anfänger-Themen 13
W Datentypen Operatoren für eigenen Datentyp nutzen Java Basics - Anfänger-Themen 2
M Array mit komplexem Datentyp Java Basics - Anfänger-Themen 9
M 2 Arrays mit komplexen Datentyp vergleichen Java Basics - Anfänger-Themen 8
G Datentypen Welcher Datentyp Java Basics - Anfänger-Themen 2
F Datentypen Welchen Wert hat ein einfacher Datentyp nach der Deklaration? Java Basics - Anfänger-Themen 6
J Datentypen Datentyp für Datum Java Basics - Anfänger-Themen 23
B Java Bean, JSP, Komplexer Datentyp Java Basics - Anfänger-Themen 3
I Datentypen Eigener DatenTyp Java Basics - Anfänger-Themen 2
E Datentyp Array Java Basics - Anfänger-Themen 10
M Datentypen Eigenen Datentyp toArray() Java Basics - Anfänger-Themen 4
A Datentyp Char wird in BlueJ nur als leerer weißer Kasten dargestellt Java Basics - Anfänger-Themen 1
N Frage zu Datentyp byte Java Basics - Anfänger-Themen 14
F Datentyp Number???? Java Basics - Anfänger-Themen 2
A einlesen, schreiben, umwandlung datentyp Java Basics - Anfänger-Themen 10
A Datentyp mit String festlegen? Java Basics - Anfänger-Themen 13
D Generischer Datentyp Java Basics - Anfänger-Themen 2
D Datentyp: Liste von String->Double dingern Java Basics - Anfänger-Themen 4
K Datentyp vs. Datenstruktur - Unterschiede Java Basics - Anfänger-Themen 13
C Datentyp von einer Variablen ermitteln. Java Basics - Anfänger-Themen 12
M Datentyp Parameter Java Basics - Anfänger-Themen 18
R Welchen Datentyp verwenden? Java Basics - Anfänger-Themen 12
B Datentyp anlegen Java Basics - Anfänger-Themen 6
M Eigene Klasse mit "Enumeration"-Datentyp verknüpfe Java Basics - Anfänger-Themen 16
K Datentyp Problem Java Basics - Anfänger-Themen 2
X Rekursion & Generischer Datentyp Java Basics - Anfänger-Themen 11
A neuen Datentyp (Digit) definieren Java Basics - Anfänger-Themen 12
A Datentyp String in char umwandeln Java Basics - Anfänger-Themen 3
J datentyp -objectTyp Rückgabe Java Basics - Anfänger-Themen 2
D Superinterface als Datentyp Java Basics - Anfänger-Themen 5
E Generischer Datentyp und Arrays Java Basics - Anfänger-Themen 3
Z ArrayList<Entry<Datentyp, Integer>> ? Java Basics - Anfänger-Themen 12
L Datentyp Problem Java Basics - Anfänger-Themen 7
F Datentyp eines Inputs überprüfen Java Basics - Anfänger-Themen 2
NightmareVirus Datentyp des Arrayinhalt abfragen Java Basics - Anfänger-Themen 4
S Probleme mit Datentyp beim Einlesen Java Basics - Anfänger-Themen 4
C Datentyp byte Java Basics - Anfänger-Themen 22
G Java Problem [Datentyp] Java Basics - Anfänger-Themen 10
B Datentyp char -> Zeichen um einen Wert erhöhen Java Basics - Anfänger-Themen 12
M long Datentyp effizient mit Daten füllen Java Basics - Anfänger-Themen 2
S Datentyp aus 3 longs Java Basics - Anfänger-Themen 3
M datentyp ausfindig machen Java Basics - Anfänger-Themen 2
C Eigenen Datentyp schreiben Java Basics - Anfänger-Themen 13
T Probleme mit Datentyp Double Java Basics - Anfänger-Themen 4
W Datentyp Zahlen sortieren Java Basics - Anfänger-Themen 12
B Datentyp gesucht Java Basics - Anfänger-Themen 5
J Datentyp einer Klasse bei Anwendung von implements Java Basics - Anfänger-Themen 4
M Linkedlist, wert auf datentyp prüfen Java Basics - Anfänger-Themen 3

Ähnliche Java Themen

Neue Themen


Oben