1、实验名称:霍夫曼编码
2、实验环境
软件环境:Windows 2000,Microsoft Visual C++6.0
硬件环境:P4,2.4GHz,256内存,IBM-PC及兼容机
3、实验目的
掌握霍夫曼编码、译码原理,并能够通过程序模拟其编码、译码功能。
4、实验原理
1、消息按其出现的概率由大到小地排成一个概率序列;
2、把概率最小两个消息分成一组,其中一个消息编为0,另一个编为1,然后求其概率和,并把这个新概率与其他尚未处理过的概率重新按概率由大到小排成一个新的概率序列;
3、重复步骤,直到所有概率都已联合处理完为止。
5、实验过程与实验结果
源程序:
#include
#include
using namespace std;
#include
typedef struct{//霍夫曼树的结构体
char ch;
double weight; //权值,此处为概率
int parent,lchild,rchild;
}htnode,*hfmtree;
typedef char **hfmcode;
/*****************************全局变量*****************************/
hfmtree HT;
hfmcode HC;
int n=0;//霍夫曼树叶节点个数
int m=0;//霍夫曼树所有节点个数
int *code_length;//用于记录每个消息字符的码长
/*****************************霍夫曼编码模块*****************************/
//对输入的字符进行检验
int Input_Char_Check()
{
int flag=1;
int j;
for(int i=1;i0&&HT[i].weight<1))//概率越界
{
flag=1;
return flag;
}
else{
sum+=HT[i].weight;
continue;
}
}
if(sum>1)//概率之和超过1
{
flag=2;
}
return flag;
}
void Select(int a,int *p1,int *p2)
/*Select函数,选出HT树到a为止,权值最小和次小且parent为0的2个节点*/
{
int i,j,x,y;
for(j=1;j<=a;++j){
if(HT[j].parent==0){
x=j;
break;
}
}
for(i=j+1;i<=a;++i){
if(HT[i].weighty){
*p1=y;
*p2=x;
}
else
{
*p1=x;
*p2=y;
}
}
/*初始化n个叶子节点及其余节点*/
void Init_htnode()
{
int i;
char temp_ch;
double temp_w;
I: cout<<"请输入信源发出的消息字符个数:";
cin>>n;
if(sizeof(n)!=sizeof(int)||n<=1)//若输入的不是整数,则报错
{
cout<<"您输入的数据有误,程序终止!"<>temp_ch;
printf("请输入第%d个字符对应的概率:",i);
cin>>temp_w;
HT[i].ch=temp_ch;
HT[i].weight=temp_w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
int flag1=Input_Char_Check();//检测输入的字符是否重复
int flag2=Input_Weight_Check();//检测输入的概率是否越界
if(!flag1)
{
cout<<"出现相同字符,输入错误,请重新输入!"<
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
模块*****************************/
//求平均编码长度
double Ave_Code_Length()
{
double Ave_L=0.0;
for(int i=1;i<=n;i++)
Ave_L+=code_length[i]*HT[i].weight;
return Ave_L;
}
//求信源熵
double To_Get_H()
{
double H=0.0;
for(int i=1;i<=n;i++)
H+=-1*HT[i].weight*log(HT[i].weight)/log(2);
return H;
}
//求编码效率
double To_Get_Code_Efficiency()
{
double H2,H,Ave_L;
H=To_Get_H();
Ave_L=Ave_Code_Length();
H2=H/Ave_L;
return H2;
}
//分析结果输出
void Output()
{
double H2,H,Ave_L;
H=To_Get_H();
Ave_L=Ave_Code_Length();
H2=To_Get_Code_Efficiency();
cout<<"霍夫曼编码结果如下:(消息字符——码长——码字)"<"<"<
本文档为【霍夫曼编码实验报告(C )】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。