#include <stdio.h>
#define max 500//定义存储的最大结点数
typedef struct //定义结点
{
char data;//结点值
int weight;//权重
int parent;//父结点
int left;//左孩子结点
int right;//右孩子结点
}huffnode;
typedef struct
{
char cd[max];
int start;
}huffcode;
char elem[1000];
char input[1000];
int weight[1000]={0};
int m=0;
int find_char(char a[],char c,int n)//在数组中查找某一个元素,返回其位置
{
int i;
for(i=0;i<=n;i++)
{
if(a[i]==c) return i;
}
return -1;
}
int get_elem_weight()
//从输入中得到除空格和回车之外的所有字符类型及其权值
{
int i,n=-1;
for(i=0;i<100;i++)
elem[i]=' ';
char c;
while(1)
{
c=getchar();
input[m++]=c;
if(c==10) break;
else if(c!=' ')
{
if(find_char(elem,c,n)==-1)
{ n++;
elem[n]=c;
weight[n]=1;
}
else weight[find_char(elem,c,n)]+=1;
}
}
printf("除空格和回车之外各字符的出现频率如下:\n");
//打印字符极其权值
for(i=0;i<=n;i++)
{
printf("%c %d",elem[i],weight[i]);
printf("\n");
}
return n+1;
}
main()
{
huffnode ht[2*max];
huffcode htd[max],d;
int i,k,f,l,r,n,c,m1,m2,j;
printf("请输入一个字符串,以回车结束\n");
n=get_elem_weight();
for(i=1;i<=n;i++)
{
ht[i].data =elem[i-1];
ht[i].weight =weight[i-1];
}
for(i=1;i<=2*n-1;i++)
ht[i].parent =ht[i].left =ht[i].right =0;//叶结点初始化
for(i=n+1;i<=2*n-1;i++)
{
m1=m2=32767;
l=r=0;
for(k=1;k<=i-1;k++)
if(ht[k].parent ==0)
//寻找当前结点中权值最小的两个结点
if(ht[k].weight <m1)
{
m2=m1;
r=l;
m1=ht[k].weight ;
l=k;
}
else if(ht[k].weight <m2)
{
m2=ht[k].weight ;
r=k;
}
ht[l].parent =i;//建立父结点信息
ht[r].parent =i;
ht[i].weight =ht[l].weight +ht[r].weight ;
ht[i].left =l;
ht[i].right =r;
}
for(i=1;i<=n;i++)//由建立的结点生成Huffman编码
{
d.start =n+1;
c=i;
f=ht[i].parent ;
while(f!=0)
{
if(ht[f].left ==c)
d.cd[--d.start ]='0';
else
d.cd [--d.start ]='1';
c=f;
f=ht[f].parent ;
}
htd[i]=d;
}
printf("输出编码\n");
for(i=1;i<=n;i++)
{
printf("%c:",ht[i].data );
for(k=htd[i].start ;k<=n;k++)
printf("%c",htd[i].cd[k]);
printf("\n");
}
printf("你所输入的字符串为\n");
for(i=0;i<m-1;i++) printf("%c",input[i]);
printf("\n");
printf("经过编码之后\n");//打印编码后结果
for(i=0;i<m-1;i++)
{
if(input[i]!=' ')
{
for(k=1;k<=n;k++)
if(ht[k].data ==input[i]) break;
for(j=htd[k].start ;j<=n;j++)
printf("%c",htd[k].cd [j]);
}
else printf("%c",input[i]);
}
printf("\n");
}