Description

写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左子树，权值大的放右子树，编码时右子树编码为1，左子树编码为0。

Input

输入表示字符集大小为n（n <= 100）的正整数，以及n个字符和n个权值（正整数，值越大表示该字符出现的概率越大）；输入串长小于或等于100的目标报文。

Output

经过编码后的二进制码，占一行；
以及对应解码后的报文，占一行；
最后输出一个回车符

• Sample Input 

  5 a b c d e 12 40 15 8 25
  bbbaddeccbbb

• Sample Output

  00011111110111010110110000
  

#include<stdio.h>  
#include<stdlib.h>  
#include<string.h>  
  
int pc = 1;  
  
typedef struct HtNode 
{  
    int weight;  
    int parent, lchild, rchild; 
    int flag; 
}HtNode;  
  
typedef struct HtTree  
{  
    HtNode ht[3000];
    int root; 
}phtree;  
  
void select(phtree* pht,int pos,int *x1,int *x2)
{  
    int m1, m2;  
    m1 = m2 = 10000;  
    for(int i = 1;i < pos;i++)  
    {  
        if(pht->ht[i].weight < m1 && pht->ht[i].parent == 0)  
        {   
            m2 = m1;  
            *x2 = *x1;  
            m1 = pht->ht[i].weight;  
            *x1 = i;   
        }  
        else if(pht->ht[i].weight < m2 && pht->ht[i].parent == 0 && pht->ht[i].weight > m1)  
        {  
            m2 = pht->ht[i].weight;  
            *x2 = i; 
        }  
    }  
}  
  
phtree *huffman(int n,int *w)  
{  
    phtree* pht;  
    int i, x1, x2;  
    pht = (phtree* )malloc(sizeof(phtree));  
       
    pht->ht[0].flag = 2;  
    pht->ht[0].lchild = 0;  
    pht->ht[0].rchild = 0;  
    pht->ht[0].parent = 0;  
    pht->ht[0].weight = 0;  
    for(i = 2*n;i < 3000;i++)  
    {  
        pht->ht[i].flag = 2;  
        pht->ht[i].lchild = 0;  
        pht->ht[0].rchild = 0;  
        pht->ht[0].parent = 0;  
        pht->ht[0].weight = 0;  
    }  
     
    for(i = 1;i <= 2*n-1;i++)   
    {  
        pht->ht[i].lchild = 0;  
        pht->ht[i].rchild = 0;  
        pht->ht[i].parent = 0;  
        pht->ht[i].flag = 2;  
        if(i <= n)  
        {  
            pht->ht[i].weight = w[i];
        }  
        else  
        {  
            pht->ht[i].weight = 0;  
        }  
    }  
      
  
    for(i = 1;i < n;i++) 
    {  
        select(pht,n+i,&x1,&x2);  
        pht->ht[x1].parent = n+i;  
        pht->ht[x1].flag = 0;  
        pht->ht[x2].parent = n+i;  
        pht->ht[x2].flag = 1;  
        pht->ht[n+i].weight = pht->ht[x1].weight + pht->ht[x2].weight;  
        pht->ht[n+i].lchild = x1; 
        pht->ht[n+i].rchild = x2;  
        pht->root = n+i;  
    }  
    return pht;  
}  
  
void traversehuffman(phtree *t,int n,int pcode[][100])  
{  
    int i = 1;  
    HtNode node;  
    node = t->ht[pc];  
    while(node.parent != 0)  
    {  
        pcode[pc][i] = node.flag;  
        node = t->ht[node.parent];  
        i++;  
    }  
    pc++;  
}  
  
void output(int pcode[][100],int n,char *x)  
{  
    int i, j, k, cnt;  
    int code[100][100];  
    for(i =0;i < 100;i++)  
    {  
        for(j = 0;j < 100;j++)  
        {  
            code[i][j] = -1;  
        }  
    }  
    for(i = 1;i <= n;i++)  
    {  
        for(cnt = 1;pcode[i][cnt+1] == 1 || pcode[i][cnt+1] == 0;cnt++);  
        k = cnt;  
        for(j = 1;j<= k;j++)  
        {  
            code[i][j] = pcode[i][cnt--];  
        }  
    }  
  
    char s[100], c;  
    scanf("%s",s);  
    int f = strlen(s);  
    for(i = 0;i <= f;i++)  
    {  
        for(j = 1;j <= n;j++) 
        {  
            if(s[i] == x[j])  
            {  
                for(k = 1;code[j][k] == 0 || code[j][k] == 1;k++)  
                {  
                    printf("%d",code[j][k]);  
                }  
            }  
        }  
    }  
      
    printf("\n%s\n",s);  
}  
  
int main()  
{  
    int i, n, cnt = 1;  
    char c;  
    int w[101];
    char s[101]; 
    int pcode[100][100]; 
    for(i = 0;i < 100;i++)  
    {  
        for(int j = 0;j < 100;j++)  
        {  
            pcode[i][j] = -1;  
        }  
  
    }  
    scanf("%d",&n);  
    while(1)  
    {  
        scanf("%c",&c);  
        if(cnt == n+1)  
        {  
            break;  
        }  
        else if(c != ' ')  
        {  
            s[cnt++] = c;  
        }  
    }  
    for(i = 1;i <= n;i++)  
    {  
        scanf("%d",&w[i]);  
    }  
    phtree* pht;  
    pht = huffman(n,w);  
    for(i = 1;i <= n;i++)  
    {  
        traversehuffman(pht,n,pcode);  
    }  
    output(pcode,n,s);  
    return 0;  
}