Referenzen Java < Java < Programmiersprachen < Praxis < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:07 Mi 02.02.2005 | | Autor: | Rusty |
Hallo Leute!
Bereite mich gerade auf INFO 1 Klausur vor und dabei sind leider ein paar unklarheiten bei der Realisireung von Zeigern in Java aufgetreten.
Erstmal eine einfache implementation eines Stacks:
public class Stack
{
class Entry
{
int value;
Entry next;
}
Entry first;
public Stack()
{
first = null;
}
public void Push (int x)
{
Entry e = new Entry();
e.value = x;
e.next = first;
first = e;
}
public void Pop ()
{
if(first!= null)
{
first = first.next;
}
}
public int Top ()
{
if(first != null)
return first.value;
else
return -1;
}
public boolean Empty ()
{
return first == null;
}
}
so nun main....
Stack s = new Stack();
s.Push(2); s.Push(4); s.Push(5);
while(! s.Empty())
{
System.out.println(s.Top());
s.Pop();
}
und nun meine Verständnisprobleme:
Ich habe versucht nachzuvollziehen auf welche Referenzen die Variablen verweisen (zeigen) um die Methoden zu verstehen (Selbe Problem besteht auch noch bei einigen anderen Progs. - der einfachheit halber habe ich dieses gewählt).
Also soweit ich das verstehe wird beim erzeugen eines Objekts der TopLevelKlasse Stack ja nur die Referenz first auf Entry erzeugt - Referenziert kein Objekt also mit "null".
Wenn ich nun mit Push(Wert) eine Zahl auf den Stack ablege dann wird eine memberKlasse Entry erzeugt - (referenz e) - , mit e.value der Wert zugewiesen - eigentlich alles trivial.
Nun soll first auf e.next Zeigen und e auf first - und genau hier beginnen meine Probleme. Ich kann mir einfach kein Bild davon machen und deshalb die zuteilungen auch nicht nachvollziehen. Ebenso mit dem herausnehmen des obersten Werts mit " first=first.next".
Ich glaub das ist alles ein bissel blöd formuliert aber vielleicht kann ja einer meine Probleme nachvollziehen.
Gruß Rusty
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 09:11 Mi 02.02.2005 | | Autor: | Lizard |
Also ich kann zwar kein Java (das sind wirklich alles Zeiger? Hui), aber prinzipiell ist das gar nicht so schwer. Vielleicht hilft es dir, die Variable "first" einfach mal mental umzubenennen in "current_top" oder so, denn so sieht ihr eigentlicher Verwendungszweck aus: Zu jedem Zeitpunkt des Programmablaufs wird dort der Wert gespeichert, der momentan ganz oben auf dem Stack liegt. Und jetzt machen auch die Zuweisungen Sinn:
public void Push (int x)
{
Entry e = new Entry();
e.value = x;
e.next = current_top;
current_top = e;
}
Zunächst erzeugen wir einen Zeiger auf den neuen Eintrag (e), den wir oben draufschieben wollen. Sodann setzen wir seine Werte so, daß sie passen: e.value ist klar, das haben wir übergeben bekommen. Wie sollte aber e.next aussehen? Naja, das sollte eigentlich ein Zeiger auf den Eintrag sein, der direkt unter dem neuen liegt. Haben wir sowas? Ja! "current_top" speichert für uns den aktuell ganz oben liegenden Eintrag, und wenn wenn wir da einen weiteren Eintrag draufpushen, macht es durchaus Sinn, in diesem neuen Eintrag zu speichern, wo der "alte" Eintrag denn gelegen hat.
[Erinnere dich daran, daß beim Allozieren von Speicher dieser nicht unbedingt "hintereinander" freigemacht wird - die Einträge können wild im gesamten Hauptspeicher verstreut sein. Der "next" Zeiger ist also auf jeden Fall nötig, um sich wieder zurückhangeln zu können, wenn ein Wert gepoppt wird. OK?]
Nachdem wir jetzt also e mit sinnvollen Werten gefüttert haben, bleibt nur noch, die interne Variable current_top upzudaten, denn die soll ja immer auf den höchsten gerade verfügbaren Eintrag zeigen. Kennen wir denn irgendwie die Adresse vom höchsten verfügbaren Eintrag? Klar, immerhin wissen wir, daß gerade e ganz oben auf den Stack geschoben wird, und so ist die Adresse von e sicher ein guter Wert für current_top. Wir setzen also auch diese Variable entsprechend.
public void Pop ()
{
if(current_top!= null)
{
current_top = current_top.next;
}
}
Ergibt jetzt auch Sinn, oder? Mein C++ Tutor würde zwar zusammenzucken, aber Java hat ja zum Glück Garbage Collection, weswegen du den gepoppten Eintrag einfach irgendwo im Speicher rumschweben lassen kannst - Java kümmert sich schon drum. Es reicht damit, den internen Zeiger auf das höchste Element auf das "nächsthöhere" zurückzusetzen, um den höchsten Wert effektiv zu löschen (*).
Ein oder zwei Anmerkungen: Die Rückgabe von -1 als Wert, wenn ein Fehler aufgetreten ist, ist vielleicht nicht so glücklich. Eigentlich würde man hier ein "throw" erwarten (das heißt doch auch in Java so? Eine Fehlermeldung), aber wenn du das absichtlich weggelassen hast, um das Programm einfach zu halten, auch gut.
Und was meine ich eigentlich mit "interne" Variable? Naja, die Klasse "Stack" merkt sich einfach ein paar Dinge über ihren eigenen Zustand (in diesem Beispiel nur eine einzige Sache, nämlich die Adresse des höchsten Eintrags), und sie ist die einzige, die darüber Bescheid weiß. Man kann also davon sprechen, daß diese Variable nach außen hin unsichtbar ist (und das ist auch gut so), mithin also klassenintern.
Wenn so ein Sachverhalt über die gesamte Lebenszeit einer Struktur (also durchaus auch einer Schleife oder so) gemerkt und aufrechterhalten wird, nennt man das auch Invariante. Einfach mal im Hinterkopf behalten, das wird wichtig für Korrektheit von Programmen (wenn ihr das machen solltet).
Gut, ist aber alles nicht so wichtig. Hauptsache, du hast verstanden, warum die Zuweisungen durchaus alle ihren Sinn haben. Wenn nicht, frag einfach nochmal.
(*) PS: Ich sehe gerade, daß ich vielleicht doch mal detailliert erklären sollte, was hier eigentlich genau passiert. Also, wir betrachten die Zeile
current_top = current_top.next
Zunächst wird ausgewertet, was current_top.next für einen Wert bekommen soll. Dazu wird der Zeiger current_top genommen, und dereferenziert: wir wandern an die Adresse im Speicher, auf die er gezeigt hat. Wenn wir da angekommen sind, verzweigen wir nochmals: In dem Speicherbrocken, den wir da herausgegriffen haben, liegen die gespeicherten Werte von value und von next (Denn current_top ist ja ein Zeiger auf einen Wert vom Typ Entry, welcher genau diese zwei Variablen speichert). Wir interessieren uns für next, also gehen wir genau an diese Stelle und greifen uns den Wert, der da liegt. Das ist jetzt also die Adresse des Eintrags, der als nächstes auf dem Stack kommen würde (D.h. der zweithöchste Eintrag auf dem Stack. Gleich werden wir ihn zum neuen höchsten Eintrag machen). Nachdem wir diese Adresse erhalten haben, ist die Auswertung beendet. Wir können nun die Zuweisung durchführen: current_top wird auf die eben erhaltene Adresse gesetzt, und die Ausführung von Pop() terminiert. Der interne Zeiger der Klasse Stack, der die Adresse des höchsten gerade verfügbaren Eintrags speichert, zeigt nun also auf den Wert, der unter dem "alten höchsten" Eintrag lag. Müsste eigentlich klar sein, oder?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:26 Mi 02.02.2005 | | Autor: | Rusty |
Hey Lizard!
Wiedermal eine sehr schöne und saubere Antwort - respekt! Danke dafür.
"Sind das wirklich alles Zeiger ?"
Jaein. Da es in Java sowas wie Zeiger nicht gibt wird stets mit Referenzen gearbeitet die ja immer auf irgendwelche Objekte verweisen, wenn sie nicht gerade mit "null" initialisiert werden. Da hab ich mich wohl ein bissel schwammig ausgedrückt.
"throw"
Gibts in Java um irgendwelche auftretenden Exceptions zu verwerfen. Wenn man Sie näher behandeln möchte oder muss, kann man den entsprechenden Programmteill in einen try/catch-Block "einfügen" (Exceptions werden dann abgefangen - Programm wird nicht abgebrochen).
So ich denke ich habe das was du mir da so prima dargestellt hast verinnerlicht - aber zu Kontrolle würde ich das gerne nochmal mit meinen eigenen Worten wiederhohlen:
first zeigt bei der initialisierung auf null;
Objekt wird gepuscht;
Zuweisung e.next = first würde dann im ersten Fall immer noch auf "null" verweisen - um sich "zurück zu hangeln....."
Zuweisung first = e; verweist dann auf den aktuellen wert
Wo der Groschen noch nicht so ganz gefallen ist, ist die Zuweisung first = first.next - wieso schreibt man nicht first = next - mir ist indem fall der gebrauch des Punktoperators nicht ganz schlüssig(next ist doch der Zeiger, der auf den vorherigen Wert verweist). Hat das damit zu tun, das man dann eben das richtige "next" erwischt und nicht irgendeines, wenn man mehere Werte gepuscht hat?
Gruß Rusty
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:28 Mi 02.02.2005 | | Autor: | Lizard |
Hi,
> Wiedermal eine sehr schöne und saubere Antwort - respekt!
> Danke dafür.
Das freut mich natürlich zu hören. Gern geschehen :)
> "Sind das wirklich alles Zeiger ?"
> Jaein. Da es in Java sowas wie Zeiger nicht gibt wird
> stets mit Referenzen gearbeitet die ja immer auf
> irgendwelche Objekte verweisen, wenn sie nicht gerade mit
> "null" initialisiert werden. Da hab ich mich wohl ein
> bissel schwammig ausgedrückt.
Alles klar, gut zu wissen.
> "throw"
> Gibts in Java um irgendwelche auftretenden Exceptions zu
> verwerfen.
Jo, so hab ich mir das vorgestellt.
> aber zu Kontrolle würde ich das gerne nochmal mit meinen
> eigenen Worten wiederhohlen:
> -snip-
Alles richtig soweit.
> Wo der Groschen noch nicht so ganz gefallen ist, ist die
> Zuweisung first = first.next - wieso schreibt man nicht
> first = next - mir ist indem fall der gebrauch des
> Punktoperators nicht ganz schlüssig(next ist doch der
> Zeiger, der auf den vorherigen Wert verweist). Hat das
> damit zu tun, das man dann eben das richtige "next"
> erwischt und nicht irgendeines, wenn man mehere Werte
> gepuscht hat?
Ja, ganz genau, das hängt daran. Du musst dir vor Augen führen, daß "next", wenn es allein steht, überhaupt nicht qualifiziert ist - das macht erst im Kontext von irgendeiner Entry Struktur Sinn. Diese Struktur ist dann eben diejenige, die man erhält, wenn man first dereferenziert, also genau diese, die oben auf dem Stack liegt. Macht auch Sinn, weil man ja die "nächste von oben", also die zweithöchste, als das neue first definieren möchte. Ja?
Übrigens gilt die gleiche Aussage für first, auch diese Variable müsste praktisch mit my_stack.first oder so qualifiziert werden. Da sie aber ausschließlich innerhalb der Klasse, zu die sie gehört, verwendet wird, kann man sich das sparen; der Kontext ist dann auch so klar (ist dann this.first oder self.first, keine Ahnung wie das in Java heißt). Das next dagegen verwendest du außerhalb der Entry Klasse, weswegen du dich auf das entsprechende Objekt beziehen musst, welches du meinst.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:00 Mi 02.02.2005 | | Autor: | Rusty |
Hey Lizard!
Das sitzt jetzt soweit. Ist im nachhinein eigentlich einfach wenn man erstmal die zusammenhänge hergestellt hat. Bin inzwischen einwenig weiter gegangen und habe leider selbiges Problem auch bei einer einfachen implementierung einer einfach verketteten Liste. Wenn du Lust und zeit hast würde ich dich bitten das kurz mal mit mir durchzugehen.
Prog:
package container
public class Node
{
Object element;
Node next;
public Node(Object e, Node n) {element=e; next=n;}
public void setElement(Object e) {element=e;}
public Object getElement() {return element;}
public void setNext(Node n) {next=n;}
public Node getNext(){return next;}
}
import container.Node;
public class NodeTest
{
public static void main(String[] args)
{
Integer x1 = new Integer(5); Integer x2 = new Integer(19);
Integer x3 = new Integer(199);
Node head = new Node(x1,null); Node n = new Node(x2, null);
n.setNext(head); head = n;
head = new Node(x3,head);
n = head;
while(n!=null)
{
System.out.println("Elemet="+ ((Integer)n.getElement()).intValue());
n=n.getNext();
}
}
}
Das prinzip einer einfach verketteten Liste ist mir sonnenklar  , hab nur wieder probleme das in den Programmzeilen "wiederzufinden"!
So ich versuch jetzt mal zu beschreiben was passiert.
In main: Erstmal werden 3 Wrapper Objekte (x1 -x3) erzeugt da ja mit Objekten gearbeitet wird müssen primitive Werte in "Containern" verwaltet werden.
Node head = new Node(x1, null) - erzeugt Exemplar von Node mit referenz auf x1 (element) und Zeiger (Variable) next zeigt auf null
Node n = new Node(x2, null) - selbige wie oben - Elemente sind zum jetztigen zeitpkt. noch nicht zu einer Liste verbunden.
Nun greife ich mit n.setNext(head) auf Objekt n zu - rufe methode setNext auf und übergebe Objekt head.
Das hat zur Folge das das Objekt x2 nun eine Referenz auf x1 hat - next von x2 zeigt auf x1.
Ich glaub bis hierhin ist das wohl richtig, leider sind mir die darauf folgenden Anweisungen wieder nicht so ganz klar.
Gruß Rusty
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:59 Mi 02.02.2005 | | Autor: | Lizard |
Hi,
> Das sitzt jetzt soweit. Ist im nachhinein eigentlich
> einfach wenn man erstmal die zusammenhänge hergestellt hat.
Jo, aber bis dahin dauert es manchmal ein bißchen. Nicht weiter tragisch, das.
> Bin inzwischen einwenig weiter gegangen und habe leider
> selbiges Problem auch bei einer einfachen implementierung
> einer einfach verketteten Liste. Wenn du Lust und zeit hast
> würde ich dich bitten das kurz mal mit mir durchzugehen.
Gut für dich! Programmieren lernt man am besten durch machen (bzw. anschauen und nachvollziehen bestehender Programme, wie du es gerade zu tun scheinst).
> So ich versuch jetzt mal zu beschreiben was passiert.
> In main: Erstmal werden 3 Wrapper Objekte (x1 -x3)
> erzeugt da ja mit Objekten gearbeitet wird müssen primitive
> Werte in "Containern" verwaltet werden.
Wenn du es sagst... sieht aber aus wie einer der Gründe, warum mir Java nicht so sympathisch ist. Gut, dafür ist hier aber nicht der Platz.
> Node head = new Node(x1, null) - erzeugt Exemplar von Node
> mit referenz auf x1 (element) und Zeiger (Variable) next
> zeigt auf null
> Node n = new Node(x2, null) - selbige wie oben - Elemente
> sind zum jetztigen zeitpkt. noch nicht zu einer Liste
> verbunden.
Korrekt.
> Nun greife ich mit n.setNext(head) auf Objekt n zu - rufe
> methode setNext auf und übergebe Objekt head.
> Das hat zur Folge das das Objekt x2 nun eine Referenz auf
> x1 hat - next von x2 zeigt auf x1.
Mehr oder weniger - du musst dir immer darüber im Klaren sein, welche Datenstruktur hier gerade was macht. Vielleicht hilft es dir, das ganze in Baumform (oder Listenform) zu visualisieren (ich hab es mir tatsächlich auch gerade aufgemalt): Jede "Node" ist ein großer Blob und hat zwei Kinder, nämlich einmal das Element (x1, x2, ...) und dann noch einen zweiten Blob (oder stattdessen auch NULL). Du hast es aber soweit richtig, daß der Blob mit dem x1 Element auf den Blob mit dem x2 Element verweist. Wenn du mir soweit folgen kannst :)
Sodann:
> head = new Node(x3,head);
>
> n = head;
> while(n!=null)
> [...]
Hier wird ein weiterer neuer Blob erstellt. Davon gibt es jetzt 3 (vergiss mal die Namen n und head, das sind nur Platzhalter. Wichtig ist nur das, was mit "new" erzeugt wurde). Dieser neue Blob kriegt als Elementkind x3 und als Nachfolger den bisherigen Listenkopf übergeben - das war genau der eine Blob, den wir vorhin hatten (der mit x2). Dann wird der Name "head" genommen, und der neu erzeugte Blob wird darin gespeichert. Die Struktur sieht also ungefähr so aus:
"head"
Blob 3 -> Blob 2 -> Blob 1 -> NULL
| | |
x3 x2 x1
Dann wird n auf Blob 3 gesetzt (denn das war ja gerade head. Wie gesagt, nicht verwirren lassen). Dann kommt der Durchlauf:
> while(n!=null)
> {
> System.out.println("Elemet="+ ((Integer)n.getElement()).intValue());
> n=n.getNext();
> }
Also: solange wir noch nicht ans Ende der Liste gestoßen sind (n == NULL), gib folgendes aus: "Element" (ohne n, naja) und danach die Ausgabe von n.getElement() (die dann noch ein bißchen vertypt werden muss. Java halt, aber was soll's). Du holst dir also von der aktuellen Node mit dem Namen n den Elementeintrag und gibst ihn aus. Danach muss nur noch die nächste Node ( n.getNext() ) als aktuelle Node n gesetzt werden, damit die Schleife auch im nächsten Durchlauf noch das richtige tut, und dann sind wir auch schon fertig. Interessant hierbei ist vielleicht, das wir tatsächlich "vom Ende der Liste fallen" und auch noch die Node verarbeiten, die selber NULL ist, was wir dann als Abbruchbedingung nehmen; ein anderer Weg, dies zu tun, wäre vielleicht ein Check, ob n.getNext() == NULL ist, bevor die Schleife von vorne beginnt. Das ließe sich dann zwar nicht mehr so kompakt schreiben, wäre aber ein Stück sicherer. Gut, letztlich eine Frage des Geschmacks.
So, wenn ich das also richtig sehe, ist die Ausgabe
Elemet 199
Elemet 19
Elemet 5
Stimmt das denn auch?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:10 Mi 02.02.2005 | | Autor: | Rusty |
jo. die reihenfolge ist korrekt!
Wie schon gesagt das Prinzip einer dynamischen datenstruktur ist ja auch nicht so schwer nachzuvollziehen. Bei mir haperts halt beim nachvollziehen der Zuweisungen..... - die Theorie in die Praxis umzusetzten. Irgendwie will dieses blöde hin und herschieben der Referenzen nicht in meinen Schädel. Ansonsten habe ich mich was das programmieren angeht dieses Semester gar nicht so blöde angestellt wie es hier vielleicht scheint . - Denkblokade
Werde jetzt einfach noch mal weiter versuchen dieses nachzuvollziehen.
Danke nochmal für die Mühe
Gruß Rusty
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:22 Mi 02.02.2005 | | Autor: | Lizard |
> jo. die reihenfolge ist korrekt!
Ein Glück :)
> Wie schon gesagt das Prinzip einer dynamischen
> datenstruktur ist ja auch nicht so schwer nachzuvollziehen.
> Bei mir haperts halt beim nachvollziehen der
> Zuweisungen..... - die Theorie in die Praxis umzusetzten.
> Irgendwie will dieses blöde hin und herschieben der
> Referenzen nicht in meinen Schädel.
Wie schon gesagt, halb so wild. Das ist auch mit das abstrakteste, was man so verstehen muss (und wo auch beim Programmieren die meisten Fehler passieren), also lass dir ruhig Zeit. Hilfreich ist wie gesagt so ein bißchen das Lösen von der Vorstellung, daß alles irgendwie mit einer Variablen zu tun haben muss: Objekte, die mit new alloziert wurde, liegen auf dem Heap, und bleiben dort auch, solange von *irgendwo* ein Pointer auf sie zeigt. Es ist also nicht nötig, daß der Pointer (sorry: Zeiger) einen speziellen Namen hat, es kann sich durchaus um ein Feld wie "next" bei Entry handeln. Stell dir einfach die allozierten Objekte vor, wie sie sich im Speicher tummeln, und frag dich: Worauf verweise ich da gerade? Wann habe ich es alloziert?
> Ansonsten habe ich mich
> was das programmieren angeht dieses Semester gar nicht so
> blöde angestellt wie es hier vielleicht scheint .
> - Denkblockade
Nein, gar nicht: Solche Fragen erwarte ich nicht von jemandem, der irgendwelche grundlegenden Sachen nicht verstanden hat. Du würdest gar nicht glauben, was für komische Dinge man sonst manchmal so gefragt wird, dagegen ist das hier echt ziemlich hohes Niveau...
> Werde jetzt einfach noch mal weiter versuchen dieses
> nachzuvollziehen.
Siehst du, das ist das wichtigste. Einfach weiter, das Verständnis kommt mit der Beschäftigung mit dem Stoff. Ich garantiere dafür!
> Danke nochmal für die Mühe
> Gruß Rusty
Ja, ist mir immer wieder eine Freude :)
|
|
|
|
