數據結構實驗之二叉樹六：哈夫曼編碼

PRoblem Description

字符的編碼方式有多種，除了大家熟悉的ASCII編碼，哈夫曼編碼(Huffman Coding)也是一種編碼方式，它是可變字長編碼。該方法完全依據字符出現概率來構造出平均長度最短的編碼，稱之為最優編碼。哈夫曼編碼常被用于數據文件壓縮中，其壓縮率通常在20%～90%之間。你的任務是對從鍵盤輸入的一個字符串求出它的ASCII編碼長度和哈夫曼編碼長度的比值。

Input

Output

Example Input

AAAAABCDTHE_CAT_IN_THE_HAT
Example Output
64 13 4.9144 51 2.8
Hint
  
Author
 xam 
#include <iostream>#include<string.h>#include<stdio.h>#include<queue>#include<stdlib.h>#include<algorithm>using namespace std;int sum;int h[10002];int main(){    priority_queue<int,vector<int>,greater<int> >q;//最小元素優先，升序相等于最大堆    int i,a,b,d[200],alen,c;    char s[10002];    while(~scanf("%s",s))    {        sum = 0;        memset(d,0,sizeof(d));        int len=strlen(s);        alen = len*8;        for(i=0;i<len;i++)        {           d[s[i]]++;        }        for(i=0;i<150;i++)        {           if(d[i]!=0)           {              q.push(d[i]);           }        }        while(!q.empty())    {        a = q.top();        q.pop();        if(!q.empty())        {           b = q.top();           q.pop();           c = a+b;           q.push(c);           sum += c;        }    }    printf("%d %d %.1lf/n",alen,sum,1.0*alen/sum);    }    return 0;}/*題目大意：FJ需要修補牧場的圍欄，他需要 N 塊長度為 Li 的木頭（N planks of woods）。開始時，FJ只有一塊無限長的木板，因此他需要把無限長的木板鋸成 N 塊長度為 Li 的木板，Farmer Don提供FJ鋸子，但必須要收費的，收費的標準是對應每次據出木塊的長度，比如說測試數據中 5 8 8，一開始，FJ需要在無限長的木板上鋸下長度 21 的木板（5+8+8=21），第二次鋸下長度為 5 的木板，第三次鋸下長度為 8 的木板，至此就可以將長度分別為 5 8 8 的木板找出題目可以轉化為Huffman樹構造問題 ：給定 N planks of woods，1. 　　在 N planks 中每次找出兩塊長度最短的木板，然后把它們合并，加入到集合A中，2.　　在集合中找出兩塊長度最短的木板，合并加入到集合A中，重復過程，直到集合A中只剩下一個元素顯然，通過每次選取兩塊長度最短的木板，合并，最終必定可以合并出長度為 Sum（Li）的木板，并且可以保證總的耗費最少*//***************************************************User name: jk160505徐紅博Result: AcceptedTake time: 0msTake Memory: 172KBSubmit time: 2017-02-09 10:17:15****************************************************/