dynamische liste von longs
-
Hallo - eigentlich eine simple frage
was verwende ich am bessten um eine menge von long zahlen zu speichern.
da die anzahl unbekannt ist, hab ich mir gedacht ich muss mir wohl eine linked list selber basteln.also struct long pointer next usw..
allerdings würde ich zahlen dann gerne mit qsort sortieren.
Die fragen ist jetzt - gibt es eine bessere methode eine dynamische liste von longs zu speichern, bzw. kann ich so eine linked list dann mit qsort sortieren?
lg
Verucca
-
Warum muss es eine LinkedList sein? Warum nicht einfach ein dynamisches Array erstellen. Damit funktioniert qsort auf jeden Fall.
-
Wenn oft mittendrin was eingefügt wird, dann verkettete Liste aber mit sortiertem Einfügen. Dann spart man sich das Sortieren (der kompletten Liste) gleich.
Ansonsten wie feigling schon sagte.
-
ja ich könnte ein dynamische array versuchen.
du meinst mit realloc das array immer wieder vergrößern.
meine aufgabe ist eigentlich ein client programm das longs einließt über einen shared memory an ein server programm schickt und dann wenn alles eingelesen ist, sortiert der server die longs und schickt das ganze wieder über den shared memory zurück zum client.
der gibts dann aus.
ausserdem soll der server mit qsort sortieren.relativ schlecht finde ich natürlich, wenn der server ein long vom shared memory liest jedesmal mit realloc das array zu erweitern.
ich könnte natürlich erstmal 100 longs anfordern und wenn nötig erweitern - am schluss der eingabe mit realloc das auf die richtige größe reduzieren und dann den qsort drüber fahren lassen. ( schon etwas besser ).aber ganz zufreiden stellen tut mich die lösung auch ned - aber ja ich denk irgendwie so werde ich das machen.
da ich nicht genau weiß ob qsort eine linked list sortieren könnte verwende ich einfach ein array :)..
lg
Verucca
-
Quicksort funktioniert auf linked lists nicht, aus offensichtlichen Gründen. Naja - man kanns wohl emulieren, aber das Laufzeitverhalten wird dadurch trotzdem beeinträchtigt - random access skaliert auf ner Liste halt mit O(n) statt mit O(1) wie in einem Array. Und qsort aus der Standardbibliothek frisst sowieso nur Arrays.
Ich denke, in diesem Szenario bietet sich ein binärer Baum an - also direkt sortiert einfügen.
-
ich bin fuer selbst-balancierende baeume
-
balanced bäume
na ich denk mal das ist etwas überzogen.
ausserdem halte ich mich lieber an die angabe - ich studier im nebenfach informatik und das ist halt eine übungsaufgabe in c.da in der angabe steht ich soll qsort verwenden, werde ich wohl in den shared memory ein long zulassen, das vom server jedesmal ausgelesen wird und in ein array eingetragen ( mit realloc ).
und dann das ganze mit qsort sortieren und wieder zurück über den gleichen weg.ist natürlich eine dumme aufgaben aber man soll ja was lernen
lg
Verucca