首页 > 代码库 > hdoj 1053 Entropy（用哈夫曼编码）优先队列

hdoj 1053 Entropy（用哈夫曼编码）优先队列

2024-07-11 08:04:08   229人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1053

讲解：

　　题意：给定一个字符串，根据哈夫曼编码求出最短长度，并求出比值。

     思路：就是哈夫曼编码。把单个字符出现次数作为权值。

AC代码：

 1 #include <iostream> 2 #include <string> 3 #include <queue> 4 #include <cstdio> 5 using namespace std; 6  7 class node{ 8 public: 9     int key; //a,b,c...10     int count;//频率11     int p;//父亲结点12     friend bool operator < (const node &a, const node &b)13     {14         if(b.count < a.count)15             return true;16         else17             return false;18     }19 };20 21 int value(char c)22 {23     if(c==‘_‘)24         return 26;25     else26         return(c-‘A‘);27 }28 int main()29 {30     string str;31     cin >> str;32     while(str!="END")33     {34         node c[60];35         for(int i=0;i<60;i++)36         {37             c[i].key=i;38             c[i].count=0;39         }40         int length=str.length();41         priority_queue<node> q;42         for(int i=0;i<length;i++)43         {44             (c[value(str.at(i))]).count++;45         }46         for(int i=0;i<=26;i++)47         {48             if(c[i].count!=0)49                 q.push(c[i]);50         }51         if(q.size()==1)52         {53             printf("%d %d 8.0\n",8*length,length);54         }55         else56         {57             int high=0;58             int n=27;59             while(q.size()>1)60             {61                 node s1=q.top();62                 q.pop();63                 node s2=q.top();64                 q.pop();65                 c[n].count=s1.count+s2.count;66                 c[s1.key].p=n;67                 c[s2.key].p=n;68                 high=high+c[n].count;69                 q.push(c[n]);70                 n++;71             }72             printf("%d %d %.1lf\n",8*length,high,(((double)(8*length))/((double)high)));73         }74         cin >> str;75     }76 }

 


联系
我们