#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define UINT_MAX 10
 
//定义一个结点结构
 
typedef struct{
 double weight;
 unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
 
typedef char **HuffmanCode;
int min1(HuffmanTree t,int i)
{
 int j,flag;
 double k=UINT_MAX;
  
for(j=1;j<=i;j++)
 {
    if(t[j].weight<k && t[j].parent==0)
    {
   k=t[j].weight;
   flag=j;
    } 
 
}
 t[flag].parent=1;
  
 return flag;
}
 
void select(HuffmanTree t,int i,int &s1,int &s2)
{
 int j;
//从t数组的前i个元素中选出weight最小且parent为0的两个，分别将其序号保存在s1和s2中
 
 s1=min1(t,i);
 s2=min1(t,i);
//左子树要小于右子树
 
 if(s1>s2)
 {
  j=s1;
  s1=s2;
  s2=j;
 }
}
 
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,double *w,int n)
{  
 int m,i,s1,s2,start;
 unsigned int c,f;
 HuffmanTree p;
 char *cd;
 if(n<=1)
 return;
 m=2*n-1;
 
//开辟一个能容纳完成哈夫曼树后形成m个结点的空间
 
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
 
//将一开始输入的n个数的权值放到HT数组里
 
for(p=HT+1,i=1;i<=n;++i,++p,++w)
 {
 (*p).weight=*w;
 (*p).parent=0;
 (*p).lchild=0;
 (*p).rchild=0;
 }
 
 for(;i<=m;++i,++p)
  (*p).parent=0;
  for(i=n+1;i<=m;++i)
  {
   select(HT,i-1,s1,s2);
   HT[s1].parent=HT[s2].parent=i;
   HT[i].lchild=s1;
   HT[i].rchild=s2;
   HT[i].weight=HT[s1].weight+HT[s2].weight;
  }
  
 HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
  cd=(char*)malloc(n*sizeof(char));
  cd[n-1]='\0';
 
 //进行Huffman编码
  
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);
}
void main(){
 HuffmanTree HT;
 HuffmanCode HC;
  
 int n,i,x,m;
 double *w;
  
 char s[20][10];
 while(1)
 {
  printf("1．输入字符集大小\n2．输入带编码字符及其权值\n3．建立哈夫曼树HT\n4．完成哈夫曼编码HC，并显示编码\n5．退出\n");
  scanf("%d",&x);
 if(x==1)
 {
    printf("请输入字符集个数:\n");
    scanf("%d",&m);}
 else if(x==2)
 {
       
          printf("请输入带编码字符:\n");
       for(i=1;i<=m;i++)
       scanf("%s",s[i]);
       printf("请输入权值的个数(>1):");
       scanf("%d",&n);
          w=(double*)malloc(n*sizeof(double));
       printf("请依次输入%d个权值:\n",n);
       for(i=0;i<=n-1;i++)
    scanf("%lf",w+i);
 }
 else if(x==3)
 {
  HuffmanCoding(HT,HC,w,n);
  printf("哈夫曼树建造完成");
 }
 else if(x==4){
 for(i=1;i<=n;i++)
 { 
     printf("%s的编码:",s[i]);
  puts(HC[i]);
  printf("\n");
 }}
 else if(x==5)
 {
  break;
 }
 else{
  printf("输入的字符为非法字符");
 }
 }
}