SortedList.java
SortedList.java — 20.1 KB
Dateiinhalt
import java.util.Arrays; /** * Implementiert den abtrakten Datentyp der sortierten, einfach verketteten * Liste ganzzahliger Werte */ public class SortedList { /** * Eine Exception für undefinierte Werte (z.B. bei Zugriff auf die leere * Liste) */ public static class UndefinedValueException extends Exception { public UndefinedValueException() { } } /** * Ein Knoten für eine einfach verkettete Liste ganzzahliger Werte */ public static class ListNode { // der Wert dieses Knotens public int value; // Zeiger auf den Nachfolger public ListNode next; public ListNode(int value) { this.value = value; } /** * Gibt zurück, ob es einen nachfolgenden Knoten gibt. * * @return true, falls es einen nachfolgenden Knoten gibt. */ public boolean hasNext() { return this.next != null; } @Override public String toString() { return String.format("%3d ", this.value); } } // der erste Knoten der sortierten Liste private ListNode headNode; public SortedList() { this.headNode = null; } /** * Konstruktor, der anhand eines Arrays die sortierte Liste erstellt. * * @param values * Array, aus dem die sortierte Liste erstellt werden soll */ public SortedList(int[] values) { this(); insertAll(values); } /** * Fügt alle Werte des Arrays in die Liste ein. * * @param values * Array, dessen Werte in die Liste eingefügt werden sollen */ public void insertAll(int[] values) { for (int value : values) { insert(value); } } /** * Gibt zurück, ob die Liste leer ist. * * @return true, falls die Liste leer ist */ public boolean isEmpty() { return this.headNode == null; } /** * Erstellt einen neuen Knoten mit Wert value und fügt ihn so in die Liste * ein, dass die Sortierung erhalten bleibt. Duplikate können also direkt vor * oder nach einem beliebigen Knoten mit identischem Wert eingefügt werden. * * @param value * der in die Liste einzufügende Wert */ public void insert(int value) { // TODO Code hier einfügen } /** * Entfernt den ersten Knoten (headNode) aus der sortierten Liste und liefert * dessen Wert zurück. Der Wert entspricht also dem Minimum der Liste. Falls * die Liste leer ist, soll stattdessen eine UndefinedValueException geworfen * werden. Der headNode wird auf den Nachfolger des entfernten Knotens * gesetzt. * * @return der Wert des ersten Knotens der Liste * * @throws UndefinedValueException * Es wird diese Exception geworfen, falls die Liste leer ist. * */ public int removeFirst() throws UndefinedValueException { // TODO Code hier einfügen throw new UndefinedValueException(); } /** * Gibt die Länge der Liste zurück oder 0, falls die Liste leer ist. Um die * volle Punkzahl zu erhalten, soll die Laufzeit Ihrer Lösung in O(1) liegen. * * @return Länge der Liste oder 0, falls die Liste leer ist */ public int getLength() { // TODO Code hier einfügen return 0; } /** * Gibt den k-größten Wert der Liste zurück (ohne ihn zu entfernen), falls er * existiert und die Liste nicht leer ist. Ansonsten wird eine * UndefinedValueException geworfen. Die Indexierung beginnt bei 1 und das * k-größte Element ist das (n-k)-te Element der sortierten Liste. * Beispielsweise ist der Wert 4 in der Liste [0,1,1,4,4,6] sowohl das zweit- * als auch das drittgrößte Element. * * @param k * Der k-größte Wert, beginnend bei 1 * @return der k-größte Wert der Liste oder UndefinedValueException, falls der * Wert nicht existiert * * @throws UndefinedValueException * Es wird diese Exception geworfen, falls der k-größte Wert nicht * existiert oder die Liste leer ist. */ public int getKLargest(int k) throws UndefinedValueException { // TODO Code hier einfügen throw new UndefinedValueException(); } /** * Gibt den Median der Liste zurück (ohne ihn zu entfernen). Falls die Anzahl * der Knoten in der Liste ungerade ist, so ist der Median definiert als der * Wert des Knotens, der an mittlerer Stelle steht. Wenn die Liste hingegen * eine gerade Anzahl von Knoten enthält, ist der Median der Wert des rechten * der beiden mittleren Knoten. Für eine leere Liste soll die * Methode eine UndefinedValueException werfen. * * @return der Median der Liste * * @throws UndefinedValueException * Es wird diese Exception geworfen, falls die Liste leer ist. */ public double getMedian() throws UndefinedValueException { // TODO Code hier einfügen throw new UndefinedValueException(); } /** * Fügt alle Knoten der übergebenen Liste otherSortedList sortiert in die * Liste ein. Die übergebene Liste otherSortedList darf dabei beliebig * verändert werden. Um die volle Punkzahl zu erhalten, soll die Laufzeit * Ihrer Lösung in O(m+n) liegen, wobei m und n die Längen der beiden Listen * sind. * * @param otherSortedList * die übergebene Liste, die in diese Liste eingefügt werden soll */ public void merge(SortedList otherSortedList) { // TODO Code hier einfügen } /** * Hilfsmethode, die zurückgibt, ob die beiden Listen identisch sind. */ @Override public boolean equals(Object obj) { SortedList s2 = (SortedList) obj; if ((this.isEmpty()) != (s2.isEmpty())) { return false; } ListNode head1 = this.headNode; ListNode head2 = s2.headNode; while (head1 != null && head2 != null) { if (head1.value != head2.value) { return false; } if (head1.hasNext() != head2.hasNext()) { return false; } if (head1.hasNext()) { head1 = head1.next; } else { break; } if (head2.hasNext()) { head2 = head2.next; } else { break; } } return true; } /** * Hilfsmethode zum Überprüfen der Referenzen in den Testfällen */ public boolean checkReferences() { ListNode sorted = this.headNode; while (sorted != null && sorted.next != null) { // prüfe, ob die Elemente sortiert sind if (sorted.value > sorted.next.value) { return false; } sorted = sorted.next; } return true; } @Override public String toString() { StringBuilder sb = new StringBuilder(); ListNode sorted = this.headNode; sb.append("["); while (sorted != null) { sb.append(sorted.toString()); if (sorted.hasNext()) { sb.append("-->"); } sorted = sorted.next; } sb.append("]"); return sb.toString(); } /** * Testläufe */ public static void main(String[] argv) { System.out.println("Einfügen testen (insert)"); { SortedList s = new SortedList(new int[] {5, 3, 1, 2, 4}); print("SortedList([5, 3, 1, 2, 4])", s); checkAndPrint("Sortiert eingefügt ", !s.isEmpty() && s.headNode.value == 1); checkAndPrint("Verlinkung OK", !s.isEmpty() && s.checkReferences()); SortedList s2 = new SortedList(new int[] {5, 4, 3, 2, 1}); print("SortedList([5, 4, 3, 2, 1])", s2); checkAndPrint("Sortiert eingefügt ", s2.headNode != null && s2.headNode.value == 1); checkAndPrint("Verlinkung OK", !s2.isEmpty() && s2.checkReferences()); checkAndPrint("Listen korrekt && identisch", !s.isEmpty() && !s2.isEmpty() && s.equals(s2)); SortedList s3 = new SortedList(new int[] {1, 2, 3, 4, 5}); print("SortedList([1, 2, 3, 4, 5])", s3); checkAndPrint("Verlinkung OK", !s3.isEmpty() && s3.checkReferences()); checkAndPrint("Listen identisch", !s3.isEmpty() && s2.equals(s3)); checkAndPrint("Listen identisch", !s3.isEmpty() && s3.equals(s)); SortedList s4 = new SortedList(new int[] {1, 2, 2, 4, 5}); print("SortedList([1, 2, 2, 4, 5])", s4); checkAndPrint("Verlinkung OK", !s4.isEmpty() && s4.checkReferences()); checkAndPrint("Listen nicht identisch", !s4.isEmpty() && !s.equals(s4)); } System.out.println("\nMinimum entfernen testen (removeFirst)"); { SortedList s = new SortedList(new int[] {5, 3, 1, 2, 4}); print("SortedList([5, 3, 1, 2, 4])", s); for (int i = 1; i <= 5; i++) { try { int returned = s.removeFirst(); print("removeFirst()", s); checkAndPrint(returned + " als Minimum zurückgegeben (erwartet: " + i + ")", returned == i); checkAndPrint("Verlinkung OK", s.checkReferences()); } catch (UndefinedValueException e) { checkAndPrint("UndefinedValueException als Minimum zurückgegeben (erwartet: " + i + ")", false); } } } System.out.println("\nLänge bestimmen (getLength)"); { SortedList s = new SortedList(); print("SortedList()", s); int returned = s.getLength(); int expected = 0; checkAndPrint(returned + " als Länge zurückgegeben (erwartet: " + expected + ")", returned == expected); s.insert(1); print("insert(1)", s); returned = s.getLength(); expected = 1; checkAndPrint(returned + " als Länge zurückgegeben (erwartet: " + expected + ")", returned == expected); try { expected = 0; s.removeFirst(); print("removeFirst()", s); returned = s.getLength(); checkAndPrint(returned + " als Länge zurückgegeben (erwartet: " + expected + ")", returned == expected); checkAndPrint("Verlinkung OK", s.checkReferences()); } catch (UndefinedValueException e) { checkAndPrint("UndefinedValueException als Länge zurückgegeben (erwartet: " + expected + ")", false); } } System.out.println("\nMedian zurückgeben (getMedian)"); { SortedList s = new SortedList(new int[] {13, 10, 5, 4, 2, 20, 21}); print("SortedList([13, 10, 5, 4, 2, 20, 21])", s); double expected = 10.0; try { double returned = s.getMedian(); checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")", returned == expected); } catch (UndefinedValueException e) { checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false); } s = new SortedList(new int[] {1, 5, 4}); print("SortedList([1, 5, 4])", s); expected = 4.0; try { double returned = s.getMedian(); checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")", returned == expected); } catch (UndefinedValueException e) { checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false); } s = new SortedList(new int[] {1, 5}); print("SortedList([1, 5])", s); expected = 5.0; try { double returned = s.getMedian(); checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")", returned == expected); } catch (UndefinedValueException e) { checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false); } s = new SortedList(new int[] {1}); print("SortedList([1])", s); expected = 1.0; try { double returned = s.getMedian(); checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")", returned == expected); } catch (UndefinedValueException e) { checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false); } s = new SortedList(new int[] {1, 5, 2, 3}); print("SortedList([1, 5, 2, 3])", s); expected = 3; try { double returned = s.getMedian(); checkAndPrint(returned + " als Median zurückgegeben (erwartet: " + expected + ")", returned == expected); } catch (UndefinedValueException e) { checkAndPrint("UndefinedValueException als Median zurückgegeben (erwartet: " + expected + ")", false); } } System.out.println("\nK-größtes Element ausgeben (getKLargest)"); { SortedList s1 = new SortedList(new int[] {5, 2, 3, 4, 1}); print("SortedList([5, 2, 3, 4, 1])", s1); for (int k = 1; k <= 5; k++) { int expected = (5 - k + 1); try { int returned = s1.getKLargest(k); checkAndPrint(returned + " als " + k + "-größten Wert zurückgegeben (erwartet: " + expected + ")", returned == expected); } catch (UndefinedValueException e) { checkAndPrint("UndefinedValueException als " + k + "-größten Wert zurückgegeben (erwartet: " + expected + ")", false); } } int returned = 0; try { returned = s1.getKLargest(0); checkAndPrint(returned + " als 0-größten Wert zurückgegeben (erwartet: UndefinedValueException )", false); } catch (UndefinedValueException e) { checkAndPrint( "UndefinedValueException als 0-größten Wert zurückgegeben (erwartet: UndefinedValueException )", true); } try { returned = s1.getKLargest(6); checkAndPrint(returned + " als 6-größten Wert zurückgegeben (erwartet: UndefinedValueException)", false); } catch (UndefinedValueException e) { checkAndPrint( "UndefinedValueException als 6-größten Wert zurückgegeben (erwartet: UndefinedValueException)", true); } } System.out.println("\nListen verschmelzen (merge)"); { int[] elementsS1 = new int[] {1, 5}; SortedList s1 = new SortedList(elementsS1); print("SortedList(" + Arrays.toString(elementsS1) + ")", s1); int[] elementsS2 = new int[] {2, 4}; SortedList s2 = new SortedList(elementsS2); print("SortedList(" + Arrays.toString(elementsS2) + ")", s2); s1.merge(s2); print("merge()", s1); checkAndPrint("Merge OK", s1.getLength() == 4); checkAndPrint("Verlinkung OK", s1.checkReferences()); SortedList s3 = new SortedList(elementsS1); s3.insertAll(elementsS2); checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3)); } { int[] elementsS1 = new int[] {2, 5}; SortedList s1 = new SortedList(elementsS1); print("SortedList(" + Arrays.toString(elementsS1) + ")", s1); int[] elementsS2 = new int[] {1, 3}; SortedList s2 = new SortedList(elementsS2); print("SortedList(" + Arrays.toString(elementsS2) + ")", s2); s1.merge(s2); print("merge()", s1); checkAndPrint("Merge OK", s1.getLength() == 4); checkAndPrint("Verlinkung OK", s1.checkReferences()); SortedList s3 = new SortedList(elementsS1); s3.insertAll(elementsS2); checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3)); } { int[] elementsS1 = new int[] {2, 4, 6, 10, 11}; SortedList s1 = new SortedList(elementsS1); print("SortedList(" + Arrays.toString(elementsS1) + ")", s1); int[] elementsS2 = new int[] {1}; SortedList s2 = new SortedList(elementsS2); print("SortedList(" + Arrays.toString(elementsS2) + ")", s2); s1.merge(s2); print("merge()", s1); checkAndPrint("Merge OK", s1.getLength() == 6); checkAndPrint("Verlinkung OK", s1.checkReferences()); SortedList s3 = new SortedList(elementsS1); s3.insertAll(elementsS2); checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3)); } { int[] elementsS1 = new int[] {1}; SortedList s1 = new SortedList(elementsS1); print("SortedList(" + Arrays.toString(elementsS1) + ")", s1); int[] elementsS2 = new int[] {2, 4, 6, 10, 11}; SortedList s2 = new SortedList(elementsS2); print("SortedList(" + Arrays.toString(elementsS2) + ")", s2); s1.merge(s2); print("merge()", s1); checkAndPrint("Merge OK", s1.getLength() == 6); checkAndPrint("Verlinkung OK", s1.checkReferences()); SortedList s3 = new SortedList(elementsS1); s3.insertAll(elementsS2); checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3)); } { int[] elementsS1 = new int[] {}; SortedList s1 = new SortedList(elementsS1); print("SortedList(" + Arrays.toString(elementsS1) + ")", s1); int[] elementsS2 = new int[] {2, 4, 6, 10, 11}; SortedList s2 = new SortedList(elementsS2); print("SortedList(" + Arrays.toString(elementsS2) + ")", s2); s1.merge(s2); print("merge()", s1); checkAndPrint("Merge OK", s1.getLength() == 5); checkAndPrint("Verlinkung OK", s1.checkReferences()); SortedList s3 = new SortedList(elementsS1); s3.insertAll(elementsS2); checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3)); } { int[] elementsS1 = new int[] {2, 4, 6, 10, 11}; SortedList s1 = new SortedList(elementsS1); print("SortedList(" + Arrays.toString(elementsS1) + ")", s1); int[] elementsS2 = new int[] {}; SortedList s2 = new SortedList(elementsS2); print("SortedList(" + Arrays.toString(elementsS2) + ")", s2); s1.merge(s2); print("merge()", s1); checkAndPrint("Merge OK", s1.getLength() == 5); checkAndPrint("Verlinkung OK", s1.checkReferences()); SortedList s3 = new SortedList(elementsS1); s3.insertAll(elementsS2); checkAndPrint("Verschmelzung erfolgreich", !s3.isEmpty() && s1.equals(s3)); } } private static void print(String message, SortedList sortedList) { System.out.println(" " + message + ": " + sortedList.toString()); } private static boolean checkAndPrint(String message, boolean correct) { System.out.println(" " + (correct ? "PASS:" : "FAIL:") + " " + message); assert (correct); return correct; } }