【C++实验】哈夫曼树与哈夫曼编码实验

#include<iostream>
using namespace std;
class HFMtreeNode
{
	public:
		HFMtreeNode()
		{
			this->lchild=-1;
			this->rchild=-1;
			this->parent=-1;
			this->weight=0;
		}
		int lchild;
		int rchild;
		int weight;
		int parent;
};
class HuffCode
{
	public:
		HuffCode(int size)
		{
			this->bit=new int[size];
			this->start=size-1;
		}
		int *bit;//长度至少容下26个小写英文字母 
		int start;
};
bool isNumStr(string str)
{
	int n=str.length();
	bool isNum_str =true;  
	for(int i=0;i<n;i++)
	{
		if(str[i]-'0'<0||str[i]-'0'>9)
		{
			isNum_str=false;
			break;
		}
	}
	return isNum_str;
}
void func()
{
	int Hash [26][2];//记录输入字符串中每个字符的权重， 
	int hash=0;
	int temp[26][2];//按权重不为0的顺序排列Hash中的字符 和字符位置 
	int number=0;//统计总共出现的字符 
	for(int i=0;i<26;i++)
	{
		for(int j=0;j<2;j++)
		{
			Hash[i][j]=0;
		}
	}
	cout<<"请输入要进行被构建的字符串："; 
	string str,num_str;
	cin>>str;
	for(int i=0;i<str.length();i++)
	{
		if(Hash[str[i]-97][0]==0)
		{
			Hash[str[i]-97][1]=hash;
			hash++;
		}
		Hash[str[i]-97][0]+=1;
	}
	for(int i=0;i<26;i++)
	{
		if(Hash[i][0]!=0)
		{
			 cout<<char(i+97)<<"的权重为："<<Hash[i][0]<<endl;
			 temp[number][0]=Hash[i][0];
			 temp[number][1]=i;
			 number++;
		} 
	}
	HFMtreeNode *hfm=new HFMtreeNode[2*number-1];
	HuffCode **code=new HuffCode*[number];//字符编码 
	for(int i=0;i<number;i++)
	{
		hfm[i].weight=temp[i][0];
		code[i]=new HuffCode(number);
	}
	//开始构建哈夫曼树 
	for(int i=0;i<number-1;i++)
	{
		int x1=0,x2=0,m1=1000,m2=1000;
		for(int j=0;j<number+i;j++)
		{
			if(hfm[j].parent==-1&&hfm[j].weight<m1)
			{
				m2=m1;
				x2=x1;
				m1=hfm[j].weight;
				x1=j;
			}
			else if(hfm[j].parent==-1&&hfm[j].weight<m2)
			{
				m2=hfm[j].weight;
				x2=j;
			}
		}
		hfm[x2].parent=number+i;
		hfm[x1].parent=number+i;
		hfm[number+i].lchild=x1;
		hfm[number+i].rchild=x2;
		hfm[number+i].weight=hfm[x1].weight+hfm[x2].weight;
	}
	//哈夫曼树构建完成 
	
	//开始构建编码
	int p,c;
	for(int i=0;i<number;i++)//有几个字符构建几个编码 
	{
		c=i;
		p=hfm[c].parent;
		while(p!=-1)
		{
			if(hfm[p].lchild==c) code[i]->bit[code[i]->start]=0;
			else code[i]->bit[code[i]->start]=1;
			code[i]->start--;
			c=p;
			p=hfm[c].parent;
		}
		code[i]->start++;
	} 
	//编码构建结束 
	cout<<"编码前的字符串："<<str;
	cout<<endl<<"编码后："<<endl;
	for(int i=0;i<number;i++)
	{
		cout<<char(temp[i][1]+97)<<":";
		for(int j=code[i]->start;j<number;j++)
		{
			cout<<code[i]->bit[j];
		}
		cout<<endl;
	}
	//打印编码 
	cout<<"原字符串经过转换后：";
	for(int i=0;i<str.length();i++)
	{
		int n=Hash[str[i]-97][1];
		int m=code[n]->start;
		for(int j=m;j<number;j++)
		{
			cout<<code[n]->bit[j];
		}
		cout<<" ";
	}
	
	//将数字编码通过树转回字母，通过对hfm的遍历，hfm[i]表示的字符和temp[i]表示的字符相同，可通过temp[i][1]+97,来表示这个字符 
	cout<<endl<<"----------------------------------------"<<endl;
	cout<<"请输入需要被转译的数字串：";
	cin>>num_str;
	int n=num_str.length();
	//开始对字符串进行转译 
	//首先判断字符串输入的是不是数字串 
	while(!isNumStr(num_str))
	{
		cout<<"您输入的不是数字编码，请从新输入：";
		cin>>num_str;
	}
	
	//对数字编码进行处理
	HFMtreeNode h=hfm[2*number-2];
	int pos=-1;//记录下标 
	string result="";
	for(int i=0;i<n;i++)
	{
			if(num_str[i]-'0'==0)
			{
				pos=h.lchild;
				if(pos==-1) 
				{
					result="错误！";
					break;
				}
				h=hfm[pos];
			}
			else if(num_str[i]-'0'==1)
			{	
				pos=h.rchild;
				if(pos==-1)
				{
					result="错误！";
					break;
				}
				h=hfm[pos];
			}
			else
			{
				result="错误！";
				break;
			}
		if(pos>=0&&pos<number) 
		{
			result+=char(temp[pos][1]+97);
			h=hfm[2*number-2];
			pos=-1;
		}
	} 
	if(h.parent!=-1) 
	{
		result="错误！";
	}
	cout<<"数字转译后的字符串为：";
	cout<<result;
}

int main()
{
	func();
	
}