1760 Problem A 算法6-12：自底向上的赫夫曼編碼

問題 A: 算法6-12：自底向上的赫夫曼編碼

時間限制: 1 Sec  記憶體限制: 32 MB

送出: 26  解決: 13

在通訊領域，經常需要将需要傳送的文字轉換成由二進制字元組成的字元串。在實際應用中，由于總是希望被傳送的内容總長盡可能的短，如果對每個字元設計長度不等的編碼，且讓内容中出現次數較多的字元采用盡可能短的編碼，則整個内容的總長便可以減少。另外，需要保證任何一個字元的編碼都不是另一個字元的編碼字首，這種編碼成為字首編碼。

而赫夫曼編碼就是一種二進制字首編碼，其從葉子到根（自底向上）逆向求出每個字元的算法可以表示如下：

在本題中，讀入n個字元所對應的權值，生成赫夫曼編碼，并依次輸出計算出的每一個赫夫曼編碼。

輸入

輸入的第一行包含一個正整數n，表示共有n個字元需要編碼。其中n不超過100。

第二行中有n個用空格隔開的正整數，分别表示n個字元的權值。

輸出

共n行，每行一個字元串，表示對應字元的赫夫曼編碼。

樣例輸入

8
5 29 7 8 14 23 3 11      

樣例輸出

0110
10
1110
1111
110
00
0111
010      

提示

經驗總結

正确代碼

#include <cstdio>
#include <climits>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=110;
struct HuffNode
{
    int w,parent,lchild,rchild;
}Node[maxn*2];
void SearchMin(int &a,int &b,int n)
{
    int min=INT_MAX;
    for(int i=0;i<n;++i)
    {
        if(Node[i].parent==0&&Node[i].w<min)
        {
            min=Node[i].w;
            a=i;
        }
    }
    min=INT_MAX;
    for(int i=0;i<n;++i)
    {
        if(Node[i].parent==0&&Node[i].w<min&&i!=a)
        {
            min=Node[i].w;
            b=i;
        }
    }
    if(a>b)
    {
        swap(a,b);
    }
}
void HuffmanCode(int n,int * w,char * * &ans)
{
    for(int i=0;i<n;++i)
    {
        Node[i].parent=Node[i].lchild=Node[i].rchild=0;
        Node[i].w=w[i];
    }
    for(int i=n;i<2*n-1;++i)
    {
        int a,b;
        SearchMin(a,b,i);
        Node[i].lchild=a;
        Node[i].rchild=b;
        Node[i].w=Node[a].w+Node[b].w;
        Node[a].parent=Node[b].parent=i;
    }
    int c,f,index;
    char temp[n];
    ans=new char * [n];
    for(int i=0;i<n;++i)
    {
        c=i;
        index=n-1;
        temp[index]=0;
        while(Node[c].parent!=0)
        {
            f=Node[c].parent;
            if(Node[f].lchild==c)
                temp[--index]='0';
            else
                temp[--index]='1';
            c=f;
        }
        ans[i]=new char[n-index];
        strcpy(ans[i],temp+index);
    }
}
int main()
{
    int n,w[maxn];
    char * * ans;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;++i)
        {
            scanf("%d",&w[i]);
        }
        HuffmanCode(n,w,ans);
        for(int i=0;i<n;++i)
        {
            printf("%s\n",ans[i]);
        }
    }
    delete ans;
    return 0;
}