#include
#include
#include
#define MAX 1000
using namespace std;
typedef struct{ /* 定义哈夫曼编码的结构数组 /
char data;
int weight; / 定义权值 /
int parent;
int lchild;
int rchild;
int num;
}huffmannode;
typedef struct{ / 定义保存哈夫曼结构体 /
char bits[50];
int start;
}huffmancode;
int main()
{
huffmannode ht[100]; / 定义储存权值的空间 /
huffmancode cd[100];
char string[100]; / 定义数组存储空间 /
char hcd[100];
int i,j,x,y,s1,s2,m1,m2,num,c,f,k;
cout<<"请输入长度 n= "; / 输入字符的个数 /
cin>>num;
cout<<"==============================="<<endl;
for(i=0;i<num;i++)
{
getchar(); / 获得输入的字符 /
cout<<"输入字符: ";
cin>>ht[i].data; / 输入字符函数 /
cout<<"输入权值: ";
cin>>ht[i].weight;
}
cout<<"============================="<<endl;
for(i=0;i<2*num-1;i++)
{
ht[i].parent=ht[i].lchild=ht[i].rchild=-1; / 初始化父结点,左右子结点 /
}
for (i=num;i<2*num-1;i++)
{
s1=s2=0; / 初始化变量 /
m1=m2=MAX;
for (j=0;j<i;j++)
{
if (ht[j].weight<m1 &&ht[j].parent==-1) / 寻找无父结点的最小值 /
{
m2=m1;
s2=s1;
m1=ht[j].weight;
s1=j; / 寻找当前最小值 /
}
else if(ht[j].weight<m2 &&ht[j].parent==-1) / 寻找无父结点的次小值 /
{
m2=ht[j].weight;
s2=j;
} / 寻找次小值 /
}
ht[s1].parent=i; / s1的父结点为i /
ht[s2].parent=i;
ht[i].weight=m1+m2; / 最小值的权值相加为i的权值 /
ht[i].lchild=s1; / i的左子为s1 /
ht[i].rchild=s2; / i的右子为s2 /
}
for(i=0;i<num;i++)
{
cd[i].start=num;
x=i;
y=ht[x].parent; / 记录父结点 /
while (y!=-1)
{
if (ht[y].lchild==x)
cd[i].bits[cd[i].start]='0'; / 给字符赋0值 /
else
cd[i].bits[cd[i].start]='1'; / 给字符赋1值 /
cd[i].start--;
x=y;
y=ht[y].parent;
}
}
cout<<"字符"<<"->"<<"权值:"<<endl;
for (i=0;i<num;i++)
{
cout<<ht[i].data; / 输出字符 /
for(j=cd[i].start;j<=num;j++)
{
cout<<cd[i].bits[j]; / 输出字符的01代码 */
}
cout<<endl;
}
cout<<"============================="<<endl;
cout<<"请输入信息: "<<endl;
cin>>string; /* 输入字符串 */
for(i=0;string[i]!='\0';i++)
{
for(c=0;c<=num;c++)
if(string[i]==ht[c].data) /* 寻找与输入字符相匹配的字母 */
{
for(j=cd[c].start;j<=num;j++)
cout<<cd[c].bits[j]; /* 输出字母代码 */
break;
}
}
cout<<"============================="<<endl;
cout<<"请输入密码:";
cin>>hcd; /* 输入0、1代码 */
f=2*num-2;
for(i=0;hcd[i]!='\0';i++)
{
if(hcd[i]=='0') /* 判断输入为0,寻找左子 */
f=ht[f].lchild;
else if(hcd[i]=='1')
f=ht[f].rchild; /* 判断输入为1,寻找右子 */
if(f<num)
{
cout<<ht[f].data; /* 输出字符串 */
f=2*num-2;
}
}
cout<<endl;
return 0;
}