0

HUFFMAN ALGORITHMでプログラムを作成しています。ここでは、シンボル ( name ) とその発生頻度 ( freq ) を含むノード ( hnode ) のクラスが 1 つあります。シンボルのコードを取得するためにツリーを形成するために使用される他のクラス（pq） 。クラスの関連部分だけを書きました。このプログラムを実行しようとすると、 2 回目に 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

あなたのコードは、ここでローカルスコープ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 に答える
2

ここをご覧になることをお勧めします：

NIST適応ハフマン

そしてここにも：

NIST ハフマン

コードサンプルもそこにあります。

于 2012-06-15T19:36:47.027 に答える