優先級隊列錯誤順序

我正在編程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

優先級隊列錯誤順序

回答

相關問題