POJ1521---哈夫曼编码，求最优WPL-白红宇

POJ1521---哈夫曼编码，求最优WPL

阅读量：4046 次

发布时间：2019-05-25

本文共 2154 字，大约阅读时间需要 7 分钟。

POJ1521---哈夫曼编码

题目描述

输入一个字符串，长度不超过100，仅由大写字母和下划分组成。求用最好的字符编码方式，令总长度最小。

输入

多组数据，每组数据在一行上输入一个字符串，格式如前所述

当遇到END时，表示输入结束

输出

对应每个输入，在一行上输出3个信息：首先是每个字母按固定长度8bit编码，字符串的总长度，然后是按最优编码的总长度，最后是前者对后者的比率，保留1位小数。

样例输入

AAAAABCD

THE_CAT_IN_THE_HAT

END

样例输出

64 13 4.9

144 51 2.8

方法一：

直接建立哈夫曼树，然后求WPL。

方法二：

举个栗子：ABBCCC

权值分别为1，2，3。

先把A,B，生成一个树，此时A对应的编码为0，B为1，ABB则为011，为三位长度，再把此树和C合并的时候，A,B编码长度都增加了1，此时A为00，B为01，ABB编码长度增加的长度就是1+2（也就是第一次合并那个树的权值）。

所以用这种思想可以不用去建哈夫曼树，直接用优先队列去存权值，每次把两个最小的权值加起来（a+b），加在sum上，然后再把（a+b）压入队列。

方法二是参考的网上的解法，感觉不好想，或者是其他思想？反正法1也很直接。

#include
   
    #include
    
     	#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            using namespace std;typedef struct HufNode { int weight; struct HufNode* Left; struct HufNode* Right;}*Huf;struct cmp { bool operator()(Huf a, Huf b) { return a->weight > b->weight; }};int WPL(Huf T, int Depth){ if ((!T->Left) && (!T->Right)) return(Depth*(T->weight)); else return (WPL(T->Left, Depth + 1) + WPL(T->Right, Depth + 1));}int main(){ string s; priority_queue< Huf, vector
            
             , cmp>Q; while (cin >> s) { if (s == "END")break; int c[200]; memset(c, 0, sizeof(c)); for (int i = 0; i
             
              weight = c[i]; H->Left = H->Right = NULL; Q.push(H); c[i] = 0; } int sum = 0; if (Q.size() == 1) { sum = s.size(); Q.pop(); }//只有一种字符。 else { while (Q.size()>1) { T = (Huf)malloc(sizeof(struct HufNode)); T->Left = Q.top(); Q.pop(); T->Right = Q.top(); Q.pop(); T->weight = T->Left->weight + T->Right->weight; Q.push(T); } T = Q.top(); Q.pop(); sum = WPL(T, 0); } printf("%d %d %.1f\n", 8 * s.size(), sum, (double)8.0 * s.size() / double(sum)); } return 0;}

#include
   
    #include
    
     	#include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include
           
            using namespace std;int main(){ string s; priority_queue

, greater

>Q; while (cin >> s) { if (s == "END")break; int c[200]; memset(c, 0, sizeof(c)); for (int i = 0; i

1) { int a = Q.top(); Q.pop(); int b = Q.top(); Q.pop(); sum += a + b; Q.push(a + b); } Q.pop(); printf("%d %d %.1f\n", 8 * s.size(), sum, (double)8.0 * s.size() / double(sum)); } return 0;}

转载地址：http://quyci.baihongyu.com/

你可能感兴趣的文章