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.
Frage nach 10.4 Skiplist
Ich habe so verstanden, dass das Array “next” jede Objekte in jeden Ebene enthaltet. Also gibt “next” “Vertikale Verkettung”.
null
null
null
head
Die Abbildung 2 von Übungsblatt zeigt die “horizontale Verkettung” wie eine Liste sein. Also hat jede Objekte eine Element und Verkettung nach nächste Objekt.
null -null
null -null
null -Objekt-null
head-Objekt
Ich weiss nicht wie ich diese Verkettung konstrieren sollen. Ich darf nicht Collection-Interface benutzen, und die Objekte mit Datentyp SkipListNode hat nur value, level, und next.
Darf ich zwei “next” benutzen, wie head.next[n].next[0], so dass ich eine Liste machen kann? Oder darf ich eine Methode implementieren, die immer nächste Objekt zurückgibt?
du hast in dem Array next nur die direkten Nachfolger der SkipListNode die du grad anschaust. Genau wie auf den Bildern in den Übungsfolien. Da hast du ein Element und darüber den Array mit den Zeigern auf das jeweilige Nachbarelement.
Also kommt in next[0] die SkipListNode, die auf Ebene 0 direkter Nachbar ist
in next[1] die SkipList Node, die auf Ebene 1 direkter Nachbar ist usw.
und das letzte Element next[length-1] zeigt auf null.
und dann hast du die Verzeigerung genau wie in den Übungsfolien. Und das nächste Objekt auf der jeweiligen Ebene findest du dann auch im next Array.
Ich verstehe
Danke