verkettete Listen < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
Hallo,
komme bei folgendem Problem nicht weiter:
ich probiere gerade eine einfach verkettete Liste(gegeben durch eine Referenz auf das erste Element) umzudrehen. Dies soll aber nur durch manipulieren der Referenzen passieren(dass heisst ohne Benutzung von Methoden, insbesondere keine Kopien).
Rein theoretisch brauch ich doch nur die länge der liste
und nehme das erste Element und hänge es ans ende,
dann nehme ich das neue erste und setzte es vor das letzte element usw.
Bin mir leider nicht sicher ob das ein guter weg ist,
bzw ob das verschieben durch ändern der Referenzen so überhaupt möglich ist.
wäre froh wenn mir jemand anregungen geben könnte.
MFG
Nathenatiker
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:21 So 23.04.2006 | | Autor: | Frank05 |
> Hallo,
Hallo,
> komme bei folgendem Problem nicht weiter:
> ich probiere gerade eine einfach verkettete Liste(gegeben
> durch eine Referenz auf das erste Element) umzudrehen. Dies
> soll aber nur durch manipulieren der Referenzen
> passieren(dass heisst ohne Benutzung von Methoden,
> insbesondere keine Kopien).
> Rein theoretisch brauch ich doch nur die länge der liste
> und nehme das erste Element und hänge es ans ende,
> dann nehme ich das neue erste und setzte es vor das letzte
> element usw.
Was "möglich" betrifft, so musst du dir immer überlegen, ob nach deiner jeweiligen Änderung noch immer eine ordentliche verkettete Liste vorliegt. Du musst also jedes betroffene Element der Liste genau betrachten und prüfen, ob sein Zeiger auf das nächste Element stimmt und ob der Zeiger auf das betroffene Element stimmt. Gerade wenn es mehr Zeiger werden (z.B. bei doppelt verketteten Listen) verrutscht gern mal der ein oder andere Zeiger wenn man nicht aufpasst.
Dein Ansatz ist zwar noch etwas unpräzise formuliert, ist aber durchaus machbar. Die Schwierigkeit liegt hier lediglich im Detail: Wenn du sagst du setzt es vor das letzte Element, wie machst du das dann genau?
Vielleicht ist es einfacher, wenn du dir das Ergebnis als eine neue Liste vorstellst. Also jedesmal wenn du ein Element der alten Liste an der 'richtigen' Stelle einfügst kannst du das auch betrachten als 'entferne das Element aus der alten Liste und füge es in die neue Liste ein'. Somit widerspricht das nicht deiner Anforderung, dass keine Kopie gemacht werden darf, da ja nur Zeiger umgebogen werden.
Wie du schon richtig erkannt hast genügt es immer wieder das erste Element der Liste zu betrachten und an die richtige Stelle zu setzen. Wenn du nun eine zweite Liste konstruierst, anstatt an das Ende der ersten Liste anzuhängen, dann benötigst du auch die Information über die Länge der Liste nicht.
Du musst dir jetzt nur noch überlegen, wo in der neuen Liste das jeweilige Element eingefügt werden muss (was nicht weiter schwer ist). Wenn du die Originalliste dermaßen abgebaut hast bleibt nur noch die ursprüngliche Referenz auf das erste Element der neuen Liste zu setzen.
Ich weiß nicht, was du damit meinst, dass du keine Methoden benutzen darfst. Wahrscheinlich ist gemeint, dass du keine API Aufrufe o.ä. verwenden sollst. Aber das ist ja auch nicht nötig. Eine Kopie der Liste ebenfalls nicht. Der Speicherbedarf liegt bei n+c wobei n die Element der Liste sind und c der Platz für eine (konstante) Anzahl von Hilfsvariablen - abhängig von deiner genauen Implementierung. Die Laufzeit ist genauso groß, wenn du nicht vorher die Länge der Liste berechnest (sonst hättest du 2*n).
> Bin mir leider nicht sicher ob das ein guter weg ist,
> bzw ob das verschieben durch ändern der Referenzen so
> überhaupt möglich ist.
Bis auf die unnötige Berechnung der Listenlänge ist deine Idee soweit in Ordnung. Versuch dich einfach mal an einer Implementierung, dann wirst du schnell erkennen, wo du dir das Ganze noch nicht weit genug klar gemacht hast.
|
|
|
|
