优先级队列错误顺序

我正在编程huffman编码。这是我的程序的开始：优先级队列错误顺序

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

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

来源

2010-03-03 TheArchitect

你应该告诉你的优先级队列它应该排序。在你的情况下，你必须告诉它按Node::occurence排序。

来源

2010-03-03 16:49:41

优先级队列中的元素是指针。由于你没有提供一个带有2个指向Node对象的函数，默认比较函数会比较2个指针。

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

您的运营<时使用节点与节点*

来源

2010-03-03 16:49:59 a1ex07

您存储指向节点在排队，但没有提供一个合适的比较功能进行比较，所以他们进行排序，通过比较指针。你提供的operator<会比较节点和指针，这不是你想要的。

有两个选项：

根据它们的值比较两个节点指针提供的功能，并给该函数到队列，或
在队列中存储节点的目的，并提供一个operator<来比较两个节点。

第二个选项也将修复你的代码中的内存泄漏，并删除一堆不必要的内存分配，所以我建议。

来源

2010-03-03 16:57:15

Tnx，现在有效。我现在编程了一段时间，但我刚接触C++。我不得不说越好，你越懂得语言就越爱你。但我认为开始很难。 – TheArchitect

优先级队列错误顺序

回答

相关问题