问题描述：
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的u信息收发编写一个哈夫曼码的编/译码系统。
基本要求：
（1）接收原始数据（电文）：从终端输入电文（电文为一个字符串，假设仅由26个小写英文字母构成）。 （2）编码：利用已建好的哈夫曼树，对电文进行编码。
（3）打印编码规则：即字符与编码的一一对应关系。
（4）打印显示电文以及该电文对应的哈夫曼编码。
（5）接收原始数据（哈夫曼编码）：从终端输入一串哈二进制哈夫曼编码（由
0和1构成）。
（6）译码：利用已建好的哈夫曼树对该二进制编码进行译码。
（7）打印译码内容：将译码结果显示在终端上。
直接上代码，大家可以自己运行测试。
代码语言：javascript复制#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();
}
