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

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

typedef   char   **HuffmanCode;   

typedef   struct   {   
	unsigned   int   s1;   
	unsigned   int   s2;   
}   MinCode;   

void   Error(char   *message);   
HuffmanCode   HuffmanCoding(HuffmanTree   HT,HuffmanCode   HC,unsigned   int   *w,unsigned   int   n);   
MinCode   Select(HuffmanTree   HT,unsigned   int   n);   

void   Error(char   *message)   
{   
	fprintf(stderr,"Error:%s\n",message);   
	exit(1);   
}   

HuffmanCode   HuffmanCoding(HuffmanTree   HT,HuffmanCode   HC,unsigned   int   *w,unsigned   int   n)   
{   //w存放n個字符的權值（均>0），構造赫夫曼樹HT，并求出n個字符的赫夫曼編碼HC。
	unsigned   int   i,s1=0,s2=0;   
	HuffmanTree   p;   
	char   *cd;   
	unsigned   int   f,c,start,m;   
	MinCode   min;   
	if(n<=1)   
		Error("Code   too   small!");   
	m=2*n-1;   
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); //0號單元未用。  
	for(p=HT,i=0;i<=n;i++,p++,w++)   
	{   
		p->weight=*w;   
		p->parent=0;   
		p->lchild=0;   
		p->rchild=0;   
	}   
	for(;i<=m;i++,p++)   
	{   
		p->weight=0;   
		p->parent=0;   
		p->lchild=0;   
		p->rchild=0;   
	}   
	for(i=n+1;i<=m;i++)   
	{   //建赫夫曼樹
		//在HT[1..i-1]選擇parent為0且weight最小的兩個結點，其序號分別為s1和s2。
		min=Select(HT,i-1);   
		s1=min.s1;   
		s2=min.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;   
	}   
	printf("HT   List:\n");   
	printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");   
	for(i=1;i<=m;i++)   
		printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",   
		i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
	//從葉子到根逆向求每個字符的赫夫曼編碼。 
	HC=(HuffmanCode)malloc((n+1)*sizeof(char   *)); //分配n個字符編碼的頭指針向量。  
	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   *)); //為第i個字符編碼分配空間。  
			strcpy(HC[i],&cd[start]);   //從cd復制編碼（串）到HC。
	}   
	free(cd);   
	return   HC;   
}   

MinCode   Select(HuffmanTree   HT,unsigned   int   n)   
{   
	unsigned   int   min,secmin;   
	unsigned   int   temp;   
	unsigned   int   i,s1,s2,tempi;   
	MinCode   code;   
	s1=1;
	s2=1;   
	for(i=1;i<=n;i++)   
		if(HT[i].parent==0)   
		{   
			min=HT[i].weight;   
			s1=i;   
			break;   
		}   
		tempi=i++;   
		for(;i<=n;i++)   
			if(HT[i].weight<min&&HT[i].parent==0)   
			{   
				min=HT[i].weight;   
				s1=i;   
			}   
			for(i=tempi;i<=n;i++)   
				if(HT[i].parent==0&&i!=s1)   
				{   
					secmin=HT[i].weight;   
					s2=i;   
					break;   
				}   
				for(i=1;i<=n;i++) 
				{
					if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)   
					{   
						secmin=HT[i].weight;   
						s2=i;   
					}  
				}
				if(s1>s2)   
				{   
					temp=s1;   
					s1=s2;   
					s2=temp;   
				}   
				code.s1=s1;   
				code.s2=s2;   
				return   code;   
}   

void main()   
{   
	HuffmanTree   HT=NULL;   
	HuffmanCode   HC=NULL;   
	unsigned   int   *w=NULL;   
	unsigned   int   i,n;   
	printf("Input   n:\n");   
	scanf("%d",&n);   
	w=(unsigned   int   *)malloc((n+1)*sizeof(unsigned   int   *)); //給權值分配空間。   
	w[0]=0; //給第一個空間賦0值。  
	printf("Enter   weight:\n");   
	for(i=1;i<=n;i++)   //錄入權值。
	{   
		printf("w[%d]=",i);   
		scanf("%d",&w[i]);   
	}   
	HC=HuffmanCoding(HT,HC,w,n);   
	printf("HuffmanCode:\n");   
	printf("Number\t\tWeight\t\tCode\n");   
	for(i=1;i<=n;i++)   
		printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]);   
    
}