huffmancode.cpp

用stl 实现的哈夫曼编码

#include <iostream>
#include <string>
#include <list>
#include <stack>
#pragma warning (disable:4786) 

using namespace std;

#define MAX_NUM  8
double Weight[MAX_NUM]={0.4,0.18,0.1,0.1,0.07,0.06,0.05,0.04};
class HuffmanNode
{
public:
	double weight;
	int num;
	char code;
	HuffmanNode* lchild;
	HuffmanNode* rchild;
public:
	HuffmanNode()
	{
		weight=0;
		num=-1;
		code='2';
		lchild=rchild=NULL;
	}
	static void Traveling(HuffmanNode* curNode);
};

	string strCode;
void HuffmanNode::Traveling(HuffmanNode* curNode)
{
	if(curNode==NULL)	return ;	
	strCode+=curNode->code;
	if(curNode->num!=-1)
	{
		cout<<"x"<<curNode->num<<" -->  ";
		if(strCode[0]=='2')  
			cout<<strCode.substr(1,strCode.size())<<endl;
		else
			cout<<strCode<<endl;
	}
	Traveling(curNode->lchild);
	Traveling(curNode->rchild);
	string::iterator it=strCode.end();
	strCode.erase(--it);


}//哈夫曼编码
void HuffmanCode(double *weight,int n);


void main()
{
	HuffmanCode(Weight,MAX_NUM);
	
}
//Huffman编码
void HuffmanCode(double* w,int n)
{
	list<HuffmanNode*> HN;
	list<HuffmanNode*>::iterator iter;
	list<HuffmanNode*>::iterator it;
	
	for (int i=0;i<n;i++)
	{
		HuffmanNode* t=new HuffmanNode();
		t->num=i+1;
		t->weight=w[i];
		HN.push_back(t);
	}	
	/*
	//display
	//-----------------------------------------------	
	for(iter=HN.begin();iter!=HN.end();iter++)
	cout<<(*iter)->num<<"---"<<(*iter)->weight<<endl;
	//------------------------------------------------
	*/
	while(HN.size()>1)
	{
		//sort
		//---------------------------------------------
		for(iter=HN.begin();iter!=HN.end();iter++)
			for(it=iter;it!=HN.end();it++)
			{
				if((*iter)->weight < (*it)->weight)
					swap((*iter),(*it));
			}
		
		iter=HN.end();
		iter--;
		HuffmanNode* t=new HuffmanNode();
		(*iter)->code='1';
		t->rchild=*iter;
		t->weight=(*iter)->weight+(*(--iter))->weight;
		// cout<<t->weight<<endl;
		(*iter)->code='0';
		t->lchild=*iter;
		iter++;
		HN.erase(iter);
		iter=HN.end();
		iter--;
		HN.erase(iter);
		HN.push_back(t);
	}
	iter=HN.begin();
	HuffmanNode*temp= *iter;
	HuffmanNode::Traveling(temp);//output
	cout<<endl;
}