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.
Aufgabe 11.2 - SkipList
Hallo zusammen!
Eine kurze Frage zum Hinweis:
“Die höchste Ebene, die ein einzufügendes Element erreicht, wird beim Einfügen zufällig bestimmt.
Implementieren Sie hierfür die Methode getRandomLevel() und nutzen Sie die Methode nextBoolean() der schon vorhandene Instanz des Random-Objekts.”
Im Zusammenspiel mit den Forderungen, wie die Ebenenverteilung erfolgen soll, ist mir gerade nicht so ganz klar, wie zur Berechnung der obersten Ebene die Methode “nextBoolean()” Anwendung finden soll.
Kann mir da jemand weiterhelfen?
Vielen Dank!
Sieh’s als Möglichkeit, einen Münzwurf zu simulieren. Hilft das?
Ja, das hilft 
Das heißt aber auch, dass ich eine bestimme Anzahl mal eine „Münze werfen muss“ und dann daraus die Ebene berechnen. Ist das so dann als Folgerung korrekt?
Hört sich nicht verkehrt an 
Hab nach langem Kampf die Aufgabe nun endlich fertig(?), bekomme keine Ausgabe außer der einen durch formatContent(), also auch keine Fehler, bekomme aber trotzdem ein ! auf EST. Bevor ich vielviel Zeit damit verschwende, ist denn in EST alles korrekt? Falls ja, mag jemand mit einem Haken eine Ausgabe von formatContent() posten? Danke 
Auch wenns vielleicht nicht für alle Methoden mit einem TODO einen [m]main[/m]-Test gibt, sollten Sie implementiert werden
Ich werd später mal aber den Test der entsprechenden Methode von der Anzeige im EST abkoppeln.
Soll das head-Objekt der SkipList an sich denn auch einen Wert speichern?
Oder soll “head” in SkipList nur den Anfang markieren ohne einen Wert zu enthalten?
[m]head[/m] verwaltet nur die Zeiger, wie auf dem Bild angedeutet.
Okay. Das macht die Sache einfacher
Vielen Dank für die zügigen Antworten!
Verstehe ich das richtig dass die SkipNodes die einzelnen Blöcke im Bild darstellen sollen? D.h. Das Element 1 wird im Bild durch vier SkipNodes repräsentiert? und was genau wird dann im Array next gespeichert?
Nein, durch eine Instanz von [m]SkipNode[/m]. Eine [m]SkipNode[/m] stellt die ganze „Säule“ dar.
In [m]next[n][/m] steht der Nachfolger auf Ebene [m]n[/m]
1 Like
Könnte bitte jemand einen korrekten Output posten, damit ich abschätzen kann, ob ich auf dem richtigen Weg bin.
Danke!
wäre es dann nicht logischer die Länge von „next“ auf „level“ zu beschränken?
Output in Eclipse bei grünem Haken:
Edit: „Der Beitrag ist zu lang. Es sind maximal 40000 Zeichen zulässig.“
23 910 → 10084 → 24406
.
.
.
00 78 → 128 → 152 → 209 → 262 → 308 → 327 → 361 → 402 → 435 → 460 → 557 → 739 → 808 → 810 → 816 → 863 → 884 → 902 → 910 → 997 → 1010 → 1014 → 1058 → 1112 → 1128 → 1223 → 1241 → 1340 → 1342 → 1457 → 1477 → 1535 → 1575 → 1590 → 1713 → 1774 → 1795 → 1828 → 1885 → 1898 → 1951 → 1959 → 1981 → 1988 → 1995 → 2035 → 2040 → 2095 → 2361 → 2438 → 2515 → 2536 → 2615 → 2646 → 2727 → 2765 → 2799 → 2851 → 2853 → 2908 → 2954 → 3004 → 3016 → 3024 → 3186 → 3215 → 3216 → 3278 → 3304 → 3390 → 3399 → 3480 → 3523 → 3577 → 3609 → 3626 → 3827 → 4006 → 4107 → 4125 → 4245 → 4274 → 4306 → 4342 → 4405 → 4411 → 4430 → 4483 → 4563 → 4641 → 4710 → 4714 → 4728 → 4905 → 4986 → 4987 → 5085 → 5086 → 5091 → 5227 → 5234 → 5435 → 5471 → 5550 → 5696 → 5750 → 5801 → 5870 → 5898 → 5989 → 6063 → 6121 → 6170 → 6336 → 6340 → 6344 → 6456 → 6502 → 6524 → 6671 → 6735 → 6757 → 6770 → 6959 → 6967 → 7049 → 7178 → 7203 → 7247 → 7248 → 7293 → 7323 → 7337 → 7341 → 7348 → 7411 → 7414 → 7494 → 7566 → 7741 → 7859 → 7887 → 7909 → 7913 → 7939 → 7975 → 7998 → 8017 → 8022 → 8053 → 8134 → 8200 → 8214 → 8222 → 8360 → 8416 → 8422 → 8555 → 8602 → 8625 → 8648 → 8672 → 8739 → 8770 → 8837 → 8847 → 8891 → 8893 → 8939 → 9019 → 9042 → 9067 → 9105 → 9164 → 9205 → 9254 → 9276 → 9280 → 9383 → 9410 → 9438 → 9446 → 9474 → 9479 → 9541 → 9588 → 9647 → 9757 → 9760 → 9773 → 9775 → 9824 → 9836 → 9945 → 10001 → 10028 → 10084 → 10086 → 10114 → 10149 → 10174 → 10192 → 10284 → 10295 → 10364 → 10423 → 10430 → 10467 → 10500 → 10522 → 10548 → 10552 → 10554 → 10571 → 10802 → 10831 → 10844 → 10889 → 10956 → 11041 → 11083 → 11155 → 11179 → 11232 → 11362 → 11404 → 11420 → 11478 → 11505 → 11625 → 11800 → 11814 → 11849 → 12099 → 12119 → 12150 → 12193 → 12290 → 12628 → 12667 → 12702 → 12782 → 12794 → 12798 → 12807 → 13000 → 13053 → 13065 → 13095 → 13142 → 13159 → 13186 → 13197 → 13240 → 13276 → 13327 → 13328 → 13349 → 13375 → 13438 → 13487 → 13561 → 13613 → 13654 → 13669 → 13672 → 13805 → 13835 → 13853 → 13943 → 13958 → 14025 → 14033 → 14105 → 14132 → 14160 → 14187 → 14237 → 14262 → 14334 → 14343 → 14354 → 14434 → 14451 → 14500 → 14576 → 14592 → 14598 → 14629 → 14638 → 14640 → 14682 → 14957 → 14975 → 14998 → 15117 → 15174 → 15181 → 15216 → 15220 → 15224 → 15304 → 15317 → 15363 → 15460 → 15522 → 15620 → 15677 → 15693 → 15721 → 15898 → 15942 → 15961 → 15977 → 16045 → 16047 → 16165 → 16171 → 16333 → 16373 → 16381 → 16386 → 16394 → 16453 → 16476 → 16568 → 16636 → 16648 → 16661 → 16678 → 16718 → 16723 → 16771 → 16805 → 16974 → 17046 → 17159 → 17161 → 17246 → 17281 → 17307 → 17396 → 17399 → 17404 → 17435 → 17453 → 17590 → 17682 → 17762 → 17795 → 17823 → 17848 → 18023 → 18030 → 18036 → 18066 → 18117 → 18184 → 18292 → 18323 → 18365 → 18408 → 18417 → 18421 → 18452 → 18684 → 18747 → 18842 → 18883 → 18907 → 18945 → 19100 → 19110 → 19132 → 19185 → 19213 → 19280 → 19338 → 19356 → 19359 → 19360 → 19434 → 19441 → 19456 → 19467 → 19494 → 19503 → 19517 → 19527 → 19573 → 19594 → 19614 → 19644 → 19790 → 19864 → 19886 → 19895 → 19912 → 20000 → 20046 → 20096 → 20106 → 20123 → 20212 → 20216 → 20227 → 20231 → 20303 → 20358 → 20411 → 20483 → 20536 → 20545 → 20560 → 20581 → 20717 → 20746 → 20748 → 20764 → 20777 → 20823 → 20866 → 20875 → 20922 → 20926 → 20947 → 20992 → 21016 → 21017 → 21021 → 21157 → 21190 → 21245 → 21322 → 21399 → 21422 → 21423 → 21482 → 21483 → 21494 → 21543 → 21592 → 21617 → 21618 → 21686 → 21812 → 21838 → 21848 → 21882 → 21932 → 21974 → 21998 → 22128 → 22161 → 22221 → 22370 → 22374 → 22399 → 22422 → 22436 → 22628 → 22639 → 22796 → 22856 → 23015 → 23099 → 23104 → 23161 → 23173 → 23233 → 23235 → 23250 → 23610 → 23621 → 23647 → 23757 → 23801 → 23843 → 23887 → 24012 → 24053 → 24155 → 24200 → 24235 → 24247 → 24356 → 24395 → 24405 → 24406 → 24558 → 24590 → 24643 → 24644 → 24660 → 24681 → 24695 → 24934 → 24994 → 25048 → 25123 → 25138 → 25140 → 25170 → 25172 → 25253 → 25287 → 25331 → 25401 → 25452 → 25659 → 25732 → 25763 → 25805 → 25897 → 25936 → 25977 → 25983 → 26039 → 26119 → 26158 → 26213 → 26392 → 26399 → 26404 → 26425 → 26488 → 26564 → 26652 → 26667 → 26800 → 26920 → 27081 → 27183 → 27289 → 27359 → 27392 → 27513 → 27523 → 27532 → 27560 → 27565 → 27573 → 27575 → 27718 → 27731 → 27740 → 27790 → 27815 → 27871 → 27874 → 27881 → 27918 → 27943 → 28018 → 28047 → 28068 → 28209 → 28233 → 28263 → 28309 → 28479 → 28619 → 28711 → 28730 → 28767 → 28771 → 28779 → 28919 → 28964 → 28989 → 29174 → 29176 → 29184 → 29304 → 29349 → 29351 → 29354 → 29356 → 29361 → 29421 → 29430 → 29449 → 29483 → 29594 → 29631 → 29636 → 29668 → 29743 → 29744 → 29793 → 29828 → 29910 → 29920 → 29935 → 29975 → 29977
Der richtige Output sollte einmal die komplette Liste mit allen Ebenen darstellen.
Ansonsten sollten einfach keine Fehlermeldungen erscheinen.
heisst das also alle 32 Level müssen bei der grünen haken ausgabe vorkommen?
Siehe meinen vorherigen Post.
Habe die „oberste“ (23) und „unterste“ (00) Ebene eingefügt.
Der komplette Output wäre zu lang.
Hätte man machen können, aber ist ja alles O(1) 
Aber ist es nicht sehr unwahrscheinlich, dass man Level 23 erreicht. Die Chancen dafür sind doch nur 1 zu 2^23/600 oder sehe ich das falsch?
ich scheitere an der Umsetzung vom Iterator,
also was ein Iterator machen kann, und was der Sinn eines Iterators ist habe ich soweit verstanden, stand ja ganz gut da in den Vorlesungsfolien, jedoch verstehe ich nicht so recht wie ich die Methode “public Iterator iterator()” implementieren soll…
theoretisch ist ja ein Iterator ein Element welches von SkipNode zu SkipNode springen kann.
kann da jemand paar erklärungen machen bzw. tipps geben wie das ganze ausschauen soll?