huffman编码-zoj_1117

huffman编码---zoj_1117

huffman编码是一种优化的编码方法，于ASCII等固定长度的编码方法相比较，他可以使编码的长度缩短。其主要的思路是，让出现频率高的字符拥有较短的编码，让出现频率较低的字符，拥有较长的编码。但是，这样的编码方式就要求任意一个字符的编码不能是其他字符编码的前缀，通常这种编码方式叫前缀编码。
         huffman编码通过构造huffmanTree来实现，贪心思想。取权值（频率）最低的2个节点为新节点的左右子节点，新节点的权值为子节点权值之和。处理之后，子节点标记为已经处理过，新节点标记为未处理。循环处理该过程。如果huffmanTree中有m个叶节点，那么huffmanTree中肯定有n=2*m-1个节点。因此，当huffmanTree中有2*m-1个节点时，huffmanTree构造就结束了。

//zoj1117.cpp  
#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
class huffmanNode
{
public:
	int value,parent,left,right,pos;
	bool isset;
	int  dir;
	huffmanNode()
	{
		this->isset=false;
		this->left=-1;
		this->right=-1;	
		this->parent=-1;
		this->pos=-1;
		this->dir=1;
	}
	huffmanNode(int value,int pos):value(value),pos(pos)
	{
		this->isset=false;
		this->left=-1;
		this->right=-1;
		this->parent=-1;
		this->dir=-1;	
	}
};
class huffmanTree
{
public:
	huffmanNode hflist[20000];
	int n,count,flag;
	huffmanTree(int count,int n)
	{
		this->count=count;
		this->n=n;
		this->flag=count;
	}
	void createTree()
	{
		while(flag<n)
		{
			int a=0;
			int b=0;
			int va=99999998;
			int vb=99999999;
			for(int i=0;i<flag;i++)
			{
				if(hflist[i].isset)
				continue;
				if(hflist[i].value<vb)
				{	
					b=i;
					vb=hflist[i].value;
				}
				if(vb<va)
				{
					int temp=vb;
					vb=va;
					va=temp;
					temp=b;
					b=a;
					a=temp;
				}
			}
			huffmanNode node(hflist[a].value+hflist[b].value,flag);
			node.left=a;
			node.right=b;
			hflist[flag]=node;
			hflist[a].parent=flag;
			hflist[a].dir=0;
			hflist[b].dir=1;
			hflist[b].parent=flag;
			hflist[a].isset=true;
			hflist[b].isset=true;
			++flag;
		}	
	}
	int  getEncoding(int n)
	{
		if(n>=count)
			return 0;
		int flag=n;
		int result=0;
		while(hflist[flag].parent!=-1)
		{
			//cout<<hflist[flag].dir<<" ";
			flag=hflist[flag].parent;
			++result;
		}
		return result;
	}

};
int num[27];
int flag,m,n;
int main()
{
	char ch[20000];
	memset(ch,0,sizeof(ch));
	while(scanf("%s",ch)!=EOF)
	{
		//cout<<ch<<endl;
		if(ch[0]=='E'&&ch[1]=='N'&&ch[2]=='D'&&ch[3]=='\0')
		break;
		memset(num,0,sizeof(num));
		flag=0;
		m=0;
		while(ch[flag]!=0)
		{
			if(ch[flag]=='_')
			{
				if(num[26]==0)
				++m;
				++num[26];
			}
			else
			{
				if(num[ch[flag]-65]==0)
				++m;
				++num[ch[flag]-65];
			}
			++flag;
		}
		n=m*2-1;
		int j=0;
		huffmanTree tree(m,n);
		for(int i=0;i<27;i++)
		{
			if(i!=26&&num[i]>0)
			{
				huffmanNode node(num[i],j);
				tree.hflist[j]=node;
				j++;
			}
			if(i==26)
			{
				huffmanNode node(num[26],j);
				tree.hflist[j]=node;
				j++;	
			}
			
		}
		/*for(int i=0;i<m;i++)
		{
			cout<<tree.hflist[i].value<<endl;
		}*/
		cout<<flag*8<<" ";
		tree.createTree();
		int result=0;
		if(m<=1)
		result=tree.hflist[0].value;
		else
		{
			for(int i=0;i<m;i++)
			{
			result+=tree.getEncoding(i)*tree.hflist[i].value;
			//cout<<endl;		
			}
		}
		cout<<result<<" ";
		printf("%.1f\n",(float)8*flag/result);
		memset(ch,0,sizeof(ch));
	}

	
}