Description

本题中，读入n个字符所对应的权值，生成赫夫曼编码，并依次输出计算出的每一个赫夫曼编码。

Input

输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。
第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。

Output

共n行，每行一个字符串，表示对应字符的赫夫曼编码。

Sample Input

8
5 29 7 8 14 23 3 11

Sample Output

0110
10
1110
1111
110
00
0111
010

HINT

赫夫曼树又名最优二叉树，它是一类带权路径长度最小的二叉树。通过构造赫夫曼树，我们可以得到赫夫曼编码，从而使得通信能够得到更高的效率。在本题中，构造赫夫曼树的过程使用了从叶子到根的逆向顺序，另外，还有一种从根出发直到叶子的赫夫曼编码构造算法

 

代码

/**************************************************************
    Problem: 2610
    User: 201717010009
    Language: C
    Result: Accepted
    Time:0 ms
    Memory:1096 kb
****************************************************************/
#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct {
    int weight;
    int parent;
    int lchild;
    int rchild;
}HTNode,*HuffmanTree;
void Select(HTNode HT[],int n,int *s1,int *s2)
{
    int min1=10000,min2=10000;
    for(int i=1;i<=n;i++)
    {
        if(HT[i].weight<min1&&HT[i].parent==0)
        {
            min1=( HT[i].weight );
            *s1=i;
        }
    }
    HT[*s1].parent=1;//找到最小的  使父节点不为0 
    for(int i=1;i<=n;i++)
    {
        if(HT[i].weight<min2&&HT[i].parent==0)
        {
            min2=( HT[i].weight );
            *s2=i;
        }
    }
    HT[*s2].parent=1;//
    int j;
    if(*s1>*s2)
    {
        j=*s1;
        *s1=*s2;
        *s2=j;
    }
}
void HuffmanCoding(int *w,int n)
{
    if(n<=1)
    return;
    int m=2*n-1;
    HTNode HT[m+1];
    HuffmanTree p;
    int i;
    for(p=&HT[1],i=1;i<=n;i++,p++,w++)//初始化1到n 
    {
        p->weight=*w;
        p->lchild=0;
        p->rchild=0;
        p->parent=0;
    }
    for(;i<=m;i++,p++)//初始化n+1到m 
    {
        p->lchild=0;
        p->parent=0;
        p->rchild=0;
        p->weight=0; 
    }
    int s1=0,s2=0;
    for(i=n+1;i<=m;i++)//构建赫夫曼树 
    {
        Select(HT,i-1,&s1,&s2);//找到最小的两个权值的位置 
        HT[s1].parent=i;
        HT[s2].parent=i;
        HT[i].lchild=s1;
        HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
    char HC[n+1][n];
    for(i=1;i<=n;i++)
    {
        char cd[n];
        cd[n-1]='\0';
        int start=n-1,c,f;
        for(c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
        {
            if(HT[f].lchild==c)
            {
                start--;
                cd[start]='0';
            }
            else
            {
                start--;
                cd[start]='1';
            }
        }
        strcpy(HC[i],&cd[start]);//从start处开始  直到最后  复制到 HC里 
    }
    for(int j=1;j<=n;j++)
    {
        printf("%s",HC[j]);
        printf("\n");
    }
}
 
int main()
{
    int n;
    scanf("%d",&n);
    int a[n];
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }
    int *w=&a[0];
    HuffmanCoding(w,n);
}