#include<stdio.h>
#include<string.h>
#define NULL 0
struct HTNode
{int weight,parent,lchild,rchild;
};
struct HTNode* HT;
char** HC;
int s1,s2;
int *w;
char *a;
void Select(int j)
{int i,t;
 for(i=1;i<j;i++)
   if(HT[i].parent==0)
     {s1=i;
      break;
     }
 for(;i<j;i++)
   if(HT[i].weight<HT[s1].weight&&HT[i].parent==0)
     s1=i;
 for(i=1;i<j;i++)
   if(HT[i].parent==0&&i!=s1)
     {s2=i;
      break;
     }
 for(;i<j;i++)
   if(HT[i].weight<HT[s2].weight&&i!=s1&&HT[i].parent==0)
     s2=i;
 if(s1>s2)
  {t=s1;
   s1=s2;
   s2=t;
  }
}
int HuffmanCoding()
{int i,n,m,start,c,f;
 struct HTNode* p;
 char *cd;
 printf("please input the number of the data:\n");
 scanf("%d",&n);
 if(n<=1)
   return 0;
 printf("please input the weight:\n");
 w=(int *)malloc((n+1)*sizeof(int));
 for(i=1;i<=n;i++)
   scanf("%d",&w[i]);
 getchar();
 printf("please input the words:\n");
 a=(char *)malloc((n+1)*sizeof(char));
 for(i=1;i<=n;i++)
   scanf("%c",&a[i]);
 m=2*n-1;
 HT=(struct HTNode*)malloc((m+1)*sizeof(struct HTNode));
 for(p=HT+1,i=1;i<=n;++i,++p)
   {p->weight=w[i];
    p->parent=0;
    p->lchild=0;
    p->rchild=0;
   }
 for(;i<=m;++i,++p)
   {p->weight=0;
    p->parent=0;
    p->lchild=0;
    p->rchild=0;
   }
 for(i=n+1;i<=m;++i)
   {Select(i);
    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;
   }
 HC=(char**)malloc((n+2)*sizeof(char*));
 HC[n+1]=NULL;
 cd=(char*)malloc(n*sizeof(char));
 cd[n-1]='\0';
 for(i=1;i<=n;i++)
   {start=n-1;
    for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
    if(HT[f].lchild==c)
      cd[--start]='0';
    else
      cd[--start]='1';
    HC[i]=(char*)malloc((n-start)*sizeof(char));
    strcpy(HC[i],&cd[start]);
   }
 free(cd);
 return 1;
}
void PrintHuffmanTree()
{int i=1;
 printf("the huffmancode:\n");
 while(HC[i]!=NULL)
   {printf("%c:%s\n",a[i],HC[i]);
    i++;
   }
}
void main(void)
{if(!HuffmanCoding())
  printf("sorry! input error.\n");
 else
   PrintHuffmanTree();
 getchar();
 getchar();
}