huffman_coding.cpp

huffman coding ke yi ce shi jian , you lei

#include "defines.h"


void GatherData(ifstream& inFile, vector<hNode>& hTree)
{
	char ch;
	while(inFile.get(ch))
	{
		bool appeared = false;
		vector<hNode>::iterator iter = hTree.begin();
		vector<hNode>::iterator iter_end = hTree.end();
		while(iter != iter_end)
		{
			if(ch == iter->value)
			{
				iter->weight++;
				appeared = true;
			}
			++iter;
		}
		if(!appeared)
		{
			hNode newNode;

			newNode.value = ch;
			newNode.weight = 1;
			hTree.push_back(newNode);
		}
	}
	
}


void CheckData(vector<hNode>& hTree, string ofile)
{
	vector<hNode>::iterator iter = hTree.begin();
	vector<hNode>::iterator iter_end = hTree.end();
	ofstream outfile(ofile.c_str());

	while(iter != iter_end)
	{
		outfile << iter->value << ' ' << iter->weight <<  ' ' << iter->used << endl;
		++iter;
	}
}

void CheckData(vector<string>& codeResult, string ofile)
{
	vector<string>::iterator iter = codeResult.begin();
	vector<string>::iterator iter_end = codeResult.end();
	ofstream outfile(ofile.c_str());

	while(iter != iter_end)
	{
		outfile << *iter << endl;
		++iter;
	}
}

vector<hNode>::iterator FindMinimumNode(vector<hNode>& hTree)
{
	vector<hNode>::iterator iter = hTree.begin();
	vector<hNode>::iterator iter_end = hTree.end();
	//pair<int, int> miniNode(iter->value, iter->weight);
	vector<hNode>::iterator miniNode;
	unsigned long miniWeight = -1;

	while(iter != iter_end)
	{
		if((iter->weight < miniWeight) && (iter->used != true))
		{
			miniNode = iter;
			miniWeight = iter->weight;
		}
		iter++;
	}
	miniNode->used = true;
	return miniNode;
}

void CreatHuffmanTree(vector<hNode>& hTree)
{
	hNode newNode;
	string ofile("rate.txt");
	int ix = 0;
	while(1)
	{
		vector<hNode>::iterator iter = hTree.begin();
		vector<hNode>::iterator iter_end = hTree.end();
		int unusedNum = 0;
		while(iter != iter_end)
		{
			if(iter->used == false)
				unusedNum++;
			iter++;
		}
		if(unusedNum <= 1)
			break;

		vector<hNode>::iterator mini_1 = FindMinimumNode(hTree);
		vector<hNode>::iterator mini_2 = FindMinimumNode(hTree);

		newNode.Clear();

		newNode.weight = mini_1->weight + mini_2->weight;
		newNode.pLeft = mini_1;
		newNode.pRight = mini_2;
		hTree.push_back(newNode);
		mini_1->pFront = hTree.end()-1;
		mini_2->pFront = hTree.end()-1;
		ofile = ofile + "b";
		ix++;
		CheckData(hTree,ofile);
	}
}

void HuffmanCoding(vector<hNode>& hTree, vector<string>& codeResult)
{
	string code;
	string zero("0");
	string one("0");
	vector<hNode>::iterator iter = hTree.begin();
	vector<hNode>::iterator iter_end = hTree.end();
	vector<hNode>::iterator iter_front = hTree.begin();
	vector<hNode>::iterator iter_tmp = hTree.begin();

	while(iter != iter_end)
	{
		if(iter->value != 0)
		{
			iter_tmp = iter;
			while(iter_tmp != iter_end)
			{
				iter_front = iter_tmp->pFront;

				if(iter_tmp == iter_front->pLeft)
					code = zero + code;
				if(iter_tmp == iter_front->pRight)
					code = one + code;
				iter_tmp = iter_front;
			}
			codeResult.push_back(code);
			code.clear();
		}
		else
		{
			break;
		}
		iter++;
	}
}