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 阅读(840)
评论(0) 编辑 收藏 引用