huffman_cpp.h

哈弗曼编码的课程设计报告

#ifndef HUFFMAN_CPP
#define HUFFMAN_CPP

#include<vector>
#include<algorithm>
#include<string>
#include"Huffman_h.h"

template<class W>
HfmTree_T<W>::HfmTree_T(void):m_tree(){}

template<class W>
HfmTree_T<W>::HfmTree_T(const BinaryTree_T<int> &rhs)
{
	m_tree=rhs.m_tree;
}

template<class W>
HfmTree_T<W>::HfmTree_T(const HfmTree_T<W> &rhs)
{
	m_tree=rhs.m_tree;
	m_weight=rhs.m_weight;
}

template<class W>
HfmTree_T<W>::~HfmTree_T(void)
{
	//空函数
}

template<class W>
bool HfmTree_T<W>::operator <(const HfmTree_T<W> &rhs)const
{
	return (m_weight<rhs.m_weight);
}

template<class W>
bool HfmTree_T<W>::operator ==(const HfmTree_T<W> &rhs)const
{
	return (m_weight==rhs.m_weight);
}

template<class W>
bool HfmTree_T<W>::operator >(const HfmTree_T<W> &rhs)const
{
	return (m_weight>rhs.m_weight);
}

template<class W>
HfmTree_T<W>::operator W()const
{
	return m_weight;
}

template<class W>
void HfmTree_T<W>::GetWeight(char c)
{
	switch(c)
	{
	case ' ':m_char_weight[0]++;break;
	case 'A':m_char_weight[1]++;break;
	case 'B':m_char_weight[2]++;break;
	case 'C':m_char_weight[3]++;break;
	case 'D':m_char_weight[4]++;break;
	case 'E':m_char_weight[5]++;break;
	case 'F':m_char_weight[6]++;break;
	case 'G':m_char_weight[7]++;break;
	case 'H':m_char_weight[8]++;break;
	case 'I':m_char_weight[9]++;break;
	case 'J':m_char_weight[10]++;break;
	case 'K':m_char_weight[11]++;break;
	case 'L':m_char_weight[12]++;break;
	case 'M':m_char_weight[13]++;break;
	case 'N':m_char_weight[14]++;break;
	case 'O':m_char_weight[15]++;break;
	case 'P':m_char_weight[16]++;break;
	case 'Q':m_char_weight[17]++;break;
	case 'R':m_char_weight[18]++;break;
	case 'S':m_char_weight[19]++;break;
	case 'T':m_char_weight[20]++;break;
	case 'U':m_char_weight[21]++;break;
	case 'V':m_char_weight[22]++;break;
	case 'W':m_char_weight[23]++;break;
	case 'X':m_char_weight[24]++;break;
	case 'Y':m_char_weight[25]++;break;
	case 'Z':m_char_weight[26]++;break;
	case 'a':m_char_weight[27]++;break;
	case 'b':m_char_weight[28]++;break;
	case 'c':m_char_weight[29]++;break;
    case 'd':m_char_weight[30]++;break;
	case 'e':m_char_weight[31]++;break;
	case 'f':m_char_weight[32]++;break;
	case 'g':m_char_weight[33]++;break;
	case 'h':m_char_weight[34]++;break;
	case 'i':m_char_weight[35]++;break;
	case 'j':m_char_weight[36]++;break;
	case 'k':m_char_weight[37]++;break;
	case 'l':m_char_weight[38]++;break;
	case 'm':m_char_weight[39]++;break;
	case 'n':m_char_weight[40]++;break;
	case 'o':m_char_weight[41]++;break;
	case 'p':m_char_weight[42]++;break;
	case 'q':m_char_weight[43]++;break;
	case 'r':m_char_weight[44]++;break;
	case 's':m_char_weight[45]++;break;
	case 't':m_char_weight[46]++;break;
	case 'u':m_char_weight[47]++;break;
	case 'v':m_char_weight[48]++;break;
	case 'w':m_char_weight[49]++;break;
	case 'x':m_char_weight[50]++;break;
	case 'y':m_char_weight[51]++;break;
	case 'z':m_char_weight[52]++;break;
	case ',':m_char_weight[53]++;break;
	case '.':m_char_weight[54]++;break;
	case ':':m_char_weight[55]++;break;
	case '(':m_char_weight[56]++;break;
	case ')':m_char_weight[57]++;break;
	case '1':m_char_weight[58]++;break;
    case '2':m_char_weight[59]++;break;
	case '3':m_char_weight[60]++;break;
	case '4':m_char_weight[61]++;break;
	case '5':m_char_weight[62]++;break;
	case ';':m_char_weight[63]++;break;
	case '-':m_char_weight[64]++;break;
	case '%':m_char_weight[65]++;break;
	default:break;
	}
}

template<class W>
void HfmTree_T<W>::CreatHfmTree(void)
{
	ifstream in;
	in.open("text.txt");

	if (!in)
	{
		cerr<<"打开文件失败!"<<endl;
	}
	else
	{
		char e;
		while (in.get(e))
		{
			if (e!='\n')
				GetWeight(e);
		}
		vector<HfmTree_T<W> >m;
		BinaryTree_T<int>a,b,c,d;
		HfmTree_T<W>x,y,z;

		int i,j=0;
		for (i=0;i<66;i++)
		{
			if (m_char_weight[i]==0)
				j++;//计数 有多少个空的
			else
			{
				a.MakeTree(m_char_weight[i],b,c);
				z.m_weight=m_char_weight[i];
				z.m_tree=a;
				m.push_back(z);
				a=d;
			}
		}

		sort(m.begin(),m.end());

		vector<HfmTree_T<W> >::iterator p;
		for (i=1;i<66-j;i++)
		{
			p=m.begin();
			x=*p;
			m.erase(m.begin());
			p=m.begin();
			y=*p;
			m.erase(m.begin());

			a.MakeTree(x.m_weight+y.m_weight,x.m_tree,y.m_tree);
			z.m_weight=x.m_weight+y.m_weight;
			z.m_tree=a;
			m.push_back(z);
			a=d;
			sort(m.begin(),m.end());
		}

		p=m.begin();
		z=*p;
		m_tree=z.m_tree;
		m_weight=z.m_weight;
	}
}

template<class W>
HfmTree_T<W>& HfmTree_T<W>::operator =(const HfmTree_T<W> &rhs)
{
	if (this!=&rhs)
	{
		m_tree=rhs.m_tree;
		m_weight=rhs.m_weight;
	}

	return *this;
}

template<class W>
void HfmTree_T<W>::GenerateCode(void)
{
	GenerateCode(m_tree);
}

template<class W>
void HfmTree_T<W>::GenerateCode(BinaryTree_T<int> &p)
{
	char **c;
	char **m_code;
	int k=m_numbers;
	c=new char*[k];
	m_code=new char*[k];

	int i,j;
	for (i=0;i<k;i++)
	{
		c[i]=new char[k];
		m_code[i]=new char[k];
		for (j=0;j<k;j++)
		{
			c[i][j]='#';
			m_code[i][j]='#';
		}
	}

	int count=0,a=0,lev=0;
	TreeNode_T<int>*q=p.GetTreeNode();
	if (q!=NULL)
		GenerateCode(q,c,m_code,count,a,lev);

	for (i=0;i<k;i++)
		delete []c[i];
	delete []c;
	for (i=0;i<66;i++)
	{
		if (m_char_weight[i]!=0)
		{
			cout<<m_char[i]<<":";
			for (j=0;j<m_numbers;j++)
			{
				if (m_code[i][j]!='#')
					cout<<m_code[i][j];
			}
			cout<<endl;
		}
	}
	Code(m_code);

	for (i=0;i<k;i++)
		delete []m_code[i];
	delete []m_code;
}

template<class W>
void HfmTree_T<W>::GenerateCode(TreeNode_T<int>*ptr,char **c,
						char **&code,int &count,int k,int lev)
{
	if ((ptr->LeftChild()==NULL) && (ptr->RightChild()==NULL))
		for (int i=0;i<lev;i++)
		{
			code[GetNumber(ptr->Data())][i]=c[k][i];
		}
		else
		{
			int k1=++count;
			for (int j=0;j<lev;j++)
				c[k1][j]=c[k][j];
			c[k][lev]='0';
			c[k1][lev]='1';
			GenerateCode(ptr->LeftChild(),c,code,count,k,lev+1);
			GenerateCode(ptr->RightChild(),c,code,count,k1,lev+1);
		}
}

template<class W>
int HfmTree_T<W>::GetNumber(int x)
{
	for (int k=0;k<66;k++)
	{
		if (m_char_weight[k]==x)
			return k;
	}
	return 0;
}

template<class W>
int HfmTree_T<W>::GetNumber(char c)
{
	int k;
	for (k=0;k<66;k++)
	{
		if (m_char[k]==c)
			return k;
	}
	return 0;
}

template<class W>
void HfmTree_T<W>::Code(char **&code)
{
	ifstream in;
	in.open("text.txt");

	if (!in)
	{
		cerr<<"打开文件失败!"<<endl;
	}
	else
	{
		ofstream out;
		out.open("codefile.txt");

		if (!out)
		{
			cerr<<"打开文件失败!"<<endl;
		}
		else
		{
			int i,j;
			char c;
			while (in.get(c))
			{
				if (c!='\n')
				{
					i=GetNumber(c);
					for (j=0;code[i][j]!='#';j++)
						out<<code[i][j];
				}
			}
		}
	}
}

template<class W>
void HfmTree_T<W>::DeCode(void)
{
	ifstream in;
	in.open("codefile.txt");

	if (!in)
		cerr<<"打开文件失败!"<<endl;
	else
	{
		TreeNode_T<int>*p=m_tree.GetTreeNode();

		int j;
		char c;

		while (in.get(c))
		{
			if (c!='\n')
			{
				if (p->LeftChild()==NULL && p->RightChild()==NULL)
				{
					j=GetNumber(p->Data());
					cout<<m_char[j];
					p=m_tree.GetTreeNode();
				}
				if (c=='0')
					p=p->LeftChild();
				else
					p=p->RightChild();
			}
			else
				cout<<endl;
		}
	}
}
#endif