Hallo

"Eine Erweiterung der Sprungliste soll implementiert werden. Diese Datenstruktur besteht aus
einer einfach verketteten Liste. Außerdem soll jedes k · 2i-te Listenelement zusätzlich auf das
(k + 1) · 2i-te Listenelement zeigen i Element {1, .., log2(n)} ^ k Element N."

Könnte mir jemand von euch der sich schon mehr mit der Aufgabe beschäftigt hat mir erklären wie diese Liste aussehen soll. Ich bekomme das nicht zusammen.

Danke

Hi…

mach dir am besten ein Beispiel. Z.B. nimm n = 16 (Anzahl der Element in der
(zunächst) einfach verketteten Liste). Dann ist log n = 4 und also durchläuft
i den Bereich von 1 bis 4. Für jedes k \in \Nat (das Sinn macht!) soll nun das
k * 2^i-te Element auf das (k+1) * 2^i-te Element verweisen.

Zunächst ist i = 1. Für k = 1 heisst das, dass das 2-te Element auf das 4-te Element
verweisen soll. Für k = 2, dass das 4-te auf das 6-te element verweisen soll usw.
Dann betrachtest du i = 2. Für k = 1 folgt, dass das 4-te Element (zusätzlich zu
obigem) auf das 8-te Element verweisen soll usw.

Hilft das schon?

Frank

PS Der Bereich für i ist ein bisschen komisch. Evtl. ist da i \in {0, …. (log n) - 1 }
sinnvoller…

Hi…

mach dir am besten ein Beispiel. Z.B. nimm n = 16 (Anzahl der Element in der
(zunächst) einfach verketteten Liste). Dann ist log n = 4 und also durchläuft
i den Bereich von 1 bis 4. Für jedes k \in \Nat (das Sinn macht!) soll nun das
k * 2^i-te Element auf das (k+1) * 2^i-te Element verweisen.

Zunächst ist i = 1. Für k = 1 heisst das, dass das 2-te Element auf das 4-te Element
verweisen soll. Für k = 2, dass das 4-te auf das 6-te element verweisen soll usw.
Dann betrachtest du i = 2. Für k = 1 folgt, dass das 4-te Element (zusätzlich zu
obigem) auf das 8-te Element verweisen soll usw.

Hilft das schon?

Frank

PS Der Bereich für i ist ein bisschen komisch. Evtl. ist da i \in {0, …. (log n) - 1 }
sinnvoller…

Danke das hilft schon ne Menge. Nun konnte ich mir aufmalen wie das zum Beispiel für n=16 aussieht und habe ein besseres Bild davon.

Nun muss ich dafür eine Datenstruktur definieren.

Ich habe das bei Punkt 1 ja auch schon gemacht aber ich bin mir immer noch nicht sicher was nun in dieser Datenstruktur stehen soll. Und muss ich hier auch eine Zeichnung hinzufügen?

Was genau gehört zur "Datenstruktur"?

ich habe mal ne ganz andere frage zu:

"Wieviele Zeiger sind maximal in einem Listenelement
enthalten?"

zählen die zeiger die auf das listenelement zeigen mit, oder nur die zeiger die vom listenelement wegführen?

Eine Datenstruktur wird meist durch die verwalteten Daten (in diesem Fall die Knoten)
und insbesondere durch die zur Verfügung stehenden Operationen (auf diesen Daten)
charakterisiert.

Siehe z.B. im Skript (oder einem Algorithmen/Datenstrukturen Buch) die Definition
der Datenstruktur "Stack". (Da keine genaueren Angaben über die Daten gemacht
werden sollen, findet man oft sowas wie Stack(T) - ein Stack für Daten vom Typ T.)
Da hast du eine Datenstruktur Stack mit den Operationen isEmpty, push, pop und
top (oder head). Normalerweise gibt man noch einen Konstruktor an (bzw. eine
Methode zum 'Erstellen').

Im Beispiel einer Liste macht es Sinn genauer auf die Knoten einzugehen. Bei einer
einfach verketteten Liste brauchst du dafür nur eine Möglichkeit das eigentliche Objekt
zu speichern (z.B. eine Zahl oder etwas komplizierteres wie einen 'Studenten'), sowie
einen Zeiger auf den nächsten Knoten in der Liste. Bei einer doppelt verketteten Liste
brauchst du schon zwei solche Zeiger (einen auf den nächsten, einen auf den vorherigen
Konten in der Liste).

Die Implementierung der Methoden gehört eigentlich nicht mehr zum Datentyp dazu
(zumindest nicht zum abstrakten), aber eine Beschreibung, was jeweils getan wird.

Eventuell bietet es sich aber an das ganze auch einmal zu implementieren (z.B. in Java).
Das übt zudem ;)

Frank :)

PS Das Bild hat mit der Datenstruktur wenig zu tun - insbesondere kannst du dir damit
nur ein Beispiel deutlich machen! -, allerdings ist in der Aufgabenstellung eine Zeichnung
gefordert, also sollte man vielleicht einfach eine Listes mit 10 Elementen aufmalen.

PS2 Obige Angaben ohne Gewähr, da ich die Vorlesung nicht höre. Es wurde doch
aber bestimmt in den Ü-Gruppen gesagt, ob ihr das implementieren sollt oder nur
abstrakt angeben sollt?

"Wieviele Zeiger sind maximal in einem Listenelement enthalten?"

zählen die zeiger die auf das listenelement zeigen mit, oder nur die zeiger die vom listenelement wegführen?

*In* einem Listenelement. Nimm z.B. eine einfach verkettete Liste um dir das
zu veranschaulichen mit den Listenelementen x, y und z:

x —> y —> z

Der Knoten y hat nun keine Möglichkeit "rauszufinden", dass x auf ihn zeigt,
ergo speichert er auch keinen Zeiger auf x (sonst wär's auch schnell eine
doppelt verkettete Liste).

Frank :)

Wäre einer von euch mal so nett und Kopiert seine lösung hier rein?
Da ich grade auch an der Aufgabe hänge und nicht so richtig weiter komme[28]

Wäre einer von euch mal so nett und Kopiert seine lösung hier rein?
Da ich grade auch an der Aufgabe hänge und nicht so richtig weiter komme[28]

vielleicht hilft dir erstmal das bild weiter?
[img]https://www.fb18.de/mybb/attachment.php?aid=171[/img]