歡迎來到Linux教程網
設為首頁 加入收藏
Linux教程網
Linux教程網
Linux教程網
您现在的位置： Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

C++使用優先隊列來構建huffman樹[哈夫曼樹]

  1. #include <iostream>   
  2. #include <queue>   
  3. #include <string.h>   
  4. #include <vector>   
  5. #include <algorithm>   
  6. using namespace std;  
  7.   
  8. char Table[26];  
  9.   
  10. struct Node  
  11. {  
  12.     int     freq;  
  13.     char    val;  
  14.     Node    * left;  
  15.     Node    * right;  
  16.     Node():left(NULL), right(NULL) , freq(0) , val('0'){}  
  17. };  
  18.   
  19. class Cmp  
  20. {  
  21. public:  
  22.     bool operator() (const Node * a, const Node * b) const  
  23.     {  
  24.         return  a->freq > b->freq;  // 從小到大 ，freq 小的 優先級別高    
  25.     }  
  26. };  
  27.   
  28. priority_queue<Node* , vector<Node*> , Cmp> myQueue;  
  29.   
  30. void BuildTree()  
  31. {  
  32.     for (int i = 0; i < 26; ++ i)  
  33.     {  
  34.         if (Table[i] > 0)  
  35.         {  
  36.             Node * node = new Node();  
  37.             node->freq = Table[i];  
  38.             node->val =(char) (i + 'A');  
  39.             myQueue.push(node);  
  40.         }  
  41.     }  
  42.       
  43.     while (myQueue.size() > 1)  
  44.     {  
  45.         Node * f = myQueue.top();  
  46.         myQueue.pop();  
  47.         Node * s = myQueue.top();  
  48.         myQueue.pop();  
  49.         Node * tmp = new Node();  
  50.         tmp->freq = f->freq + s->freq;  
  51.         tmp->left = f;  
  52.         tmp->right = s;  
  53.         myQueue.push(tmp);  
  54.     }  
  55.     //cout << myQueue.top()->freq<<endl;   
  56. }  
  57.   
  58. struct PrintNode  
  59. {  
  60.     int freq;   
  61.     char val;  
  62.     string code;  
  63. };  
  64.   
  65. vector<PrintNode> vpn;  
  66. bool cmp(const PrintNode & a , const PrintNode & b)  
  67. {  
  68.     return a.freq > b.freq;  
  69. }  
  70.   
  71. void Print( Node * node , string res)  
  72. {  
  73.     if (node == NULL)  
  74.     {  
  75.         return;  
  76.     }  
  77.     if (node->val != '0')  
  78.     {  
  79.         PrintNode pn;  
  80.         pn.val = node->val;  
  81.         pn.freq = node->freq;  
  82.         pn.code = res;  
  83.         vpn.push_back(pn);  
  84.         //cout <<node->val <<" | " << node->freq <<" | "<< res <<endl;   
  85.         return ;  
  86.     }  
  87.     Print(node->left , res + "0");  
  88.     Print(node->right, res + "1");  
  89.     delete node->left;  
  90.     delete node->right;  
  91. }  
  92.   
  93. int main()  
  94. {  
  95.     int N;  
  96.     memset(Table , 0 , sizeof(Table));  
  97.     cin >> N;  
  98.     for (int i = 0; i < N; ++i)  
  99.     {  
  100.         char ch ;  
  101.         cin >> ch;  
  102.         if (ch >= 'A' && ch <= 'Z')  
  103.         {  
  104.             ++Table[ch - 'A'];  
  105.         }  
  106.     }  
  107.     BuildTree();  
  108.     Node * root = myQueue.top();  
  109.     myQueue.pop();  
  110.     Print(root , "");  
  111.       
  112.     sort(vpn.begin() , vpn.end() , cmp);  
  113.       
  114.     for (int i = 0; i < vpn.size(); ++i)  
  115.     {  
  116.         cout <<vpn[i].val << " "<<vpn[i].freq <<" " << vpn[i].code<<endl;  
  117.     }  
  118.     return 0;  
  119. }  
具體的構成算法不再這裡討論了，

Linux編程

C及C++中typedef的簡單使用指南

使用C/C++寫Python模塊

C++基礎基礎：C與C++的區別

使用C/C++擴展Python

[C/C++基礎] C語言常用函數memset的使用方法

[C/C++基礎] C語言常用函數strlen的使用方法

在Objective-C中使用C++

Linux C/C++(或標准C++或標准C)編程雜記

相關文章
  • Linux編程
  • SHELL編程
  • PERL編程
    • Copyright © Linux教程網 All Rights Reserved