huffman.cpp

哈夫曼树

#include "iostream"
#include "vector"
#include "algorithm"
using namespace std;

typedef struct HuffInfotag
{
	double dP;
	double dPSum;
	string code;
	int step;
}HuffInfo;

bool compareDP( HuffInfo h1, HuffInfo h2 )
{
	return h1.dP < h2.dP;
}

bool compareDPSum( HuffInfo h1, HuffInfo h2 )
{
	if( h1.dPSum != h2.dPSum )
		return h1.dPSum < h2.dPSum;

	return h1.step < h2.step;
}

vector< string > huffman( vector< double > &vdP )
{
	vector< string > result;
	vector< HuffInfo > vhTemp( vdP.size() );
	int i, j, k, sTemp;
	double dpTemp;

	//sort
	sort( vdP.begin(), vdP.end() );

	for( i = 0; i < vdP.size(); i++ )
	{
		vhTemp[ i ].dP = vhTemp[ i ].dPSum = vdP[ i ];
		vhTemp[ i ].step = 0;
	}

	for( i = 0; i < vdP.size() - 1; i++ )
	{
		j = 1;
		dpTemp = vhTemp[ 0 ].dPSum;
		if( vhTemp[ 1 ].step != 0 )
			while( vhTemp[ j ].step == vhTemp[ 0 ].step )
				j++;
		sTemp = vhTemp[ j ].step;
		for( k = 0; k < j; k++ )
		{
			vhTemp[ k ].dPSum += vhTemp[ j ].dPSum;
			vhTemp[ k ].code.insert( 0, '1');
			vhTemp[ k ].step = i + 1;
		}
		k = j;
		do{
			vhTemp[ k ].dPSum += dpTemp;
			vhTemp[ k ].code.insert( 0, '0' );
			vhTemp[ k ].step = i + 1;
			k++;
		}while( k < vdP.size() && vhTemp[ k ].step == sTemp && vhTemp[ k ].step != 0 );

//		cout << endl;
//		for( k = 0; k < vhTemp.size(); k++ )
//			cout << vhTemp[ k ].dP << '\t' << vhTemp[ k ].dPSum << '\t' << vhTemp[ k ].step << '\t' << vhTemp[ k ].code.c_str() << endl;

		sort( vhTemp.begin(), vhTemp.end(), compareDPSum );
	}
	sort( vhTemp.begin(), vhTemp.end(), compareDP );
	for( i = 0; i < vdP.size(); i++ )
		result.push_back( vhTemp[ i ].code );
	
	return result;
}

void main()
{
	vector< double > vdP;
	vector< string > vsCode;
	double fPValue, fPSum = 0;
	int i;
	
	cout << "Please input the first n-1 possibility value, 0 for the end:" << endl;
	while( cin >> fPValue )
	{
		if( fPSum + fPValue >= 1 )
		{
			cout << "Warning! Possibility sum is more than 1, the last value is not included." << endl;

			break;
		}
		fPSum += fPValue;
		if( fPValue == 0.0 )
			break;

		vdP.push_back( fPValue );
	}
	vdP.push_back( 1 - fPSum );

	vsCode = huffman( vdP );
	
	cout << endl << "All the possibility value input is:" << endl;
	for( i = 0; i < vdP.size(); i++ )
	{
		cout << vdP[ i ] << '\t';
	}
	cout << endl;

	cout << endl << "The code is as below:" << endl;
	for( i = 0; i < vdP.size(); i++ )
	{
		cout << vdP[ i ] << '\t' << vsCode[ i ].c_str() << endl;
	}

	return;
}