C++ und verkettete Liste

Lazarus

Hallo habe ein Beispiel für eine verkettete Liste gefunden und irgenwie passt da etwas nicht glaube ich.

struct Stack {
  struct Link {
    void* data;
    Link* next;
    void initialize(void* dat, Link* nxt);
  }* head;                //hier ist der Knackpunkt*
  void initialize();
  void push(void* dat);
  void* peek();
  void* pop();
  void cleanup();
};

Wenn ich so eine Struktur definiere, dann wird doch jedes mal wenn ich eine erzeuge automatisch zusätzlich zu der erzeugten Struktur ein Zeiger von typ Link mit dem namen head angelegt.

Jetzt kommt die Methode um Elemente am Anfang hinzuzufügen

void Stack::push(void* dat) {
Link* newLink = new Link;
newLink->initialize(dat, head);
head = newLink;
}

So nun fordere ich Speicherplatz für eine neue Link Struktur an. Müsste dabei nicht automatisch wieder ein Zeiger auf die Struktur mit dem namen head erstellt werden? Der müsste doch denn den bisherigen Head irgendwie überschreiben. Zu dem macht das doch icht allzuviel sinn nachdem ich eine neue LinkStruktur erstellt habe mit einem wilden Pointer auf Strukturtyp die Struktur zu initialisieren.

Oder ist das so das dieser pointer gar nicht erstellt wird wenn der Speicher allociert wird?

Mir ist schon klar daß besser Klassen verwendet werden sollten aber auf so ein problem bin ich bisher nicht gestoßen.

das_brot

Nein, AFAIK ist einfach ein globaler Zeiger mit dem Namen "head" vorhanden. In diesem Beispiel wird wohl nicht damit gerechnet, dass mehrere Listen erstellt werden.

Ben04

Hier ist gar nix global.

head ist eine Membervariable von Stack. Ein einfacher Zeiger. Es zeigt auf das erste Element in einer verketteten Liste. push fügt am Begin der Liste ein Element ein. Also head zeigt auf das neue Element und das neue Element enthält den alten Wert von head. Wenn es nicht klar ist Papier nehmen und Pfeile zeichnen.

PS: Dein Beispiel ist nicht sehr gut von einem C++ Standpunk her. Such mal nach Konstruktor und Destruktor um initialize und cleanup zu ersetzen und nach Templates um den void* weg zu kriegen.

Lazarus

ich glaube da ist ein denkfehler. Nicht jedes mal wenn ich eine Struktur erzeuge wird dieser Pointer erzeugt sondern nur einmalig bei der Definition wird eine Variable vereinbart. Bei küntigen instanzierungen fällt die weg.

Ben04

Lazarus schrieb:

ich glaube da ist ein denkfehler. Nicht jedes mal wenn ich eine Struktur erzeuge wird dieser Pointer erzeugt sondern nur einmalig bei der Definition wird eine Variable vereinbart. Bei küntigen instanzierungen fällt die weg.

Also ich sehe nicht wo dein Problem ist. head ist ein Member von Stack. Wenn du mir das nicht glauben willst, dann lass mal dieses Program laufen

struct A
{
  struct B{}*b;
  void foo(){
    cout<<&b<<endl;
  }
};

int main()
{
  A a,b;
  a.foo();
  b.foo();
}

Konfusius

ich weiß jetzt nicht genau, was du meinst. aber ich versuche mal, es trotzdem zu erklären.

ein zeiger ist eine zahl, die eine speicheraddresse bezeichnet. eine zeigervariable ist ein speicherplatz von vier bytes, in den man einen zeiger ablegen kann. üblicherweise die startaddresse (addresse des ersten bytes) eines speicherbereiches. so ein speicherbereich wäre etwa der speicher deiner Link-struktur. wenn man nicht weiß, was für eine addresse man in eine zeigervariable eintragen soll, zb wenn man den speicherbereich, auf den die variable zeigen soll, noch nicht alloziert hat, dann wird per konvention eine null eingetragen. null bedeutet so viel wie "ich zeige im moment noch auf garnichts".

wenn du new Stack ausführst, dann gibt dir der befehl einen zeiger auf die neu erstellte Stack-struktur zurück. also eine zahl, die die addresse des ersten bytes des speicherbereichs, den new für dich alloziert hat, bezeichnet. in diesem speicherbereich befinden sich auch vier bytes für das feld head. da der new-befehl nicht weiß, was er da reinsetzen soll, hat er da einen null reingeschrieben. das head-feld der von new Stack gelieferten Stack-struktur zeigt also erst mal auf garnichts.

ich brech meine ausführungen jetzt ab, bevor ich hier noch endlos weiterlabere. vielleicht helfen dir ja meine "ausführungen", deine frage hier präziser zu stellen. weil das, was du geschrieben hast, kapiert nämlich kein mensch. du scheinst dich in irgendeinem parallelen c++-universum zu bewegen.

aber eins will ich noch sagen. als ich als jugendlicher auf einem zx81 das programmieren angefangen habe, hatte ich ein echtes problem damit, zu verstehen, was der befehl x=1 bedeuten sollte. ich war absolut unfähig, zu begreifen, warum x jetzt gleich eins sein sollte . so ein ähnliches problem scheinst du mit zeigervariablen zu haben.

so, jetzt ist aber endgültig schluß

EDIT
rechtschreibung korrigiert. soweit da überhaupt noch was zu retten ist