#include
#include /* 数组头文件 /
#include
#define MAX 999 / 定义长度 /
typedef struct{ / 定义哈夫曼编码的结构数组 /
char data;
int weight; / 定义权值 /
int parent;
int lchild;
int rchild;
}huffmannode;
typedef struct{ / 定义保存哈夫曼结构体 /
char bits[50];
int start;
}huffmancode ;
void main()
{
huffmannode ht[100]; / 定义储存权值的空间 /
huffmancode cd[100];
char string[100]; / 定义数组存储空间 /
char hcd[100];
int i,j,x,y,s1,s2,m1,m2,n,c,f,k;
printf("please input the n ="); / 输入字符的个数 /
scanf("%d",&n);
printf("\n============================\n");
for(i=0;i<n;i++)
{
getchar(); / 获得输入的字符 /
printf("please input the value :");
scanf("%c",&ht[i].data); / 输入字符函数 /
printf("please input the weight:\n");
scanf("%d",&ht[i].weight);
}
printf("\n=============================\n");
for(i=0;i<2*n-1;i++)
{
ht[i].parent=ht[i].lchild=ht[i].rchild=-1; / 初始化父结点，左右子结点 /
}
for (i=n;i<2*n-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<n;i++)
{
cd[i].start=n;
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;
}
}
printf("\cout the huffmancode:\n");
for (i=0;i<n;i++)
{
printf("%c:",ht[i].data); / 输出字符 /
for(j=cd[i].start;j<=n;j++){
printf("%c",cd[i].bits[j]); / 输出字符的01代码 /
}
printf("\n");
}
printf("\n=============================\n");
printf("\n Please input the message:\n");
scanf("%s",string); / 输入字符串 /
for(i=0;string[i]!='0';i++)
{
for(c=0;c<=n;c++)
if(string[i]==ht[c].data) / 寻找与输入字符相匹配的字母 /
{
for(j=cd[c].start;j<=n;j++)
printf("%c",cd[c].bits[j]); / 输出字母代码 /
break;
}
}
printf("\n=============================\n");
printf("Please input the HuffmanCode:\n");
scanf("%s",hcd); / 输入0、1代码 /
f=2*n-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<n)
{
printf("%c",ht[f].data); / 输出字符串 */
f=2*n-2;
}
}
printf("\n");
getch();
}
