Variable vom Typ einer eigenen Klasse in Klasse selbst definieren

  • C++/CLI

Es gibt 14 Antworten in diesem Thema. Der letzte Beitrag () ist von TheVBTutorialsVB.

    Variable vom Typ einer eigenen Klasse in Klasse selbst definieren

    Hallo,

    ich versuche aktuell einen eigenen Stack in C++ zu implementieren. Dazu habe ich eine Klasse "Node" (Knoten), die eine Variable hat, die ebenfalls vom Typ Node ist und den Nachfolger von des Knotens darstellt, sodass ich einen Anfangsknoten habe, von dem aus alle andere Knoten ausgehen. Mein Problem ist jetzt, dass ich in meiner Klasse Node keine Variable des Typ Node definieren kann ohne die Fehlermeldung "ein unvollständiger Datentyp ist nicht zulässig" zu erhalten. Ich habe versucht das Problem zu lösen, indem ich statt eines Nachfolgerknoten einen Pointer auf den Nachfolgerknoten erstellt habe. Die Fehlermeldung verschwindet, allerdings kann ich den Pointer nicht mit new initialisieren. Wie kann ich also eine Variable des Typ Node in meiner Klasse Node selbst definieren?

    C-Quellcode

    1. class Node
    2. {
    3. private:
    4. int value;
    5. Node next; //Fehlermeldung "unvollständiger Datentyp ist nicht zulässig"
    6. //Node * next gibt keine Fehlermeldung
    7. public:
    8. Node();
    9. ~Node();
    10. void set_next(Node node);
    11. Node get_next();
    12. void set_value(int val);
    13. int get_value();
    14. bool has_next;
    15. };


    C-Quellcode

    1. #include "Node.h"
    2. Node::Node()
    3. : has_next(false)
    4. {
    5. next = new Node(); //wenn ich "next" als Pointer definiert habe gibts hier einen Stack overflow
    6. }
    7. Node::~Node()
    8. {
    9. }
    10. void Node::set_next(Node node)
    11. {
    12. *next = node;
    13. has_next = true;
    14. }
    15. Node Node::get_next()
    16. {
    17. return *next;
    18. }
    19. void Node::set_value(int val)
    20. {
    21. value = val;
    22. }
    23. int Node::get_value()
    24. {
    25. return value;
    26. }

    Ergibt Sinn mit dem StackOverflow oder? Hab kaum Ahnung von C++, aber wenn du einen Node initialisiert, der im ctor einen Node initialisiert, der im ctor einen Node initialisiert, der im ctor.... Du verstehst was ich meine.
    Erst ein Childnode hinzufügen, wenn es einen geben soll.
    Warum das nur mit Pointern funktioniert, kann ich dir nicht beantworten.

    Btw: Was haben Nodes mit einem Stack zu tun?
    »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais
    In C++ gibt es zwischen class und struct nur den Unterschied, dass in structs standardmäßig alles public ist und in classes alles private.
    Ansonsten funktionieren classes und structs in C++ so wie structs in C#. Und dass in C# struct Foo { Foo f; } keinen Sinn macht, weil sich die Struktur selbst beinhalten müsste, sollte klar sein.
    Mit einem Pointer funktioniert es, weil ein Pointer eine bekannte Größe hat (4 oder 8 Bytes, typischerweise). Ein Node* funktioniert genauso wie ein int*, float*, unsigned char* oder void*. Es sind alles nur Pointer.

    Um es verständlicher zu erklären:
    Stell dir diese C++ klasse bzw. structure vor:

    Quellcode

    1. class Foo
    2. {
    3. int a;
    4. float b;
    5. Foo c;
    6. }

    Der Compiler muss Arbeitsspeicher reservieren, wenn man z.B. eine Variable vom Typ Foo deklariert. Wie viel Arbeitsspeicher? Gucken wir uns das mal an:
    Nehmen wir mal an, wir mallocen Speicher im Heap, weil wir da ein Objekt von irgend einem Typen drin ablegen wollen.
    Nehmen wir auch einfach mal an, der zurückgegebene Pointer zeigt zu 0xd00f0000.
    Wäre das Objekt, das wir ablegen möchten, ein int, müssten wir 4 Bytes reservieren: 0xd00f0000, 0xd00f0001, 0xd00f0002 und 0xd00f0003. Denn sizeof(int) ist 4. (Ich gehe jetz mal von sinnvollen Größen aus. ist natürlich compilerabhängig und weißgottwas bei C++.)
    Aber wir möchten ein Foo ablegen. Wie viele Bytes müssen wir reservieren? Wir wissen die Größen von a und b. Beides 4 Bytes.

    Quellcode

    1. 0xd00efffe ...
    2. 0xd00efffe Anderes Zeugs
    3. 0xd00effff Anderes Zeugs
    4. 0xd00f0000 a 4 Bytes für den int
    5. 0xd00f0001 a
    6. 0xd00f0002 a
    7. 0xd00f0003 a
    8. 0xd00f0004 b 4 Bytes für den float
    9. 0xd00f0005 b
    10. 0xd00f0006 b
    11. 0xd00f0007 b
    12. 0xd00f0008 c ? Aber wie viele Bytes für Foo?
    13. 0xd00f0009 c ?
    14. 0xd00f000a ...

    Foo besteht aus 4 Bytes für a + 4 Bytes für b + wie viele Bytes halt für Foo rauskommen. Eine Rekursion!

    Quellcode

    1. sizeof(Foo) = sizeof(int) + sizeof(int) + sizeof(Foo)
    2. sizeof(Foo) = 4 + 4 + sizeof(Foo)
    3. sizeof(Foo) = 8 + sizeof(Foo) | -sizeof(Foo)
    4. sizeof(Foo) = 8
    5. sizeof(Foo) - sizeof(Foo) = 8
    6. 0 = 8

    Es gibt keine Lösung für sizeof(Foo).

    Verwendest Du dagegen einen Pointer, ist alles OK. Pointer sind immer 4 Bytes groß (oder 8 Bytes auf 64-Bit Plattformen, oder wofür auch immer sich C++ entscheided).

    Quellcode

    1. sizeof(Foo) = sizeof(int) + sizeof(int) + sizeof(Foo*)
    2. sizeof(Foo) = 4 + 4 + 4
    3. sizeof(Foo) = 12

    Foo ist also in diesem Fall 12 Bytes groß.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils
    @TheVBTutorialsVB: Wie @Plexian schon mit seiner Abschlussfrage andeutete: Was Du bauen willst, hat eher was von ner ne Linked List.

    Aber egal, welches Kostrukt das wird, hat Dein bisheriger Code einen Knackpunkt: Wenn Du jetzt vom ersten Item (Du nennst es Node, ist aber in diesem Fall eher ein irreführender Begriff) auf das nächste per get_next() zugreifst, hast Du keinen Bezug mehr zum ersten. Das erste Item wäre im MemoryNirvana verloren. Es sei denn, dass alle Nodes in einer Liste wären. Doch dann bräuchtest Du keine Verbindung zwischen den einzelnen Items.

    Wenn es also wirklich ein Stack werden soll, wär also sinnvoll, ein neues Item zu erstellen, das Next-Item als pointer zu belassen, damit auf das vorherige/bisher oberste Item zu verweisen und dir als Zusatzvariable das oberste Item zu merken.
    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „VaporiZed“, mal wieder aus Grammatikgründen.

    Aufgrund spontaner Selbsteintrübung sind all meine Glaskugeln beim Hersteller. Lasst mich daher bitte nicht den Spekulatiusbackmodus wechseln.

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „VaporiZed“ ()

    @Niko Ortner Wie könnte ich dieses Problem umgehen? Ich benötige eben eine Klasse die einen solchen Knoten darstellt, um eben eine verkettete List (ja ich meinte Liste nicht Stack, mein Fehler) zu realisieren. Bei uns in der Schule hatten wir mal so eine Liste in Delphi (ja ich weiß Delphi..) umgesetzt und dort ging das ohne Probleme. Wie könnte ich diesen Fehler umgehen?

    Vielleicht hilft Dir ja neben den bisherigen Hinweisen auch Volkards C++ Kurs im entsprechenden Kapitel über verkettete Listen weiter. Vor 15 Jahren hab ich damit meine ersten C++-Erfahrungen gesammelt.
    Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „VaporiZed“, mal wieder aus Grammatikgründen.

    Aufgrund spontaner Selbsteintrübung sind all meine Glaskugeln beim Hersteller. Lasst mich daher bitte nicht den Spekulatiusbackmodus wechseln.
    @TheVBTutorialsVB
    Verwende einen Pointer.

    Quellcode

    1. class Node
    2. {
    3. public:
    4. Node* Next;
    5. }
    6. Node* Root = new Node();
    7. Root.Next = new Node();
    8. Root.Next.Next = new Node();
    9. Root.Next.Next.Next = new Node(); // Und so weiter.
    "Luckily luh... luckily it wasn't poi-"
    -- Brady in Wonderland, 23. Februar 2015, 1:56
    Desktop Pinner | ApplicationSettings | OnUtils
    @Niko Ortner danke <3

    Edit: Kriege trotzdem noch einen Stack overflow sobald ich einen Node in meiner main-Funktion anlege. Der Konstruktor der Node-Klasse ist leer und ich habe next mit new initialisiert.

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „TheVBTutorialsVB“ ()

    Du gehst das ganze falsch an.
    Zunächst teile alles auf was eine LinkedList ausmacht.
    Für eine Liste ist das zunächst folgendes:

    1. Sie kann dynamisch viele Elemente beinhalten
    2. Man kann auf jedes Element von aussen zugreifen

    Speziell für eine LinkedList ist die interne Implementierung für (1) vorgegeben:

    3. Es gibt eine Referenz an die jeweils nächste Referenz (eine Kette).

    Damit gilt insbesondere:

    Kennt man das erste Element, kennt man alle Elemente.

    Somit kann man sich mit etwas überlegung auf folgendes einigen:

    Es gibt eine Klasse LinkedList die eine nested klasse Node besitzt. Die LinkedList hat eine Referenz auf ein Node objekt (undzwar auf das erste). Node ist eine zusammengesetzte Klasse aus dem zu speichernden Wert und der Referenz zum nächsten Node.

    Nun ist es möglich die Kette von Anfang bis Ende zu durchlaufen. Jetzt überlegst du dir, welche Methoden du implementieren möchtest. Grundsätzlich sind da natürlich add , getNext, remove u.ä.

    Dann fängst du bei getNext an. Zuerst die Frage, was kann da alles schief gehen?
    1. Die Liste ist leer. Dann ist Node = null
    2. Man ist am letzten Element angelangt. Dann ist Node.getNext () gleich null.

    Wie kann man diese Probleme umgehen?
    Dazu muss man natürlich erstmal wissen, was bedeutet "am letzten Element angelangt".

    Dazu kann man sich überlegen, dass die LinkedList den aktuellen Node speichert. Das kann man auch auslagern, nennt sich Iterator Entwurfsmuster, so dass eine extra Klasse angelegt wird die einmal die Kette (den Anfangsknoten) als Referenz erhält und einmal den aktuelle Node sich merkt. Dann muss die LinkedList nur noch eine Instanz dieser Klasse über eine Methode nach aussen zurückgeben sodass von ausserhalb über die LinkedList iteriert werden kann ohne über die interne Struktur von der LinkedList bescheid zu wissen (Node Klasse usw.).

    Wenn man dies in eine externe Klasse ausgelagert hat, kommt man zurück zu den vorhin erwähnten Problemen. Diese löst man durch explizites Abfragen:

    Zeigt die aktuelle Node Referenz auf etwas? Nein -> man ist am Ende (bei einer leeren Liste eben direkt)
    Ja -> Dann gib den Wert von aktuelle Node zurück und setze aktuelle Node auf die nächste Referenz auf die es zeigt.

    Damit hast du schonmal getNext fertig.

    Für add und remove sind die Überlegungen analog.

    add -> normalerweise ans Ende der Liste.
    Man kann nun jedesmal die komplette Liste durchlaufen (vom anfang an) und wenn man dann ein Node mit getNext () = null hat dieses auf ein neuen Node mit dem in add übergebenen Wert setzen oder wenn einem.effizienz etwas wichtig ist dann speichert man nun auch den letzten Node in der Kette d.h. eine Referenz auf das letzte Node Element sodass add (n) statt linearer zeit nur noch Konstante Zeit benötigt (Theta(n) zu Theta (1)).
    @RushDen Ich weiß schon selbst wie ich eine Liste implementiere. Das was du geschrieben hast hat überhaupt nichts mit dem Problem zu tun, dass ich einen Stack overflow bekomme wenn ich new Node() aufrufe.

    Natürlich hat es das, weil das was du machst keinen Sinn macht. Wieso erstellst du bei get_next () ein neues Node objekt? Das ist konzeptionell schonmal blödsinn.
    Außerdem schreibst du was von dee main funktion, dann poste den Code von der main funktion damit man sehen kann wo der fehler ist wegen stackoverflow
    @RushDen
    Wieso erstellst du bei get_next () ein neues Node objekt?


    Tue ich nicht.

    C-Quellcode

    1. class Node
    2. {
    3. private:
    4. int value;
    5. Node * next = new Node(); //Stack overflow
    6. public:
    7. Node();
    8. ~Node();
    9. void set_next(Node node);
    10. Node get_next();
    11. void set_value(int val);
    12. int get_value();
    13. bool has_next;
    14. };


    In main erstelle ich nur zu Testzwecken einen Knoten:

    C-Quellcode

    1. int main()
    2. {
    3. Node test;
    4. return 0;
    5. }

    Natürlich ergibt das ein Stackoverflow weil das new Node () was du machst implizit vom Compiler in den Konstruktor verlagert wird.
    Du musst das in eine eigene Methode packen (testweise) und diese dann aufrufen.
    Oder wie ich es oben erwähnt habe, tust du eine neue Klasse erstellen (LinkedList) und legst eine innere Klasse Node an, dann kannst du im Konstruktor von LinkedList ein Node Objekt erstellen ohne Stackoverflow

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „RushDen“ ()