Probleme mit Pointer und Rekursion

hssjc

Hallo Leute,
ich habe mich grade hier neu im Forum angemeldet weil ich ein Problem habe und einfach nicht weiter komme. Ich bin gerade dabei ein Programm zu schreiben welches Datei mittels Huffmann Algorithmus komprimiert.

Soweit so gut, ich kann die Datei einlesen und den Baum aufbauen, aber beim erstellen der Code Tabelle habe ich Probleme. Ich durchlaufe den Huffmann Baum rekusiv, und immer wenn ich an einem Blatt angekommen bin wird der erzeugte Huffman Code in der Code Tabeklle gespeichert.
Der Huffmann Code wird mit Strings erzeugt, für den linken Teilbaum wird eine
0 angehängt und für den rechten Teilbaum eine 1.
Wenn ich das so mache wirft mir der Computer irgendwas mit den Pointern durcheinander und die manche Zeiger auf Child-Nodes zeigen irgendwohin und es kommen gnaz komische Werte raus.
Wenn ich den Baum durchlaufe und mir nur die Werte der Blätter ausgeben lasse funktioniet aber alles einwandfrei.
Ich bin ziemlicher C++ Neuling und kann mir das nicht recht erklären, wisst ihr Rat ?

Hier der Code der den Baum durchläuft

void Huffmann::traverseNodes(vector<string>* vec, struct node* aNode, string s)
{
  if (aNode -> leaf == true)
  {
    vec -> at(aNode -> value) = s;
    printf("Wert %d mit Freq %f hat den H-Code %s \n", aNode -> value,
        aNode -> frequency, s.c_str());
  }
  else
  {

    string l = "0";
    string r = "1";
    l.insert(0, s);
    r.insert(0, s);

    struct node* ln = aNode -> left;
    struct node* rn = aNode -> right;
    if (ln == NULL || rn == NULL)
    {
      printf("Fehler, ein Kindkonten ist null");
      exit(0);
    }

    traverseNodes(vec, ln, l);
    traverseNodes(vec, rn, r);
  }
}

node ist einfach ein struct das ich mir definiert habe

struct node
{
  struct node* left;
  struct node* right;
  unsigned char value;
  float frequency;
  bool leaf;
  bool selected;
};

und hier noch der Code der vor dem Aufruf der traverse Funktion ausgeführt wird.
Also zu Anfang füge ich alle Blätter in den Vector "theTree", und gehe dann nachd em Huffmann Algorithmus vor und suche mir immer die kleinsten Zwei Werte und verbinde diese mit einer Kante. Die Nachfolgerknoten werden dann in left und right gespeichert. (lastIndex1 und lastIndex2 sind die Positionen im Vector der zwei kleinsten Knoten)

struct node newNode;
    newNode.left = &theTree.at(lastIndex1);
    newNode.right = &theTree.at(lastIndex2);
    newNode.selected = false;
    newNode.leaf = false;
    newNode.value = 1;
    newNode.frequency = node1.frequency + node2.frequency;

    printf("FÃ¼ge neuen Knoten hinzu, left %d right %d frequency %f \n",
        node1.value, node2.value, newNode.frequency);
    theTree.push_back(newNode);
  }

  // save code into vector
  std::vector<string> replaceTable(256, "11111111");
  traverseNodes(&replaceTable, &theTree.at(theTree.size() - 1), "");

Kann mein Fehler daher kommen das ich die Adressen der Nodes aus dem Vector beziehe, und wenn ich was mit Strings mache die interne Speicherverwaltung das alle über den Haufen wirft und manchen Nodes im Vector neue Adrssen vergibt ?

Wenn ich die Traverse Funktion rekursiv mit leeren Strings "" sich selbst aufrufen lasse, oder mit einem statischen dann wird der Baum korrekt durchlaufen, als Ergebnis erhält man dann

Wert 114 mit Freq 0.363636 hat den H-Code a
Wert 122 mit Freq 0.090909 hat den H-Code a
Wert 115 mit Freq 0.090909 hat den H-Code a
Wert 116 mit Freq 0.090909 hat den H-Code b
Wert 118 mit Freq 0.090909 hat den H-Code a
Wert 121 mit Freq 0.090909 hat den H-Code b
Wert 97 mit Freq 0.181818 hat den H-Code b

Wenn man aber in der Rekusion irgendwelche String Operationen macht kommt
folgendes raus

Wert 114 mit Freq 0.363636 hat den H-Code 0
Wert 122 mit Freq 0.090909 hat den H-Code 100
Wert 255 mit Freq 0.090821 hat den H-Code 1010
Wert 4 mit Freq 0.000000 hat den H-Code 1011
Wert 3 mit Freq 0.000000 hat den H-Code 1100
Wert 25 mit Freq 0.000000 hat den H-Code 1101
Wert 97 mit Freq 0.181818 hat den H-Code 111

Da verhauts dann irgendwie 4 Werte ??

DocShoe

Erst einmal Herzlich Willkommen im Forum und allergrößten Respekt für dein erstes Posting! Ordentlich Sätze, sogar mit Satzzeichen, eine genaue Beschreibung des Problems, Bereitstellung des Quelltextes inklusive Verwendung von Code Tags... vorbildlich!

Wie du schon richtig vermutet hast können Adressen von Elementen in einem Vektor ungültig werden, nämlich dann, wenn die Kapazität des Vektors nicht mehr ausreicht und er reallokieren muss. Damit kann es passieren, dass deine Zeiger irgendwo in´s Nirvana zeigen und dein Programm seltsame Ergebnisse produziert.

Edit:
Kannst dir ja mal die Adressen der Vektorelemente und die Adressen, auf die sie zeigen ausgeben lassen. Da solltest du erkennen können, ob die Zeiger noch gültig sind oder nicht.

hssjc

Hi Doc,
Hast du ne Idee wie ich das Problem umgehen könnte ?
Ich meine am Vektor selbst wird ja nichts verändert, sondern
ich führe einfach nur folgende String Operationen in
der Rekursion aus

string l = "0";
    string r = "1";
    l.insert(0, s);
    r.insert(0, s);

Ich könnte mir einen Tree aus festen Objekten aus dem fertigen Baum erstellen.
Aber kann dann nicht schon während des Aufbaus des Huffmann-Tree die Adressen
der Pointer ungültig werden ?
Gruß
Till

DocShoe

Du kannst die Knoten dynamisch auf dem Heap erstellen und die Zeiger in den Vektor einfügen. Die Zeiger bleiben auch nach einem vector::resize() gültig, allerdings musst du die hinterher alle manuell wieder abräumen.
Wenn du Zugriff auf die boost Bibliotheken hast kannst du ptr_vector benutzen, der das dann von alleine macht.

Nexus

Wenn du die Anzahl Elemente vorher weisst, kannst du auch mit std::vector::reserve() genügend Speicher anfordern, sodass keine Reallokationen nötig sind. Oder du verwendest einen anderen Container. std::deque sollte bestehende Elemente nicht verschieben, wenn du nur neue einfügst. Und sonst sicher std::list und alle vier assoziativen Container.

hssjc

Hi Leute,
Danke für eure Tips.
Also mit dem reserve hat es nicht geklappt.
Ich habe in den Nodes nun anstatt einen Zeiger auf die Kindknoten
einfach den Index im Vektor gespeichert. Da sich die Reihenfolge
im Vektor nicht ändert klappt das wunderbar
Gruß
Till