#include "stdio.h"
#include "string.h"
#define LEN 50   /*輸入字符最大值*/
#define MAX 100  /*選parent 為0時 S1和S2的初值*/
#define BLEN 100 /*解碼時輸入字符的最大值*/
struct HTNode{
	int letter;    /*字符序號*/
	int weight;    /*權重*/
	int parent;    /*雙親*/
	int lchild;    /*左孩子*/
	int rchild;    /*右孩子*/
	char code[LEN-1]; /*赫夫曼編碼,僅用于葉子結點*/
	};
main(){
	struct HTNode HT[LEN];/* HT為編碼區*/
	static int m, n,s1,s2,f1,f2;/*f1,f2用于選parent 為0且weight最小的兩個結點,s1,s2為最小兩結點序號,n為字符個數,m為總點個數,*/
	int i,j,p,num;	/*mun為字符個數,i,j為循環數,p用于解碼序號*/
	int c,f;
	char cd[LEN-1],HC[LEN-1],Buff[BLEN];/*cd為暫存空間,HC為編碼存儲空間,Buff為輸入解碼的空間*/
	printf("----Huffmancode code----\n");/*赫夫曼編碼建立*/
	printf("Please input the coding piece:",n);/*字符個數*/
	scanf("%d",&n);
	num=n;
	m=2*n-1;
	for(i=1;i<=n;i++){
	printf("please input the %d code weight: ",i);/*輸入各字符權重*/
		scanf("%d",&HT[i].weight);
		HT[i].letter=i;
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	}/*for*/	
	for(i=n+1;i<=m;++i,n++){
		f1=f2=MAX;s2=s1=0;
	 for(j=1;j<=n;j++){
	 	if(HT[j].parent==0)/*選parent 為0且weight最小的兩個結點,把序號附給s1,s2*/
	 	if(HT[j].weight<f2)
	 	if(HT[j].weight<f1){
	 		f2=f1;f1=HT[j].weight;
	 		s2=s1;s1=j;}
	 	else{
	 		f2=HT[j].weight;
	 		s2=j;}
	 		}	
	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;		
	 }/*for*/
	printf(" num weight parent lchild rchild\n");/*輸出赫夫曼樹初態*/
	for(i=1;i<=m;i++){
		printf("%3d %6d %5d %6d %6d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
		if(i%10==0){getchar();}
	}/*for*/
	getchar();getchar();
	for(i=1;i<=num;i++){
		strcpy(HC,"\0");
		printf("the %d Huffmancode: ",i);
		for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
		if(HT[f].lchild==c){
			 strcpy(cd,"0");
			 strcpy(HC,strcat(cd,HC));
			 }/*if*/
		else{
			 strcpy(cd,"1");
			 strcpy(HC,strcat(cd,HC)); 
		}/*else*/
		strcpy(HT[i].code,HC);
		printf("%s",HT[i].code);
		printf("\n");
		if(i%10==0){getchar();}
	}/*for*/  
	getchar();
	printf("----Huffmancode Decoding----\n");/*赫夫曼編碼解碼*/
	printf("please input Huffmancode:");/*輸入要解碼的01編碼*/
	scanf("%s",Buff);
	i=0;p=2*num-1;
   printf("Huffmancode Decoding:");
	while(Buff[i]!='\0'){
		if(Buff[i]=='0') p=HT[p].lchild;
		else p=HT[p].rchild;
		if(HT[p].lchild==0&&HT[p].rchild==0){
			printf("%d",HT[p].letter);
			p=2*num-1;
		}
		i++;
		}
}/*main*/