CODEWITHSUNDEEP
c++classhuffman-code
cirronimbo
cirronimbo

Reputation: 929

huffman algorithm

I'm making a program on the HUFFMAN ALGORITHM where I have one class of nodes (hnode) to contain the symbol (name) and its frequency of occurence (freq); and other class (pq) which is used to form the tree to get the code for the symbols. I have written only the relevant parts of the classes. Now when I try to run this program it always gets stuck in the while loop (in main()) when it enters the while loop second time. I've tried everything but still couldn't figure out why... Can somebody please help to make this code run !!

#define NPTR hnode*
class pq;
class hnode
{
    string name;
    int freq;
    friend class pq;

    public:

    NPTR phnode;
    void show () 
    { cout << "name = " << name << endl << ", freq= " << freq <<endl ; }

    hnode (string x, int fr): name(x), freq(fr)
    {
        phnode = this;
    }

    friend hnode operator + (hnode p, hnode q)
    {
        string s = q.name + p.name;
        int f = q.freq + p.freq ;
        hnode foo (s,f);
        return foo;
    }
};

class pq /// ascending priority queue
{
    struct node
    {
    NPTR data;
    node* next;
    node (NPTR p) : data(p), next(0) {}
    };
    public:
    int count;
    node* getnode (NPTR p) { return new node(p); }
    node* listptr;
    void place (NPTR );
    NPTR mindelete();
    pq() : listptr(0), count(0) {}
};

void pq::place (NPTR p)
{
    if(count == 0)
    {
        listptr = getnode(p);
    }

    else
    {
        node* foo = listptr, *bar = NULL;
        while( (foo!= NULL) && (p->freq >= foo->data->freq) )
        {
            bar = foo;
            foo = foo->next;
        }
        node* ptr = getnode(p);
        ptr->next = bar->next;
        bar->next = ptr;
    }
    ++count;
}

NPTR pq::mindelete()
{
    if(count==0) { cout<<"invalid\n"; exit(1);}
    NPTR val = listptr->data;
    listptr = listptr->next;
    --count;
    return val;
}

void main ()
{
    pq list;
    for ( int i=0; i<3; ++i)
    {
        string s;
        int f;
        cin>>s>>f;
        NPTR p = new hnode(s,f);
        list.place(p);
    }
    while(list.count>1)
    {
        NPTR p1 = list.mindelete();
        NPTR p2 = list.mindelete();
        hnode po = (*p1)+(*p2); // overloaded operator
        NPTR p = &po;
        p->show();
        list.place(p);
    }
}

Upvotes: 0

Views: 1608

Answers (2)

greatwolf
greatwolf

Reputation: 20838

Your code's creating a locally scoped hnode po over here:

while(list.count > 1)
{
    NPTR p1 = list.mindelete();
    NPTR p2 = list.mindelete();
    hnode po = (*p1)+(*p2); // overloaded operator
    NPTR p = &po;
    p->show();
    list.place(p);
}

Then you're passing that around by address and you're making pq::node hold onto that. Sounds like a really bad idea since hnode po goes out of scope at the end of your while loop on every iteration.

In general, you want to be using smart points and RAII for automated memory management rather than new'ing and delete'ing all over the place.

Upvotes: 2

Mare Infinitus
Mare Infinitus

Reputation: 8172

I suggest having a look here:

NIST adaptive Huffman

and also here:

NIST Huffman

Code samples can be found there also.

Upvotes: 2

Related Questions