sind die wichtig?

Hi,
mal ne Frage.
Muss jeder C++ Programmierer Verkettete Listen (Knoten) können?
Ich verstehe das einfach nicht. kA warum.
Oder ist das nicht so schlimm wenn ich das Thema überspringe ?

langeweile

Listen schrieb:

Hi,
mal ne Frage.
Muss jeder C++ Programmierer Verkettete Listen (Knoten) können?
Ich verstehe das einfach nicht. kA warum.
Oder ist das nicht so schlimm wenn ich das Thema überspringe ?

Ich hab sie wirklich lange nicht gebraucht, aber wenn man dann anfängt komplexe Algorithmen zu schreiben, ist's irgendwie schon praktisch... :p

Skym0sh0

naja man sollte das prinzip schon verstanden haben

ich selbst weis was es ist und wie es ugefähr geht
aber selbst geschrieben hab ich sowas noch nicht...

Nexus

Wenn du das Prinzip verstehst, schadet das sicher nichts.
Aber ich denke, du wirst relativ lange ohne sie auskommen, da gibt es beispielsweise auch noch die STL-Liste ( std::list<> ), die eigentlich alles für dich erledigt. Eventuell ist es jedoch auch bei deren Benutzung vorteilhaft, wenn du ungefähr weisst, was intern abläuft.

*D*

Du solltest es dir vielleicht mal durchlesen, dass du einen groben Überblick
hast, wie sie funktionieren. Aber selber programmieren musst du normalerweise
so etwas nie! Wozu gibt es den die STL???

Konrad Rudolph

Nexus schrieb:

Wenn du das Prinzip verstehst, schadet das sicher nichts.
Aber ich denke, du wirst relativ lange ohne sie auskommen

Vergiss es. Wer das Konzept verketteter Listen nicht versteht, versteht auch das Konzept von Zeigern allgemein nicht. Das wird nichts.

PS: http://cslibrary.stanford.edu/104/

Nexus

Konrad Rudolph schrieb:

Nexus schrieb:

Wenn du das Prinzip verstehst, schadet das sicher nichts.
Aber ich denke, du wirst relativ lange ohne sie auskommen

Vergiss es. Wer das Konzept verketteter Listen nicht versteht, versteht auch das Konzept von Zeigern allgemein nicht. Das wird nichts.

Das sehe ich aber anders. Zuerst sollte man das Prinzip der Zeiger allgemein lernen. Denn die verketteten Listen sind nur ein Spezialfall, den man nicht unbedingt selber zu implementieren braucht. Und wenn man versteht, wie ein Zeiger im Allgemeinen funktioniert, ist es auch nur noch ein kleiner Schritt, bis man die Funktionsweise von verketteten Listen versteht.

Aber die verketteten Listen sind nicht für das Verständnis von Zeigern erforderlich. Umgekehrt jedoch schon.

Konrad Rudolph

Nexus schrieb:

Konrad Rudolph schrieb:

Nexus schrieb:

Wenn du das Prinzip verstehst, schadet das sicher nichts.
Aber ich denke, du wirst relativ lange ohne sie auskommen

Vergiss es. Wer das Konzept verketteter Listen nicht versteht, versteht auch das Konzept von Zeigern allgemein nicht. Das wird nichts.

Das sehe ich aber anders. Zuerst sollte man das Prinzip der Zeiger allgemein lernen. Denn die verketteten Listen sind nur ein Spezialfall, den man nicht unbedingt selber zu implementieren braucht. Und wenn man versteht, wie ein Zeiger im Allgemeinen funktioniert, ist es auch nur noch ein kleiner Schritt, bis man die Funktionsweise von verketteten Listen versteht.

Eben. Wenn man Zeiger richtig verstanden hat, versteht man verkettete Listen automatisch. Wenn man die nicht versteht, hat man Zeiger auch nicht verstanden.

Jeder Anfänger kann in der Zeit, die ihr mit dieser sinnlosen Diskussion vertut mehrere Listen schreiben ...

Es ist nicht das schwerste Kapitel also machs halt einfach.

@Nexus: Du bist sicher ein Profi und kannst dich nicht mehr zurückerinnern, jedoch braucht ein Anfänger Praxis, welche eine Liste hervorragend abdeckt.

Nexus

Konrad Rudolph schrieb:

Eben. Wenn man Zeiger richtig verstanden hat, versteht man verkettete Listen automatisch. Wenn man die nicht versteht, hat man Zeiger auch nicht verstanden.

Okay, dann habe ich dich falsch verstanden.

gähn schrieb:

@Nexus: Du bist sicher ein Profi und kannst dich nicht mehr zurückerinnern, jedoch braucht ein Anfänger Praxis, welche eine Liste hervorragend abdeckt.

Ein Profi bin ich noch lange nicht
Aber es stimmt, gerade am Anfang bringt es einem relativ viel an Erfahrung, wenn man eine eigene verkettete Liste schreibt (ich hab das zwar nie selber gemacht, aber ich kann es mir gut vorstellen). Zeiger sollte man generell nicht unterschätzen, man wird sie immer wieder antreffen.

@ Listen:
Kennst du dich mit Zeigern aus? Du solltest diese vielleicht noch einmal genau anschauen, dann wirst du auch verkettete Listen verstehen.
Und falls du denkst, du beherrschst Zeiger, dann stell doch einfach eine konkrete Frage, was du an den verketteten Listen nicht verstehst.

Hey,

stell dir die verkettete Liste einfach wie ein Raum mit Türen vor.

Der Raum enthält die Daten. Die Tür ist der Zugang zum nächsten Raum(=den nächsten Daten). Bei einer einfach verketteten Liste ist jedoch nur auf der einen Seite eine Klinke, dass bedeutet du kannst immer weiter nach vorne gehen, aber nicht mehr zurück:

|-----|-----|-----|-----|-----|-----|
|  -> '  -> '  -> '  -> '  -> '     |
|-----|-----|-----|-----|-----|-----|

Jetzt setz das ganze in Programmcode um:

struct Data
{
  int val; // Daten
  Data *next; // nächster Raum
};

Data entspricht dem Raum. Die Tür ist einfach ein Zeiger auf einen weiteren Raum.

Du willst also jetzt z.B. in den zweiten Raum und dort den Wert von val auslesen:

std::cout << meineListe->next->next->val << std::endl; // Der Wert von val im zweitem Raum.

Das "komplizierte" ist dabei einfach dafür zu sorgen, dass man alle Elemente richtig initalisiert(new) und wieder löscht(delete).

Ich hoffe, dass konnte dir ein bisschen weiterhelfen. Wenn du eine doppelt verkettete Liste(=man kann sowohl vorwärts als auch rückwärts in der Liste gehen) haben willst, musst du noch eine weitere Tür einbauen, welche in die andere Richtug aufgeht:

|-----|-----|-----|-----|-----|-----|
|  -> '  -> '  -> '  -> '  -> '     |
|     |     |     |     |     |     |
|     ' <-  ' <-  ' <-  ' <-  ' <-  |
|-----|-----|-----|-----|-----|-----|

Jetzt setz das ganze wieder in Programmcode um:

struct Data
{
  int val; // Daten
  Data *next; // nächster Raum
  Data *prev; // vorheriger Raum
};

Versucht erstmal eine einfach verketete Liste selber zu schreiben. Viel Erfolg!!!

drakon

@Sonnenstrahl:
Sehr schöne Erklärung und auch sehr anschaulich.
Ich denke, dass er das Prinzip so gut versteht, denn ich denke auch, dass es gut ist die Arbeitsweise einer Liste zu verstehen, ansonsten hat man auch noch Mühe mit Iteratoren usw.

Nanyuki

Vielleicht sollte man noch erwähnen, dass sich in jedem Türrahmen noch ein Warpportal befindet, das einen dann zum nächsten/vorherigen Raum bringt, wodurch die Räume sich an beliebigen Orten befinden können. Das ganze hat den Vorteil, dass man nicht die Hälfte der Räume abreißen und dann eine Stelle weiter neu aufbauen muss, wenn man in der Mitte mal einen Raum weghaben will. Stattdessen muss man nur den einen Raum abreißen und zwei der Portale umprogrammieren.

drakon

Nanyuki schrieb:

Vielleicht sollte man noch erwähnen, dass sich in jedem Türrahmen noch ein Warpportal befindet, das einen dann zum nächsten/vorherigen Raum bringt, wodurch die Räume sich an beliebigen Orten befinden können. Das ganze hat den Vorteil, dass man nicht die Hälfte der Räume abreißen und dann eine Stelle weiter neu aufbauen muss, wenn man in der Mitte mal einen Raum weghaben will. Stattdessen muss man nur den einen Raum abreißen und zwei der Portale umprogrammieren.

Das ist jetzt aber schon recht abstrakt. Ich denke, dass ihn das noch mehr verwirren könnte..
(Dennoch auch sehr schön formuliert. ^^)

also ich hab mir das nochmal genauer angeschaut.
Was ich nicht verstehe ist wie
Data *next; // nächster Raum
man mit next auf den nächten Raum kommt.
Der zeigt doch gar nicht auf ein nächstes Element oder so

Doch, dafür ist der Zeiger ja da, er speichert die Speicheradresse des nächsten "Raumes" und wenn du ihn dereferenzierst kommst du an den nächsten "Raum" ran.