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];//對應每種字符的數目，無需關注具體對應的是哪個字符，只需記錄數目即可?！緸槭裁茨兀俊?/span>

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 }