verkettete liste ...

$nooc

Alter Hase

Beiträge: 873

Wohnort: Österreich / Kärnten

Beruf: Schüler

41

12.03.2007, 10:09

achso

omg ich stand auf der leitung! ok jetzt isses klar! danke dir

edit:
das einzige was mich so verwirrt hat, war das "shall" ..

Am Anfang der Weisheit steht die eigene Erkenntnis, dass man selbst nichts weiß! - Sokrates

Zum Seitenanfang

$nooc

Alter Hase

Beiträge: 873

Wohnort: Österreich / Kärnten

Beruf: Schüler

42

12.03.2007, 10:21

jetzt hätte ich da noch eine weitere frage, um die zugriffsgeschwindigkeit zu erhöhen!

zur zeit sehen die elemente so aus

	C-/C++-Quelltext
1 2 3 4 5 6 7 8	inline struct Element { unsigned long m_ID; int m_Value; Element m_pPrevElement; Element m_pNextElement; }; // Element

einfach ein struct (beinhaltet halt noch nix außer int m_Value

!
im moment kann ich auf element Nr. 50 von 100 Elementen nur zugreifen, wenn ich eben in einer schleife alle elemente durchlaufe, und immer die m_ID; überprüfe.. naja.. also bei 1.000.000 Elementen gibts eig. keine probleme, funktioniert meiner meinung nach sogar überraschend schnell, aber ich bin mir sicher es gibt ne schnellere lösung!

mal angenommen mein struct sieht so aus:

	C-/C++-Quelltext
1 2 3 4 5 6 7	inline struct Element { Data MyData; Element m_pPrevElement; Element m_pNextElement; }; // Element

und ich hab so 100 Elemente miteinander verkettet!
wie könnte ich so schnell es geht auf Element Nr. 50 zugreifen?

Am Anfang der Weisheit steht die eigene Erkenntnis, dass man selbst nichts weiß! - Sokrates

Zum Seitenanfang

Beliah

Treue Seele

Beiträge: 115

Wohnort: Söhlde - LK Hildesheim

Beruf: FI-Anwendungsentwicklung

43

12.03.2007, 10:27

Lies einmal das durch und dann überleg nochmal ob du einen vector oder eine liste willst.

Debuggers don't remove bugs, they only show them in slow motion.

Google Suche ohne Werbung und Cookies: Scroogle

Derzeitige(s) Freizeitprojekt(e)

Zum Seitenanfang

$nooc

Alter Hase

Beiträge: 873

Wohnort: Österreich / Kärnten

Beruf: Schüler

44

12.03.2007, 10:36

ja wie man sieht habe ich mich eben für die doppelte verkettete liste entschieden.

	C-/C++-Quelltext
1 2 3 4 5 6 7	inline struct Element { Data MyData; Element m_pPrevElement; Element m_pNextElement; }; // Element

oder hab ich was falsch verstanden?

die klasse die ich geschrieben habe funktioniert im großen und ganzen wie ich es will! ich kann elemente irgendwo in der liste reingeben, oder auch rausnehmen, und die elemente zeigen der reihe nach immer auf das element davor und danach.

Am Anfang der Weisheit steht die eigene Erkenntnis, dass man selbst nichts weiß! - Sokrates

Zum Seitenanfang

big_muff

Alter Hase

Beiträge: 460

Wohnort: Schweiz

Beruf: Informatikstudent (4. Semester)

45

12.03.2007, 10:46

Es gibt nun mal verschiedene Datenstrukturen und die haben alle Ihre Vor- und Nachteile. Der Vorteil einer doppelt verketteten Liste ist das man sehr schnell Elemente am Anfang, am Ende oder vor oder nach einem beliebigen anderen Eintrag einfügen oder entfernen kann. Der Nachteil ist halt das der Zugriff auf einzelne Elemente nicht sehr effektiv implementiert werden kann. Eine Liste eignet sich deshalb überall dort, wo oft neue Elemente hinzukommen und wo die Elemente im Allgemeinen durchlaufen werden (zum Beispiel eine Liste mit den darzustellenden Objekten in einer 3D-Anwendung, wo man alle nacheinander durchgeht und darstellt). Ein Vektor (=dynamisches Array, siehe std::vector im C++-Buch deiner Wahl) dagegen hat extrem schnelle Zugriffe an irgendeinem Ort, dafür kann das hinzufügen oder entfernen neuer Elemente unter umständen sehr lange dauern.

Nur Idioten halten Ordnung, ein Genie beherrscht das Chaos.[size=7]

[/size]HardFate - Ein Start, Ein Ziel, Viele Wege[size=7]

[/size]Ein Mitglied der VEGeiCoUndGraSonMaWiGeS Bewegung.

Zum Seitenanfang

Beliah

Treue Seele

Beiträge: 115

Wohnort: Söhlde - LK Hildesheim

Beruf: FI-Anwendungsentwicklung

46

12.03.2007, 10:49

Ich meine das hier:

Zitat

[...]
Nachteile

* Es ist aufwändig nach Daten zu suchen, Knoten einzufügen, zu löschen und die Liste zu sortieren, da über jedes einzelne Element gegangen (iteriert) werden und das Einfügen an der ersten und der letzten Stelle gesondert behandelt werden muss.
[...]

Und das liegt daran das bei einer verketteten Liste die Elemente nicht, wie bei einem vector, hintereinander im Speicher liegen. Deswegen muss man ja einen Zeiger auf das vorherige (und nächste) Element speichern.

Dafür ist aber ein Hinzufügen am Anfang (und Ende) schneller da nicht, wie bei einem vector, die komplette Liste in einen größeren freien Speicherbereich kopiert werden muss falls der freie Speicher nach dem letzen Element nicht mehr ausreicht.

€
big_muff war schneller

Debuggers don't remove bugs, they only show them in slow motion.

Google Suche ohne Werbung und Cookies: Scroogle

Derzeitige(s) Freizeitprojekt(e)

Zum Seitenanfang

$nooc

Alter Hase

Beiträge: 873

Wohnort: Österreich / Kärnten

Beruf: Schüler

47

12.03.2007, 11:22

ok ich denke ich habs gecheckt! d.h. bei einer verketteten liste ist es eben der nachteil dass man ein element in der mitte eben nicht besonders schnell zur hand bekommt, dafür aber recht schnell ein element am anfang bzw. ans ende einfügen kann! ok .. aber wenn ich jetzt eben ein element in der mitte der liste einfügen will.. ist es dann nicht etwas lahm wenn ich in einer schleife bis zu entsprechenden stelle laufe und dann das element einfüge? bei vielen elementen muss ich dann ja trotzdem irgendwie zum element in der mitte kommen.. versteht ihr was ich eigentlich meine?