#include"stdio.h"
#include"stdlib.h"
#include"string.h"

typedef char ElemType;
typedef struct
{
   ElemType elem;
   unsigned int m_weight;
   unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char** HuffmanCode;
typedef int Status;
typedef struct weight
{
  char elem;
  unsigned int m_weight;
}Weight; // save the information of the symbolizes;

void HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int);
void Select(HuffmanTree,int,int *,int *);
void OutputHuffmanCode(HuffmanTree,HuffmanCode,int);

Status main(void)
{
  HuffmanTree HT;
  HuffmanCode HC;
  Weight *w;
  char c;     // the symbolizes;
  int i,n;      // the number of elements;
  int wei;    // the weight of a element;

  printf("input the tatol number of the Huffman Tree:" );
  scanf("%d",&n);
  w=(Weight *)malloc(n*sizeof(Weight));
  for(i=0;i<n;i++)
  {
    printf("input the element & its weight:");
    scanf("%1s%d",&c,&wei);
    w[i].elem=c;
    w[i].m_weight=wei;
  }

  HuffmanCoding(&HT,&HC,w,n);
  OutputHuffmanCode(HT,HC,n);
  return 1;

}

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n)
{
  int i,m,s1,s2,start,c,f;
  char *cd;
  HuffmanTree p;
  if(n<=1)
  return;

  m=2*n-1;
  (*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
  for(i=1;i<=n;++i)
  {
     (*HT)[i].elem=w[i-1].elem;
     (*HT)[i].m_weight=w[i-1].m_weight;
     (*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
  }

  for(;i<=m;++i)
  {
    (*HT)[i].elem='0';
    (*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].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].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_weight;
  }

  (*HC)=(HuffmanCode)malloc(n*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]=(char *)malloc((n-start)*sizeof(char));
     strcpy((*HC)[i],&cd[start]);
  }
}

void Select(HuffmanTree HT,int n,int *s1,int *s2)
{
  int i;
  (*s1)=(*s2)=0;
  for(i=1;i<=n;i++)
  {
    if(HT[i].m_weight<HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
{
      if(HT[i].m_weight<HT[(*s1)].m_weight)
  {
  (*s2)=(*s1);
  (*s1)=i;
      }
      else (*s2)=i;

    }

    if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
{
      if((*s1)==0) (*s1)=i;
      else if((*s2)==0)
  {
  if(HT[i].m_weight<HT[(*s1)].m_weight)
  {
  (*s2)=(*s1);
  (*s1)=i;
  }
  else (*s2)=i;
      } // end of else if
    } // end of if
  } // end of for

  if((*s1)>(*s2))
  {
    i=(*s1);
(*s1)=(*s2);
(*s2)=i;
  }
  return;
}

void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
  int i;
  printf("\nnumber---element---weight---huffman code\n");
  for(i=1;i<=n;i++)
    printf("  %d        %c         %d        %s\n",i,HT[i].elem,HT[i].m_weight,HC[i]);
}