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.
:
Verschoben durch User
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;-)
Hast du den Bubblesort freiwillig gewählt? Für Listen gäbe es geeignetere Algorithmen.
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.
Oder die low-ball Lösung (auch wenn das nicht Sinn der Übung ist): Vertausch nicht die Listenelemente sondern den Inhalt der Listenelemente ;)
1 | temp = first->val |
2 | first->val = second->val |
3 | second->val = temp |
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.