huffman.cpp

哈夫曼树的实现.

#include"Huffman.h"

//此函数用于选取最小权值的下标分别放在min1和min2
static void SelectTwoMin(HuffmanTree HT,int n,int &min1,int &min2){
	int i=1;
	int tmp;
	int m1,m2;
	for(;i<=n;i++)
	{
		if(HT[i].parent !=0) continue;
		else
		{
			m1=i;
			break;
		}	
	}
	i++;
	for(;i<=n;i++)
	{
		if(HT[i].parent !=0) continue;
		else
		{
			(HT[i].weight>=HT[m1].weight)?(m2=i):(m2=m1,m1=i);
			break;
		}
	}
	i++;
	for(;i<=n;i++)
		if(HT[i].parent !=0) continue;
		else
		{
			tmp=m1;
			m1=((HT[m1].weight <HT[i].weight)?m1:i) ;
			m2=((m1==tmp)?((HT[m2].weight <=HT[i].weight)?m2:i):tmp);
			//((HT[m2].weight <HT[tmp].weight)?min2:tmp);
		}	
min1=m1,min2=m2;

	}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n){
	int i,f,m,start,min1,min2,*pi;
	unsigned c;
	char* cd;
	pi=w;
	if(n<=1)return ;
	m=2*n-1;
	HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
	for(i=1;i<=n;++i,++pi)
	{
		HT[i].weight=*pi;
		HT[i].parent=HT[i].lchild=HT[i].rchild=0;
	}
	for(;i<=m;++i)
	{
		HT[i].weight=0;
		HT[i].parent=HT[i].lchild=HT[i].rchild=0;
	}
	for(i=n+1;i<=m;++i)
	{
		SelectTwoMin(HT,i-1,min1,min2);
		HT[min1].parent=i;	HT[min2].parent=i;
		HT[i].lchild=min1;	HT[i].rchild=min2;
		HT[i].weight =HT[min1].weight+HT[min2].weight;
	}
	HC=(HuffmanCode)malloc((n+1)*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]);
	}
	free(cd);
	
	}