#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>

typedef struct
{
 int weight;
 char ch;
 int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef struct
{
 char ch;
 char *chs;
}HuffmanCode;

typedef struct
{

 char ch;
 int weight;
}sw;

typedef struct
{
 HuffmanTree HT;
 HuffmanCode *HC;
}huf;

void select(HTNode * HT,int n,int *n1,int *n2)
{
 int i=1;        
 int n3;
 while(HT[i].parent!=0)         i++;
 *n1=i;
 i++;
 while(HT[i].parent!=0)         i++;
 *n2=i;
 if(HT[*n1].weight<HT[*n2].weight)
 {        
  n3=*n1;
  *n1=*n2;
  *n2=n3;
 }
 for(i++;i<=n;i++)
 {
  if(HT[i].parent==0)
  {        
   if(HT[i].weight<HT[*n1].weight)
    *n1=i;
   else if(HT[i].weight<HT[*n2].weight)
    *n2=i;

  }

 }

}

huf * HuffmanCoding(HuffmanTree HT,HuffmanCode *HC,sw *w,int n,huf *HUF)
{
 int m,i,s1,s2,start,c,f;
 HuffmanTree p;
 char *cd;
 if(n<=1) return 0;
 m=2*n-1;
 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
 for(p=HT+1,i=1;i<=n;i++,p++,w++)
 {
  p->weight=w->weight;
  p->ch=w->ch;
  p->parent=0;
  p->lchild=0;
  p->rchild=0;
 }
 for(;i<=m;i++,p++)
 {
  p->weight=0;
  p->ch='^';
  p->parent=0;
  p->lchild=0;
  p->rchild=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;
 }
 HC=(HuffmanCode *)malloc((n+1)*sizeof(char));
 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].ch=HT[i].ch;
  HC[i].chs=(char*)malloc((n-start)*sizeof(char));
  strcpy(HC[i].chs,&cd[start]);
  printf("%c %-10s\n",HC[i].ch,HC[i].chs);
 }
 HUF->HT=HT;
 HUF->HC=HC;
 return HUF;
}

char *       convert(char *chars,char *chars1,HuffmanCode *hc,int n)

{
 char *p=chars; int i;
 strcpy(chars1,"");
 while(*p)
 {
  i=1;       
  while(hc[i].ch!=*p&&i<=n)        i++;
  strcat(chars1,hc[i].chs);       
  p++;
 }
 printf("the chars translate are:%s\n",chars1);
 return chars1;
 fflush(stdin);
}

void transcode(HuffmanTree ht,char *chars2,char*chars3)

{
 int i=1,p; char *q=chars2;char *r=chars3;
 while(ht[i].parent!=0)        i++;
 p=i;
 while(*q)
 {
  while(ht[p].lchild!=0 && *q)
  {
   if(*q=='0')
   p=ht[p].lchild;
   else p=ht[p].rchild;
   q++;
  }
  if(ht[p].lchild==0)
  {
   *r=ht[p].ch;
   r++;
  }
  p=i;
 }
 *r='\0';
 printf("the chars are:");
 puts(chars3);
 fflush(stdin);
}

void input(int *n,sw *w)
{
 int i;
 printf("input the amount of char:");   /*输入字符的数目*/
 scanf("%d",n);
 for(i=1;i<=*n;i++,w++)
 {
  printf("input the %dth char and weight:",i); /*输入每个节点的字符和其权值*/
  fflush(stdin);
  scanf("%c%d",&w->ch,&w->weight);
 }
}

void main()
{
 char x;
 HTNode HT;
 HuffmanCode HC,*hc;
 HuffmanTree ht;
 huf *HUF,huf2;
 int n;
 sw w[40];
 char ch,inchar[500],outchar[1000];
 char *abc;
 char *p=inchar;
 printf("下面开始进行Huffman编译码：\n");
 input(&n,w);
 HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);
 printf("input chars to translate and end with '#':");
 fflush(stdin);/*清除流,解决输入干扰*/
 ch=getchar();
 while(ch!='#')
 {
  *p=ch;
  p++;
  ch=getchar();
 }
 *p='\0';
 hc=HUF->HC;
 ht=HUF->HT;
 abc=convert(inchar,outchar,hc,n);
 transcode(ht,abc,outchar);
 getchar();
 fflush(stdin);
 printf("Do you want to try again?(y/n)");
 x=getchar();
 while(x=='y'){
  input(&n,w);
  HUF=HuffmanCoding(&HT,&HC,w,n,&huf2);
  printf("input chars to translate and end with '#':");
  fflush(stdin);/*清除流,解决输入干扰*/
  ch=getchar();
  while(ch!='#')
  {
   *p=ch;
   p++;
   ch=getchar();
  }
  *p='\0';
  hc=HUF->HC;
  ht=HUF->HT;
  abc=convert(inchar,outchar,hc,n);
  transcode(ht,abc,outchar);
  fflush(stdin);
  getchar();
  fflush(stdin);
  printf("Do you want to try again?(y/n)");
  x=getchar();
 }
 while(x=='n') break;
 getchar();
}