Verkettete Listen "dynamisch" verschachteln

[sunny]

Hallo!

Erstmal wünsch ich euch allen ein gute neues Jahr! :-)

Zu meinem Problem: Bin Java-Anfänger und stehe gerade vor einem Problem, bin nicht ganz sicher, ob ich überhaupt richtig begonnen habe.

Es geht darum, dass (einfach) verkettete Listen erstellt werden sollen. In meinem Fall heißt die erste Liste "Bags". Dieser Liste werden dann Objekte "zugefügt", die wieder Listen enthalten. In meinem Fall heißen diese dann zB immer "BagWithPresents" (da hier "Geschenke eingepackt" werden sollen).

Jetzt habe ich das Ganze zuerst einmal irgendwie testen wollen (ob das mit den Listen überhaupt funktioniert) und hab das so gemacht:

  
 BagList Bags = new BagList();  
  
 Bag BagWithPresents1 = new Bag(capacityOfBags);  
 Bag BagWithPresents2 = new Bag(capacityOfBags);  
  
 Bags.add(BagWithPresents1);  
 Bags.add(BagWithPresents2);  
  
 BagWithPresents1.add(new Present(10));  
 BagWithPresents2.add(new Present(10));  
 BagWithPresents2.add(new Present(20));  
 BagWithPresents2.add(new Present(30));  
 BagWithPresents1.add(new Present(50));  

Das scheint soweit auch zu funktioneren wenn ich mir die "Ergebnisse" auf der Konsole ausgeben lasse (habe für Testzwecke eine print-Methode der beiden Listen erstellt). Allerdings hab ich keine Idee, wie ich das Ganze "dynamisch" machen könnte. Denn eigentlich weiß ich nicht, wieviele Bags ich brauchen werde, und natürlich auch nicht, wieviele Objekte der zweiten Liste (BagWithPresents) dann zugefügt werden. Wie kann man so etwas lösen? Eigentlich geht es darum, dass hier dann ein best-fit-Algorithmus erstellt werden soll (die "BagWithPresents" haben nur eine begrenzte Kapazität (jeder dieselbe) und die "Present"s unterschiedliche Gewichte) ...

Am Ende soll es also eine BagList-Liste "Bags" geben, die beliebig viele "BagWithPresents" enthält, und diese einzelnen "BagWithPresents" sollen dann beliebig viele "Present"s enthalten. Wieviele "Present"s das sind, kommt aus einer User-Eingabe, wieviele "Bags" benötigt werden kann ebenfalls erst zur Laufzeit (durch den Algorithmus für das Verteilen) festgelegt werden, das mit der Numerierung war also fürs Testen zwar noch irgendwie möglich, führt aber natürlich nicht zu einer Lösung. Wie kann ich so etwas "richtig" machen? Sodass die Objekte sozusagen "dynamisch" erstellt werden?

Liebe Grüße
sunny

[Biesterfeld]

Hej,

Am Ende soll es also eine BagList-Liste "Bags" geben, die beliebig viele "BagWithPresents" enthält, und diese einzelnen "BagWithPresents" sollen dann beliebig viele "Present"s enthalten. Wieviele "Present"s das sind, kommt aus einer User-Eingabe, wieviele "Bags" benötigt werden kann ebenfalls erst zur Laufzeit (durch den Algorithmus für das Verteilen) festgelegt werden, das mit der Numerierung war also fürs Testen zwar noch irgendwie möglich, führt aber natürlich nicht zu einer Lösung. Wie kann ich so etwas "richtig" machen? Sodass die Objekte sozusagen "dynamisch" erstellt werden?

Du erläuterst dein Problem leider nicht so, dass ich es verstehen würde und den relevante Code, nämlich die Implementierung von BagList und Bag verheimlichst du aber. Ich vermute jetzt mal einfach, dass BagList nichts anderes als ein Wrapper für ein Bag[]-Array und Bag ein Wrapper für ein Present[]-Array sind. Und ich vermute, dass dein Problem die feste Größe der primitiven Java-Arrays sind, richtig?

Kennst du [link:http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html@title=java.util.LinkedList] und [link:http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html@title=java.util.ArrayList]? Helfen dir diese beide Klassen dein Problem zu lösen? Vieleicht möchtest du dich allgemein erstmal etwas zu den verschiedenen Algorithmen und Datenstrukturen, die in Java bereits implementiert sind belesen:

http://www.galileocomputing.de/openbook/javainsel6/javainsel_11_001.htm
http://java.sun.com/javase/6/docs/technotes/guides/collections/index.html

Andererseits, könntest du natürlich auch (wenn also die Kapazität der Arrays tatsächlich dein Problem ist) auch selber eine ähnliche Implementierung wie die Standard-Java-Datenstrukturen vornehmen.

* Starte mit einer initialen Kapazität,
* Prüfe bei jedem add() ob die aktuelle Kapazität überschritten wird,
* falls ja, leg ein neues Array mit größerer Kapazität an,
* kopiere das alte Array in das neue mittels [link:http://java.sun.com/javase/6/docs/api/java/lang/System.html#arraycopy(java.lang.Object,%20int,%20java.lang.Object,%20int,%20int)@title=java.util.System.arraycopy()]

Ansonsten noch eine kurze Anmerkung:

  

>  BagList Bags = new BagList();  
>  // Variablen-Bezeichner bitte immer klein schreiben  
>   
>  Bags.add(BagWithPresents2);  
>  // da dies sonst wie ein statischer Aufruf der add() Methode einer Bags-Klasse aussieht  
> // [...]  

Beste Grüße
Biesterfeld

[sunny]

Hallo!

Vielen Dank erstmal für Deine ausführliche Antwort!

Am Ende soll es also eine BagList-Liste "Bags" geben, die beliebig viele "BagWithPresents" enthält, und diese einzelnen "BagWithPresents" sollen dann beliebig viele "Present"s enthalten. Wieviele "Present"s das sind, kommt aus einer User-Eingabe, wieviele "Bags" benötigt werden kann ebenfalls erst zur Laufzeit (durch den Algorithmus für das Verteilen) festgelegt werden, das mit der Numerierung war also fürs Testen zwar noch irgendwie möglich, führt aber natürlich nicht zu einer Lösung. Wie kann ich so etwas "richtig" machen? Sodass die Objekte sozusagen "dynamisch" erstellt werden?

Du erläuterst dein Problem leider nicht so, dass ich es verstehen würde und den relevante Code, nämlich die Implementierung von BagList und Bag verheimlichst du aber.

Nur deswegen, weil mein Problem nicht in der Implementierung der Listen an sich liegt, sondern im "dynamischen" umgehen mit den Listen ... weil ich eben in Java Anfänger bin, wusste ich nicht so recht, wie ich hier dynamisch mehrere Objekte erstellen soll, die ich später auch wieder ansprechen kann (mit Arrays wäre dies für mich klar gewesen, einfach über die Indizes).

Ich vermute jetzt mal einfach, dass BagList nichts anderes als ein Wrapper für ein Bag[]-Array und Bag ein Wrapper für ein Present[]-Array sind. Und ich vermute, dass dein Problem die feste Größe der primitiven Java-Arrays sind, richtig?

Nein, das stimmt nicht. Arrays kommen darin gar nicht vor, es handelt sich lediglich um die Implementierung von einfach verketteten Listen, mit einer add-Methode (sodass Objekte zur Liste hinzugefügt werden können), einer print-Methode für Testzwecke usw.

Auszug aus der BagList-Klasse (vielleicht wird es dann verständlicher was ich da fabriziere):

  
 public Bag begin; //First bag in list  
 public Bag end; //Last bag in list  
  
 //Method to add present in bag  
 public void add(Bag obj) {  
  
  //Instance new element in queue  
  Bag newBag = new Bag(obj);  
  
  //If it's the first present in bag, set new element as first element  
  if (begin == null && end == null) {  
   begin = newBag;  
  }  
  //If it's the second present in bag, set new element as last element  
  else if (begin != null && end == null) {  
   begin.next = newBag;  
   end = begin.next;  
  }  
  //Else set present as last element  
  else {  
   end.next = newBag;  
   end = end.next;  
  }  
 }  
  

Kennst du [link:http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html@title=java.util.LinkedList] und [link:http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html@title=java.util.ArrayList]?

Kenne ich, darf ich aber nicht verwenden. Wir müssen die Liste selber implementieren und dürfen keine solchen Strukturen verwenden.

Helfen dir diese beide Klassen dein Problem zu lösen?

Nein, aber mittlerweile bin ich selber schon einen Schritt weitergekommen. Ich muss in meine Liste ja "nur" eine weitere Methode implementieren, die mir das benötigte Objekt (den Bag) zurückliefert, sodass ich dann dort wieder (Unter-)Objekte (die Presents) einfügen kann (mit meiner "add"-Methode). So müsste ich auf meine Bags zugreifen können und somit sollte es auch möglich sein, den best-fit-Algorithmus zu implementieren. Ich weiß, die Frage war fast außerordentlich blöd, aber wenn man mit einer Sprache neu anfängt, so verstrickt man sich oft selber in irgendwelche falschen "alten" Denkweisen aus bereits bekannteren Dingen ... und ist dann völlig verwirrt. Von Objektorientierung hab ich nämlich eigentlich keinen Plan und daher fällt mir das alles im Moment ein wenig schwer.

Vieleicht möchtest du dich allgemein erstmal etwas zu den verschiedenen Algorithmen und Datenstrukturen, die in Java bereits implementiert sind belesen:

http://www.galileocomputing.de/openbook/javainsel6/javainsel_11_001.htm
http://java.sun.com/javase/6/docs/technotes/guides/collections/index.html

Ja genau die darf ich ja nicht verwenden ... *grummel*.
Btw, oberen Link ("Java ist auch eine Insel") hab ich ohnehin andauernd in Verwendung, mittlerweile sogar so oft, dass ich mir jetzt zusätzlich die Buch-Version bestellt habe, ich glaube damit kann man echt gut lernen, gefällt mir gut.

Andererseits, könntest du natürlich auch (wenn also die Kapazität der Arrays tatsächlich dein Problem ist) auch selber eine ähnliche Implementierung wie die Standard-Java-Datenstrukturen vornehmen.

* Starte mit einer initialen Kapazität,
* Prüfe bei jedem add() ob die aktuelle Kapazität überschritten wird,
* falls ja, leg ein neues Array mit größerer Kapazität an,
* kopiere das alte Array in das neue mittels [link:http://java.sun.com/javase/6/docs/api/java/lang/System.html#arraycopy(java.lang.Object,%20int,%20java.lang.Object,%20int,%20int)@title=java.util.System.arraycopy()]

Ja, naja, das kommt nicht ganz hin, aber so etwas Ähnliches: Erstelle einen Bag und füge ihn der Liste hinzu, nimm das erste Present und stecke es in den Bag. Wenn das zweite Present noch hineinpasst, packe es dazu, ansonsten mache einen neuen Bag und stecke es dort hinein. Dann nimm das nächste Geschenk, prüfe die bereits vorhandenen Bags und packe das Present in den Bag, in welchen es am besten hineinpasst (wo die Differenz zwischen dem Maximalgewicht des Bags und dem aktuellen Gewicht nach zufügen des Presents am geringsten ist). So jedenfalls glaube ich, dass der best-fit-Algorithmus funktionieren soll, aber das muss ich mir erst ansehen, wenn der "Zugriff" auf die einzelnen Bags erstmal funktioniert, ich mach das immer so Schritt für Schritt.

Bevor ich also wirklich zum Implementieren des best-fit-Algorithmus komme, muss ich erst noch so eine "getBag"-Methode irgendwie hinbekommen (die mir den später den "besten" Bag liefern soll), ich denke so könnte das Ganze funktionieren ... da bin ich jetzt gerade dabei.

Ansonsten noch eine kurze Anmerkung:

BagList Bags = new BagList();
// Variablen-Bezeichner bitte immer klein schreiben

Bags.add(BagWithPresents2);
// da dies sonst wie ein statischer Aufruf der add() Methode einer Bags-Klasse aussieht
// [...]

  
Du hast Recht. Mach ich immer, aber komischerweise nicht bei Objekten. Werde das beheben. Danke!  
  
Liebe Grüße  
sunny

[Blaubart]

Tach.

das mit der Numerierung war also fürs Testen zwar noch irgendwie möglich, führt aber natürlich nicht zu einer Lösung. Wie kann ich so etwas "richtig" machen? Sodass die Objekte sozusagen "dynamisch" erstellt werden?

Da jedes bereits vorhandene BagWithPresents in deiner BagList hängt, mußt du dich Element für Element durch diese Liste hangeln, um bei jedem BagWithPresents vorbeizukommen, wenn du dort Geschenke reinpacken möchtest o. ä. Bei einfach verketteten Listen ist das auch gar nicht anders möglich.

Wenn dein Best-Fit-Algorithmus nach einem weiteren Sack für Geschenke verlangt, erzeugst du dir ein neues Objekt BagWithPresents und hängst es in die Liste – an welcher Stelle du das machst (Anfang, Ende, irgendwo mittendrin), ist deine Entscheidung. Die Referenz auf dieses neue Objekt brauchst du nicht extra außerhalb deiner Liste in einer Variablen zu speichern, da du das ja bereits in deiner BagList tust.

[Blaubart]

Übrigens ...

BagWithPresents1.add(new Present(10));

Hier machst du doch mit einem Present bereits erfolgreich das, was bei BagWithPresents scheinbar ein Problem darstellt.

[sunny]

Hallo!

das mit der Numerierung war also fürs Testen zwar noch irgendwie möglich, führt aber natürlich nicht zu einer Lösung. Wie kann ich so etwas "richtig" machen? Sodass die Objekte sozusagen "dynamisch" erstellt werden?

Da jedes bereits vorhandene BagWithPresents in deiner BagList hängt, mußt du dich Element für Element durch diese Liste hangeln, um bei jedem BagWithPresents vorbeizukommen, wenn du dort Geschenke reinpacken möchtest o. ä. Bei einfach verketteten Listen ist das auch gar nicht anders möglich.

Ja, genau das versuche ich seit einiger Zeit auch ...

Wenn dein Best-Fit-Algorithmus nach einem weiteren Sack für Geschenke verlangt, erzeugst du dir ein neues Objekt BagWithPresents und hängst es in die Liste – an welcher Stelle du das machst (Anfang, Ende, irgendwo mittendrin), ist deine Entscheidung. Die Referenz auf dieses neue Objekt brauchst du nicht extra außerhalb deiner Liste in einer Variablen zu speichern, da du das ja bereits in deiner BagList tust.

In diesem Fall natürlich nicht. Aber in dem Fall dass das Present in einen bereits vorhandenen Bag eingefügt werden soll, der ja irgendwo in der Liste liegen kann.

Dafür wollte ich eine Methode "bauen", die mir später immer die Referenz auf den passenden Bag liefern soll.

Diese Methode sieht bei mir im Moment (für Testzwecke) einfach so aus:

  
public Bag getBestBag(int actWeight, int capacityOfBags) {  
  
 Bag actBag = begin;  
  
 if (actBag == null) {  
  Bag newBag = new Bag(capacityOfBags);  
  return newBag;  
 }  
  
 while (actBag != null) {  
  
  if (actBag.getActWeight() <= 30) {  
   return actBag;  
  }  
  actBag = actBag.next;  
 }  
  
 Bag newBag = new Bag(capacityOfBags);  
 return newBag;  
}  

Zum Testen hab ich einfach mal gesagt, solang der aktuelle Bag noch weniger als 30 wiegt, gib einfach den aktuellen zurück, wenn nicht dann erstelle einen neuen. Ich weiß das ist gerade ein wenig gemurkst, aber ist momentan ja nur Herumgeteste.

Aufgerufen wird das Ganze hier (auch Testcode):

  
 BagList bags = new BagList();  
  
 for (int i = 0; i < weightOfPresent.length; i++) {  
  
  System.out.println("\n" + (i+1) + ". DURCHLAUF");  
  
  Bag bestBag = bags.getBestBag(weightOfPresent[i],capacityOfBags);  
  
  if (bestBag.getActWeight() == 0) {  
   bags.add(bestBag);  
  }  
  
  bestBag.add(new Present(weightOfPresent[i]));  
  System.out.println("Bag " + bestBag + " wiegt jetzt " + bestBag.getActWeight());  
 }  
 bags.print();  

Sprich, wenn der zurückgegebene Bag ein Gewicht von 0 hat (also ein neu erstellter ist), dann soll dieser der BagList hinzugefügt werden.
Und da hab ich jetzt wieder "Pfusch". Die Methode, die das hinzufügen ermöglicht:

  
 public void add(Bag obj) {  
  
  Bag newBag = new Bag(obj);  
  
  if (begin == null && end == null) {  
   begin = newBag;  
  }  
  else if (begin != null && end == null) {  
   begin.next = newBag;  
   end = begin.next;  
  }  
  else {  
   end.next = newBag;  
   end = end.next;  
  }  
 }  

Da wird zwar die Objektreferenz übergeben, aber dann ja für die Liste ein neues Objekt erzeugt, deswegen funktioniert das Ganze nicht, das erste Element beim ersten Aufruf ist nicht dasselbe ... Deswegen wollte ich das Ganze nun so abändern, dass hier kein neues Objekt erzeugt wird, sondern als begin direkt das übergebene Objekt gesetzt wird.

Aber dann funktioniert meine Print-Methode nicht mehr:

  
 public void print() {  
  
  Bag actBag = begin;  
  int i = 1;  
  
  while (actBag != null) {  
      System.out.println("Bag " + i + " with " + actBag.element.getActWeight() + " gramm. (" + actBag + ")");  
      actBag = actBag.next;  
      i++;  
     }  
 }  

... weil hier dann eine NullPointerException auftritt, auch wenn auf actBag.next != null geprüft wird ... schön langsam bin ich nur mehr verwirrt, kann mir irgendjemand aus diesem Wirrwar heraushelfen? Wie löst man denn sowas, das ist doch eigentlich alles ganz einfach!? Ohweh ...

Lg,
sunny

[sunny]

Also ich glaube, jetzt funktioniert jedenfalls mal der Testlauf (noch ohne best-fit) ...

  

>  public void add(Bag obj) {  
>   
>   Bag newBag = new Bag(obj);  

------------------^  
Hier hab ich nun direkt das Objekt zugewiesen, wie im vorigen Posting geschrieben ...  
  

>   if (begin == null && end == null) {  
>    begin = newBag;  
>   }  
>   else if (begin != null && end == null) {  
>    begin.next = newBag;  
>    end = begin.next;  
>   }  
>   else {  
>    end.next = newBag;  
>    end = end.next;  
>   }  
>  }  

  

>  public void print() {  
>   
>   Bag actBag = begin;  
>   int i = 1;  
>   
>   while (actBag != null) {  
>       System.out.println("Bag " + i + " with " + actBag.element.getActWeight() + " gramm. (" + actBag + ")");  

-----------------------------------------------------------^  
wo auch immer das herkommt, das element muss weg ... verhaspelt ...  
  

>       actBag = actBag.next;  
>       i++;  
>      }  
>  }  

Bin mir zwar noch nicht wirklich sicher, was für einen Blödsinn ich da sonst noch so zusammengefuselt habe, aber jetzt funktioniert zumindest endlich "irgendwas" ... *jetztallesnochmalinRuheanschau*

Lg
sunny