# Datentyp Ring - zyklisch doppelt verkettete Liste - HILFE!



## rydnic (19. Jan 2006)

Hallo  ,

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. 



```
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:


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


----------



## AlArenal (19. Jan 2006)

Wo ist jetzt genau das Problem? Eigentlich ist ja fast alles gegeben....


----------



## rydnic (19. Jan 2006)

ja fast bis auf [...] 
weiß einfach nicht wie ich das insert und extract implementieren soll


----------



## Guest (19. Jan 2006)

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:


```
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:


```
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 (19. Jan 2006)

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 (19. Jan 2006)

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


----------



## Guest (19. Jan 2006)

@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 (19. Jan 2006)

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.


```
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 (19. Jan 2006)

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 (19. Jan 2006)

```
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 (19. Jan 2006)

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:

```
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 (19. Jan 2006)

```
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 (19. Jan 2006)

Ich würde Item erweitern um


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

Dann kann semis Testcode nämlich umgestellt werden :


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


----------

