我正在编程霍夫曼编码。这是我的程序的开头:
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* 比较时使用您的运算符 <
关于c++ - 优先队列错序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/2373119/