Huffman failing - stuck on traversal

This is a discussion on Huffman failing - stuck on traversal within the C++ Programming forums, part of the General Programming Boards category; Well, I'm still stuck here. I thought that I would be able to create a copy of my values vector ...

  1. #1
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79

    Huffman failing - stuck on traversal

    Well, I'm still stuck here. I thought that I would be able to create a copy of my values vector of Huff pointers, and start on them as a method of going from the leaves of this budding Huffman tree up to it's root. I did not use delete in the deletePtr function because I thought it would interfere with the pointer in the traverse function recognizing the tree structure that I have created in main before calling it. Well, after I call it, I have traced the fact that the while loop:
    Code:
    void traverse(vector<Huff*> v)  // took out ampersand
    {
        int i;
        Huff* p;
        stack<int> s;
        //cout<<v[0]->parent<<endl;
        for(i=0; i<v.size(); i++)
        {
            p=v[i];
            cout<<p->parent<<endl;
    /***************************here************/
            while(p->parent != NULL)
            {
                cout<<"Debug"<<endl;
                p=p->parent;
                if(p->left->ch == v[i]->ch)
                {
                    s.push(0);
                }
                else
                {
                    s.push(1);
                }
            }
            //cout<<v[i]->ch<<" ";
            while(!s.empty())
            {
                cout<<"Debug";
                cout<<s.top();
                s.pop();
            }
        }
        cout<<endl;
        return;
    }
    never executes. Furthermore, I can't figure out why parent is always NULL. I expected it to be recognized, but clearly I am mistaken. Any ideas why this attempted traversal of the Huffman algorithm I have dreamed up has not gotten off the launching pad? I may have to wind up doing a pre-order traversal. If so, could someone give me some pointers about that? Thanks, Steve
    Code:
    #include<iostream>
    #include<vector>
    #include<fstream>
    #include<stack>
    using namespace std;
    
    struct Huff;
    
    void deletePtr(vector<Huff*>& v, Huff* m);
    Huff* findMinimum(vector<Huff*>& v);
    void traverse(vector<Huff*> v); // took out ampersand
    
    struct Huff
    {
        Huff();
        int count;
        char ch;
        Huff* left;
        Huff* right;
        Huff* parent;
    };
    
    int main(int argc, char* argv[])
    {
    	if(argc<2)
    	{
    	    cout<<"Not enough arguments were provided."<<endl;
    		return -1;
    	}
        ifstream myFile(argv[1], ios::in);
    	if(!myFile.is_open())
    	{
    	    cout<<"Unknown file specified."<<endl;
    		return -1;
    	}
    	char cz;
        int i;
        vector<Huff*> values;
        while(myFile.get(cz))
        {
            if(cz < 'a' || cz > 'z')
                continue;
            for(i=0; i<values.size(); i++)
            {
                if(values[i]->ch == cz)
                {
                    values[i]->count++;
                    break;
                }
            }
            if(values.size()==i)
            {
                Huff* h = new Huff;
                h->ch=cz;
                h->count=1;
                values.push_back(h);
            }
         }
         if(values.size() == 0)
         {
             cout<<"File is empty.\n";
             return 0;
         }
         if(values.size() == 1)
         {
             cout<<values[0]->ch<<"1"<<endl;
         }
         vector<Huff*> copy;
         for(i=0; i<values.size(); i++)
         {
             copy.push_back(values[i]);
         }
         Huff* min;
         Huff* min2;
         while(values.size() > 1)
         {
             min=findMinimum(values);
             deletePtr(values, min);
             min2=findMinimum(values);
             deletePtr(values, min2);
             Huff* p=new Huff;
             p->left=min;
             p->right=min2;
             p->count=min->count+min2->count;
             values.push_back(p);
         }
         traverse(copy);
         return 0;
    }
    
    Huff::Huff() : ch(0), count(0), left(NULL), right(NULL),
                  parent(NULL) { }
    
    Huff* findMinimum(vector<Huff*>& v)
    {
         int i, minCo=v[0]->count;
         char minCh=v[0]->ch;
         Huff* h3=v[0];
         for(i=1; i<v.size(); i++)
         {
             if(v[i]->count < minCo)
             {
                 minCo=v[i]->count;
                 minCh=v[i]->ch;
                 h3=v[i];
             }
         }
         return h3;
    }
    
    void deletePtr(vector<Huff*>& v, Huff* m)
    {
        int i;
        i=0;
        while(i < v.size() && v[i]->ch != m->ch)
        {
            i++;
        }
        for( ; i<v.size()-1; i++)
        {
            v[i]=v[i+1];
        }
        v.pop_back();
        // decided not to delete m
    }
    
    void traverse(vector<Huff*> v)  // took out ampersand
    {
        int i;
        Huff* p;
        stack<int> s;
        //cout<<v[0]->parent<<endl;
        for(i=0; i<v.size(); i++)
        {
            p=v[i];
            cout<<p->parent<<endl; // always "0"
            while(p->parent != NULL)
            {
                cout<<"Debug"<<endl; // never executes
                p=p->parent;
                if(p->left->ch == v[i]->ch)
                {
                    s.push(0);
                }
                else
                {
                    s.push(1);
                }
            }
            cout<<v[i]->ch<<" ";
            while(!s.empty())
            {
                cout<<"Debug";
                cout<<s.top();
                s.pop();
            }
        }
        cout<<endl;
        return;
    }

  2. #2
    Banned master5001's Avatar
    Join Date
    Aug 2001
    Location
    Visalia, CA, USA
    Posts
    3,685
    Could you do me a big favor and show me the source for the class?

  3. #3
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>I may have to wind up doing a pre-order traversal. If so, could someone give me some pointers about that?
    std::vector<pre_order_traversal*> pPot(10);


    Err.. sorry. Assuming v[0] is the root node, doesn't that mean its parent is NULL? So you'll crash on the very first try and never realize that it would have worked if you just kept going That's just a wild guess, by the way. But I don't really see why you need to have all your pointers in a vector; all you really need, usually, is the root pointer and a few good recursive functions that do the traversing from there. I'm pretty sure Sang-drax posted a nice implementation of that for a contest a while back (though it had a minor bug). I wrote a similar implementation later, which you can find at my website (see my signature) if you're interested.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  4. #4
    C++ Developer XSquared's Avatar
    Join Date
    Jun 2002
    Location
    Ontario, Canada
    Posts
    2,718
    > I'm pretty sure Sang-drax posted a nice implementation of that for a contest a while back (though it had a minor bug).
    I had done one with a minor bug in it for this contest. I posted the correct code near the end of the thread.
    Naturally I didn't feel inspired enough to read all the links for you, since I already slaved away for long hours under a blistering sun pressing the search button after typing four whole words! - Quzah

    You. Fetch me my copy of the Wall Street Journal. You two, fight to the death - Stewie

  5. #5
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    My bad. It was XSquared
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  6. #6
    diligentStudent()
    Join Date
    Apr 2002
    Posts
    79
    Thanks folks. I got it eventually. Best, Steve

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. depth-first traversal of directories
    By geekoftheweek in forum C Programming
    Replies: 0
    Last Post: 03-31-2009, 01:22 AM
  2. Replies: 6
    Last Post: 10-23-2006, 07:22 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. initializes all components of failing to false
    By romeoz in forum C++ Programming
    Replies: 21
    Last Post: 08-01-2003, 09:30 PM
  5. Huffman compression
    By SMurf in forum C Programming
    Replies: 2
    Last Post: 09-01-2001, 07:30 AM

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