#include"stdio.h"
#include"string.h"
#define MAX 99
char cha[MAX];
char hc[MAX-1][MAX];
int s1,s2; //設置全局變量，以便在方法(函數)select中返回兩個變量

typedef struct  //huffman樹存儲結構
{
 unsigned int weight;
 int lchild,rchild,parent;
}huftree;

void select(huftree tree[],int k)  //找尋parent為0,權最小的兩個節點
{
  int i;
  for (i=1;i<=k && tree[i].parent!=0 ;i++); s1=i;
  for (i=1;i<=k;i++)
    if (tree[i].parent==0 && tree[i].weight<tree[s1].weight) s1=i;
  for (i=1; i<=k ; i++)
    if (tree[i].parent==0 && i!=s1) break; s2=i;
  for (i=1;i<=k;i++)
    if ( tree[i].parent==0 && i!=s1 && tree[i].weight<tree[s2].weight) s2=i;
}

void huffman(huftree tree[],int *w,int n)  //生成huffman樹
{  int m,i;
   if (n<=1) return;
   m=2*n-1;
  for (i=1;i<=n;i++)
   { tree[i].weight=w[i]; tree[i].parent=0;
     tree[i].lchild=0;    tree[i].rchild=0; }
  for (i=n+1;i<=m;i++)
   { tree[i].weight=0;   tree[i].parent=0;
     tree[i].lchild=0;   tree[i].rchild=0; }
   for (i=n+1;i<=m;i++)
   {  select(tree, i-1);
         tree[s1].parent=i;
         tree[s2].parent=i;
         tree[i].lchild=s1;
         tree[i].rchild=s2;     
         tree[i].weight =tree[s1]. weight+ tree[s2].weight;
      }
}

void huffmancode(huftree tree[],char code[],int n)
{
 int start,c,i,f;
 code[n-1]='\0';
 printf("Huffman Code:\n");
 for(i=1;i<=n;i++)
 {start=n-1;
 for(c=i,f=tree[i].parent;f!=0;c=f,f=tree[f].parent)
 {if(tree[f].lchild==c)code[--start]='0';
 else code[--start]='1';}
 strcpy(hc[i],&code[start]);
 printf("%c-->%s\n",cha[i],hc[i]);
 }
}


void tohuffmancode(int n)
{
   int i=0,j;
   char anychar[9999];
   printf("Please enter a word:\n>>> ");
   scanf("%s",&anychar);
   printf("Huffman Code:");
   for (;anychar[i]!='\0';i++)
   {
      j=0;
      for(;anychar[i]!=cha[j]&&j<=n;) j++;
   if (j<=n)  printf("%s",hc[j]);
   }
   printf("\n");getchar();
}

void decode(char ch[],huftree tree[],int n)
{
 int i,j,m;char b;
 m=2*n-1;
 i=m;
 printf("please enter the code:\n>>> ");
 scanf("%c",&b);
 printf("Decode:");
 while(b!=10)   //遇到回車時，結束
 {
  
  if(b=='0')i=tree[i].lchild;
  else i=tree[i].rchild;
  if(tree[i].lchild==0)
  {printf("%c",ch[i]);
   j=i,i=m;
  }
  scanf("%c",&b);
 }
 if(tree[j].lchild!=0)
  printf("\nERROR\n");
 printf("\n\n");
}

void main()
{
 int i=0,n=0;
 int *w,weight[MAX];
 char code[MAX],ch;
 huftree tree[MAX];
 w=weight;
 printf("Please enter n:");
    scanf("%d",&n); getchar();
 printf("Please enter character and  weight( such as: a2 ):\n");
 for(i=1;i<=n;i++)
 {
  printf(">>> ");
  scanf("%c%d",&cha[i],&weight[i]);getchar();
 }
 huffman(tree,w,n);   //生成huffman樹
 huffmancode(tree,code,n);  //編碼A
 tohuffmancode(n);  //編碼B
 decode(cha,tree,n);           //譯碼
}