hfm.h

求哈夫曼树的代码

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

void print(HuffmanTree HT,HuffmanCode HC,int n){ 
	int i,j,k; 
	//printf("\n由于字符多于32且小于64个所以有小于2^6个\n所以每行有32个空格左有32个字符\n");
	for(i=1;i<=n;i++) {
	//	for(j=0;j<32-i;j++)printf(" ");
	//	for(j=1;j<=i;j++)
	//		for(i=1;i<=n;i++) {
	//			if (HC[i]
	//printf("%s ",HT[j].code); 
	//		}
	printf(" %d %c %d %s\n",i,HT[i].code,HT[i].weight,HC[i]);
	}
}
void Select(HuffmanTree HT,int n,int *s1,int *s2){ 
	int i; 
	(*s1)=(*s2)=0; 
	for(i=1;i<=n;i++) { 
		if(HT[i].weight<HT[(*s2)].weight&&HT[i].parent==0&&(*s2)!=0){ 
			if(HT[i].weight<HT[(*s1)].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].weight<HT[(*s1)].weight) { 
						(*s2)=(*s1); 
						(*s1)=i; 
					} else 
						(*s2)=i; 
				}
		} 
	}  
	if((*s1)>(*s2)) { 
		i=(*s1); 
		(*s1)=(*s2); 
		(*s2)=i; 
	} 
	return; 
} 

void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,char *code,int n) { 
	int i,m,s1,s2,start,c,f; 
	char *cd; 
	if(n<=1) return; 
	m=2*n-1; 
	(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); 
	for(i=1;i<=n;++i) { 
		(*HT)[i].code=code[i-1]; 
		(*HT)[i].weight=w[i-1]; 
		(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0; 
	}
	for(;i<=m;++i) { 
		(*HT)[i].code='0'; 
		(*HT)[i].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].weight=(*HT)[s1].weight+(*HT)[s2].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]); 
	} 
	msg(">哈夫曼编码初始化完毕");
}