#include<stdio.h>
#include<stdlib.h>
#define MAXLEAF 50 /*叶子数最大值*/
#define MAXNODE 2*MAXLEAF-1 //最大节点数目
#define MAXCODE 30 //最大编码位数
#define MAXVALUE 1000 //最大权值
typedef struct node
{ /*节点类型定义*/
int weight;
char letter;
int parent;
int lchild;
int rchild;
} huffnode;
typedef struct code
{ /*编码类型定义*/
int bits[MAXCODE];
int start;
} huffcode;
void HuffManTree(huffnode a[],int n)
{ /*构造哈夫曼树*/
int i,j,m1,m2,x1,x2;
for(i=0;i<n-1;i++)
{
m1=m2=MAXVALUE;
x1=x2=0;
for(j=0;j<n+i;j++)
{ /*找出最小的两个权值节点*/
if(a[j].parent==-1&&a[j].weight<m1)
{
m2=m1;
x2=x1;
m1=a[j].weight;
x1=j;
}
else if(a[j].parent==-1&&a[j].weight<m2)
{
m2=a[j].weight;
x2=j;
}
}
a[x1].parent=n+i;
a[x2].parent=n+i;
a[n+i].lchild=x1;
a[n+i].rchild=x2;
a[n+i].weight=a[x1].weight+a[x2].weight;
}
}
void HuffManCode(huffnode a[],int n)
{ /*哈夫曼编码*/
int i,j,c,p;
huffcode cd ,code[MAXNODE];
HuffManTree(a,n);
for(i=0;i<n;i++)
{
cd.start=n;
c=i;
p=a[c].parent;
while(p!=-1)
{
if(a[p].lchild==c)//左孩子为0
cd.bits[cd.start]=0;
else
cd.bits[cd.start]=1;//右孩子为1
cd.start--;
c=p;
p=a[p].parent;
}
cd.start++;
for(j=cd.start;j<=n;j++)
code[i].bits[j]=cd.bits[j];
code[i].start=cd.start;
}
puts("\n输出哈夫曼编码:");
puts("字符 权值 哈夫曼编码");
for(i=0;i<n;i++)
{ printf("%c ",a[i].letter);
printf(" %d ",a[i].weight);
for(j=code[i].start;j<=n;j++)
printf("%d",code[i].bits[j]);
printf("\n");
}
}
void Error(char *str)
{
printf("error:%s",str);
puts("请按任意键返回");
getchar();
exit(0);
}
int main()
{
int i,j,n;
huffnode huff_node[MAXNODE];
huffcode huff_code[MAXNODE];
puts("请输入叶子节点数目");
scanf("%d",&n);
if(n<0||n>MAXLEAF)
Error("输入叶子节点数目越界");
for(i=0;i<2*n-1;i++)
{
huff_node[i].weight=0;
huff_node[i].rchild=-1;
huff_node[i].parent=-1;
huff_node[i].lchild=-1;
huff_node[i].letter='\0';
}
printf("\n请输入%d个叶子节点的字母和权值\n",n);
getchar();
for(i=0;i<n;i++)
{ puts("请输入字母和权值");
scanf("%c%d",&huff_node[i].letter,&huff_node[i].weight);
getchar();
}
puts("======================================");
printf("字符 权值\n");
for(i=0;i<n;i++)
{
printf("%c %4d \n",huff_node[i].letter,huff_node[i].weight);
}
puts("======================================");
HuffManCode(huff_node,n);
}