Mehrwegbaum I , initialiseren und speichern



  • Ich lese hier schon eine ganze Zeitlang mit und fand auch ziemlich schnell Lösungen für meine kleinen Programme die ich im Alltag verzapfe. 😃 Allerdings bastel ich seit Freitag an einem Programm was mir überhaupt nicht gelingen will. 😡

    Frage: Um was geht es?

    Es geht um einen Stammbaum. Der Baum ist nicht binär und daher mehrwegig.

    Da man überall zum Thema Binärbäume kleinere Bildchen präsentiert, hab ich eins für den Stammbaum gebastelt. 😃

    http://home.arcor.de/connyr23/fam2.jpg <- Image

    Wie versuchst du es?

    In meinem Beispiel ist der max. Grad der Kindsknoten bekannt [max_children]. Darum versuche ich ein Array von Kindsknoten in den Knoten zu legen.

    Wie weit bist du?

    - Der Stammbaum wird von mir aus einer Datei ausgelesen. (http://home.arcor.de/connyr23/tree.txt)
    Diese ist nach der pre-order Methode aufgebaut. Das bedeutet der Baum wird über die Wurzel von Links nach rechts "aufgebaut".

    Bsp.: // Teilbaum von Rudi
    Rudi
    2
    Otto
    2
    Gabi
    0
    Anna
    1
    Olga
    0
    - cut -

    Von der Wurzel Rudi, gehen 2 Äste weg. Rudi's linker Ast führt zum inneren Knoten Otto von dem wieder 2 Aste weg führen. Der linke Ast von Otto führt zu Gabi. Da Nach Gabi eine 0 folgt, bedeutet dies, Gabi ist ein Blatt und enthält keine weiteren Knoten mehr. Wir springen jetzt zum letzten offenen inneren Knoten und zwar Otto. Von Votto führt ein weiterer Ast weg zu Anna. Von anna führt ein nur ein Ast weg und dieser geht zu Olga, elche auch ein Blatt ist da nach ihr kein Knoten mehr folgt.

    Rudi's rechter Teilbaum baut sich dann genauso auf.

    #include <iostream>
    #include <stdio.h>
    using namespace std;
    
    const int max_children = 4;
    
    struct node {
        string data;
        node* children[max_children];
    };
    
    struct tree {
        node* root;
    };
    
    int main(int argc, char* argv[]){
    
      string name;
      int number;
    
      FILE* datei;
    
      datei = fopen("tree.txt", "r");
    
      if ( !datei)
      {
        cerr << "Fehler beim öffnen der Datei.";
      }  
    
      while(fscanf(datei, "%s%i", &name, &number) != EOF)
      {
       // --- noch offen  --- 
      }
      fclose(datei);
    
      return 0;
    }
    

    Hier sitz ich seit 2 Tagen. Es gelingt mir nicht den Stammbaum zu initalisieren und auf dem Bildschirm richtig auszugeben. Aber ich versuch es weiter. Wäre toll wenn mir jemand etwas mit unter die Arme greifen könnte.

    Erläuterungen, Links etc. sind gerne willkommen. 😉



  • Wow, so eine gut erklärte Fragestellung hab ich lange nicht mehr gesehen 👍 🙂

    So, erstmal eine Anmerkung zu deinem Code: Irgendwie scheinst du C und C++ zu mischen, was an sich nicht besonders gut ist.

    Du hast ja (zum Glück) schon eine recht genaue Vorstellung, wie der Baum aufgebaut werden soll. Ein paar Sachen würde ich trotzdem abändern, z.B. dass die Anzahl der Kinder nicht begrenzt ist. Variable Arrays lassen sich z.B. wunderbar mit dem std::vector darstellen ( vector<node> children; ).
    Desweiteren würde ich erst die komplette Textdatei in ein String-Array einlesen. Müsste es wunderbar viele Beispiele dazu im Forum geben oder auch in Tutorials, sähe etwa so aus:

    #include <vector>
    #include <string>
    using namespace std;
    ...
    vector<string> lines;
    ifstream file( "dateiname" );
    if ( ! file )
        cerr << "fehler bla" << endl;
    else
    {
        // Schleife zum auslesen von file in lines
    }
    

    So, und dann könntest du dir erstmal einen genauen Algorithmus ausdenken, also die Vorgehensweise, wie die Knoten etabliert werden. Von der Formulierung zum Source-Code ist es dann ein Kinderspiel 😉
    Übrigens: Zum Formulieren des Algorithmus ist es meist am Einfachsten, wenn du dir aus der Liste auf dem Papier den Baum aufbaust und dabei jeden (wirklich jeden) Schritt, den du dabei geistig und körperlich machst, aufschreibst.


  • Mod

    Nur ein Hinweis: bau den Algorithmus rekursiv auf. Da die Die Kinder hier ihre Eltern nicht kennen, ist ein iterativer Algorithmus etwas umständlich zu formulieren.

    Hinsichtlich der Organisation (vector<node> statt array aus Zeigern) schließe ich mich Badestrand an.

    struct node {
        string data;
        std::vector<node> children;
    };
    

    Damit hast du keine künstliche Beschränkung der Kinderanzahl und der ganze Baum ist auch ohne Weiteres kopierbar. Generell läuft etwas falsch, wenn du bereits bei so einem einfachen Problem mit rohen Arrays und Zeigern anfängst. Es wird dann nicht mehr besser werden.



  • Wow, so eine gut erklärte Fragestellung hab ich lange nicht mehr gesehen 👍 🙂

    Ich sitz auch schon seit Freitg drann. 😃 Warten wir mal ab bis dann die OOP dran kommt. *hust*

    So, erstmal eine Anmerkung zu deinem Code: Irgendwie scheinst du C und C++ zu mischen, was an sich nicht besonders gut ist.

    Das Problem für mich ist viel mehr eine klare Linie zwischen den beiden Sprachen zu finden, in Büchern die als Titel "c/c++" haben, mißbrachen offensichlich die Richtlinien. Und sowas nehme ich mir dann sicherlich unbewußt an(ohne den unterschied zu kennen). 😞 Manches ist für mich in C verständlicher aber in c++ schnellerer zu tippen. 😃

    So nun wieder zum Programm.

    Nur ein Hinweis: bau den Algorithmus rekursiv auf. Da die Die Kinder hier ihre Eltern nicht kennen, ist ein iterativer Algorithmus etwas umständlich zu formulieren.

    Ich hatte mir dahingegend auch schon meine Gedanken gemacht. Allerdings setzte das wiederum die initialisierung vorraus. Um mit dem -bereits eingelesenen und iniialisierten- Baum, Begriffe wie Tiefe,Anzahl d.Knoten zu demonstrieren. dachte ich an folgende Funktion:

    unsigned int treesize(node* proot)
    {
         unsigned int size = 0; // leerer Baum
         if (proot != NULL) // Fallunterscheidung
         {
           // Reduktionsfall
           size++; 
           for (unsigned int son=0; son < max_children; son++)
           {
             // jeder Unterbaum ist kleiner als gesamter Baum!
             size += size(proot->children[son]);
           }
         }
         return size;
    }
    

    Aber das wäre halt erst das nächste.

    Ich bekomme die Kurve nicht bei:

    - ausgelesene Wurzel
    - ausgelesene Anzahl der Kinder

    - prüfe ob links 'null ist' wenn ja links lang, ansonsten links+1
    - unter baum erstellen

    - am Blatt angekommen -> gehe zurück zum letzten OFFNEN Unterbaum.

    und das rekursiv. Da scheitere ich momentan. 😡

    Ich habe den Quellcode abgändert und eure Vorschläge, für dich ich mich bedanken möchte, mit eingebaut.

    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <string>
    using namespace std;
    
    struct node {
        string data;
        std::vector<node> children;
    };
    
    struct tree {
        node* root;
    };
    
    int main(int argc, char* argv[]){
    
      string name;
      int number;
      vector<string> lines;
      ifstream file("tree.txt");
    
      if ( !File)
      {
        cerr << "Fehler beim öffnen der Datei.";
      }else{
        while(getline(file, name))
        {
           lines.push_back( name );
        }
      }  
    
      return 0;
    }
    


  • Wow, so eine gut erklärte Fragestellung hab ich lange nicht mehr gesehen 👍 🙂

    Ich sitz auch schon seit Freitg drann. 😃 Warten wir mal ab bis dann die OOP dran kommt. *hust*

    So, erstmal eine Anmerkung zu deinem Code: Irgendwie scheinst du C und C++ zu mischen, was an sich nicht besonders gut ist.

    Das Problem für mich ist viel mehr eine klare Linie zwischen den beiden Sprachen zu finden, in Büchern die als Titel "c/c++" haben, mißbrachen die offensichlich die Richtlinien. Und sowas nehme ich mir dann sicherlich unbewußt an(ohne den Unterschied zu kennen). 😞 Manches ist für mich in C verständlicher aber in c++ schnellerer zu tippen. 😃

    So nun wieder zum Programm.

    Nur ein Hinweis: bau den Algorithmus rekursiv auf. Da die Die Kinder hier ihre Eltern nicht kennen, ist ein iterativer Algorithmus etwas umständlich zu formulieren.

    Ich hatte mir dahingegend auch schon meine Gedanken gemacht. Allerdings setzte das wiederum die initialisierung voraus. Um mit dem -bereits eingelesenen und iniialisierten- Baum, Begriffe wie Tiefe,Anzahl d.Knoten zu demonstrieren. dachte ich an folgende Funktion:

    unsigned int treesize(node* proot)
    {
         unsigned int size = 0; // leerer Baum
         if (proot != NULL) // Fallunterscheidung
         {
           // Reduktionsfall
           size++; 
           for (unsigned int son=0; son < max_children; son++)
           {
             // jeder Unterbaum ist kleiner als gesamter Baum!
             size += size(proot->children[son]);
           }
         }
         return size;
    }
    

    Aber das wäre halt erst das nächste.

    Ich bekomme die Kurve nicht bei:

    - ausgelesene Wurzel
    - ausgelesene Anzahl der Kinder

    - prüfe ob links 'null ist' wenn ja links lang, ansonsten links+1
    - unter baum erstellen

    - am Blatt angekommen -> gehe zurück zum letzten OFFNEN Unterbaum.

    und das rekursiv. Da scheitere ich momentan. 😡

    Ich habe den Quellcode abgändert und eure Vorschläge, für dich ich mich bedanken möchte, mit eingebaut.

    #include <iostream>
    #include <stdio.h>
    #include <vector>
    #include <string>
    using namespace std;
    
    struct node {
        string data;
        std::vector<node> children;
    };
    
    struct tree {
        node* root;
    };
    
    int main(int argc, char* argv[]){
    
      string name;
      int number;
      vector<string> lines;
      ifstream file("tree.txt");
    
      if ( !File)
      {
        cerr << "Fehler beim öffnen der Datei.";
      }else{
        while(getline(file, name))
        {
           lines.push_back( name );
        }
      }  
    
      return 0;
    }
    


  • Na das sieht doch jetzt schon richtig gut aus 🙂

    Also ich bin das mal auf dem Papier durchgegangen, sah etwa so aus:

    Eingabe:
    Rudi
    2
    Otto
    2
    Gabi
    0
    Anna
    1
    Olga
    0
    Luci
    3
    Karl
    0
    Paul
    1
    Egon
    0
    Ilse
    0
    
    Anfang:
    Aktueller Knoten = root
    
    Namen lesen -> "Rudi"
    Zahl lesen -> "2"
    Name von aktuellem Knoten = "Rudi"
    Zahl ist größer 0, also Kind anlegen, Zahl=Zahl-1, aktueller Knoten=angelegtes Kind
    
        Rudi(1)
       /
    Kind*
    
        Namen lesen -> "Otto"
        Zahl lesen -> "2"
        Name von aktuellem Knoten = "Otto"
        Zahl ist größer 0, also Kind anlegen, Zahl=Zahl-1, aktueller Knoten=angelegtes Kind
    
        Rudi(1)
       /
    Otto(1)
     |
    Kind*
    
            Namen lesen -> "Gabi"
            Zahl lesen -> "0"
            Name von aktuellem Knoten = "Gabi"
            Zahl ist = 0, also zum vorherigen Zustand zurückgehen (aktueller Knoten=Vater von Gabi)
    
        Rudi(1)
      / 
    Otto(1)* 
     |
    Gabi(0)
    
        Namen lesen -> "Anna"
        Zahl lesen -> "1"
        Zahl ist größer 0, also Kind anlegen, Zahl=Zahl-1, aktueller Knoten=angelegtes Kind
    
        Rudi(1)
      / 
    Otto(0)--
     |       \
    Gabi(0)   Kind*
    

    usw. Das Sternchen soll den aktuellen Knoten markieren. Hoffe das hilft dir weiter 🙂



  • Also ich bin das mal auf dem Papier durchgegangen,

    Danke. 🙂

    Nun wird es halt n bissel wacklig für mich. Aber ich versuch es einfach mal.

    Aktueller Knoten = root

    #include // ...
    
    string name. int number;
    
    struct tree *einordnen(struct tree *knot_zeig);
    
    int main(void){
    
    struct tree *wurzel;
    wurzel = NULL;
    
    }
    

    Namen lesen -> "Rudi"
    Zahl lesen -> "2"
    Name von aktuellem Knoten = "Rudi"
    Zahl ist größer 0, also Kind anlegen, Zahl=Zahl-1, aktueller Knoten=angelegtes Kind

    struct tree *wurzel;
    wurzel = NULL;
    
    for(unsigned int i = 0; i < lines.size(); i++)
    {
        // einlesen des Namens und der Kindsanzahl
    
        name = lines[i];
        zahl = stringzuint(lines[i++]);
        i++;
    
        wurzel = einordnen(wurzel);
    }
    
    struct tree *einordnen(struct tree *knot_zeig){
    
       if(knot_zeig = NULL)
       {
             knot_zeig = (struct tree *)malloc(sizeof(struct tree));
             if(knot_zeig == NULL) {
                cout << "Speicherplatzmangel" << endl;
                exit(1);
             }
             knot_zeig->root->data = name;
    
               if(zahl > 0)
                if(int i = 0; i < zahl; i++)
                 knot_zeig->root->data->children[i];
             zahl--;
        }
        return(knot_zeig);
    
    }
    
    int stringzuint(string z){
    
        int t;
        istring inStream(z);
        inStream >> t;
    
        return t;
    
    }
    

    Da bin ich mir noch sehr sehr unsicher. Die Variablen Name und Zahl hab ich erstmal global gemacht und die funktion stringzuint(), wandelt mir die eingelesene 'Zahl' um.

    Kannst du mal bitte drüber schaun Badestrand? 😞



  • Ich sage mal: Fast 😉

    // Damit das mit dem "nächsten String holen" und "nächste Zahl holen" auch schön einfach ist:
    class FileHoster
    {
        vector<string> lines;
        vector<string>::iterator iter;
    
        FileHoster( const string& path )
        {
            // Datei laden in "lines"
            // "iter" auf das erste Element von lines setzen
        }
    
        string getName()
        {
            // Wirft eine exception, wenn kein Element mehr da ist (also wenn "iter==lines.end()")
            // gibt das aktuelle Element hinter "iter" zurück
            // vor dem zurückgeben wird aber der "iter"-Iterator noch auf's nächste Element geschoben
        }
    
        unsigned int getNumber()
        {
            // Holt den nächsten String mittels der Funktion "getName",
            //   wandelt ihn in eine Zahl um und gibt diese zurück
        }
    };
    
    struct node
    {
        string data;
        vector<node> children;
    };
    
    // Der Einfachheit halber haben wir jetzt einfach mal keine tree-Struktur. Falls du doch eine haben willst,
    //   kannst du in "main" auch sowas machen:
    // tree t;
    // t.root = new node();
    // readTree( file, *t.root );
    
    /*struct tree
    {
        node* root;
    };*/
    
    void readTree( FileHoster& hoster, node& aktueller_knoten )
    {
        // Namen lesen
        strig name = hoster.getNam();
    
        // Zahl lesen
        unsignedint children_to_red = hoster.gtNumber();
    
        // Name von aktuellem Knoten = "..."
        aktuellr_knoten.data = name;
    
        // Zahl ist = 0, also zum vorherigen Zustand zurückgehen (aktueller Knoten=Vater von diesem)
        // Hiermit wird dahin zurückgegangen, von wo die Funktion aufgerufen wurde. Diese Funktion hat
        //   dann ja wieder ihren "alten" aktueller_knoten-Parameter
        if ( children_t_read == 0 )
            return;
    
        // Zahl ist größer 0, also Kind anlegen, Zahl=Zahl-1, aktueller Knoten=angelegtes Kind
        // Hierhin kommt der Code ja nur, wenn children_to_read >0 ist, deshalb brauchen wir auch keine Abfrage mehr
        while ( childen_to_read > 0 )
        {
            // Kind anlegen
            node chil;
    
            // Zahl = Zahl - 1
            children_o_read--;
    
            // aktueller Knoten = angelegtes Kind
            // In der aufgerufenen Funktion ist aktueller_knoten dann ja unser "child" hier
            readTreeh( hostil, child );
    
            // Und das Kind noch in die Liste dazunehmen, muss aber nach readTree geschehen, da dabei
            //   eine Kopie des Kindes gemacht wird.
            aktueller_knoten.phush_back( child );
        }
    }
    
    main-Funktion:
        FileHoster file( "C:/Datei.txt" );
        node mytree;
        readTree( file, mytree );
        // Und jetzt noch irgendwie ausgeben :)
    

    Oh, und noch ein Zusatz: Ich hatte am Anfang (eigentlich sogar recht lange) auch ziemlich Schwierigkeiten mit dem "C++ gegen C" -Krams, ist aber auch nicht so schlimm, nur die 'vector'en, 'string's usw sind schon recht komfortabel 🙂

    Und Iteratoren sind hier noch kurz erklärt: http://www.kharchi.eu/wiki/doku.php?id=cpp:std:iterator (sind ja eigentlich auch nur Zeiger)

    edit: Hab extra einige kleine Rechtschreibfehler in den Code gehauen, damit du auch noch was zu tun hast :p Und um die Klasse "FileHoster" zu füllen, war ich jetzt einfach mal zu faul, aber dir soll ja auch nicht langweilig werden 🙂 Ich hab's übrigens nicht getestet, kann also was falsch sein, und die Abfrage auf 0 und die while-Schleife kannst du auch zusammenfassen, da diese ja gar nicht durchlaufen wird, wenn children_to_read null ist.

    edit nummero 2: Du könntest die Funktion "readTree" auch als Memberfunktion von "node" machen, dann hast du einen Parameter weniger und irgendwie gehörts ja auch thematisch da rein 🙂



  • dumme frage:
    wäre nicht ein

    vector<node *> children;
    

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



  • 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 😃



  • 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();
    
    }
    


  • 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.



  • 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.



  • Wäre die initialsierug so ok ?

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


  • 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.



  • 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*



  • 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?



  • restore_tree_depth 😃

    Ich poste nachher mal meine Baustelle. 🙂


Log in to reply