yet another huffman tree problem

This is a discussion on yet another huffman tree problem within the C++ Programming forums, part of the General Programming Boards category; Code: #include <iostream> #include <string> #include <vector> #include <algorithm> #define NONE_FOUND 30000 using namespace std; struct node { node* one; ...

  1. #1
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493

    yet another huffman tree problem

    Code:
    #include <iostream>
    #include <string>
    #include <vector>
    #include <algorithm>
    #define NONE_FOUND 30000
    using namespace std;
    struct node {
     node* one;
     node* zero;
     node* parent;
     char value;
     int amount;
     node (int x) {
       one=NULL;
       zero=NULL;
       value=x;
       amount=1;
       parent=NULL;
     }
     void add() {
      amount++;
     }
    };
    
    class huffman_tree {
    
    public:
    vector<node*> node_list;
    vector<int> code_temp;
    
     int search(int x) {
       for (int i=0;i<node_list.size();i++)
        if (node_list[i]->value==x)  return i;
     return NONE_FOUND;
     }
    
     void add(int x) {
      int temp=search(x);
      if (temp!=NONE_FOUND)
        node_list[temp]->add();
      else node_list.push_back(new node(x));
     }
    
    
    
     void bubblesort()  {
       node* temp;
       int n=node_list.size();
       for (int i=0;i<n-1;++i)
        for (int j=1;j<n-i;++j)
         if (node_list[j-1]->amount > node_list[j]->amount) {
           temp=node_list[j];
           node_list[j]=node_list[j-1];
           node_list[j-1]=temp;
    
         }
     }
    
    void sort_it() {
     bubblesort();
     }
    
      void huff() {
    
       while (node_list.size() > 1) {
    
         join (node_list[0],node_list[1]);
         node_list.erase(node_list.begin(),node_list.begin()+1);
         node_list[0]=node_list[0]->parent;
         int place=0;
         while (node_list[place] -> amount <= node_list[0]->amount && place < node_list.size()) place++;
         node_list.insert(node_list.begin()+place,node_list[0]);  //find place
         node_list.erase(node_list.begin(),node_list.begin()+1);
    
    
       }
      }
      void join(node* a, node* b) {
       add(1);
       node* parent;
       parent=node_list[node_list.size()-1];
       b->parent=parent;
       a->parent=parent;
       parent->one=b;
       parent->zero=a;
       a->parent->amount=a->amount+b->amount;
    
      }
      void print_tree() {
        cout << node_list[0]->value;
        cout << node_list[0]->zero->value;
        /*this function used mostly for debugging */
      }
      void lookup() {
    
        get_letters(node_list[0]); //all values should have been stored in the code_temp vector array
        while (code_temp.size()) {
         code_temp.erase(code_temp.begin(),code_temp.begin()+1);
        cout << code_temp[0];  //show the results, this is gonna be changed later
         }
      }
      int get_letters(node* x) {
    
       if (x->zero!=NULL) { code_temp.push_back(0); /*next statement added for debugging */
    cout << x->zero << " "; get_letters(x->zero); }
       if (x->one!=NULL)  { code_temp.push_back(1); get_letters(x->one); }
    
    
      }
    
    };
    
    int main()
    {
    huffman_tree tree;
    
    
    string temp="yabba dabba doo";
    char letter;
    while (temp.length()) {
     letter=temp.at(0);
     temp.erase(0,1);
     tree.add(letter);
    }
    tree.sort_it();
    tree.huff();
    tree.print_tree();
    tree.lookup();
    }
    if this code looks familiar, it's because i posted a few days ago concerning a problem. basicly, this code causes a stack overrun. what's happening is after linking the nodes together in a huffman coding manner(which i think it's messing up on), the lookup function is supposed to probe each tree limb and print a code for each letter.
    i think that for some reason, by some mistake, a node points to itself. (i've confirmed this with cout statements until it complains of stack overrun). can anyone spot why this is happening?
    thanks for reading this far.

    some other info:
    most everything else works, until the huffman tree is created. the vector array node_list stores and sorts the nodes by frequency. each node has a parent pointer, a one pointer, and a zero pointer. the zero and one pointers point further down the tree, while the parent pointer goes up.
    huff() is supposed to organize the nodes into a tree. the nodes are assumed already sorted into order by frequency. the two lowest nodes are combined using the join function. one node is removed from the array, and the other one is replaced by its newly created parent node. then the parent node is sorted back into line. this process repeats until only one node is left.

  2. #2
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    here's the simplified code:
    Code:
    struct node {
     node* one;
     node* zero;
     node* parent;
     char value; //letter
     int amount; //number of letters
     node (int x) {
       one=NULL; //for some reason this changes as it progresses through the code
       zero=NULL;//ditto
       value=x;
       amount=1;
       parent=NULL;
     }
     void add(); //just does amount++
    };
    
    class huffman_tree {
    public:
    vector<node*> node_list; //an array of nodes. once they get linked into a tree everything will be under node_list[0]
    vector<int> code_temp; // a fairly global solution, will change later
    
     int search(int x); //if the character 'x' is found in the node_list, return its location
    
    void add(int x); //add letter 'x' onto the node_list
    void bubblesort(); //sort node_list by frequency (ie, by amount)
    void sort_it(); //calls bubblesort for now, will change later to better sorting method
    
    void huff() {
    //while there's still two nodes left:
     //call join(), join node_list[0] and node_list[1]
     //remove two nodes from beginning, replace with their parent
     //locate the right space to insert the new parent node
     //move the parent node there
    }
    
    void join(node* a, node* b) //make a node, put two other nodes under it
    {
    //call add function to create new node with value of 1 to distinguish it from letter nodes
    //assign temp. 'parent' pointer to newly created node
    //point the two nodes' parent pointers at it
    //point ther parent's two children pointers at the two nodes
    //make the parent node's amount the sum of the children nodes
    }
    void print_tree() ; //debugging purposes
    void lookup() //create lookup table
    {
    //call get_letters(top node) 
    //then print the code
    }
    int get_letters(node* x) {
    //if x's zero pointer is pointing to something, push a zero into the buffer
    //if x's one pointer is pointing to something, push a one into the buffer
    //in either case, call get_letters for a node under this one
    }
    };
    
    int main()
    {
    huffman_tree tree;
    
    
    string temp="yabba dabba doo";
    char letter;
    while (temp.length()) {  //add 'temp' into huffman list
     letter=temp.at(0);
     temp.erase(0,1);
     tree.add(letter);
    }
    tree.sort_it();  //sort tree by 'amount' value: 0 is smallest
    tree.huff(); // organize into huffman table
    tree.print_tree(); //right now it does practicly nothing
    tree.lookup(); // organize tree into lookup table
    }
    hope it helps:
    Last edited by ygfperson; 04-17-2002 at 09:53 PM.

  3. #3
    Just because ygfperson's Avatar
    Join Date
    Jan 2002
    Posts
    2,493
    solved it by rewriting the code. got rid of join(), and rewrote huff() like this:
    Code:
    void huff() {
       while (node_list.size() > 1) {
        node_list[0]->parent=new node(1); /// transform two nodes into its parent node
        node_list[0]->parent->zero=node_list[0];
        node_list[0]->parent->one=node_list[1];
        node_list[1]->parent=node_list[0]->parent;
        node_list.erase(node_list.begin(),node_list.begin()+1);
        node_list[0]=node_list[0]->parent;
        node_list[0]->amount=node_list[0]->zero->amount + node_list[0]->one->amount;
    
        sort_it();  //a cheap way to sort it back
       //repeat
       }
      }
    simplicity rocks. (yes, i know it's very wasteful to sort the whole list every single loop instead of just moving the node, but i'm tired and bug-prone)

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  2. Problem passing data between functions
    By manutdfan in forum C Programming
    Replies: 9
    Last Post: 12-10-2006, 04:32 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM
  4. Binary Search Tree, Inserting node
    By cheryl_li in forum C Programming
    Replies: 1
    Last Post: 09-13-2003, 04:53 AM
  5. BST/Red and Black Tree
    By ghettoman in forum C++ Programming
    Replies: 0
    Last Post: 10-24-2001, 11:45 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21