Links und Funktionen
Sprachumschaltung

Navigationspfad


Inhaltsbereich

LoesungAufgabe8-3

Java source code icon LoesungAufgabe8-3.java — Java source code, 6 KB (6891 bytes)

Dateiinhalt

public class RechteckListe {

   // Instanzvariablen / Attribute
   private RechteckElement first;
   //private RechteckElement last;
   
   /* Falls Sie diese Klasse für Aufgabe 9-1 wiederverwenden wollen,
    * müssen Sie:
    *  - Rechtecke durch Kreise ersetzen
    *  - Anstelle der Klasse Punkt ggf. Point verwenden, da CanvasFrame Klick-Koordinaten als Point liefert
    *  - Ein Attribut "last" einfügen, welches auf das letzte Element der Liste zeigt.
    *    Es empiehlt sich dann, mithilfe einer Methode "addLast" neue Elemente hinten anzuhängen,
    *    und vorne mit der existierenden Methode removeFirst alte Elemente zu entfernen.
    */
   
   // Konstruktoren
   public RechteckListe() {
      first = null;
   }

   public RechteckListe(Rechteck r) {
      first = new RechteckElement(r);
   }
   
   /**
    * Testet ob die Liste leer ist
    * @return true falls die Liste leer ist
    */
   public boolean isEmpty() {
	   return (first == null);
   }
   
   /**
    * Fügt ein Rechteck vorne in die Liste ein
    * 
    * @param r Rechteck, welches zum neuen Kopf der Liste werden soll 
    */
   public void addFirst(Rechteck r) {
	   first = new RechteckElement(r, first);   
   }
   
   /**
    * Entfernt den Kopf der Liste
    * 
    * @return entferntes Rechteck, welches am Kopf der Liste stand
    */
   public Rechteck removeFirst() {
	   Rechteck result = null;
	   if (first == null) {
		   System.out.println("Warnung: removeFirst auf leere Liste angewandt!");
		   // removeFirst liefert in diesem Fall null zurück.
	   } else {
		   // Null-Pointer Exception ist hier ausgeschlossen, da first != null gelten muss.
		   result = first.getValue();
		   first  = first.getNext();
	   }
	   return result;
   }
   
   /**
    * Wie removeFirst(), ohne jedoch das Rechteck aus der Liste zu enternen
    *  
    * @return Rechteck, welches momentan am Kopf der Liste steht
    */
   public Rechteck readFirst() {
	   Rechteck result = null;
	   if (first == null) {
		   System.out.println("Warnung: readFirst auf leere Liste angewandt!");
		   // readFirst liefert in diesem Fall null zurück.
	   } else {
		   // Null-Pointer Exception ist hier ausgeschlossen, da first != null gelten muss.
		   result = first.getValue();
	   }
	   return result;
   }
   
   /**
    * Hängt eine gegebene Liste von Elementen hinten an
    * 
    * @param l 
    *    Liste, welche hinten angehängt werden soll
    */
   public void append(RechteckListe l) {
	   if (first == null) {
		   first = l.first;
	   } else {
		   RechteckElement next = first;
		   while (next.getNext() != null) {
			   next = next.getNext();
		   }
		   next.setNext(l.first);
	   }
   }
   
   /**
    * Dreht die Reihenfolge der list um.
    */
   public void reverse() {
	   RechteckElement last = null;
	   RechteckElement current = first;
	   while (current != null) {
		   RechteckElement next = current.getNext();
		   current.setNext(last);
		   last = current;
		   current = next;
	   }
	   first = last;
   }
   
   /**
    * Fügt das Rechteck vor das erste größere Rechteck in die Liste ein
    * 
    * @param r Rechteck, welches geordnet eingefügt werden soll.
    */
   public void insert(Rechteck r) {
	   if (first == null || r.isSmaller(first.getValue())) {
		   this.addFirst(r);
	   } else {
		   first.insertAfter(r);
	   }
   }
   
   /** 
    * Sortiert die Liste der Größe nach, wobei das kleinste Rechteck am Anfang steht.
    */
   public void sort() {
	   // Hier gibt es gleich zwei Varianten der Sortierung als Musterlösung,
	   // welche zur leichteren Unterscheidung in zwei Methoden aufgeteilt wurden.
	   this.quickSort();
	   //this.insertSort();
   }
   
   /**
    * Sortiert die Liste nach dem Insertion Sort Verfahren.
    * Diese Lösungsmöglichkeit bot sich insbesondere deshalb an,
    * da die bereitgestellte Klasse RechteckListe bereits eine
    * Methode zum Einfügen (siehe "insert" weiter oben) anbot.
    * 
    * Somit war der Aufwand recht gering, aber es ging in dieser Aufgabe
    * ja auch nicht um das Sortieren selbst, sondern um den Umgang mit Klassen -
    * insbesondere auch das Lesen von Klassendefinitionen. ;)
    *
    * @author jost
    */
   public void insertSort() {
	   // Neue, leere Liste generieren.
	   RechteckListe sorted = new RechteckListe();
	   //Zeiger anlegen, welcher beim ersten Element der unsortierten Liste started.
	   RechteckElement current = first;
	   while (current != null) {
		   //Eins nach dem anderen wird nun jedes Element der unsortierten List in die sortierte eingefügt.
		   sorted.insert(current.getValue());
		   current = current.getNext();
	   }
	   // Jetzt ersetzen wir den Zeiger auf die unsortierte Liste durch die sortierte.
	   first = sorted.first;
	   /*
	    *  Man beachte: 
	    *  Das RechteckListe Objekt bleibt unverändert, 
	    *  genauso bleiben die Rechteck Objekte unverändert.
	    *  
	    *  Die RechteckElement Objekte werden dagegen alle ausgetauscht!
	    *  Vor der Zuweisung "first=sorted.first" existiert daher 
	    *  die sortierte Liste und auch die originale unsortierte Liste gleichzeitig. 
	    */
   }
   
   /**
    *  Ein klein wenig aufwändiger (im Sinne von mehr Code), 
    *  aber vielleicht leichter (im Sinne von Verstehen),
    *  ist eventuell das Quicksort-Verfahren:
    *  Dabei wählen wir einfach das erste Element als Pivot aus
    *  und teilen die Liste auf und sortieren rekursiv weiter.
    *  
    *  Auch hierfür kommt uns der bereitgestellte Code entgegen,
    *  da die Klasse bereits eine Methode zum Anhängen einer anderen Liste enthält.
    *
    * @author jost
    */
   public void quickSort() {
	   if (first != null) {	
		   // Wir erstellen zwei neue leere Listen: Die kleineren Rechtecke.und die größeren Rechtecke. 
		   RechteckListe smaller = new RechteckListe();
		   RechteckListe bigger  = new RechteckListe();
		   // Das erste Element wird als Pivot gewählt.
		   Rechteck pivot = first.getValue();
		   // Wir erstellen einen Zeiger zum durchlaufen der aktuellen Liste
		   RechteckElement current = first.getNext();
		   while (current != null) {
			   Rechteck r = current.getValue(); 
			   // Je nach Größe werden die Rechtecke aufgeteilt
			   if (r.isSmaller(pivot)) {
				   smaller.addFirst(r);
			   } else {
				   bigger.addFirst(r);
			   }
			   current = current.getNext();
		   }
		   // Nun sortieren wir einfach _rekursiv_ die beiden Teillisten
		   bigger.quickSort();
		   smaller.quickSort();
		   // Jetzt hängen wir die beiden sortierten Listen aneinander an, das Pivot kommt in die Mitte (also als erstes Element vor den größeren).
		   bigger.addFirst(pivot);
		   smaller.append(bigger);
		   // Jetzt ersetzen wir den Zeiger auf die unsortierte Liste durch einen, der auf die vollständig sortierte Liste zeigt.
		   first = smaller.first;
	   }
   }  
}

Artikelaktionen


Funktionsleiste