#include <iostream.h>
#include <string.h>
#include <stdio.h>
const int n=8;
const int m=2*n-1;
struct tree
{
char message;//字符
int weight;//权重
int parent,lchild,rchild;//父结点，左孩子结点，右孩子结点
};
void Initialization(tree [m]);
void Encoding(tree[],char [n][n]);
void Decoding(char [1000],char [n][n],tree[],char [1000]);
void Select(tree[],int &,int &,int);
void Print(tree[],char [n][n],char[1000]);
void Initialization(tree huffmancode[m] )
{
int flag=0;
int i;
while (flag==0)
{
char words[100];
cout<<"请输入一段英文（出现的字符种数应为"<<n<<"个）"<<endl;
gets (words);//接受英文
int t=0;
for(i=0;words[i]!='\0';i++)//对输入的一段英文中的每个字符统计其权值
{
int k=-1;
for(int j=0;j<t;j++)//判断该字符前面是否出现
{
if(huffmancode[j].message==words[i])//如果有，则找到该结点
{
k=j;
break;
}
}
if(k==-1)//如果没有，且合法，则创建新结点
{
if(t==n)
{
cout<<"你输入的字符种数超过上限，以非法字符出现前建立哈夫曼树"<<endl;
break;
}
huffmancode[t].message=words[i];
huffmancode[t].weight++;
t++;
}
else huffmancode[k].weight++;
}
if(t<n) cout<<"请重新输入"<<endl;
else flag=1;
}
/* for(int i=0;i<n;i++)
{
cin>>huffmancode[i].message>>huffmancode[i].weight ;
}*/
int s1;
int s2;
for(i=n;i<m;i++)//建立哈夫曼树
{
s1=0;s2=1;
Select(huffmancode,s1,s2,i);
huffmancode[s1].parent=i;
huffmancode[s2].parent=i;
huffmancode[i].lchild=s1;
huffmancode[i].rchild=s2;
huffmancode[i].weight=huffmancode[s1].weight+huffmancode[s2].weight;
}
}
void Encoding(tree ht[],char hc[n][n])//利用已建好的哈夫曼树，对每个字符进行编码
{
char cd[n];
cd[n-1]='\0';//编码结束符
int c;
int f;
int start;
for (int i=0;i<n;i++)//逐个字符求哈夫曼编码
{
start=n-1;//编码结束符位置
for(c=i,f=ht[i].parent;f!=m;c=f,f=ht[f].parent)//从叶子到根逆向求编码
{
if(ht[f].lchild==c)
{
cd[--start]='0';//左孩子为零
}
else
{
cd[--start]='1';//右孩子为一
}
}
strcpy(hc[i],&cd[start]);//从cd复制编码到hc
}
}
void Decoding(char codes[1000],char hc[n][n],tree huffmancode[m],char words[1000])
{//利用已建好的每个编码，对输入的一个由0、1组成的序列进行译码
int flag;
int i;
int j=0;
while(strlen(codes)!=0)//密文长度不为零时，继续破译
{
flag=0;
for(i=0;i<n;i++)//寻找各个哈夫曼编码
{
if(strncmp(codes,hc[i],strlen(hc[i]))==0)//判断是否与哈夫曼编码相同
{
strcpy(codes,&codes[strlen(hc[i])]);//相同的话，删除该部分
words[j++]=huffmancode[i].message;
flag=1;
break;
}
}
if(flag==0)
{
cout<<"抱歉！该密文无法破译.";
break;
}
}
if(j==0)
{words[j]=' ';j++;}
words[j]='\0';
}
void Select(tree huffmancode[],int & s1,int & s2,int i)
{//在小于i的哈夫曼树中选择parent为m，且weight最小的两个节点，其序号分别为s1和s2
while((huffmancode[s1].parent!=(m))||(huffmancode[s2].parent!=(m)))
{//找到俩个父结点为空的结点
if(huffmancode[s1].parent!=(m)) s1++;
if(huffmancode[s2].parent!=(m)) s2++;
if(s1==s2) s2++;
}
for(int j=0;j<i;j++)
{
if(huffmancode[j].weight<huffmancode[s1].weight&&huffmancode[j].parent==m&&s2!=j)
s1=j;
else if(huffmancode[j].weight<huffmancode[s2].weight&&huffmancode[j].parent==m&&s1!=j)
s2=j;
}
}
void Print(tree ht[],char hc[n][n],char words[1000])//将每个字符编的哈夫曼码和译码结果显示在终端上
{
int i;
cout<<"每个字符的哈夫曼编码是："<<endl;
for(i=0;i<n;i++)
cout<<ht[i].message<<":"<<hc[i]<<endl;
cout<<"译码结果是："<<endl;
puts(words);
}
int main()
{
tree huffmancode[m];
for(int i=0;i<m;i++)
{//初始化哈夫曼树
huffmancode[i].weight=0;
huffmancode[i].message=' ';
huffmancode[i].lchild=m;
huffmancode[i].parent=m;
huffmancode[i].rchild=m;
}
Initialization(&huffmancode[0]);
char hc[n][n];
Encoding(huffmancode,hc);
char codes[1000];
cout<<"请输入密文"<<endl;
gets(codes);
char words[1000];
Decoding(codes,hc,huffmancode,words);
Print(huffmancode,hc,words);
return 0;
}
评论3