随笔-65  评论-6  文章-0  trackbacks-0
 1 /*
 2 Author:    Leo.W
 3 Descriptipn:对输入字符串【长度不知,仅含26个大写英文字母和一个空格表示符‘_’,共27种字符】,
 4             统计每种字符出现频度,按哈夫曼编码原理给出最小的编码位数之和,得出与8位固定字长
 5             编码的比率【保留一位小数】。
 6 How to Do:    哈夫曼编码原理的理解及优先队列的运用<priority_queue>,引用头文件<queue>
 7   */
 8 #include <iostream>
 9 #include <string.h>
10 #include <queue>
11 #include <algorithm>
12 using namespace std;
13 #define lenth 300
14 int main(){
15     //freopen("in.txt","r",stdin);
16     char str[1000];//输入字符串
17     while(scanf("%s",str),strcmp(str,"END")!=0){
18         int lenStr=strlen(str);
19         int worse=lenStr<<3;//固定字长编码所需的总位数
20         char ch[lenth];int lenCh=0;//输入字符的种类
21         int i,j,num[lenth];//对应每种字符的数目,无需关注具体对应的是哪个字符,只需记录数目即可。【为什么呢?】
22         memset(num,0,lenth);//字符数目数组初始置零
23         //对字符串逐个统计出现次数
24         for(i=0;i<lenStr;i++){
25             for(j=0;j<lenCh;j++){
26                 if(str[i]==ch[j]){
27                     num[j]++;break;
28                 }
29             }
30             if(j==lenCh){
31                 ch[j]=str[i];num[j]++;lenCh++;
32             }
33         }
34         sort(num,num+lenCh);//对得到的字符数目【大于零,即至少出现过一次,才存在统计必要】序列进行升序快排
35         priority_queue<int,vector<int>,greater<int> >    que;//对于int整型数据,进行自小至大的优先级排列
36         for(i=0;i<lenCh;i++)    que.push(num[i]);
37         int sum=0;
38         while(true){
39             int aa=que.top();    que.pop();
40             if(que.empty())    {
41                 if(lenCh==1)    sum=aa;
42                 break;
43             }
44             int bb=que.top();    que.pop();
45             sum+=aa+bb;        que.push(aa+bb);
46         }
47         printf("%d %d %.1lf\n",worse,sum,worse*1.0/sum);
48     }
49     return 0;
50 }
posted on 2012-03-02 14:48 Leo.W 阅读(834) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理