#include <stdio.h>
#include <stdlib.h>
#define MAXVALUE 1000     /*定義最大權(quán)值*/
#define MAXLEAF 30           /*定義哈夫曼樹中葉子結(jié)點(diǎn)個(gè)數(shù)*/
#define MAXNODE  MAXLEAF*2-1
#define MAXBIT 10                 /*定義哈夫曼編碼的最大長(zhǎng)度*/
    
typedef struct {
        int weight;
        int parent;
        int lchild;
        int rchild;
       }HNodeType;

typedef struct {
        int bit[MAXBIT];
        int start;
       }HCodeType;

 void  HaffmanTree(HNodeType HuffNode [ ],int n)
{		/*哈夫曼樹的構(gòu)造算法*/
	int i,j,m1,m2,x1,x2;
	for (i=0;i<2*n-1;i++)         /*數(shù)組HuffNode[ ]初始化*/
        { HuffNode[i].weight=0;
          HuffNode[i].parent=0;
          HuffNode[i].lchild=0;
          HuffNode[i].rchild=0;
         }
      for (i=0;i<n;i++)
	  {
		  printf("輸入%d個(gè)葉子結(jié)點(diǎn)的權(quán)值:",i+1);
		scanf("%d",&HuffNode[i].weight); 
	  } /*輸入n個(gè)葉子結(jié)點(diǎn)的權(quán)值*/
      for (i=0;i<n-1;i++)            /*構(gòu)造哈夫曼樹*/
        { m1=m2=MAXVALUE;
          x1=x2=0;
          for (j=0;j<n+i;j++)
           { if (HuffNode[j].weight<m1 && HuffNode[j].parent==0)
              { m2=m1;     x2=x1;
                m1=HuffNode[j].weight;    x1=j;
              }
		  else if (HuffNode[j].weight<m2 && HuffNode[j].parent==0)
                  { m2=HuffNode[j].weight;
                    x2=j;
                  }
           }
         /*將找出的兩棵子樹合并為一棵子樹*/
         HuffNode[x1].parent=n+i;         HuffNode[x2].parent=n+i; 
         HuffNode[n+i].weight= HuffNode[x1].weight+HuffNode[x2].weight;
         HuffNode[n+i].lchild=x1;  HuffNode[n+i].rchild=x2;     
        }
}


void HaffmanCode (int n )
{ /*生成哈夫曼編碼*/
		HNodeType HuffNode[MAXNODE];
		HCodeType HuffCode[MAXLEAF],cd;
		HaffmanTree (HuffNode ,n);		/*建立哈夫曼樹*/
		 int i,j, c,p;
		 for (i=0;i<n;i++)                /*求每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼*/
		 {	
					cd.start=n-1;   c=i;
					p=HuffNode[i].parent;
				while(p!=0)                 /*由葉結(jié)點(diǎn)向上直到樹根*/
				{
					if (HuffNode[p].lchild==c) cd.bit[cd.start]=0;
					else  cd.bit[cd.start]=1;
					cd.start--;    c=p;
					p=HuffNode[p].parent;
				}
        for (j=cd.start+1;j<n;j++)       /*保存求出的每個(gè)葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位*/
			HuffCode[i].bit[j]=cd.bit[j];
			HuffCode[i].start=cd.start;
		 }
			for (i=0;i<n;i++)                /*輸出每個(gè)葉子結(jié)點(diǎn)的哈夫曼編碼*/
       {		
				printf("the number:%d's code is:",i+1);
				for (j=HuffCode[i].start+1;j<n;j++)
					printf("%d",HuffCode[i].bit[j]);
					printf("\n");

       }
}

void main()
{
	int n;
	printf("輸入字符個(gè)數(shù):\n");
	scanf("%d",&n);
	HaffmanCode (n );

}