附：程序代码如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define MaxValue 10000
#define MaxBit 10
#define MaxN 100
typedef struct /*哈夫曼树的结点结构*/
{
double weight; /*权值*/
int flag; /*标记*/
int parent; /*双亲结点下标*/
int leftChild; /*左孩子下标*/
int rightChild; /*右孩子下标*/
}HaffNode;
typedef struct/*存放哈夫曼编码的数组元素结构*/
{
int bit[MaxN]; /*数组*/
int start; /*编码的起始下标*/
double weight; /*字符的权值*/
}Code;
void Haffman(double weight[], int n, HaffNode haffTree[])/*建立叶结点个数为n权值数组为weight的哈夫曼树haffTree*/
{
int i,j,x1,x2;
double m1,m2;
for(i=0;i<2*n-1;i++)
{
if(i<n)haffTree[i].weight=weight[i];
else haffTree[i].weight=0;
haffTree[i].parent=-1; haffTree[i].flag= 0;
haffTree[i].leftChild=-1; haffTree[i].rightChild=-1;
}
for(i=0;i<n-1;i++)
{
m1=m2=MaxValue; x1=x2=0;
for(j=0;j<n+i;j++)
{
if(haffTree[j].weight<m1&&haffTree[j].flag==0)
{
m2=m1; x2=x1;
m1=haffTree[j].weight; x1=j;
}
else if(haffTree[j].weight<m2&&haffTree[j].flag==0)
{ m2=haffTree[j].weight; x2=j;}
}
haffTree[x1].parent=n+i; haffTree[x2].parent=n+i;
haffTree[x1].flag=1; haffTree[x2].flag=1;
haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight;
haffTree[n+i].leftChild=x1; haffTree[n+i].rightChild=x2;
}
}
void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[])
{
Code *cd=(Code*)malloc(sizeof(Code));
int i,j,child,parent;
for(i=0;i<n;i++)
{
cd->start=n-1; cd->weight=haffTree[i].weight;
child=i; parent=haffTree[child].parent;
while(parent != -1)
{
if(haffTree[parent].leftChild==child) cd->bit[cd->start]=0;
else
cd->bit[cd->start]=1;
cd->start--; child=parent;
parent=haffTree[child].parent;
}
for(j=cd->start+1;j<n;j++)
haffCode[i].bit[j]=cd->bit[j];
haffCode[i].start=cd->start+1; haffCode[i].weight=cd->weight;
}
}
void main(void)
{
int i,j,n;
double weight[MaxN];
typedef struct
{
char ch;
double weight;
}CodeWeight;
printf("请输入信源符号个数:\n");
scanf("%d",&n);
if(n>MaxN)
{
printf("给出的n越界,修改MaxN值!\n");
exit(0);
}
HaffNode *myHaffTree=(HaffNode*)malloc(sizeof(HaffNode)*(2*n-1));
Code *myHaffCode=(Code*)malloc(sizeof(Code)*n);
CodeWeight *myfuhao=(CodeWeight*)malloc(sizeof(CodeWeight)*n);
printf("请输入%d个信源符号:\n",n);
for(i=0;i<=n;i++)
scanf("%c",&myfuhao[i].ch);
printf("请输入对应信源符号的权重:\n");
for(i=0;i<n;i++)
scanf("%d",&myfuhao[i].weight);
for(i=0;i<n;i++)
weight[i]=myfuhao[i].weight;
Haffman(weight,n,myHaffTree);
HaffmanCode(myHaffTree,n,myHaffCode);
for(i=0;i<n;i++)
{
printf("%c-----Weight=%d Code = ",myfuhao[i+1].ch,myHaffCode[i].weight);
for(j=myHaffCode[i].start;j<n;j++)
printf("%d", myHaffCode[i].bit[j]);
printf("\n");
}
}
