哈夫曼编码

#include<stdio.h>
#include<malloc.h>
#include<string.h>
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;

void Select(HuffmanTree &HT,int n,int &s1,int &s2)
{
    
    for (int i = 0; i < n; i++)
    {
        if (HT[i].parent == 0)
        {
            s1=i;    
            break;
        }
    }
    for (int i = 0; i <n; i++)        
    {
        if ((HT[s1].weight > HT[i].weight) && (HT[i].parent == 0))        
        {
            s1 = i;
        }
    }
    
    for (int i = 0; i <n; i++)
    {
        if ((HT[i].parent == 0)&&i!=s1)        
        {
            s2 = i;    
            break;
        }
    }
    for (int i = 0; i <n; i++)        
    {
        if ((HT[s2].weight > HT[i].weight) && (HT[i].parent == 0) && (i != s1))
        {
            s2 = i;
        }
    }
    
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)
{
	int i,m,s1,s2,start;
 	char *cd;
 	unsigned int c, f;
 	if(n<=1)
		return;
 	m=2*n-1;
 	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
 	for(i=1;i<=n;i++)
 	{
  		HT[i].weight=w[i-1];
  		HT[i].parent=0;
  		HT[i].lchild=0;
  		HT[i].rchild=0;
 	}
 	for(i=n+1;i<=m;i++)
 	{
 		HT[i].weight=0;
  		HT[i].parent=0;
  		HT[i].lchild=0;
  		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].weight=HT[s1].weight+HT[s2].weight;
 	}
 	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]); 
 	}
 	free(cd);
}
int main()
{
	int i,n;
	int *w;
	HuffmanTree HT;
	HuffmanCode HC;
    //汉字编码出了问题。。。。。。。
	//printf("锟斤拷锟斤拷锟斤拷权值锟斤拷锟斤拷锟斤拷\n");
	scanf("%d",&n); 
	w=(int *)malloc(n*sizeof(int)); 
	//printf("锟斤拷锟斤拷锟斤拷权值锟斤拷\n"); 
	for ( i=0;i<n;i++) 
		scanf("%d",&w[i]);

	HC=(char **)malloc((n+1)*sizeof(char*));
	HT=(HuffmanTree)malloc((2*n+1+1)*sizeof(HTNode));
	HuffmanCoding(HT, HC, w, n);
	for(i=1;i<n+1;i++)
	{
		puts(HC[i]); 
		free(HC[i]); 
	}
	free(HC);
	free(HT);
	return 0;
}