[c++]Bibliothek mit Baumstruktur erstellen

04/29/2011 15:21 Z!ppo#1

Hallo Leute,
ich muss bis Sonntag f�r die Uni ein eigentlich einfaches c++ Terminal Programm schreiben. Ich bin erst im zweiten Semester und kenne mich zwar mit der c-Syntax und Algorithmen aus, aber ich verzweifle grad an der ganzen OOP Sache :confused:

Die Aufgabe ist folgende:

- drei Dateien (tree.h, tree.cxx und main.cxx) erstellen.
- Es soll eine Baumstruktur erstellt werden mit einem Objekt namens "node"
- die Memberfunktionen sind :

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

die genaue Aufgabe ist

Quote:

1 Praxis
1.1 Bibliothek mit Baumdatenstruktur (5 Pt)
1.1.1 Grundger�st der Baumdatenstruktur (2 Pt)
Erstellen Sie zwei neue Dateien tree.h und tree.cxx und implementieren Sie
eine Baumdatenstruktur wie folgt.
Die Knotenklasse node soll einen Namen vom Typ std::string speichern
k�nnen und folgende Methoden bereitstellen (Typen der Argumente und R�ckgabewerte
sind bewusst weggelassen und m�ssen erschlossen werden)
Konstruktor mit einem Argument vom Typ const std::string&, das den
Knotenname initialisiert

Destruktor zum L�schen aller Kindknoten mit dem delete-Operator. Deklarieren
Sie den Destruktor als virtuelle Methode.

get_name() const ... gibt den Namen des Knotens zur�ck

set_name(new_name) ... setzt den Namen des Knotens auf einen neuen
Namen

get_nr_children() const ... gibt die Anzahl der Kindknoten an

get_child(i) const ... gibt einen Zeiger auf den i-ten Kindknoten zur�ck

add_child(node) ... f�gt am Ende einen neuen Kindnoten hinzu

Nutzen Sie zum Speichern der Kindknotenzeiger die Template Klasse std::vector
der Standard Template Library, die im Header <vector> deklariert ist.
1.1.2 Programmstruktur (2 Pt)
Erstellen Sie eine dritte Datei main.cxx. Binden Sie tree.h mit einem entsprechenden
#include-Befehl ein
Implementieren Sie eine main-Funktion, die einen Baum mit einem Wurzelknoten
namens "root" und zwei Kindern namens "left child" und
"right child" erzeugt und danach den ganzen Baum mit dem delete-
Operator angewendet auf den Wurzelknoten wieder l�scht.

Erstellen Sie zwei Visual Studio Projekte - ein Projekt namens tree, das
aus tree.cxx eine statische Bibliothek erzeugt und ein Projekt namens
tree_test, das aus main.cxx eine Anwendung erstellt. Setzen Sie in der
Solution das Projekt tree_test als abh�ngig vom Projekt tree.

meine tree.h:

Code:

#include <iostream>
#include <string>
#include <vector>

Class node
{
	private:
	string name;		//name des Knotens
	int nr_children;
	vector<int> vec;
	
	public:
	node(void){const std::string& name;};     //constructor
	virtual ~node(void);                 //destructor
		
	//=======GET=========//
	
	//liest den Namen aus
	get_name(){								
		return name;
	};
	
	//gibt die Nummer der Kindknoten aus
	get_nr_children(){		
				
	};
	
	//gibt die Nummer 
	get_child(i);
	// =======SET========//
	set_name(new_name){
		name = new_name;
	};
	
	add_child(node){};
};

die tree.cxx:
also so wie ich das mitbekommen habe wird die Datei dann automatisch vom Visual Studio erstellt. Das ist aber gerade noch am downloaden, deswegen hab ich mich mal selbst dran probiert ^^

Code:

#include "tree.h"

node::node(void){}

node::virtual ~node(void){}

und die main.cxx:

Code:

#include "tree.h"
#include <iostream>


int main(){
	root = new node("root");
	left_child = new node("left");
	right_child = new node("right");
	
	
	
	return 0;
}

Ich habe echt keine Ahnung wo ich anfangen soll und das Gef�hl dass ich irgendwas grundlegendes falsch mache. Mir gehts jetzt eigentlich nur darum, die Nodes erstellen zu k�nnen und den Namen zu speichern, auszugeben und die Kindknotenanzahl anzuzeigen. Und nat�rlich die Knoten wieder l�schen zu k�nnen.

Ich weis, das ist ziemlich viel stuff, aber w�re echt cool wenn sich jemand die M�he machen w�rde und mal alles durchsehen w�rde :)

Ich will auch nich unbedingt den genauen Code wissen, nur rein logisch betrachtet, was ich machen muss und wie ich die Memberfunktionen richtig einsetze. Und vor allem wie ich das mit dem Vektor als Relation f�r die Knoten richtig hinbekomme.

04/29/2011 15:51 xNopex#2

Erstmal rein von der Theorie:

In die Headerdatei (*.h) kommen nur deklarationen rein, d.h. Methodenk�pfe, Variablendeklarationen, Klassendeklarationen, etc. Die R�mpfe der Methoden programmierst du in der *.cpp Datei:

tree.h:

Code:

#include <string>
#include <vector>

class node
{
	private:
	    std::string name;
	    std::vector<node*> children;
	public:
	    node(const std::string& new_name);     //constructor
	    virtual ~node(void);                 //destructor
	
	    std::string get_name();
	    unsigned int get_nr_children();
	    node* get_child(unsigned int i);
	    void set_name(std::string new_name);
	    void add_child(node* new_node);
};

tree.cpp:

Code:

#include "tree.h"

node::node(const std::string& new_name)
{
    this->name = new_name;
}

node::~node()
{
    for(unsigned int i = 0; i < this->children.size(); i++)
        delete(this->children.at(i));
}

std::string node::get_name()
{
    return this->name;
}

void node::set_name(std::string new_name)
{
    this->name = new_name;
}

unsigned int node::get_nr_children()
{
    return this->children.size();
}

node* node::get_child(unsigned int i)
{
    return this->children.at(i);
}

void node::add_child(node* new_node)
{
    this->children.push_back(new_node);
}

main.cpp:

Code:

#include <iostream>
#include "tree.h"

using namespace std;

int main()
{
    node* root = new node("root");
    root->add_child(new node("left child"));
    root->add_child(new node("right child"));
    delete root;
    return 0;
}

Code ohne Gew�hr auf vollst�ndigkeit und Richtigkeit. Schaus dir gut an, frag nach, sonst kannst du dir dein Studium knicken. Sind halt echte Basics.

04/29/2011 16:09 Z!ppo#3

Ahhh nice, langsam versteh ich das.
Danke vielmals, dein Code ist erstmal sehr verst�ndlich f�r mich :)

Ich hab die Idee, den Vektor dreidimensional zu machen, der dann die Zeiger auf den Parent-Node und die 2 Child-Nodes speichert.

Quote:

Originally Posted by xNopex

Schaus dir gut an, frag nach, sonst kannst du dir dein Studium knicken. Sind halt echte Basics.

Hab ich mir in letzter Zeit auch gedacht. Hab bis jetzt viel verpennt im Studium und wenn ich mir die c++ Beispiele so angucke die es am Anfang des Semesters gab und die ich alle schon drauf haben m�sste merke ich dass ich echt noch ne menge zu b�ffeln hab ... nix mit Party und Chilln :( - so wie ich es das erste Semester gemacht hab ^^

04/29/2011 17:10 xNopex#4

Quote:

Ich hab die Idee, den Vektor dreidimensional zu machen, der dann die Zeiger auf den Parent-Node und die 2 Child-Nodes speichert.

Nicht sehr sinnvoll. Dann lieber drei verschiedene Attribute einrichten. Aber das geht ein bisschen am Ziel der Datenstruktur vorbei. Der Baum unterscheidet nicht nach "left-child" und "right-child", das ist dem pups-egal. Er durchl�uft sp�ter einfach rekursiv alles mal.
Beim geordneten Bin-Baum sieht das schon anders aus.

04/29/2011 18:40 Z!ppo#5

Aber eine Baumstruktur hei�t doch, dass z.B. das erste "Left_Child" auch wieder ein left und right child haben kann.

Code:

                    root _ node
                   /              \
         left_c                     right_c
        /       \                  /        \
left_c         right_c       left_c           right_c

Wenn ich jetzt was mit den Nodes anstellen will brauch ich ja auch noch die Zeiger f�r jeden Node auf die (max 2) child Nodes und auf den root Node. was ja eher auf eine (3 * n)-Matrix hinauslaufen w�rde ...

Wenn ich die child Nodes einfach an den Vektor anf�ge ergibt sich doch eigentlich nur eine Folge von Nodes, also:

root -> left_c -> right_c -> left_c -> right_c ..... usw

Und �brigens funktioniert dein Code super, kein Fehler :)

04/29/2011 19:24 xNopex#6

Das, was du hier aufgezeichnet hast, ist eben ein Spezialfall. Ein Bin�rbaum. Ein Baum kann aber allgemein auch so aussehen:

Code:

                    root _ node
                   /              \
         left_c                     right_c
        /   |       \                 /           \
left_c  middle_c right_c      left_c      right_c

Ein Knoten braucht dabei immer nur die Referenz auf seine Nachfolger, was in der Klasse durch den Vektor realisiert wird. Da du nicht zwischen den einzelnen Knoten unterscheiden musst, langt es, dass du einfach alle Nachfolger eines Knoten in den Vektor steckst.
Wenn du etwas mit den Knoten anstellen willst, l�ufst du solange alle Knoten durch (Stichwort Rekursion) bist du an dem Knoten angelangt bist, mit dem du was machen willst (�berpr�fung �ber Name).

Beispiel: Sagen wir du hast 6Knoten und einen Root-Knoten:

Code:

                    root _ node
                   /              \
            A                          B
        /       \                  /        \
      C         D                E           F

root_node hat nur jeweils eine Referenz auf A und B. A jeweils eine Referenz auf C und D und B auf E und F. Die Zeiger zu den Nachfolgern sind jeweils in den Vektoren der Knoten gespeichert. Sagen wir du willst bei Knoten B eine weitere Referenz auf einen neuen Knoten G einf�gen. Daf�r m�ssen wir eine neue Funktion einf�gen:

Code:

bool node::insert_node_at(std::string node, node* new_node)
{
     if(this->name == node)
     {
           this->add_child(new_node);
           return true;
     }

     for( unsigned int i = 0; i < this->children.size(); i++ )
     {
           if(this->children.at(i)->insert_node_at(node, new_node))
               return true;
     }

     return false;
}

Aufgerufen wird sie nun so:

Code:

int main()
{
     //Zuvor wurde der Baum erstellt
     if(root_node->insert_node_at("B", new node("G"));
        cout << "Knoten wurde erfolgreich eingef�gt";
     else
        cout << "Knoten konnte nicht eingef�gt werden";
}

Du siehst, mithilfe rekursiver Funktionen, gen�gt es bei solchen Datenstrukturen, wenn man seinen Nachfolger kennt. Das verh�lt sich genauso bei Listen, BinB�umen, Stapeln, Graphen, etc.

EDIT: Code wieder ohne Gew�hr auf Vollst�ndigkeit und Richtigkeit
EDIT2: Rein aus Interesse, wo und was genau studierst du?

04/29/2011 20:05 Z!ppo#7

Puh, also ich denke ich habs nu verstanden ^^
Das Problem war dass ich gar nich dran gedacht hab dass ja f�r jeden Knoten ein neues Objekt erstellt wird, was dann wieder nen eigenen Vektor hat, wie du ja gerade sehr sch�n erkl�rt hast :)
Langsam hab ichs glaub ich im Kopf :D

Quote:

Originally Posted by xNopex

Rein aus Interesse, wo und was genau studierst du?

Ich studiere Bachelor Medieninformaik in Dresden (TU). Wollt eigentlich (weil das bis nun im 2. Semester noch ohne Probleme geht) auf reine Informatik umsteigen, weil ich mir die ganzen Programmiergeschichten eigentlich ziemlich geil vorstelle wenn mans drauf hat ^^ und genau da liegt das Problem :D