Mit this keyword auf Variablen zugreifen/WS14 Aufgabe 7 (Doppelverkettung)

Forum: Bachelor › Algorithmik › Algorithmen und Datenstrukturen

SpeedyGonzalez

Member since Jul 2017

103 posts

2019-03-30, 15:11 #1

Subject: Mit this keyword auf Variablen zugreifen/WS14 Aufgabe 7 (Doppelverkettung)

Hallo allerseits,

Was wird in der unten mit "HIER" markierten Zeile gemacht?
Die Methode isDLL() wird auf den aktuellen Knoten this aufgerufen.
In der Methode wird dann eine Variable "d" vom Typ Node erstellt, der dann this als Inhalt zugewiesen wird.
Später im Code wird dann eine neue Variable "e" vom Typ Node erstellt, der dann this.d als Inhalt zugewiesen wird.

Worauf greife ich mit this.d zu?
Ich dachte bisher this repräsentiert den Knoten von dem aus die Methode foo() aufgerufen wird und dass dieser dann nur die Attribute a, v und z hat, also auch nur this.a, this.v oder this.z Sinn machen würden?

Ich habe versucht hier unten den Sachverhalt kompakt darzustellen, konkret wird der Zugriff this.d aber im Lösungsvorschlag zu WS14 Aufgabe 7 (Doppelverkettung) Teilaufgabe a) in der zweiten Lösungsalternative, direkt nach dem ersten While-Loop bei der Instanziierung von DLNode<V> e verwendet. Die Methode isDLL soll dort prüfen, ob der aktuelle Knoten this und die von ihm aus erreichbarenKnoten eine doppelt verkettete Liste bilden:
https://fsi.cs.fau.de/dw/pruefungen/bachelor/aud/loesungws14

class Node<V> {
    Node<V> a;
    V v;
    Node<V> z;

Methode isDLL()
    Node<V> d = this;

    [...]

    Node<V> e = this.d; <-- HIER!!!

Liebe Grüsse,
Speedy

Ezekiel15 Ezekiel15 Member since Oct 2015 181 posts	2019-03-31, 18:24 #2 +1 SpeedyGonzalez +1 SpeedyGonzalez Recht sicher: this.d ist ein Schreibfehler und soll this.z sein. Siehst du auch warum? Ich habe den Fehler einmal ausgebessert.

SpeedyGonzalez Member since Jul 2017 103 posts	2019-04-02, 12:11 #3 +1 Ezekiel15 +1 Ezekiel15 Danke Ezekiel15! Ja, e wird sozusagen zum neuen current Pointer um sich auch die entgegengesetzte Richtung anzusehen, wenn ich alles richtig verstanden habe.

dom
dom

Member since Feb 2011

36 posts

2019-07-11, 10:47 #4

Ich greife das Thema noch mal auf, da ich der Meinung bin, dass der Loesungsvorschlag zur Teilaufgabe a) nicht vollstaendig ist.

Konkret geht es um folgenden Code:

boolean isDLL() {
DLNode<V> d = this, c = this.a; //drag/current pointers
while (c != this && c != null) {
if (c.z != d) {
return false;
}
d = c;
c = c.a;
}
d = this; // Ruecksetzen von d
DLNode<V> e = this.z;
while (e != this && e != null) {
if (e.a != d) {
return false;
}
d = e;
e = e.z;
}
// Either both null (non-circular) or both not null (circular in both directions!)
return ((c == null && e == null) || (c != null && e != null));
}

1. Annahme: Der Knoten this ist der einzige Knoten in der Liste. Liegt dann laut Aufgabenstellung bereits eine DLL vor, oder nicht?

   null <--|_a_|
   |_v_|
   |_z_|--> null

   |
   |
   this

2. Annahme: Bei einem Knoten in der Liste fehlt die Referenz auf den Vorgaenger (a) bzw. sie zeigt auf null. Ist der Knoten ganz rechts dann laut Aufgabenstellung noch vom aktuellen Knoten this aus erreichbar, oder nicht? Gleiches kann natuerlich auch fuer den Nachfolger (z) gelten.

   null <--|_a_| <--|_a_| <--|_a_| |_a_|
   |_v_| |_v_| |_v_| |_v_|
   |_z_|--> |_z_|--> |_z_|--> |_z_|--> null

      |
      |
      this

3. Die beiden if-Anweisungen in den Zeilen 5,6 und 15, 16 machen fuer mich wenig Sinn, denn so wie die while Schleife aufgebaut ist, folgt der Schleppzeiger d dem Positionszeiger c/e immer im Abstand eins. c/e wird irgendwann null oder bei einer zirkulaeren Verkettung this sein und der Schleppzeiger d bleibt weiterhin im Abstand eins hinter c/e.

if (c.z != d) {
return false;
}
if (e.a != d) {
return false;
}

Fuer mich waere es logischer, wenn man die Liste in eine Richtung (z) durchlaeuft bis man am Ende (null) angekommen ist, und dann rueckwaerts (a) wieder zu this zurueck geht. Das gleiche macht man dann noch fuer die Elemente auf der anderen Seite von this. Falls die Liste zirkulaer ist, durchlaeuft man sie in eine Richtung (z) bis man wieder bei this angekommen ist und prueft dann noch die andere Richtung (a) bei der man dann wieder bei this rauskommen sollte.
Nach meinem Verstaendnis muessen pro Element in der Liste immer Nachfolger und Vorgaenger stimmen, damit es eine DLL ist und der Knoten von this aus erreichbar ist (siehe 2.).

Wie seht ihr das?

TOKAMAK

Member since Oct 2014

125 posts

2019-07-12, 13:03 #5

zu 1.: ja natürlich, das ist eine DLL mit einem Element... NICHT zirkulär wohlgemerkt.

zu 2.: wenn du über die Liste "iterierst" kannst du den Knoten erreichen, also ist der Knoten erreichbar, vielleicht solltest du dir mal die Vorlesungsfolien zu Graphen durchlesen. Lauf doch einfach den Pfeilen entlang, gibt es einen Pfad von this zum Element? Ja, dann ist es erreichbar, nein, dann nicht. ABER!!! das Element this ist von dem Element, ohne Referenz a, aus NICHT erreichbar. Das ist aber alles in den Vorlesungsfolien definiert. Eine Liste ist im übrigen auch nichts anderes als ein Graph mit Ausgangs-/Eingangsgrad 1 bzw. 2 bei DLLs

zu 3.: Meiner Ansicht nach ist der Code korrekt, welchen Sinn würde es denn machen, den Nachfolger zu überprüfen, abgesehen davon, dass es nicht geht? Der Nachfolger ist automatisch das nächste Objekt. Mit was würdest du das den vergleichen wollen? Den Vorgänger kann ich überprüfen indem ich ihn mit dem drag-Pointer vergleiche, aber den Nachfolger kann ich ja mit nichts vergleichen, wieso auch? Du musst auch nicht von null zu this zurücklaufen, du hast doch in die Richtung schon alles überprüft, als du von this zu null gelaufen bist. Du schlägst vor Vor- und Nachfolger zu überprüfen, willst aber GAR KEINE if-Anweisung, wie überprüfst du dann Vorgänger und Nachfolger? Das bloße durchlaufen einer DLL in beide Richtungen beweist NICHT, dass es eine DLL ist, weil du auch einfach zwei verschieden Listen haben könntest, die sich das Element this teilen. Du würdest bei beiden wieder bei this ankommen, es wäre aber keine DLL.

dom
dom

Member since Feb 2011

36 posts

2019-07-17, 10:08 #6

Vielen Dank TOKAMAK fuer deine ausfuehrliche Antwort :-)

Quote by TOKAMAK on 2019-07-12, 13:03:
zu 1.: ja natürlich, das ist eine DLL mit einem Element... NICHT zirkulär wohlgemerkt.

Gut. Das habe ich auch so angenommen.

Quote by TOKAMAK on 2019-07-12, 13:03:
zu 2.: [...] ABER!!! das Element this ist von dem Element, ohne Referenz a, aus NICHT erreichbar. [..]

Das ist genau der Punkt, den ich meine.

Quote by TOKAMAK on 2019-07-12, 13:03:
zu 3.: [...] Du schlägst vor Vor- und Nachfolger zu überprüfen, willst aber GAR KEINE if-Anweisung, wie überprüfst du dann Vorgänger und Nachfolger?
Das bloße durchlaufen einer DLL in beide Richtungen beweist NICHT, dass es eine DLL ist, weil du auch einfach zwei verschieden Listen haben könntest, die sich das Element this teilen. Du würdest bei beiden wieder bei this ankommen, es wäre aber keine DLL.

Gar keine if-Anweisung zu verwenden habe ich nicht gesagt. Dass sich 2 Listen this teilen, war genau der Fall der mir in den Sinn gekommen ist. Mir erschliesst sich nur nicht, wie die beiden if-Anweisungen reichen, um das zu ueberpruefen. Aber vielleicht muss ich da einfach noch etwas laenger darueber nachdenken.

Go to forum

Datenschutz | Kontakt