3. Baumstruktur

Baumstruktur

  • U

    Hat jemand da einen guten Link für mich parat? Google spuckt in jedem zweiten Link nur was zu binären Bäumen aus. Mir geht es aber um einen Baum mit n Ästen je Knoten.

    0
  • G

    Fütter google mit Bayer-Bäumen.

    MfG

    GPC

    0
  • U

    Mhh das scheint mir auch nicht das richtige zu sein. Da bei mir für jede Ebene die Anzahl der Äste variiert, d.h. n1 != n2
    Außerdem scheint der Bayer-Baum eine Sortierung vorzunehmen, die in diesem Sinn von mir nicht erwünscht ist.

    Ich brauche einen Baum, der die Struktur einer XML-Datei darstellt ähnlich einem HTML-Dokument 😉

    0
  • J

    UNeverNo schrieb:

    Ich brauche einen Baum, der die Struktur einer XML-Datei darstellt ähnlich einem HTML-Dokument 😉

    Wie wär's dann mit irgendeiner XML-Library, die ne DOM-Implementierung hat? Ansonsten halt die übliche Struktur:

    class Node {
  std::vector<Node*> children;
}

    Oder sowas ähnliches.

    0
  • U

    Ja, DOM habe ich mir schon mal heruntergeladen, allerdings war mir eine Projektmappe mit 32 Projekten dann doch zuviel des guten für das an sich kleine Problem.

    Schöner Code 😃

    Allerdings kann ich damit wenig bis gar nichts anfangen, daher auch meine Frage nach einem Link 😉

    0
  • D

    Naja Bäume mit mehreren Knoten sind B-Bäume oder B*-Bäume (ersteres hab ich mal ausprogrammiert und es war ne scheiß heidenarbeit).

    Das mit der xml struktur lesen kannst du dir ja selber schreiben (wobei es GARANTIERT komplizierter ist als ich mir das vorstelle) und dann den Baum nach der Reihe mit den einträgen füllen

    0
  • J

    DeX3 schrieb:

    Naja Bäume mit mehreren Knoten sind B-Bäume oder B*-Bäume (ersteres hab ich mal ausprogrammiert und es war ne scheiß heidenarbeit).

    Ne, umgekehrt. B-Bäume sind Bäume mit mehreren Knoten. Aber nicht jeder Baum mit mehr als zwei Kindern pro Knoten ist gleich ein B-Baum.

    @UNeverNo:

    Wieso kannste damit nichts anfangen? Was genau ist daran unklar?
    Ansonsten kannste auch mal nach Kompositum googlen (oder ins GOF-Buch schaun). Sowas in der Art wirste wohl brauchen.

    0
  • U

    Ich habe jetzt mal ein wenig herumversucht. Allerdings wurden mir, als ich eine leere Methode einbinden wollte zwei Fehler gemeldet. Habe sie mal unten aufgeführt.

    Ich nutze Dev-CPP.

    #include <list>
#include <string>

using namespace std;

class xmldir
 {
    xmldir* father; //Knoten
    list <xmldir*> children; //Äste
    string name; //Name des Knotens
    string value; //Inhalt des Knotens

    public void insert(string Name, string Value)  //syntax error before `void'
    {
    } //missing ';' before right brace

 };

 int main(void)
 {
     xmldir* xmltree = new xmldir();
     return 0;
 }

    Der Ansatz sollte von der Struktur richtig sein, oder?

    0
  • J

    UNeverNo schrieb:

    public void insert(string Name, string Value) //syntax error before `void'
    {
    } //missing ';' before right brace

    Zu viel Java programmiert. 🙂
    In C++ kommt das public nicht in die Methodendeklaration.

    Sieht schonmal nicht schlecht aus. Du solltest Dir allerdings überlegen, ob Du wirklich ne list haben willst um die Kinder zu halten. Da haste halt keinen Indexzugriff und wenn Du vernünftig viele Kinder hast ist Einfügen/Löschen mit dem vector trotz Verschiebens noch schneller. Da aber alles schön private ist sollte sich das auch später noch austauschen lassen.

    0
  • U

    Eher zuviel Java-Beispiele angesehen 😃

    Die XML-Dateien, die ich parsen will werden max. 10k groß sein, nichtsdestotrotz ist so ein indizieren natürlich praktisch und man weiss ja nie, wozu man den Parser nochmal gebrauchen kann 😉
    Vektoren habe ich mir mal kurz angeschaut, die sollten handlebar sein.

    Allerdings war Zeiger-Arithmetik schon immer ein Buch mit sieben Siegeln für mich, wäre nett, wenn man mich da ein wenig unterstützen könnte 🙂

    Habe es jetzt mal in eine Headerdatei ausgelagert.

    xmldir.h

    #include <vector>
#include <string>

using namespace std;lös

class xmldir
{
    xmldir* father; //Knoten
    vector <xmldir*> children; //Äste
    string name; //Name des Knotens
    string value; //Inhalt des Knotens

    public:
        xmldir(void);
        ~xmldir(void);
        void insertNode(string Name, string Value);
        string getInfo(string Name);
        void delAll(void);
};

    xmldir.cpp

    #include <xmldir.h>
#include <vector>
#include <string>

using namespace std;

xmldir::xmldir(void)
{
}

xmldir::~xmldir(void)
{
}        

void xmldir::insertNode(string Name, string Value)
{
}    

string xmldir::getInfo(string Name)
{
}

void xmldir::delAll(void)    
{
}

    main.cpp

    #include <xmldir.h>
#include <vector>
#include <string>

using namespace std;

int main(void)
{
    xmldir* xmltree = new xmldir();
    return 0;
}

    Im Konstruktor müßte ich wohl einen Anker setzen, um mir das oberste Element zu merken, oder?
    Im Destruktor müßte das Objekt zerstört werden, was letztlich identisch mit dem DeleteAll ist. Daher kann ich das wohl entfernen?
    Mhh beim schreiben muss der aktuelle ast zu einem unterknoten werden.
    Beim lesen kann ich mich dann anhand des namens langhangeln, nur halt irgendwie mit zeigern 😕

    0
  • J

    UNeverNo schrieb:

    Allerdings war Zeiger-Arithmetik schon immer ein Buch mit sieben Siegeln für mich, wäre nett, wenn man mich da ein wenig unterstützen könnte 🙂

    Zeigerarithmetik solltest Du eigentlich nicht brauchen.

    Im Konstruktor müßte ich wohl einen Anker setzen, um mir das oberste Element zu merken, oder?
    Im Destruktor müßte das Objekt zerstört werden, was letztlich identisch mit dem DeleteAll ist. Daher kann ich das wohl entfernen?
    Mhh beim schreiben muss der aktuelle ast zu einem unterknoten werden.
    Beim lesen kann ich mich dann anhand des namens langhangeln, nur halt irgendwie mit zeigern 😕

    Das verwirrt mich jetzt auch gerade etwas. Mal langsam. Damit das ganze praktisch benutzbar wird, solltest Du jedem Node mal ne Methode geben, mit der man alle Kinder abfragen kann. Im Prinzip reicht da ne const-Referenz auf den vector mit den Pointern.

    Den Zeiger auf den Vaterknoten mußt Du immer dann setzen, wenn der Knoten irgendwo eingehängt wird. Das muß aber nicht unbedingt bei der Konstruktion sein. Ich würde vorschlagen, daß das die Aufgabe des Vaters ist. Wenn Du also einen Knoten einfügst, dann mußt Du ihm mitteilen, wer sein Vater ist.

    Allerdings könntest Du Dir das auch sparen, wenn Du möchtest. Du weißt schließlich normalerweise auf welchem Weg Du in einen Tag gekommen bist und kannst diese Information außen mitverwalten. Ich bin mir auch nicht sicher, inwiefern da wirklich Bedarf dafür da ist.

    Das Interface würde ich erstmal so einfach wie möglich halten:

    class xmlNode
{
    vector <xmlNode*> children;
    string name; 
    string value;

public:
    xmlNode(string name, string value):name(name), value(value) {}

    ~xmldir() 
    {
      for(size_t i=0; i<children.size(); ++i)
        delete children[i];  
    }

    std::vector<xmlNode*> const& getChildren() { return children; }

    void addNode(xmlNode*node)
    {
      children.push_back(node);
    }

    // vielleicht noch ein insertNode mit Positionsangabe an welcher Stelle 
    // bei den Kindern es eingefügt werden soll.

    void removeNode(xmlNode*node) // in children suchen und entfernen
    void deleteNode(xmlNode*node) // in children suchen, delete und entfernen

    // Methoden zum Zugriff auf die Daten in diesem Node
};

    Zu bessern Benutztung würde ich dann noch einen XmlTree bauen, der intern den root-Node speichert und vielleicht ein paar unterstützende Methoden bereitstellt.

    MfG Jester

    0
Anmelden zum Antworten