哈夫曼树构造及哈夫曼编码

mastertravels77 · 发表于 2023-2-19 13:33

前情提要

请为用于通信的电文中的字母进行赫夫曼编码。如各个字母在电文中出现的频率分别为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[5]; //节点值
int weight; //权重
int parent; //双亲节点
int lchild; //左孩子节点
int rchild; //右孩子节点
}HTNode;
typedef struct
{
char cd[N];//存放哈夫曼码
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[i].parent=ht[i].lchild=ht[i].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[k].parent==-1)//只在尚未构造二叉树的节点中查找
{
if(ht[k].weight<min1)//找权重最小的两个节点
{
min2=min1;rnode=lnode;//把min1的下标值给了min2,原左孩子的下标lnode给右孩子的下标rnode
min1=ht[k].weight;lnode=k;//把权重最小的下标赋给lnode
}
else if(ht[k].weight<min2)
{
min2=ht[k].weight;
rnode=k;//把权重第二最小的下标赋给rnode
}
}
ht[lnode].parent=i;ht[rnode].parent=i;//将当前权重最小的两个的双亲节点设为下标为i的节点
ht[i].weight=ht[lnode].weight+ht[rnode].weight;//下标为i的节点的权重为两个子女的权重和
ht[i].lchild=lnode;ht[i].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[i].parent;//获取输入的叶子节点的双亲节点下标
while(f!=-1)//循序直到树根节点，树根节点的双亲节点下标为-1
{
if(ht[f].lchild==c)//处理左孩子节点，判断当前双亲节点的左孩子是否是节点为c下标，是，就处理
hc.cd[hc.start--]='0';//hc.start--从当前节点开始标记0/1一直到根节点
else //处理右孩子，判断当前双亲节点的右孩子是否是节点为c下标，是，就处理
hc.cd[hc.start--]='1';
c=f;f=ht[f].parent;//c获取当前节点的下标，f获得双亲节点下标
}
hc.start++;//start指向哈夫曼编码最开始字符,最后一次循环产生作用
hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n)//输出哈夫曼编码
{
int i,k;
printf("输出哈夫曼编码：\n");
for(i=0;i<n;i++)
{
printf(" %s:\t",ht[i].data);
for(k=hcd[i].start;k<=n;k++)
{
printf("%c",hcd[i].cd[k]);
}
printf("\n");
}
}
void main()
{
int n=8,i;
HTNode ht[M];
HCode hcd[N];
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[i].data,str[i]);
ht[i].weight=fnum[i];
}
CreateHT(ht,n);
CreateHCode(ht,hcd,n);
DispHCode(ht,hcd,n);
}

复制代码

输出

		自动登录	找回密码
密码			立即注册

哈夫曼树构造及哈夫曼编码

本帖子中包含更多资源