Geschwindigkeit einer verketteten Liste optimieren
-
Hallo zusammen,
Also erst mal ne Frage:
Wie kann eine verkettete Liste mit der C-Funktion qsort() durchsuchen ?DANN:
Also wenn ich ein Element in einer verketteten Liste ermitteln möchte, das bspw. an Position 34 steht (insgesamt 3000 Elemente) muss ich doch von vorne oder hinten (hier: sinnvollerweise von vorne) bis zu diesem Element durchgehen oder?
Bietet sich da nicht dann eher ein Array an ?DAnke für Antworten...
MfG CodeFinder
-
CodeFinder schrieb:
Also erst mal ne Frage:
Wie kann eine verkettete Liste mit der C-Funktion qsort() durchsuchen ?Garnicht, da qsort nicht sucht, sondern sortiert (komisch eigentlich, bei dem Namen :D) - aber selbst wenn Du sortieren möchtest, kann qsort dass nur auf Arrays, also wenn alle Elemente in zusammenhängendem Speicher liegen.
Also wenn ich ein Element in einer verketteten Liste ermitteln möchte, das bspw. an Position 34 steht (insgesamt 3000 Elemente) muss ich doch von vorne oder hinten (hier: sinnvollerweise von vorne) bis zu diesem Element durchgehen oder?
Ja.
Bietet sich da nicht dann eher ein Array an ?
Ja.
(Allerdings, wenn Du bei bspw. 100 Elementen nur einmal Indexieren und dann zehnmal in der Mitte etwas einfügen musst, solltest Du schon lieber bei der Liste bleiben - alles Sache der Anwendung)
-
CodeFinder schrieb:
Also erst mal ne Frage:
Wie kann eine verkettete Liste mit der C-Funktion qsort() durchsuchen ?Gar nicht. qsort operiert nicht auf listen und außerdem sucht es nicht, sondern (oha, wer hätte's gedacht) sortiert ein Array.
DANN:
Also wenn ich ein Element in einer verketteten Liste ermitteln möchte, das bspw. an Position 34 steht (insgesamt 3000 Elemente) muss ich doch von vorne oder hinten (hier: sinnvollerweise von vorne) bis zu diesem Element durchgehen oder?jap.
Bietet sich da nicht dann eher ein Array an ?
Du musst auch beim Array sequentiell durchgehen (außer es ist sortiert, dann kannst du mit binarysearch drüber).
Wenn du oft aus deiner Datenstruktur löschst/einfügst (besonders in der Mitte), dann ist eine Liste besser geeignet.Welche Anforderungen hast du denn sonst an die Datenstruktur? CStoll hat in seinem Artikel was hilfreiches geschrieben.
MfG
GPC
-
hähä, jo danke erstmal...
das qsort sortiert und nicht sucht is mir klar..vertippt
hmm also ich schreib n Media Player, der ne Playlist enthalten soll...
Bisher implementier ich die inner verket. Liste...
Dann müsste ich also die ganzen 'Einträge' erst inn Array packen, das mit qsort sortieren
und dann wieder 'verketten' ... oha
gibt da noch ne andere Möglichkeit ?... danke!
MfG CodeFinder
-
CodeFinder schrieb:
hähä, jo danke erstmal...
das qsort sortiert und nicht sucht is mir klar..vertippthehe, ja ja...
gibt da noch ne andere Möglichkeit ?... danke!
Wie wär's, wenn du die Liste sortierst?
MfG
GPC
-
Nimm dir die STL-list<> für deine Datenstruktur - die hat eine eigene sort()-Methode dafür.
-
hmm...
STL-list<>
aha...^^ kannste da vll. n paar Takte zu sagen...noch nie gehört...welche Header/Libs... Doku. ?
DANKE!!
MfG CodeFinder
-
An Headern benötigst du nur <list> (gehört zum ANSI Standard), an Dokus empfehle ich den Artikel, den GPC freundlicherweise verlinkt hat, und notfalls noch www.cppreference.com
-
CodeFinder schrieb:
hmm...
CStoll schrieb:
STL-list<>
aha...^^ kannste da vll. n paar Takte zu sagen...noch nie gehört...welche Header/Libs... Doku. ?
Den Link vorher hast du nicht beachtet, heh? Wir wär's mit n bisschen mehr Initiative?
GPC schrieb:
CStoll hat in seinem Artikel was hilfreiches geschrieben.
eeh, zu lahm...
-
ok danke
MfG CodeFinder