Linked List und Operationen |
| 17.01.2016, 14:34 | Auf diesen Beitrag antworten » |
| jordy | 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 
|
|
|
|
| 24.01.2016, 14:08 | Auf diesen Beitrag antworten » |
| Hacker95 | 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 |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
|
