 Linked List und Operationen |
jordy
unregistriert
 |
|
| Linked List und Operationen |
     |
Meine Frage:
Elemente x aus einer Menge M werden verwaltet als Knotenelemente mit Zeiger x.next und x.repr.
Die Teilmengen S aus M mit Komponenten S.head und S.tail sind Zeiger auf Anfang und Ende der mittels x.next einfach verketteten Liste der Elemente in S.
Für alle x in S gilt : x.repr = S .
Die Operation SimpleUnion(x,y)
help1 <- y.repr.head
help2 <- y.repr.tail
help1.next <- x.repr.tail
x.repr.tail <- help2
while help2 ungleich help1.next
do help2.repr <- x.repr
help2 <- help2.next
Ich verstehe die Operation SimpleUnion(x,y) nicht. Mir erschließt sich nicht, was diese bewirkt und ich kann mir den Mechanismus dahinter nicht vorstellen .
Meine Ideen:
Ein Beispieldurchlauf für gewählte Mengen würde sicherlich Licht ins Dunkle bringen 
|
|
17.01.2016 14:34 |
|
|
Hacker95
unregistriert
|
|
Servus,
so erkläre ich es mir, ich hoffe ich kann dir helfen.
Der SimpleUnion-Algorithmus hängt die Liste von y an das Ende der Liste von x. Der Repräsentant von x's Liste wird der Repräsentant der resultierenden Liste. Wir verwenden den Zeiger tail der Liste von x, um schnell herauszufinden, wo die Liste von y anzuhängen ist. Damit alle Elemente von y's Liste in die Liste von x eingefügt werden, müssen wir den Zeiger auf das Mengenobjekt in allen Objekten, die ursprünglich in der Liste von y waren, aktualisieren.
help1 <- y.repr.head
// help1 enstspricht also dem Anfang der Liste y
help2 <- y.repr.tail
// help2 entspricht dem Ende der Liste y
help1.next <- x.repr.tail
// an den Anfang bzw. an das erste Element der Liste y wird das Ende der Liste x gehängt
x.repr.tail <- help2
// das Ende der Liste x wird dem Ende der Liste y zugewiesen. Du könntest dir also vorstellen, dass die Liste x nun "so lang" wird, wie beide Listen gemeinsam, sie also die Liste y "umschließt".
while help2 != help1.next
// wir fangen am Ende der Liste y an (help2) und machen solange weiter, bis wir ans Ende der Liste x (und aufgrund des vorherigen Schritts auch Ende der Liste y) kommen.
do help2.repr <- x.repr
// alle Repräsentanten der y-Elemente werden auf den x-Repräsentanten gesetzt, da die Liste x die resultierende, vereinigte Liste wird
help2 <- help2.next
// in der Liste der "ehemaligen" y-Elemente wird sich immer weiter durchgehangelt
PS: Algodat beim Krause zum Zweittermin? Schreibe ich auch, viel Erfolg 
Gruß, Jean
|
|
|
24.01.2016 14:08 |
|
|
|
