Bibliothek mit Baumdatenstruktur erzeugen?



  • Hallo, ich arbeite in einer Gruppe von 3 relativen C++- Neulingen und wir haben die Aufgabe, eine Bibliothek mit Baumdatenstruktur zu erzeugen. Dies soll mit einer tree.cpp und einer tree.h - Datei geschehen. Die Knotenklasse soll dann einen Namen vom Typ string speichern und folgende Methoden bereitstellen können:

    - einen Konstruktor
    - einen Destruktor
    - get_name() const
    - set_name(new_name)
    - get_nr_children() const
    - get_child(i) const
    - add_child(node)

    Die Kindknotenzeiger sollen mithilfe der Template-Klasse std::vector gespeichert werden.

    Abgesehen davon, dass mir der Sinn bzw. die Relevanz der Aufgabe in Zusammenhang mit dem Schwierigkeitsgrad (Das ist die erste Aufgabe in unserer Vorlesung und wir haben bis jetzt nur 2 Stunden C++-Einführung gemacht :S) schleierhaft ist, haben wir uns dann trotzdem mal rangemacht und haben bis jetzt folgendes erreicht:

    // tree.h
    
    #pragma once
    #include <iostream>
    #include <string>
    #include <vector>
    
    using namespace std;
    
    class node {
    private: 
    	node (const string& name);
    	virtual ~node(void);
    public:
    	const string get_name(string name) {
    		return name;
    	}
    	string set_name(string new_name) {
    		string name = new_name;
    	}
    	const int get_nr_children() {
    
    	}
    	const int get_child(int i) {
    		return i;
    	}
    	int add_child(node) {
    
    	}
    
    }
    
    //tree.cpp
    #include <iostream>
    #include <string>
    
    using namespace std;
    
    int node(string name) {
    }
    

    Jetz stellt sich uns die Frage, wie die Methoden get_nr_children() und add_child(node) definiert werden müssen, da wir sozusagen keine Peilung haben, genau so bei der Klasse node, wie wir dort alles implementieren müssen...
    Würde mich freuen, wenn uns jemand vielleicht etwas auf die Sprünge helfen könnte.
    LG taiBsu



  • Wie speichert ihr denn die Kinder eines Knotens? Da du schon die <vector> eingebunden hast, würde ich mal darauf tippen, daß ihr dort einen vector<node> dafür habt. Also kannst du die Funktionen, die die Kindknoten betreffen, auch an diesen weiterleiten (get_child=operator[] bzw. at(), get_nr_children=size(), add_cild=push_back()).



  • Erstmal danke für die schnelle Antwort.
    Das Problem ist, dass wir nicht so recht wissen, was wir mit diesem vector überhaupt anfangen sollen, also wie wir damit umzugehen haben...



  • Du verpasst der Klasse eine entsprechende Member-Variable:

    class node
    {
    private:
      std::vector<node> children;
    public:
      ...
      int get_nr_children() const
      { return children.size(); }
      ...
    };
    

    (ürigens macht es sich für den praktischen Einsatz nicht besonders gut, wenn Konstruktor und Destruktor privat sind ;))



  • taiBsu schrieb:

    Abgesehen davon, dass mir der Sinn bzw. die Relevanz der Aufgabe [...] schleierhaft ist,

    Bäume sind grundlegende Datenstrukturen, da wirst du wohl im Informatikstudium immer wieder drauf zurückkommen.

    taiBsu schrieb:

    (Das ist die erste Aufgabe in unserer Vorlesung und wir haben bis jetzt nur 2 Stunden C++-Einführung gemacht :S)

    taiBsu schrieb:

    Das Problem ist, dass wir nicht so recht wissen, was wir mit diesem vector überhaupt anfangen sollen, also wie wir damit umzugehen haben...

    Was ist der Unterschied zwischen Schule und Studium? In der Schule wird alles dreimal durchgekaut, und der Lehrer geht danach nciht davon aus, dass das danach aus dem FF beherrscht wird.
    Im Studium wird ein Thema einmal oberflächlich erklärt. Danach geht der Prof davon aus, dass der Student sich das Thema daheim selbstständig erarbeitet. Wenn euch für die Erledigung der Übungsaufgaben nötiges Wissen fehlt, solltet ihr die zur Verfügung stehenden Quellen (Internet, Literaturliste+Bibliothek) nutzen und euch das Wissen aneignen. "Herr Lehrer, das hatten wir doch noch garnicht" funktioniert höchstens in der Schule 😉

    Offenbar ist euch schon der Tip mit vector gegeben worden (sosnt hättet ihr den Header wohl nicht eingebunden). Wenn ihr nicht wisst, was das ist oder wie man damit arbeitet, helfen euch Bücher und Tutorials sicher weiter. Ihr werdet schnell erfahren, dass ein vector ein Container ist. Container können viele Dinge von etwas aufnehmen. Ein Knoten kann viele Kindknoten haben. Da könnte ein Zusammenhang bestehen 😉



  • Hab' mich jetzt mal ein bisschen mit diesen vectors belesen und bin erstmal zu folgendem Ergebnis gekommen:

    class node {
    private: 
    	virtual ~node(void);
    	int nr_children, i;
    	vector<int> v;
    public:
    	node (const string& name) {
    		i = 0;
    		nr_children = 0;
    	}
    	const string get_name(string name) {
    		return name;
    	}
    	string set_name(string new_name) {
    		string name = new_name;
    	}
    	const int get_nr_children() {
    		return nr_children;
    	}
    	const int get_child(int *i) {
    		return *i;
    	}
    	int add_child(node) {
    		for (nr_children = 0; nr_children<i; ++nr_children) {
    			v.push_back(nr_children);
    			++v[nr_children];
    			 nr_children = v.size();
    		}
    	}
    	void delete_all_children(node) {
    		v.clear();
    	}
    
    }
    


  • Erstens: Der Name des Knotens sollte auch ein Element der Klasse sein. Umgekehrt solltest du Hilfsvariablen direkt in der Funktion definieren, die sie benötigt.
    Zweitens: Überleg dir nochmal genau, was du in dem vector speichern willst. Du willst einen Baum aufbauen, da sind die Kinder ebenfalls vom Typ node.
    Drittens: Der Destruktor ist gleich dreifach unsinnig:
    - mit einem privaten Konstruktor verhinderst du effektiv die Verwendung dieser Klasse
    - virtual brauchst du nur, wenn du mit polymorphen Klassen arbeitest (danach sieht es bisher nicht aus)
    - die Klasse enthält nichts, was einen selbstdefinierten Destruktor rechtfertigen würde - der compilergenerierte Destruktor reicht völlig



  • CStoll schrieb:

    Erstens: Der Name des Knotens sollte auch ein Element der Klasse sein. Umgekehrt solltest du Hilfsvariablen direkt in der Funktion definieren, die sie benötigt.

    Das kann ich jetz nich so wirklich nachvollziehen. Der Name des Knotens ist doch ein Element der Klasse, oder nicht?
    Und die Hilfsvariablen sollte ich dann quasi in public: node {} definieren, richtig?

    CStoll schrieb:

    Zweitens: Überleg dir nochmal genau, was du in dem vector speichern willst. Du willst einen Baum aufbauen, da sind die Kinder ebenfalls vom Typ node.

    In dem Vektor möchte ich doch die Anzahl der Knoten speichern, oder?

    CStoll schrieb:

    Drittens: Der Destruktor ist gleich dreifach unsinnig:
    - mit einem privaten Konstruktor verhinderst du effektiv die Verwendung dieser Klasse
    - virtual brauchst du nur, wenn du mit polymorphen Klassen arbeitest (danach sieht es bisher nicht aus)
    - die Klasse enthält nichts, was einen selbstdefinierten Destruktor rechtfertigen würde - der compilergenerierte Destruktor reicht völlig

    Ich habe den Konstruktor public gesetzt, nur der Destruktor ist noch privat. Schätze mal, der sollte wohl auch public gesetzt werden?
    In der Aufgabenstellung steht, dass (ich zitiere:) "der Destruktor als virtuelle Methode zu deklarieren ist". Wo ist da der Unterschied, ob virtuell oder nicht?
    Also kann ich dann quasi auch die Funktion "delete_all_children()" löschen?



  • Zudem würde ich zu einer .h eine .c machen und zu einer .hpp eine .cpp. Nur so als kleiner Tipp 😉



  • taiBsu schrieb:

    CStoll schrieb:

    Erstens: Der Name des Knotens sollte auch ein Element der Klasse sein. Umgekehrt solltest du Hilfsvariablen direkt in der Funktion definieren, die sie benötigt.

    Das kann ich jetz nich so wirklich nachvollziehen. Der Name des Knotens ist doch ein Element der Klasse, oder nicht?
    Und die Hilfsvariablen sollte ich dann quasi in public: node {} definieren, richtig?

    Du hast zwei Methoden zum Lesen und Schreiben des Namens, aber die greifen nicht auf das drunterliegende Objekt zu - get_name() liefert den übergebenen Parameter, set_name() schreibt in eine lokale Variable, die sofort vernichtet wird.

    CStoll schrieb:

    Zweitens: Überleg dir nochmal genau, was du in dem vector speichern willst. Du willst einen Baum aufbauen, da sind die Kinder ebenfalls vom Typ node.

    In dem Vektor möchte ich doch die Anzahl der Knoten speichern, oder?

    Nein, für die Anzahl würde ein int-Wert ausreichen. Du benötigst eine Liste, in der die Kind-Knoten enthalten sind.

    CStoll schrieb:

    Drittens: Der Destruktor ist gleich dreifach unsinnig:
    - mit einem privaten Konstruktor verhinderst du effektiv die Verwendung dieser Klasse
    - virtual brauchst du nur, wenn du mit polymorphen Klassen arbeitest (danach sieht es bisher nicht aus)
    - die Klasse enthält nichts, was einen selbstdefinierten Destruktor rechtfertigen würde - der compilergenerierte Destruktor reicht völlig

    Ich habe den Konstruktor public gesetzt, nur der Destruktor ist noch privat. Schätze mal, der sollte wohl auch public gesetzt werden?
    In der Aufgabenstellung steht, dass (ich zitiere:) "der Destruktor als virtuelle Methode zu deklarieren ist". Wo ist da der Unterschied, ob virtuell oder nicht?

    lies dir mal dein Buch durch, was virtual bedeutet. Ein virtueller Destruktor macht nur Sinn, wenn du andere Klassen von node ableiten willst (und dann über einen node-Zeiger special_node Objekte freigeben willst). Ein privater Destruktor macht gar keinen Sinn.

    btw, wer stellt denn solche Aufgaben?

    Also kann ich dann quasi auch die Funktion "delete_all_children()" löschen?

    Kommt darauf an, ob es benötigt wird. Ich würde sie behalten.



  • taiBsu schrieb:

    Hab' mich jetzt mal ein bisschen mit diesen vectors belesen und bin erstmal zu folgendem Ergebnis gekommen:

    Das ist alles totaler Quatsch. Aber ich kann es nachvollziehen. Die Aufgabe ist nämlich viel zu schwer wenn erst zwei Stunden unterrichtet wurde.

    Evtl. hat jemand Lust Dir die Aufgabe zu lösen. Ich sehe wenig Hoffnung, dass du das in ein paar Tagen selbst hinbekommst.



  • Muss ich jetzt aber auch irgendwie mal zustimmen ... jemand der sich noch nie mit Programmieren auseinandergesetz hat soll so eine AUfgabe innerhalb 2-3 Tagen lösen ? Wohl kaum, dazu müsste er wohl erstmal ein Gespür für das Programmieren an sich bekommen. Alleine die Vermutung " Den vector brauche ich doch, um die Anuahl der Kinderknoten zu speichern " verräte einem, dass hier vorher noch nie programmiert wurde. Und da soll jetzt eine Baumstruktur draus werden ?! Es scheitert doch schon bei den Funktions-prototypen. Post/in/Preorder-Suche etc. wird sie dann wohl maßlos überfordern.



  • Hmmm, na super.
    Kann mir denn da nicht irgendjemand behilflich sein? Ich hab irgendwie das Gefühl dass ich bei VC++ gerade gegen die Wand rede.

    EDIT: Ich habe noch 5 Stunden Zeit, bis die Aufgabe abgegeben sein muss... Ich hoffe inständigst, dass jemand mir irgendwie dabei noch behilflich sein kann, ich komme nämlich überhaupt nich mehr vorwärts, da ich scheinbar überhaupt keine Ahnung allein schon von der Struktur habe...



  • @taiBsu hast du dann die Lösung gefunden ? Die gleiche Aufgabe habe ich nach 8 Jahren 😂
    TU Dresden ECG✌🏻


  • Mod

    Muss das sein? Seit diese Frage gestellt wurde, gab es drei neue C++-Standards. Die Fragesteller in diesem Thread sind aufgewachsen und haben nun selber Kinder, die zur Uni gehen. Denkst du wirklich, das bringt jemanden etwas, diesen alten Thread auszugraben? Oder das du von den damaligen Teilnehmern noch eine Antwort bekommst? Mach einen neuen Thread für deine Hausaufgaben auf, ggf. mit Verweis auf diesen hier.


  • Mod

    @SeppJ sagte in Bibliothek mit Baumdatenstruktur erzeugen?:

    Muss das sein? Seit diese Frage gestellt wurde, gab es drei neue C++-Standards. Die Fragesteller in diesem Thread sind aufgewachsen und haben nun selber Kinder, die zur Uni gehen.

    Aehh—der Thread ist 8 Jahre alt. Die Fragesteller beenden gerade den Master... 😂

    Edit: Sorry, ich hatte nicht beabsichtigt, den Thread schon wieder zu pushen. Schluss mit lustig hier.


Log in to reply