Хаффман алгоритм

Question

Я делаю программу на HUFFMAN АЛГОРИТМА где у меня есть один класс узлов (hnode) содержать символ (имени) и частоты его встречаемости (FREQ); и другой класс (pq), который используется для формирования дерева , чтобы получить код для символов. Я написал только соответствующие части классов. Теперь, когда я пытаюсь запустить эту программу, он всегда застревает в цикле while (в main()), когда он вводит во время цикла второй раз. Я пробовал все, но все еще не мог понять, почему ... Может кто-нибудь, пожалуйста, поможет сделать этот код запущенным!

#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); 
    } 
} 

Answer 1

вашего кода, создающего локальную область hnode po здесь:

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); 
} 

Тогда вы передаете, что вокруг по адресу и вы делаете pq::node держаться на что. Звучит как очень плохая идея, так как hnode poвыходит за рамки в конце вашего цикла while на каждой итерации.

В общем, вы хотите использовать смарт-точки и RAII для автоматического управления памятью, а не для новых и удалений по всему месту.

Answer 2

Я предлагаю иметь взгляд здесь:

NIST adaptive Huffman

, а также здесь:

NIST Huffman

Образцы кода можно найти там.