Lineare Listen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:45 Fr 29.04.2005 | | Autor: | Jaykop |
Hallo,
ich hab hier folgendes Problem:
Gegeben ist eine lineare Liste mit folgenden Eigenschaften:
1.) das Ende der Liste zeigt auf null oder auf ein Element in der Liste selbst.
2.) die Anzahl der Elemente ist unbekannt
3.) die Elemente enthalten außer dem Nachfolger keine wieteren Informationen
4.) die Zeiger der Liste sind unveränderbar.
Jetzt soll ich einen Algorithmus angeben der zusätzlich Speicher verbraucht(wenn möglich Konstant viel) und mir sagt ob die Liste nun geschlossen ist oder bei null endet. Und als eingabe bekomm ich den Zeiger auf den Anfang.
Meine Lösung für die endende Liste ist folgende:
Man geht solange durch bis man auf null trifft.
Dazu benötigt man nur einen Zeiger der durchläuft.
Aber bei der geschlossenen liste, hab ich keine idee wie ich das mit den oben genannten einschränkungen anstellen soll.
Vieleicht habt ihr ja Ideen, Lösungsansätze oder sogar Lösungen.
Vielen Dank
Jaykop
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:27 Fr 29.04.2005 | | Autor: | Lizard |
Dazu gibt es einen relativ einfachen Ansatz, den sogenannten "Hase-Igel" Algorithmus. Man nimmt sich zwei Zeiger auf Listenelemente, der eine ist der Hase, der andere der Igel. Beide beginnen am Anfang der Liste loszulaufen, wobei der Igel ganz gemütlich ein Element nach dem anderen anschaut, der Hase dagegen doppelt so schnell ist und immer gleich zwei Elemente verarbeitet. Ist die Liste endend, so stößt der Hase vermutlich irgendwann auf Null und man ist fertig; ist sie es allerdings nicht, dann gelangen Hase und Igel irgendwann beide in den Zyklus, und man kann sich leicht überlegen, daß der Hase den Igel dann recht schnell eingeholt hat (Egal, wo der Hase hinkommt: Der Igel "ist schon da"). In diesem Fall kann man sicher davon ausgehen, daß die Liste zyklisch ist, und auch dann terminiert der Algorithmus. Als ich den Algorithmus damals kennengelernt habe, hab ich mich ziemlich gefreut, daß er so anschaulich ist (man kann sich zwar noch ein paar Gedanken zu Laufzeit und Terminierungsverhalten machen, aber schrecklich kompliziert ist das nicht). Falls du aber trotzdem noch Fragen haben solltest, gib einfach noch mal Bescheid.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:39 Fr 29.04.2005 | | Autor: | Jaykop |
Ich werd erstmal ein bischen damit rumprobieren, vieleicht erbgeben sich ja noch fragen. Dankeschön!
Gruß
Jaykop
|
|
|
|
