哈夫曼编码--贪心算法

 

#include<iostream>

using namespace std;

#define MAX 1001
#define INF 99999999

struct stuTreeNode
{
	int nFr;
	int nLeft;
	int nRight;
};

struct stuNodeTow
{
	int nA;
	int nB;
};

void vInputNode(int nN,int nNode[],bool bVist[]);
void vBuildTree(int nN,int nNode[],bool bVist[],stuTreeNode stuTree[]);
stuNodeTow stuGetAB(int nC,int nNode[],bool bVist[]);
void vGetCode(int nHaCode[],stuTreeNode stuTree[],int nRoot,int nDepth);
void vOutputSum(int nN,int nNode[],int nHaCode[]);

int main()
{
	int nNum;
	int nFrNode[2*MAX];
	int nCode[2*MAX];
	bool bIsVist[2*MAX];
	stuTreeNode stuTree[2*MAX];

	while(1 == scanf("%d",&nNum))
	{
		vInputNode(nNum,nFrNode,bIsVist);
		memset(stuTree,0,sizeof(stuTree));
		vBuildTree(nNum,nFrNode,bIsVist,stuTree);
		vGetCode(nCode,stuTree,2*nNum-1,0);
		vOutputSum(nNum,nFrNode,nCode);
	}

	return 0;
}

void vInputNode(int nN,int nNode[],bool bVist[])
{
	int i;

	for(i=1;i<=nN;i++)
	{
		scanf("%d",&nNode[i]);
		bVist[i] = true;
		bVist[i+nN] = false;
	}
}

void vBuildTree(int nN,int nNode[],bool bVist[],stuTreeNode stuTree[])
{
	int nCount;
	stuNodeTow stuNodeAB;

	nCount = nN;
	while(nCount < 2*nN-1)
	{
		stuNodeAB = stuGetAB(nCount,nNode,bVist);
		nCount ++;//相加后节点值的下标
		bVist[nCount] = true;//相加后节点值为新节点
		bVist[stuNodeAB.nA] = false;//已访问
		bVist[stuNodeAB.nB] = false;//已访问
		stuTree[nCount].nLeft = stuNodeAB.nA  //下标赋值给左子树
		stuTree[nCount].nRight = stuNodeAB.nB;
		nNode[nCount] = nNode[stuNodeAB.nA] + nNode[stuNodeAB.nB];//当前值最小两节点的和
		stuTree[nCount].nFr = nNode[nCount];
	}
}

//遍历所有没有用到过的节点，查找最小的两个节点，返回其下标
stuNodeTow stuGetAB(int nC,int nNode[],bool bVist[])
{
	int i;
	stuNodeTow stuAB;
	int nTemp1,nTemp2;

	nTemp1 = INF;
	nTemp2 = INF;
	stuAB.nA = 1;
	stuAB.nB = 1;
	for(i=1;i<=nC;i++)
	{
		if(bVist[i])
		{
			if(nNode[i] < nTemp1)
			{
				nTemp2 = nTemp1;
				stuAB.nB = stuAB.nA;
				nTemp1 = nNode[i];
				stuAB.nA = i;
			}
			else
				if(nNode[i] < nTemp2)
				{
					nTemp2 = nNode[i];
					stuAB.nB = i;
				}
		}
	}

	return stuAB;
}

void vGetCode(int nHaCode[],stuTreeNode stuTree[],int nRoot,int nDepth)
{
	int nL,nR;

	nL = stuTree[nRoot].nLeft;
	if(nL != 0)
	{
		vGetCode(nHaCode,stuTree,nL,nDepth+1);
	}
	else
	{
		nHaCode[nRoot] = nDepth;
		return ;
	}
	nR = stuTree[nRoot].nRight;
	if(nL != 0)
	{
		vGetCode(nHaCode,stuTree,nR,nDepth+1);
	}
	else
	{
		nHaCode[nRoot] = nDepth;
		return ;
	}
}

void vOutputSum(int nN,int nNode[],int nHaCode[])
{
	int i;
	int nAns;

	nAns = 0;
	for(i=1;i<=nN;i++)
	{
		nAns += nHaCode[i]*nNode[i];
	}
	printf("%d\n",&nAns);
}