Welcome 微信登录
编程资源 图片资源库 蚂蚁家优选 PDF转换器

首页 / 操作系统 / 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. }  
具体的构成算法不再这里讨论了，
版权所有©石家庄振强科技有限公司2024 冀ICP备08103738号-5 网站地图