哈夫曼树.cpp

一些数据结构源代码

#include <stdio.h>
#define max 21
struct huffnode
{
	char data;
	int weight; 
	int parent;
	int left;
	int right;
};
struct huffcode
{
	char cd[max];
	int start;
};

void main()
{
	struct huffnode ht[2*max];
	struct huffcode hcd[max],d;
	int i,k,f,l,r,n,c,m1,m2;
	printf("please input n\n");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		getchar();
		printf("No.%d=>Data:",i);
		scanf("%c",&ht[i].data);
		printf("\n\t Weight:");
		scanf("%d",&ht[i].weight);
	}
	for(i=1;i<=2*n-1;i++)
		ht[i].parent=ht[i].left=ht[i].right=0;
	for(i=n+1;i<=2*n-1;i++)
	{
		m1=32767;
		l=r=0;
		for(k=1;k<=i-1;k++)
			if(ht[k].parent==0)
				if(ht[k].weight<m1)
				{
					m2=m1;
					r=l;
					m1=ht[k].weight;
					l=k;
				}
				else if(ht[k].weight<m2)
				{
					m2=ht[k].weight;
					r=k;
				}
				ht[l].parent=i;
				ht[r].parent=i;
				ht[i].weight=ht[l].weight+ht[r].weight;
				ht[i].left=l;
				ht[i].right=r;
				}
	for(i=1;i<=n;i++)
	{
		d.start=n;
		c=i;
		f=ht[i].parent;
		while(f!=0)
		{
			if(ht[f].left==c)
				d.cd[d.start]='l';
			d.start=d.start-l;
			c=f;
			f=ht[f].parent;
		}
		hcd[i]=d;
	}
	printf("output huffman-code:\n");
	for(i=1;i<=n;i++)
	{
		printf("%c",ht[i].data);
		for(k=hcd[i].start;k<=n;k++)
			printf("%c",hcd[i].cd[k]);
		printf("\n");
	}
}