huffmantree.cpp

创建静态

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

typedef char **HuffmanCode;

HuffmanTree HT;
HuffmanCode HC;
int n, wei[30];

void select(HuffmanTree HT,int n,int &s1,int &s2);
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n)
{
	
	int i, j, m, s1, s2, start;
	char *cd;
	int c, f;
	cout<<"输入你要编码的个数 ，例如 5回车  "<<endl;
	cin>>n;
	cout<<"依次输入它们的权重值， 例如:1 3 5 7 9回车  "<<endl;
	for(i=0;i<n;i++)
		cin>>wei[i];
	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;
	}
	printf("\n哈夫曼树的构造过程如下所示：\n");
	cout<<"HT初态:\n  结点  weight  parent  lchild  rchild"<<endl;
	for (i=1; i<=m; i++)
		printf("%4d%8d%8d%8d%8d\n",i,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild);
    printf("    按回车键，继续 ...");
	getchar();
	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;
		printf("\nselect: s1=%d   s2=%d\n", s1, s2);
		printf("  结点  weight  parent  lchild  rchild");
		for (j=1; j<=i; j++)
			printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);
		printf("    按回车键，继续 ...");
		getchar();
		
	}
	
	//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
	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); 
	cout<<"***********************赫夫曼编码为**********************"<<endl;
	for(i=1;i<=n;i++)
		cout<<wei[i-1]<<(char)45<<(char)45<<(char)16<<"\t"<<HC[i]<<endl;
} 


void select(HuffmanTree HT,int n,int &s1,int &s2)
{
	int weight,i;
	s1=0;s2=0;
	weight=100;
	for(i=1;i<=n;i++)
	{
		if(HT[i].parent==0)
		{
			if(HT[i].weight>weight)
				continue;
			else
			{
				weight=HT[i].weight;
				s1=i;
			}
		}
	}
	HT[s1].parent=s1;
	weight=100;
	for(i=1;i<=n;i++)
	{
		if(HT[i].parent==0)
		{
			if(HT[i].weight>weight)
				continue;
			else
			{weight=HT[i].weight;
			s2=i;
			}
		}
	}
}