哈夫曼树构造及哈夫曼编码
前情提要请为用于通信的电文中的字母进行赫夫曼编码。如各个字母在电文中出现的频率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11。试为这8个字母设计哈夫曼编码。
通信的电文中的字母一般是a,b,c,d,e,f,g,h
根据其出现的概率可设8个字符的权值为：w=（5，29，7，8，14，23，3，11）
将树的左分支标记为0，右分支标记为1，便得到其哈夫曼编码表
代码函数
void CreateHT(HTNode ht[],int n);//构造哈夫曼树
void CreateHCode(HTNode ht[],HCode hcd[],int n);//构造哈夫曼编码
void DispHCode(HTNode ht[],HCode hcd[],int n);//输出哈夫曼编码
代码实现
#include<stdio.h>
#include<string.h>
#define N 50 //叶子节点数
#define M 2*N-1 //树中节点总数
typedef struct
{
char data; //节点值
int weight; //权重
int parent;//双亲节点
int lchild;//左孩子节点
int rchild;//右孩子节点
}HTNode;
typedef struct
{
char cd;//存放哈夫曼码
int start;
}HCode;
void CreateHT(HTNode ht[],int n);//构造哈夫曼树
void CreateHCode(HTNode ht[],HCode hcd[],int n);//构造哈夫曼编码
void DispHCode(HTNode ht[],HCode hcd[],int n);//输出哈夫曼编码
void CreateHT(HTNode ht[],int n)//构造哈夫曼树
{
int i,k,lnode,rnode;
int min1,min2;//设置权重最小的两个节点
for(i=0;i<2*n-1;i++)//所有节点的相关域设置初始值为-1
{
ht.parent=ht.lchild=ht.rchild=-1;
}
for(i=n;i<2*n-1;i++)//构造哈夫曼树
{ //n前面的空间给输入的值，树的其他节点给算出来的权重和
min1=min2=32767;//min1为第一个最小的权重，min2为第二个最小的权重
lnode=rnode=-1;//lnode和rnode为最小权重的两个节点位置
for(k=0;k<=i-1;k++)
if(ht.parent==-1)//只在尚未构造二叉树的节点中查找
{
if(ht.weight<min1)//找权重最小的两个节点
{
min2=min1;rnode=lnode;//把min1的下标值给了min2,原左孩子的下标lnode给右孩子的下标rnode
min1=ht.weight;lnode=k;//把权重最小的下标赋给lnode
}
else if(ht.weight<min2)
{
min2=ht.weight;
rnode=k;//把权重第二最小的下标赋给rnode
}
}
ht.parent=i;ht.parent=i;//将当前权重最小的两个的双亲节点设为下标为i的节点
ht.weight=ht.weight+ht.weight;//下标为i的节点的权重为两个子女的权重和
ht.lchild=lnode;ht.rchild=rnode;//设置下标为i的节点的孩子为下标为lnode和rnode
//注意，设置为孩子的双亲，还要设置双亲的孩子
}
}
void CreateHCode(HTNode ht[],HCode hcd[],int n)//构造哈夫曼编码
{
int i,f,c;
HCode hc;
for(i=0;i<n;i++)//根据哈夫曼树求哈夫曼编码
{
hc.start=n;c=i;//c获取当前节点的下标
f=ht.parent;//获取输入的叶子节点的双亲节点下标
while(f!=-1)//循序直到树根节点，树根节点的双亲节点下标为-1
{
if(ht.lchild==c)//处理左孩子节点，判断当前双亲节点的左孩子是否是节点为c下标，是，就处理
hc.cd='0';//hc.start--从当前节点开始标记0/1一直到根节点
else //处理右孩子，判断当前双亲节点的右孩子是否是节点为c下标，是，就处理
hc.cd='1';
c=f;f=ht.parent;//c获取当前节点的下标，f获得双亲节点下标
}
hc.start++;//start指向哈夫曼编码最开始字符,最后一次循环产生作用
hcd=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n)//输出哈夫曼编码
{
int i,k;
printf("输出哈夫曼编码：\n");
for(i=0;i<n;i++)
{
printf(" %s:\t",ht.data);
for(k=hcd.start;k<=n;k++)
{
printf("%c",hcd.cd);
}
printf("\n");
}
}
void main()
{
int n=8,i;
HTNode ht;
HCode hcd;
char *str[]={"a","b","c","d","e","f","g","h"};
int fnum[]={5,9,7,8,14,23,3,11};
for(i=0;i<n;i++)
{
strcpy(ht.data,str);
ht.weight=fnum;
}
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
}
输出
页:
[1]