3

私はハフマン符号化をプログラミングしています。これが私のプログラムの始まりです。

using namespace std;

//Counting methods
int *CountCharOccurence(string text)
{
    int *charOccurrence = new int[127];
    for(int i = 0; i < text.length(); i++)
    {
        charOccurrence[text[i]]++;
    }
    return charOccurrence;
}

void DisplayCharOccurence(int *charOccurrence)
{
    for(int i = 0; i < 127; i++)
    {
        if(charOccurrence[i] > 0)
        {
            cout << (char)i << ": " << charOccurrence[i] << endl;
        }
    }
}

//Node struct
struct Node
{
    public:
        char character;
        int occurrence;

        Node(char c, int occ) {
            character = c;
            occurrence = occ;
        }

        bool operator < (const Node* node)
        {
            return (occurrence < node->occurrence);
        }
};

void CreateHuffmanTree(int *charOccurrence)
{
    priority_queue<Node*, vector<Node*> > pq;
    for(int i = 0; i < 127; i++)
    {
        if(charOccurrence[i])
        {
            Node* node = new Node((char)i, charOccurrence[i]);
            pq.push(node);
        }
    }

    //Test
    while(!pq.empty())
    {
        cout << "peek: " << pq.top()->character <<  pq.top()->occurrence << endl;
        pq.pop();
    }
}

int main(int argc, char** argv) {

    int *occurrenceArray;
    occurrenceArray = CountCharOccurence("SUSIE SAYS IT IS EASY");
    DisplayCharOccurence(occurrenceArray);
    CreateHuffmanTree(occurrenceArray);

    return (EXIT_SUCCESS);
}

プログラムは最初に文字とその出現番号を出力します。これは問題ないようです：

：4
A：2
E：2
I：3
S：6
T：1
U：1
Y：2

ただし、ノードの内容を優先順に表示する必要があるテストループは、次のように出力します。

ピーク：Y2
ピーク：U1
ピーク：S6
ピーク：T1
ピーク：I3
ピーク：E2
ピーク：4
ピーク：A2

これは予期された順序ではありません。なんで？

4

3 に答える 3

5

プライオリティ キューの要素はポインタです。Node オブジェクトへの 2 つのポインターを受け取る関数を提供していないため、デフォルトの比較関数は 2 つのポインターを比較します。

bool compareNodes(Node* val1, Node* val2)
{
   return val1->occurence < val2->occurence;
}
priority_queue<Node*, vector<Node*>,compareNodes > pq;

演算子 < は、Node が Node* と比較されるときに使用されます

于 2010-03-03T16:49:59.730 に答える
1

キュー内のノードへのポインターを格納していますが、適切な比較関数が提供されていないため、ポインターを比較してソートされます。あなたoperator<が提供したものは、ノードをポインタと比較しますが、それはあなたが望むものではありません。

2つのオプションがあります。

  • 2つのノードポインタをその値に従って比較する関数を提供し、この関数をキューに渡すか、または
  • ノードオブジェクトをキューに格納し、operator<2つのノードを比較するためのを提供します。

2番目のオプションも、コードのメモリリークを修正し、不要なメモリ割り当ての山全体を削除するので、それをお勧めします。

于 2010-03-03T16:57:15.373 に答える
1

プライオリティ キューに何を並べ替えるかを指定する必要があります。あなたの場合、 でソートするように指示する必要がありますNode::occurence。

于 2010-03-03T16:49:41.663 に答える