Algorithmen + Datenstrukturen

[biene82]

Hallo allerseits!

ich wurde mit der folgenden aufgabe beauftragt und könnte hierbei ein bißchen hilfe gebrauchen, da mir irgendwie der ansatz fehlt. für jede hilfe wäre ich sehr dankbar!!! :-))

aufgabe: implementieren sie eine routine "exchange" für eine verkettete liste, die die knoten, auf die die zeiger t und u zeigen, miteinander vertauscht.

da ich neu in diesem bereich bin wäre ich für sämtliche hinweise, tipps oder lösungsansätze echt dankbar!!

grußli

biene

[geloescht_Newlukai]

Einfach oder doppelt verkettet?

Im Prinzip hast Du also nur 2 Zeiger. Die zeigen auf Knoten, die jeweils einen Zeiger auf den nächsten Knoten haben.

Du mußt die Zeiger "umbiegen": Knoten B zeigt auf C und Knoten E zeigt auf F. B und E sollen getauscht werden. D. h. Knoten B muß auf F und Knoten E auf C zeigen.

A -> B -> C -> D -> E -> F


// wird zu


       |-------------|

A -> B |-> C -> D -> E |-> F

     |-----------------|

Das ist dann aber erst die Hälfte. Denn jetzt kommen noch Knoten A und D ins Spiel. A zeigt auf B und D auf E. Um die Knoten B und E zu tauschen, muß A auf E und D auf B zeigen. Wenn Du das geschafft hast und einfach den Zeigern folgst, erhältst Du

A -> E -> C -> D -> B -> F

[biene82]

Hallo Newlukai!

wow, das war wirklich eine schnelle antwort! :-)

so in etwa hatte ich mir das auch schon aufgemalt. es handelt sich übrigens um eine einfach verkettete liste.

kann ich das denn in nur einem programm schreiben? also in der main funktion? irgendwie blick ich da noch nicht so ganz durch :-) (sorry, bin newbie)

gruss

biene

[geloescht_Newlukai]

wow, das war wirklich eine schnelle antwort! :-)

np

es handelt sich übrigens um eine einfach verkettete liste.

Dann wird's etwas schwieriger, da Du dann vor dem Tauschen erst einmal durch die Liste "latschen" mußt, um die Knoten vor den zu tauschenden Knoten zu finden.

kann ich das denn in nur einem programm schreiben? also in der main funktion?

:confused:

Ach so. Du meinst, ob das in der main reicht?!? Naja. Wenn es nur eine Übung ist, sicher.

Eleganter ist natürlich eine Klasse Liste, die mehrere Knoten hat. Liste bietet dann noch eine Methode exchange(KnotenA, KnotenB) an, die dann das gewünschte fabriziert.

Streng genommen ist sogar Liste unnötig. Du benötigst ja eigentlich nur den Anfang der Liste.

Aber das sind alles listen-implementierungs-spezifische Geschichten. :hells:

irgendwie blick ich da noch nicht so ganz durch :-) (sorry, bin newbie)

Das waren wir alle mal. Es gibt keine doofen Fragen. Nur doofe Antworten

[biene82]

:-)

okay, wie ich die zuweisung der werte, also der zeiger hinbekomme, das sollte ich irgendwie schaffen. aber wie bzw. mit welchem c-befehl kann ich die liste durchlaufen?

das programm soll so ablaufen, dass der anwender 5 integer werte eingeben kann und anschließend auswählt, welche der werte "t" bzw. "u" sein sollen. dann soll das "vertauschen" erfolgen.

[Guybrush Threepwood]

Ist dir denn klar wie du die Verkettete Liste aufbauen musst?

Durchlaufen kannst du sie dann z.B. mit einer Schleife...

[geloescht_Newlukai]

Du sollst das ganze also in C implementieren (nicht C++?)?

Sorry, aber in C/C++ bin ich nicht ganz so fit. Vielleicht hakst Du da nochmal eher im entsprechenden Forum nach.

[Guybrush Threepwood]

bzw. gibt es da schon einiges drüber