Hallo Jungs,
hab da ne Frage, ich steh' im Moment grausam auf dem Schlauch.
Ich habe eine verkettete Liste (in C) von Elementen, die ich sortieren
möchte. Dazu habe ich mir Bubblesort angedacht.
Die Liste ist doppelt verkettet. Um sie zu sortieren, möchte ich erst
eine einfache Funktion bauen, die zwei Elemente vertauscht. Aber ich
blick das grade nicht, probiere schon seit 2 Stunden herum und vermurkse
mir immer meine Liste. WIE tausche ich zwei Elemente in einer doppelt
verketteten C-Liste? Kann mir einer einen Tipp geben? allzu trivial
scheint es ja nicht zu sein.
Das einzige, was ich über die Liste weiss:
ich kriege einen Pointer auf ein Element, und dieses ist mit seinem
Nachfolgerelement, sofern existent, zu tauschen.
Bin mal gespannt - ich habe es nicht fertiggebracht.
Wenn du zwei Elemente tauschen willst, so musst du vier Elemente
'anfassen'/modifizieren.
1 <-> 2 <-> 3 <-> 4
Wenn du 2 und 3 tauscht, müssen in 1 und 4 die vorwärts bzw. rückwärts
gerichteten Zeiger ebenso angepasst werden.
Wenn Du nur einen Pointer hast, der auf das nächste Element zeigt, dann
hast Du "nur" eine Einfach verkettete Liste ... bei der mußt Du pro
Element zwei Pointer anpassen: 1.) Den Pointer vor dem Element welches
Du tauschen willst und den Pointer im Element...
Wenn Du eine Doppelt verkettete Liste hast, dann sind es pro tauschenden
Element schon vier Pointer die Du anpassen mußt... zwei pro Element plus
dem Eintrag vor dem tauschenden und Element und dem dahinter...
Am besten malst du dir anhand eines Beispiels auf, wie die Verpointerung
vor und nach dem Tausch auszusehen hat. Dann siehst du sofort, welche
Pointer du wohin verbiegen musst.
Noch ein wichtiger Tipp:
Je nachdem, wie du die beiden Enden der Liste implementiert hast, ist
beim Vertauschen der ersten beiden oder der letzten beiden Elemente
evtl. eine Sonderbehandlung erforderlich.
Lass doch mal deine bisherigen Bemühungen sehen, vielleicht fehlt ja bis
zum perfekten Ergebnis gar nicht mehr so arg viel.
Also, ich habe folgende Situation:
Die Elemente der Liste sind doppelt verkettet - wie bereits erwähnt. Den
Anfang der Liste habe ich. Nun möchte ich die Liste sortieren, und
übergebe dazu einer Funktion den Start der Liste, also das 1. Element.
Die Sortier- bzw. Tauschfunktion kennt also nur ein einziges Element,
aber via prev und next kann sie ja auch Vorgänger und Nachfolger
zugreifen.
Also echt, das Problem klingt sowas von trivial, ich schäme mich schon
fast, zu fragen, weil eigentlich sollte man meinen, es sei wirklich
einfach! aber ich kriege immer "Kurzschlüsse" in meiner Liste -_-
Dass ist 4 Elemente anfassen muss ist klar, und auch der Anfang und das
Ende der Liste wird eine Spezialbehandlung benötigen, weil im einen Fall
prev == NULL ist (ANfang) bzw. next == NULL (Ende der Liste).
Spar dir die Sonderbehandlung und lass die Kette mit einem leeren
Element Beginnen und Enden. Macht das Leben einfacher.
Alt:
1 --> 2 --> 3 --> 4
1 <-- 2 <-- 3 <-- 4
Neu:
1 --> 3 --> 2 --> 4
1 <-- 3 <-- 2 <-- 4
Wenn du Element E2 und E3 tauscht:
E1 zeigte vorwärts auf E2, nun auf E3
E2 zeigte vorwärts auf E3, nun auf E4
E3 zeigte vorwärts auf E4, nun auf E2
E4 zeigte rückwärts auf E3, nun auf E2
E3 zeigte rückwärts auf E2, nun auf E1
E2 zeigte rückwärts auf E1, nun auf E3
Hoffe ich habe keinen Dreher drin;-)
olaf schrieb:> Also echt, das Problem klingt sowas von trivial, ich schäme mich schon> fast, zu fragen, weil eigentlich sollte man meinen, es sei wirklich> einfach! aber ich kriege immer "Kurzschlüsse" in meiner Liste -_-
Wie Yalu schon sagte.
Mal
es
dir
auf
!
Das Problem klingt trivial und wenn man den Bogen raushat ist es auch
nicht schwer, aber auf Anhieb kriegt man es im Kopf nicht hin. Daher
muss man sich die Situation aufmalen
+####+ +####+ +#####+ +#####+
#N o------>#N o------>#N o------->#N #
#P #<------o P#<--------- P#<-------- P#
+####+ +####+ +#####+ +#####+
^ ^
| |
frst scnd
gegeben die beiden Pointer frst und scnd, wie und in welcher Reihenfolge
muss welcher Pointer wohin umgesetzt werden, damit diese Endisituation
+--------------+
+----------|-+ |
| +--------|------------+ |
| | | | | |
+####+ | | +####+ | | +#####+ | | +#####+
#N o---+ +>#N o--+ +->#N o----+ +>#N #
#P #<+ +---o P#<+ +------ P#<+ +----- P#
+####+ | | +####+ | | +#####+ | | +#####+
| | ^ | | ^ | |
| | | | | | | |
| | frst | | scnd | |
| | | | | |
+-|--------|-+ | |
| +------------|-+
+---------------------+
entsteht?
Und man sieht hier auch schon: da bleibt kein Stein auf dem anderen.
Alle Pointer werden angefasst. Wenn du dir nicht zuvor auf einem Papier
klar machst, in welcher Reihenfolge du das tun musst, damit nichts
verloren geht, dann hast du schon verloren. Denn niemand kann das beim
ersten mal ohne Hilfsmittel im Kopf ausknobeln.
Also: nachdem das Ziel jetzt klar ist, geh von der Ausgangssituation aus
und verändere die Pointer, wie du denkst. Radiere bestehende
Verbdindungen aus und zeichne die neuen ein - Schritt für Schritt. Damit
du einen Pointer irgendwohin zeigen lassen kannst, brauchst du immer
mindestens einen anderen Pointer, der im Moment genau dort hin zeigt.
Denn dessen Pointerwert wirst du dann für den neu zu installierenden
Pointer einfach übernehmen.
Dein einziger Ankerpunkt sind die Pointer frst und scnd. Alle
Veränderungen lassen sich ausgehend von diesen beiden Pointern
beschreiben.
Und nein: Es bringt auch nichts, dir das jetzt hier vorzubeten. Du musst
das selber machen. Denn im eigentlichen Sinne geht es hier darum, dass
du eine für dich funktionierende Technik erlernst, mit der du
Manipulationen an dynamischen Datenstrukturen in den Griff kriegst. Das
kannst aber nur du dir selber beibringen, so wie du auch nur radfahren
gelernt hast, indem du es gemacht hast. Zusehen bringt da wie dort
nichts.
