s.cpp

哈夫曼树算法 根据给定的n个权值{w1,w2,……wn}

#include<stdio.h>
#define M 10;
#define MAX 100;
struct JD
{
	int data;
	JD* pa,lc,rc;
};
void HuffmanTree(int n,int w[],JD t[])
{
	int i,j,k,x1,x2,m1,m2;
	for(i=1;i<(2*n-1);i++)
	{
		t[i].lc=t[i].rc=t[i].pa=0;
		if(i<=n)
			t[i].data=w[i-1];
		else
			t[i].data=0;
	}
	for(i=1;i<=n;i++)//
	{
		m1=m2=MAX;
		x1=x2=0;
		for(j=1;j<(n+i);i++)
		{
			if((t[j].data<m1)&&(t[j].pa==0))
			{
				m2=m1;
				m1=t[j].data;
				x2=x1;
				x1=j;
			}
			else if((t[j].data<m2)&&(t[j].pa==0))
			{
				m1=t[j].data;
				x2=x1;
				x1=j;
			}
		}
		k=n+i;
		t[x1].pa=t[x2].pa=k;
		t[k].data=m1+m2;
		t[k].lc=x1;
		t[k].rc=x2;
	}
}
void main()
{
	int i,s[4]={7,5,2,4};
    HuffmanTree(4,s[],t[]);
	for(i=1;i<(2*n-1);i++)
	printf("%d,%d,%d,%d\n",t[i].lc,t[i].data,t[i].rc,t[i].pa);
	printf("\n");
}