huff.cpp

一个用VC++做的3D魔方游戏,注意不是用JAVA做的哦

# include <iostream.h>
struct HuffNode
{
	char data;   //存放字符
	int bit[100];   //存放字符的哈夫曼编码
	int weight;    //存放频度
	HuffNode * lc;    //左子树的地址
	HuffNode * rc;    //右子树的地址
	HuffNode * parent;     //父母树的地址
	int num;     //该结点的编码值，0或1，根结点的值是-1
	int m;      //判断该结点是否为初始结点
	int n;      //判断是否参加比较
	int i;      
};

int min(HuffNode * a[])             //找出频度值最小的结点
{
	int i=0,j;

	while (a[i]->n!=1)
		i++;

	HuffNode * minNode=new HuffNode;
	minNode=a[i];
	j=i;

	for (i;i<15;i++)
		if (a[i]->n==1)
			if (minNode->weight >a[i]->weight )
			{
				minNode=a[i];
				j=i;
			}

	return j;
}

void main ()
{
	char date[15]={' ','A','E','F','G','H','I','M','O','P','R','S','T','V','Y'};
	int num[15]={186,64,103,21,15,47,57,20,63,15,48,51,80,8,16};

	HuffNode * node2[15];
	HuffNode * node1[15];

	int j=0,i;

	for (i=0;i<15;i++)     //初始化初始结点
	{
		HuffNode * q=new HuffNode;
		q->data =date[i];
		q->weight =num[i];
		q->n=1;            //该结点参加比较
		q->m=1;            //该结点是初始结点

		node1[i]=q;
	}

	for (i=0;i<15;i++)     //建立哈夫曼树
	{
		int min1,min2;
		min1=min(node1);        //找出频度最小的结点
        node1[min1]->n=0;       //第一个结点不再参与比较
		min2=min(node1);        //找出频度最小的结点

		HuffNode * p=new HuffNode;

		p->weight =node1[min1]->weight +node1[min2]->weight ;   //父母结点的频度是子结点的频度之和
		p->lc =node1[min1];     //左结点
		p->rc =node1[min2];     //右结点
		p->n=1;                //该结点参与比较
		p->m=0;                //该结点不是初始结点
		p->parent =NULL;       //父母结点初始为空

		node1[min1]->parent =p;           //父母结点
		node1[min2]->parent =p;           //父母结点

		node1[min1]->num =0;              //左结点的编码值是0
		node1[min2]->num =1;              //右结点的编码值是1

		if(node1[min1]->m==1 && j<15)             //第一个结点若是初始结点，则存在第二个数组中
		{
			node2[j]=node1[min1];
			cout<<node2[j]->data<<endl;
			j++;
		}

		if (node1[min2]->m==1 && j<15)            //第二个结点若是初始结点，则存在第二个数组中
		{
			node2[j]=node1[min2];
			cout<<node2[j]->data<<endl;
			j++;
		}
        
		node1[min2]=p;                      //把P放入到第二个结点的位置上，P的属性在上面设定的

	}

	for(i=0;i<15;i++)
		cout<<node2[i]->data<<endl;

	for ( i=0;i<15;i++)                     //算出结点的编码初始值，初始值顺序是颠倒的
	{
		j=0;
        node2[i]->i=0;

		HuffNode * temp=new HuffNode;
		temp=node2[i];

		while(temp->parent !=NULL)
		{

			node2[i]->bit [j]=temp->num ;
			j++;

			node2[i]->i++;
			temp=temp->parent ;
		}
		cout<<node2[i]->data<<endl;
	}

	for (i=0;i<15;i++)                 //将初始值的顺序按正确顺序存储
	{
		int c=node2[i]->i;

		for(j=0;j<c/2;j++)
		{
			int d=node2[i]->bit[j];
			node2[i]->bit[j]=node2[i]->bit [c-1-j];
			node2[i]->bit[c-i-j]=d;
		}
	}

	for (i=0;i<15;i++)
	{
		cout<<node2[i]->data <<"   ";

		for(j=0;j<node2[i]->i;j++)
			cout<<node2[i]->bit[j];
		cout<<endl;
	}

}