哈弗曼树.cpp

请你设计一下

#include<iostream>
using namespace std;
#define csMaxLimit 1001;
#define csINF 99999999;
bool bUsedFlag[2001];
struct stNodeInfoType
{
	int iLeftSon;
	int iRightSon;
	int iFrequence;
};
struct stNodeInfoType stNodeInfo[2001];
int iFirstFreq,iCurrentNodeCount,iNumOfChars,iTotalCodeLength,
iSingleCodeLength[2001],iFreqOfChars[100000],iFirstIndex,iSecondIndex,iSecondFreq;
void procInput()
{
	int i;
	for (i=1;i<=iNumOfChars;i++)
	{
		scanf("%d",&iFreqOfChars[i]);
	}
}
void procOuput()
{
	int i;
	iTotalCodeLength=0;
	for(i=1;i<=iNumOfChars;i++)
	{
	iTotalCodeLength+=iSingleCodeLength[i]*iFreqOfChars[i];
	}
	printf("%d\n",iTotalCodeLength);
}
void procInitial()
{
	int i;
	iCurrentNodeCount=iNumOfChars;
	for(i=1;i<=iNumOfChars;i++)
	{
		bUsedFlag[i]=true;
		stNodeInfo[i].iLeftSon=0;
		stNodeInfo[i].iRightSon=0;
		stNodeInfo[i].iFrequence=0;
	}
}
void procFindFirstAndSecond()
{
	int i;

	iFirstFreq=csINF;
	iFirstIndex=0;
	iSecondFreq=csINF;
	iSecondIndex=0;
	for(i=1;i<=iCurrentNodeCount;i++)
	{
		if(bUsedFlag[i])
{
	if(iFreqOfChars[i]<iFirstFreq)
	{
		iSecondFreq=iFirstFreq;
		iSecondIndex=iFirstIndex;
		iFirstFreq=iFreqOfChars[i];
		iFirstIndex=i;
	}
	else
	{
		if(iFreqOfChars[i]<iSecondFreq)
		{
			iSecondFreq=iFreqOfChars[i];
			iSecondIndex=i;
		}
	}
}
	}
}
void procGetCodeLength(int iNodeIndex,int iDeepth)
{
	int iIndex;
	iIndex=stNodeInfo[iNodeIndex].iLeftSon;
	if(iIndex!=0)
	{
		procGetCodeLength(iIndex,iDeepth+1);
	}
	else
	{
		iSingleCodeLength[iNodeIndex]=iDeepth;
		return ;
	}
	iIndex=stNodeInfo[iNodeIndex].iRightSon;
	if(iIndex!=0)
	{
		procGetCodeLength(iIndex,iDeepth+1);
	}
	else
	{
		iSingleCodeLength[iNodeIndex]=iDeepth;
		return ;
	}
	return ;
}
void procHuffmanCoding()
{
	while(iCurrentNodeCount!=2*iNumOfChars-1)
	{
		procFindFirstAndSecond();
		iCurrentNodeCount++;
		bUsedFlag[iFirstIndex]=false;
		bUsedFlag[iSecondIndex]=false;
		bUsedFlag[iCurrentNodeCount]=true;
		iFreqOfChars[iCurrentNodeCount]=iFreqOfChars[iFirstIndex]+iFreqOfChars[iSecondIndex];
		stNodeInfo[iCurrentNodeCount].iFrequence=iFreqOfChars[iCurrentNodeCount];
		stNodeInfo[iCurrentNodeCount].iLeftSon=iFirstIndex;
		stNodeInfo[iCurrentNodeCount].iRightSon=iSecondIndex;
	}
	procGetCodeLength(iCurrentNodeCount,0);
}



int main()
{
	while (1==scanf("%d",&iNumOfChars))
	{
		procInput();
		procInitial();
		procHuffmanCoding();
		procOuput();
	}
	return 0;
}