Hallihallo!
Ich hab schon wieder eine Frage.... Und zwar, wie erstellt man eine aufsteigend (oder absteigend- ist ja im prinzip egal) sortierte verkettete Liste?
Ich hab mir schon überlegt, dass wenn ich das erste Element als minimum setze und dann das nächste damit vergleiche und dann halt weiter so vorgehe (sprich das nächste Element mit dem letzten vergleiche), so ginge das nur in dem Fall, dass jedes neue Element wirklich kleiner ist als das letzte bzw. als das vorletzte. Aber sonst...
Am DI ist schon die Klausur und ich habe das Gefühl nicht sehr weit gekommen zu sein...
Danke im voraus für eure Hilfe!
Irina
Verkettete Listen
-
Irinita -
28. Juli 2004 um 21:16 -
Erledigt
-
-
Hallo,
ist schon eine Weile her, dass ich sowas mal gemacht habe und ich denke, es gibt auch noch bessere Algorithmen, aber hier mal einen Vorschlag.
Du baust zwei Listen auf. Die erste willst du sortieren und die zweite ist am Anfang leer. Nun suchst du das größte (bzw. kleinste) Element der vollen Liste.
Dieses Element setzt du an den Anfang der leeren Liste. Gleichzeitig löscht du das Element aus der anderen Liste, in dem du dem Vorgängerelement einen neuen Nachfolger gibst.
Nun suchst du wieder das größte (kleinste) Element und hängst dieses ans Ende deiner zweiten Liste. Aus der ersten Liste löschst du das Element wieder und setzt die Verknüpfungen neu. Dies machst du solange (While-Wend-Schleife) bis die erste Liste leer ist.Es gibt hier sicherlich auch noch einen rekursiven Algorithmus, der etwas effektiver ist, doch dazu fehlt mir im Moment die Zeit.
Viele Grüße
Jens
Webmaster http://www.bankstudent.de -
Hi!
Danke! Ist zwar wirklich ziemlich aufwendig, aber auf was besseres komme ich so wieso nicht. Jetzt aber eine ganz doove frage: Wie finde ich denn das größte element in der liste?!
lg
Irina -
Schade, dass ich das erst jetzt hier sehe. Ich studiere auch in Dortmund und kam gestern ebenso in den Genuß dieser Klausur. Ich hoffe das lief gut für dich. Ich beantworte deine Frage mal dennoch, in EDV ist die Wahrscheinlichkeit ja durchaus gegeben, dass man mehrmals ran muss:
Du brauchst eine weitere Variable desselben Datentyps neben Neu und Wurzel. Nennen wir sie mal größter. Zudem brauchst du noch eine weitere Variable, die genau vom selben Typ ist wie das was du suchst (Bei größtem Element also INTEGER oder REAL). Nennen wir diese Variable gwert.
gwert setzt du = 0.
Nun durchläufst du die Liste (angenommen der größte Wert ist im Record unter umsatz gespeichert):WHILE neu^.next <> NIL DO
BEGIN
IF neu^.umsatz > gwert THEN
BEGIN
größter := neu
gwert := neu^.umsatz
END;
neu := neu^.next;
END;Nachdem die liste Fertig durchlaufen wurde zeigt größter auf das Listenelement mit dem größten Umsatz.
-
Hallo,
ich glaube, dein Programm kann nicht ganz funktionieren. Die Schleife sucht nur das größte Element der Liste und macht nichts weiter.
Das könntest du jedoch auch einfacher haben, indem du deinen Quellcode wie folgt vereinfachst:größter:=0
while neu<>nil do begin
if neu^.umsatz>größter then größter=neu^.umsatz
neu:=neu^.next
end;das hat jedoch nicht mit dem Sortieren einer Liste zu tun.
Viele Grüße
Jens
Webmaster http://www.bankstduent.de -
Mein Code bezog sich auch nur auf das Finden des größten Umsatzes, also die Frage von Irinita im 3. Beitrag dieses Threads. Beim sortieren würde ich genauso vorgehen wie du das schon vorgeschlagen hast. Hab jetzt aber auch nicht die Zeit mich dafür mit den vielen Laufzeigern rumzuschlagen. Übrigens Irinita, wie man eine fertige Liste sortiert kam auch in einer Vorlesung dran.
-
Ok, dann passt es. Nur der Code kann dann noch etwas kürzer formuliert werden (siehe letzter Beitrag von mir). Das ganze mit der kompletten Liste wollte ich mir auch sparen, aus dem gleichen Grund wie du.
Bin ja nicht mal Informatiker (nur seit 14 Jahren Programmierer) und ansonsten seit einem Jahr auch schon aus meinem WiWi-Studium raus. Habe hier also eigentlich kaum noch was verloren (das einzige was noch passt ist das Alter).
Viele Grüße
Jens
Webmaster http://www.bankstudent.de