3. Mehrwegbaum I , initialiseren und speichern

Mehrwegbaum I , initialiseren und speichern

  • V

    dumme frage:
    wäre nicht ein

    vector<node *> children;

    sinnvoller?
    Dann musste gar nix kopieren, außer dem Zeiger.

    0
  • B

    Vorden schrieb:

    dumme frage:
    wäre nicht ein

    vector<node *> children;

    sinnvoller?
    Dann musste gar nix kopieren, außer dem Zeiger.

    Weiß nicht, ich glaube das ist nur teils/teils sinnvoll. Zum einen muss nichts kopiert werden, was ja schon einen theoretischen Geschwindigkeitsvorteil bietet, je größer der Baum, desto sinnvoller. Allerdings allokiert man damit jeweils winzige Speicherbereiche, und das auch noch oft, dazu muss man sich noch um die manuelle Speicherfreigabe kümmern 😕
    Vielleicht wäre es am sinnvollsten mit eigenem Speichermanager und schlauen Zeigerchen. Da kommt dann die Sinnhaftigkeit aber auch auf den Schreibaufwand an, wie groß der Baum werden soll und so weiter 🙂 Wie Simon2 sagen würde: It depends 😃

    0
  • F

    Hingeklatscht und erfüllt mal wieder keine der tollen Designanforderungen, funzt aber. 😉
    Jetzt hat man zwar auch noch die Anzahl der nodes im struct, kann man aber ja auch trennen, wenn man denn möchte.

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

using namespace std;

struct person{
    string name;
    int nodes;
    vector<person> children;
};
istream& operator>>(istream &in, person &p){
    in >> p.name >> p.nodes;
    return in;
}

void readChildren(int d, istream &in, person &p){
    for(int k = 0; k < d; k++){
	cout << "  ";
    }
    cout << p.name << endl;
    for(int i = 0; i < p.nodes; i++){
	person np;
	in >> np;
	p.children.push_back(np);
	readChildren(d+1, in, np);
    }
}

int main(int argc, char *argv[]){
    ifstream stream ("test.txt");

    person root;
    stream >> root;
    readChildren(0, stream, root);

    stream.close();

}
    0
  • C

    So da bin ich wieder. 🙂 Ich würde das Program in eine schickere und modernere Ebene hiefen. Damit meine kleinen Probleme vlt. für den einen oder anderen als Einstieg in die Erstellungen von Bäumen dienen. Nach diesem Muster wäre eine entsprechende Implementierung auf Binäre-baumstrukturen sicher möglich.

    Neues Bildchen 🙂

    http://home.arcor.de/connyr23/tree3m.jpg

    // "tree" (pointer to root node)
typedef struct nodeUBL* treeUBL;
// subtree list item
struct itemUBL {
treeUBL child;
itemUBL* succ;
};

// subtree list
struct listUBL {
unsigned int degree;
itemUBL* first;
itemUBL* last;
};
// tree node
struct nodeUBL {
string data;
listUBL children;
};

    Das wären die Strukturen. Nun steht halbwegs die Rahmenfunktion die einen Zeiger auf den erzeugten Baum zurück gibt.

    treeUBL* restore_tree(ifstream& infile)
{
treeUBL proot = NULL;
listUBL forest; // Dummy-Unterbaumliste (= "Wald")
initialise(&forest); // Frage:

// den Baum als ersten Unterbaum im "Wald" rekonstruieren
// rst_t_dp(ifstream, &forest, 1);
/*

Funktion folgt ... 

*/

// Ist überhaupt ein Baum entstanden (der Wald nicht leer)?
// Genau genommen müssten wir auch auf degree>1 testen zwecks Fehlerbehandlung...
if (forest.degree > 0)
{
proot = forest.first->child;
// Gib nun den Speicherplatz für die Liste wieder frei, in dem diese geleert wird.
// (Der extrahierte Baum sollte dabei natürlich nicht wieder aufgelöst werden!)
remove(forest, 1); // macht intern das delete für das entfernte itemUBL
}
return

    Die grobe Rekonsruktionsfunktion(rst_t_dp(ifstream, &forest, 1)) ist in arbeit. 🙂

    Ich möchte gerne zum initialisieren die Funktion initialise() erstellen.

    Zum einen soll Sie die Struktur forest initialisieren zum anderen auch die später auftauchenden Knoten:

    treeUBL pnode = new nodeUBL; // Knoten erzeugen
initialise(pnode->children);

    Wie sieht aber dann die Funktion aus und wie initialisiere ich nun meine 2 Strukturen? Wäre es da Sinnvoll einfach nur mit malloc den Speicher für zu reservieren? 😕

    Ich wünsch euch erstmal eine gute Nacht.

    0
  • B

    connyr23 schrieb:

    Wie sieht aber dann die Funktion aus und wie initialisiere ich nun meine 2 Strukturen? Wäre es da Sinnvoll einfach nur mit malloc den Speicher für zu reservieren? 😕

    Also malloc ist hier schonmal Mist 😉 Der Nachteil an malloc ist, dass dann die Konstruktoren nicht aufgerufen werden, es wird nur Speicher reserviert. Wenn du Speicher für eine Struktur oder Klasse brauchst und darin befindet sich ein String oder irgendwas, was einen Konstruktor besitzt, dann kannst du das nur ordentlich benutzen, wenn du den Speicher mit "new" holst 🙂

    Ich würde auf der bestehenden Einlese-Routine aufbauen. Das, was du ändern musst, ist, dass du beim Einlesen der Kinder keinen Eintrag im Knoten hinzufügen musst, sondern einen neuen Eintrag in der verketteten Liste erstellen musst. Wenn du dann alle Kinder eingelesen hast, setzt du die "last"-Variable auf das Ende der Liste.

    0
  • C

    Wäre die initialsierug so ok ?

    void initialise(listUBL* list)
{
list->First = list->Last = NULL;
}
    0
  • B

    Du kannst auch einfach Konstruktoren einbauen, die werden ausgeführt, wenn du das Objekt mit listUBL l; oder listUBL* l = new listUBL(); erstellst.

    struct listUBL
{
    unsigned int degree;
    itemUBL* first;
    itemUBL* last;

    // Entweder (1)
    listUBL() : degree(0), first(NULL), last(NULL)
    {
    }

    // Oder (2)
    listUBL()
    {
        degree = 0;
        first = NULL;
        last = NULL;
    }

    // Nur der Vollständigkeit halber, mit einer Tilde davor ist es ein Destruktor, der
    //   wird aufgerufen, wenn das Objekt zerstört wird, also bei 'delete obj;' oder
    //   wenn das Stack-Objekt aus dem Gültigkeitsbereich läuft.
    ~listUBL()
    {
    }
};

    Bei (1) werden die (eingebauten) Konstruktoren von 'degree', 'first' und 'last' aufgerufen, bei zwei werden die Werte halt "normal" gesetzt 🙂
    Konstruktoren dürfen auch (wie normale Funktionen) Parameter übernehmen, Destruktoren dagegen nicht.

    0
  • C

    gut zu wissen, vermerk ich mir mal gleich. 🙂

    struct node_info {
     T data;
     unsigned int depth;
}
node_info* rst_t_dp(ifstream& infile, listUBL* subtrees, unsigned int depth)
{
     bool isDone = false;
     node_info* pinfo = NULL;

     while ( !isDone )
     {
        if ( pinfo == NULL && (pinfo = read_node_info(infile)) == NULL )
     { //wenn infile erschöpft, sollte read_node NULL liefern

     isDone = true;
}
else if ( pinfo->depth >= depth )
{

     bool down = pinfo->depth > depth; // Merken der Tiefenrelation
     treeUBL pnode = new nodeUBL; // Knoten erzeugen
     pnode->data = pinfo->data; // Informationen eintragen

     initialise(pnode->children); // " "

     //hier sitz ich noch
     // add_last(subtrees, pnode); // Knoten zu den Unterbäumen hinzufügen

     delete pinfo; // Beseitige temporäre Info und ersetze sie ggf. aus Rekursion

     pinfo = NULL; // Wichtig für Unterscheidung im nächsten Schleifendurchlauf
     if (down)
     {
     // Entweder die Rekursion konsumiert den gesamten Strom, oder wir bekommen
     // eine Knoteninfo mit pinfo->depth <= depth
     pinfo = rst_t_dp(ifstream, pnode->children, depth+1);
     }
}
else // Entweder pinfo == NULL oder pinfo->depth < depth, also raus hier!
{
isDone = true;
}
}
return pinfo;
}

    So, nun häng ich am verknüpfen 😞

    add_last(subtrees, pnode); // Knoten zu den Unterbäumen hinzufügen

    An der scheitert es momentan. *CRY*

    0
  • B

    Irgendwie blick ich bei deinem Code nicht ganz durch 😕 Kryptische Funktionsnamen wie "rst_t_dp" solltest du auch besser nicht verwenden, Code sollte definitiv lesbar sein 😉

    Wie ist denn generell die Struktur von deinem Quelltext? Also welche Funktionen hast du, in welcher Reihenfolge oder wann werden sie aufgerufen usw?

    0
  • C

    restore_tree_depth 😃

    Ich poste nachher mal meine Baustelle. 🙂

    0
Anmelden zum Antworten