0

我正在HUFFMAN ALGORITHM上编写一个程序，其中我有一类节点（hnode）来包含符号（name）及其出现频率（freq）；和其他用于形成树以获取符号代码的类 ( pq )。我只写了课程的相关部分。现在，当我尝试运行该程序时，当它第二次进入while 循环时，它总是卡在 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);
    }
}
4

2 回答 2

2

我建议在这里看看：

NIST 自适应霍夫曼

还有这里：

NIST 霍夫曼

代码示例也可以在那里找到。

于 2012-06-15T19:36:47.027 回答
2

您的代码在这里创建了一个本地范围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抓住它。听起来是一个非常糟糕的主意，因为在每次迭代的 while 循环结束时hnode po 都会超出范围。

通常，您希望使用智能点和 RAII 进行自动内存管理，而不是到处进行新的和删除的操作。

于 2012-06-15T20:35:44.197 回答