c – 优先级队列错误的顺序

发布时间：2020-12-16 09:26:34 所属栏目：百科来源：网络整理

导读：我正在编写霍夫曼编码.这是我的计划的开始： using namespace std;//Counting methodsint *CountCharOccurence(string text){ int *charOccurrence = new int[127]; for(int i = 0; i text.length(); i++) { charOccurrence[text[i]]++; } return charOccurr

我正在编写霍夫曼编码.这是我的计划的开始：

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

但是必须以优先级顺序显示节点内容的测试循环输出：

peek: Y2
peek: U1
peek: S6
peek: T1
peek: I3
peek: E2
peek:  4
peek: A2

这不是预期的顺序.为什么？

解决方法

优先级队列中的元素是指针.由于您没有提供带有2个指向Node对象的函数,因此默认比较函数会比较2个指针.

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

您的操作符< Node与Node *比较时使用

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!