Entwerfen und Implementieren Sie einen abstrakten Datentyp Queue

Schwierigkeit 1

Eine Queue oder auch Warteschlange genannt ist eine öfter in der Informatik vorkommende Datenstruktur. Es lassen sich Werte (int) zu einer Queue hinzufügen und wieder entfernen. Es werden immer die zuerst hinzugefügten Werte entfernt. Dieses Verwaltungsprinzip nennt man deswegen auch first-in-first-out (FIFO). Eine Warteschlange kann zum Beispiel bei der Prozessumschaltung in einem Betriebssystem verwendet werden: der zuerst hinzugefügte - wartende - Prozess, bekommt als nächstes wieder Prozessorzeit zugeordnet: vor allen nach ihm hinzugefügten Prozessen.

Entwerfen Sie ein Interface Queue, mit denen Werte hinzugefügt und wieder weggenommen werden können. Ebenso soll eine Methode existieren, die überprüft, ob die Queue leer ist oder nicht.

Implementieren Sie diese Queue mit einem Feld. Wenn mehr Werte als das Feld fassen kann hinzugefügt werden, dann soll das Feld dieser Queue-Implementierung automatisch vergrössert werden: es kann zum Beispiel durch ein doppelt so grosses Feld ersetzt werden.

Testen Sie Ihre Implementierung ausgiebig. Insbesondere mit anfangs kleinen Felder und mehreren Hinzufüge- und Wegnahme-Operationen.

Lösung

Vergleichen von chemischen Elementen mit den abstrakten Datentypen Comparable und Comparator

Für diese Aufgabe sollten sie vorher chemische Elemente entworfen und implementiert haben.

Schwierigkeit 2

Das Java Collection Framework kennt zwei abstrakte Datentypen, um festzustellen ob ein Objekt grösser, gleich oder kleiner als ein anderes ist: Comparable und Comparator. Comparable wird immer von der Klasse des Objekts selbst implementiert. Es stellt somit eine kanonische Ordnung dieser Elemente dar. Darüberhinaus könnte ein Objekt allerdings auch noch nach anderen Kriterien geordnet werden. In diesem Fall wird jeweils eine neue Klasse programmiert, die Comparator implementiert.

Comparable definiert eine Methode int compareTo(Object o): Sie gibt 0 zurück, wenn das Objekt o dem Objekt gleicht, bei dem die Methode aufgerufen wurde; ein negativer Wert, wenn o kleiner ist; ein positiver Wert, wenn o grösser ist. Darüberhinaus müssen noch weitere Eigenschaften gelten. Lesen Sie sich bitte dazu den Javadoc-Kommentar von Comparable genau durch. String zum Beispiel implementiert Comparable.

Comparator definiert eine Methode int compareTo(Object o1, Object o2). Sie hat praktisch das gleiche Verhalten wie bei Comparable - der erste Parameter stellt lediglich das erste zu vergleichende Objekt dar.

Zum Beispiel könnten die "normale" Ordnung bei Personen die lexikographische Ordnung von Nach- gefolgt von Vorname sein. "Christian Pape" ist dann kleiner als "Max Zorn" (da "P" < "Z"). Eine Softwareanwendung könnte Personen aber vielleicht auch nach Geburtstagen chronologisch ordnen wollen. Dazu müsste dann eine separate Klasse PersonGeburtstagsComparator implementiert werden.

Chemische Elemente werden bei Strukturformeln (H2O, NaCl) aufsteigend nach ihrer Elektronegativität sortiert. Implementieren Sie diese Ordnung jeweils als Comparable beim chemischen Element und einmal als Comparator.

Testen Sie Ihre Implementierung auch mit Arrays.sort(), um eine Feld von chemischen Elementen zu sortieren.

Eine andere Anordnung chemische Elemente ist das Hill-System:

Also ClNa statt NaCl.

Achten Sie darauf, dass Gross- und Kleinschreibung ignoriert wird. Sehen Sie sich dazu Methoden von String genauer an. Kann diese Ordnung als Comparable oder Comparator zweier chemischen Elemente implementiert werden, um zum Beispiel ein Feld mit chemischen Elementen entsprechend zu sortieren?

Lösung Comparator und Lösung Comparable

Implementieren Sie einen abstrakten Datentyp für komplexe Zahlen

Schwierigkeit 2

Eine komplexe Zahl ist durch einen Realteil a und Imaginärteil b gegeben. Komplexe Zahlen werden meist in der Form a + i*b angegeben. i ist eine imaginäre Zahl mit i2 := -1.

Mit komplexen Zahlen lassen sich für alle reelwertigen Polynome Nullstellen finden. Zum Beispiel ist i (= 0 + i*1) und -i Nullstelle von x2+1.

Das Symbol + verhält sich wie eine normale Addition: es ist streng genommen aber nur ein Trennsymbol, kein Operator. Zwei komplexe Zahlen a1 + ib1 und a2 + ib2 werden wie folgt addiert und multipliziert:

Implementieren Sie diesen abstrakten Datentyp für komplexe Zahlen (UTF-8): 

public interface KomplexeZahl {

	public double getRealteil();
	
	public double getImaginaerteil();

	public KomplexeZahl addieren(KomplexeZahl zahl);

	public KomplexeZahl multiplizieren(KomplexeZahl zahl);
}

Lesen Sie sich vorher genau die Javadoc der Datei durch.

Lösung

Implementieren Sie einen abstrakten Datentyp für kartesische Koordinaten

Schwierigkeit 3

Implementieren Sie diesen abstrakten Datentyp eines Punktes (x, y) im zwei-dimensionalen Raum mit kartesischen Koordinaten. Ihre Implementierung muß einen Konstruktor besitzen, mit dem ein Punkt (x, y) erzeugt werden kann.

Der euklidische Abstand zweier Punkte (x1, y1) und (x2, y2) ist definiert als die Quadrtwurzel von (x1 − x2)2 + (y1 − y2)2.

Hinweis: Math.sqrt(double) berechnet die Quadratwurzel eines double-Wertes.

Lösung

Implementieren Sie einen abstrakten Datentyp für beliebig große Dezimalzahlen

Geben sei ein abstrakter Datentyp Dezimalzahl.java mit dem beliebig große Dezimalzahlen repräsentiert werden können (nur ganze positive Zahlen). Dieser hat unter anderem Methoden zum Addieren und Multiplizieren.

Implementieren Sie diesen abstrakten Datentyp mit Hilfe eines Feldes. Nehmen Sie zur Vereinfachung eine feste Feldlänge etwa 1000 an.

Lösung