Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Übungblatt 9.2
Was wollen die da eigentlich von mir???
Weiß auch net so recht., was die da so genau wollen. Hab jetzt einfach mal einen keller implementiert aber ziemlich geschummelt, dass ich die keller-objekte aneinander hängen kann. (zusätzliche klasse deren Objekte dann die übergebenen Objekte vom Typ Object speichern und einen Pointer auf ein ein weiteres objekt haben…)
hoffe die aufgabenstellung wird noch weng konkreter oder mir geht ein licht auf
Naja, wenn man mal in das Denkschema von verketteten Listen reingekommen ist, dann geht’s eigentlich.
Der Anfang sieht halt bei mir so aus:
public class SortedListImplementierung implements SortedList {
private class ListNode {
public Comparable c; // Referenz auf ein Listenelement
public ListNode next; // Nächster Knoten der verketteten Liste
}
ListNode m_lnFirstNode = null;
...
}Man hat den ersten Node der Liste und kann sich dann von da aus durch die Liste “hangeln”. Dann sind die Funktionen eigentlich recht einfach zu implementieren…
Frag mich nur wie man die Teilaufgabe zu getNext() lösen soll, ohne trotzdem über die Liste zu laufen (ob jetzt interativ oder rekursiv), oder den Listenansatz ad absurdum zu führen (zB mit 'ner zusätzlichen Hashmap oder so). Das ist doch gerade der Witz bei Listen, dass ich keine direkte Referenz auf einzelne Elemente hab, sondern nur etwas über das erste Element weiß.
Und die Testcases sind auch schon wieder für’n Ar… :motz:
Ich häng im Moment nur noch an der getNext und der shuffle methode.
Bei der getNext hab ich ja nun mal gar keine Ahnung wie ich das machen soll???
Habs mir schon tausendmal aufgezeichnet und durchgedacht aber es geht einfach nicht ohne durch die Liste zu “klettern”.
Wenn mir jemand der die Shuffle methode schon implementiert hat
bitte nen kleinen Denkanstoss geben könnte wär ich sehr dankbar!
Das mit der geforderten getNext is echt so ne Sache.
Ich mein als Anhaltspunkt bekommt man nur ein Comparable Object. D.h. ich muss doch irgendwo irgendwie zwangsläufig dieses Object mit all den in der Liste schon gespeicherten “vergleichen”, um zu sehen, welche ListNode zu welchem Comparable Object (CO) gehört. Das CO alleine stellt ja keinerlei Verbindung zu einer ListNode her.
Also irgendwo muss ich doch irgendwie “verlgeichen” und meinem CO das richtige ListNode zuordnen und um das richtige zu finden, MUSS ich doch das in der ListNode gespeicherte CO mit dem Übergebenen “vergleichen”? Aber hat ja Flow schon beschrieben.
Ich glaub wir verstehen die Aufgabenstellung “falsch”, bzw. korrekt formuliert: Die Aufgabenstellung is mal wieder fürn Ar…
Die Shufflemethode ist ganz klar…
Das erste Element wird mit dem Letzen Element zusammen gebracht.
Das zweite Element mit dem vorletzen Element zusammen gebracht.
a b c d e
a e b d c
Also, ich habe mir das so gedacht: Man könnte immer mitzählen, wie viele Elemente die Liste hat. Und in [m]add()[/m], wo man sowieso auf jeden Fall die ganze Liste durchklappern muss, könnte man sich jetzt das Element herauspicken, das sich genau in der Mitte der Liste befindet, und davon das [m]Comparable[/m] und die Referenz auf den zugehörigen [m]ListNode[/m] in einer Variable speichern. Wenn man jetzt [m]getNext()[/m] verwendet, schaut man als allererstes, ob das gesuchte [m]Comparable[/m] größer ist als dieser gespeicherte Vergleichswert oder kleiner. Dadurch müsste man schlimmsten Fall nur noch maximal die Hälfte der Liste durchgehen.
Aber ob das mit der Aufgabenstellung gemeint ist?
Nachtrag:
Es geht viel einfacher! Wenn man davon ausgeht, dass der Zugriff auf [m]getNext()[/m] in den allermeisten Fällen sequentiell erfolgt, könnte man den aktuellen [m]ListNode[/m] als Instanzvariable zwischenspeichern. Ich nehme mal an, dass so etwas in der Richtung verlangt ist.
Und noch was:
Auf http://airhardt.eckental-brand.de/algo habe ich wieder einen alternativen Testcase ins Netz gestellt.
Also irgendwie hab ich mit der Aufgabe noch ganz schöne Probleme…
Es ist doch schon so, dass das ‘erste’ Element das kleinste sein soll und getNext() dann das nächst grössere liefern soll, oder?
An dieser Stelle auch gleich mal die Frage wie ich denn getNext ohne die Liste durchzulaufen implementieren soll?
Bisher habe ich eine Instanzvariable private ListNode head; die eben immer das kleinste Element speichert und von wo aus ich dann die Liste durchgehe.
War aber nicht genau das das Problem mit Listen, dass man in ihnen keine Indizierungsoperationen durchführen kann?
Also hab ich doch eigentlich garkeine Möglichkeit als am Head zu starten oder nicht?
Vielleicht kann mir das ja nochmal jemand erklären, wäre super!
Und dann hab ich noch ein Verständnisproblem.
Beispielsweise bei der add-Methode arbeite ich mit einer zusätzlichen ListNode:
[code]
public void add(Comparable o) {
ListNode nNode = new ListNode();
nNode.c = o;
nNode.next = head;
ListNode tmpNode = new ListNode();
while(nNode.c.compareTo(nNode.next.c) < 0) {
tmpNode = nNode.next;
nNode.next = nNode.next.next;
}
tmpNode.next = nNode;
}[/code]
Aber ist es jetzt nicht so, dass tmpNode immer nur eine Kopie des entsprechenden Elements enthält? Sprich, selbst wenn ich an tmpNode Änderungen vornehme existiert doch immer noch das ‘originale’ Objekt ohne diese Änderungen, da tmpNode ja kein Pointer sondern eine Kopie ist.
Oder bin ich einfach total auf dem falschen Weg?
Ich hoffe mal mir kann da jemand etwas Licht ins Dunkel bringen 
Danke schonmal
Gruß
Marko
Schau einfach mal in meinen letzten Beitrag zum Punkt „Nachtrag“! Oder von hier aus drei Zeilen tiefer…
Exakt. Aber wenn du in [m]getNext()[/m] den aktuell verwendeten [m]ListNode[/m] speicherst, kannst du beim nächsten Aufruf von [m]getNext()[/m] gleich wieder dort anfangen, wo du aufgehört hast. (Vorausgesetzt, die Liste wird von vorne nach hinten durchgegangen - wenn nicht, muss man es doch auf die harte Tour machen und wieder von vorne suchen.)
Java kennt keine Zeiger wie C oder C++, aber bei allen Objekten werden von vornherein Referenzen verwendet - und das ist im Prinzip auch nichts Anderes. Das heißt, dass du bei einer einfachen Zuweisung [m]objekt1 = objekt2;[/m] keine Kopie von [m]objekt2[/m] erhältst, sondern eine Referenz auf das Objekt. Und genau das brauchst du in dieser Aufgabe.
vielleicht 'ne dumme Frage, aber tut ihr Comparable implementieren und compareTo überladen?
Nein. Wozu auch? [m]Comparable[/m] wird doch auch so schon implementiert, z.B. von [m]String[/m], [m]Integer[/m] usw.
Nach langem hin- und her-basteln hab ich das ganze jetzt soweit, dass es einigermassen läuft.
Allerdings bin ich nach wie vor bei stolzen 5%, aber dank Airhardt’s Testcase liegt es wohl daran dass ich keine Referenzen verwende.
Das wiederum liegt daran, dass ich ehrlich gesagt nicht wirklich weiss was die da von mir wollen?!
Einfach nur in jeder Methode
public *** (Comparable o) {
Comparable ref = new Comparable;
ref = o;
...
}
oder was?
Vermutlich super simple, aber ich bin grade :wand:
Danke schonmal
Marko
public add(Comparable o) {
// hier fehlt noch Code
ListNode insertHere.next = new ListNode();
insertHere.nect.c = o;
// hier fehlt noch Code
}
Ich erkläre am besten mal genau, was ich mit “Referenzen statt Werte” gemeint habe:
Nehmen wir zum Beispiel die Methode [m]getNext()[/m] (zur Einfachheit ohne die in der Angabe geforderte Optimierung). Die Funktion kriegt ein [m]Comparable[/m] rein und soll dessen “Nachfolger” ausspucken. Den finden wir natürlich nur, wenn wir erst mal den [m]ListNode[/m] gefunden haben, wo das übergebe [m]Comparable[/m] drinsteckt, und dann noch einen Knoten weiter gehen. Aber nach welchem Kriterium genau soll man jetzt suchen? Dafür gibt es zwei Möglichkeiten:
a) Ich suche so lange, bis ich einen [m]ListNode[/m] finde, für den gilt: [m]node.c.compareTo(o) == 0[/m] (oder [m]node.c.equals(o)[/m]), d.h. ich untersuche jeweils den Wert der Objekte.
b) Ich suche so lange, bis ich einen [m]ListNode[/m] finde, für den gilt: [m]node.c == o[/m], d.h. ich vergleiche die Referenzen der beiden Objekte. Und laut Angabe soll man das auf diese Art und Weise machen.
Vorsicht: Beim Herasusfinden der Sortierreihenfolge in [m]add()[/m] muss man trotzdem [m]compareTo()[/m] verwenden.
Die Musterlösung arbeitet auch mit Referenzen.
Ich weiß aus eigener Erfahrung, dass es 100% gibt, wenn man gleiche Werte zulässt. UND auch nur, wenn man die geforderte Optimierung einbaut.
Die beiden Punkte sind nämlich verzahnt.
ABER wenn man die Liste so nutzt:
SortedList bitch = new SortedListImplementierung();
bitch.add(new Integer(1));
bitch.add(new Integer(1));
bitch.add(new Integer(1));
bitch.add(new Integer(3));Dann muss man in der getNext mit compareTo arbeiten.
Denn die 1 ist zwar immer eine 1, aber der 1. new Integer(1) ist eben eine andere Referenz als der 2. new Integer(1).
D.H. prüfe ich nur per Referenzen in getNext(), ob ich die „1“ (new Interger(1)) schon kenne, bekommt man NEIN zurück und startet also am Listenkopf → Ausgabe: 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.
Ich habe NUR mit compareTo gearbeitet und bekomme als Ausgabe: 1 1 1 3.
Weiterhin lasse ich es zu, dass nach dem schuffeln einfach so mit add() neue Elemente hinzugefügt werden. Die Liste wird von mir davor nicht noch mal sortiert. Die neuen Elemente werden gemäß der „natürlichen“ Einfügelogik der Liste eingefügt.
@hehejo: Also, irgendwie finde ich diese Ausführungen recht konfus und schwer nachvollziehbar…
Ich habe die Testdaten {1, 1, 1, 3} mal bei meiner Implementierung ausprobiert, und es funktioniert ohne Probleme! Also verwirr hier die Leute nicht!
Ja, ich weiß dass es etwas verwirrend klingt.
Aber ich bin mir sicher, dass die Musterlösung mit new Integer(3) nicht abkann.
Aber ich kann mich auch gerne ausschweigen - mein funktioniert ja.
@hehejo: Das is einfach nur falsch.
man MUSS mit „==“ arbeiten.
Stell dir vor, du implementierst in einem eigenen String Objekt von dir das Comparable Interface und schreibst deine compareTo Methode so, dass sie die Länge der Strings vergleicht. Was dein compareTo macht, das bleibt je deiner Implementierung überlassen. (Also denk nicht an Zahlen/Integer! compareTo kannst du implementieren, wie du willst)
Zurück zum String Beispiel. Nehmen wir die drei:
„Haus“
„Hund“
„Katze“
Pseudocode:
h = „Haus“;
list.add(h);
k = „Katze“;
list.add(k);
u = „Hund“;
n = list.getNext(u);
Wenn du jetzt mit compareTo arbeitest bekommst du für n die Referenz auf k („Katze“), was einfach total falsch ist, u („Hund“) ist ja nichtmal in der Liste! (u liefert aber den gleichen „compareTo“ Wert wie h, da beide Strings halt 4 Zeichen haben)
Man MUSS mit „==“ arbeiten
Ich gehe bei der Aufgabenstellung davon aus, dass [m]list.getNext(new Integer(3))[/m] kein gültiges Element der Liste zurückliefern soll. Wenn er bei dieser Eingabe ein Objekt ungleich [m]null[/m] zurückgeben sollte, würde ich das als Fehler beurteilen, weil die Referenzen nicht übereinstimmen.
In jedem Fall ginge aber [m]list.getNext(list.getNext(list.getNext(list.getFirst())))[/m].