C++实现哈夫曼编码完整代码Word下载.doc
- 文档编号:3700381
- 上传时间:2023-05-02
- 格式:DOC
- 页数:10
- 大小:63.50KB
C++实现哈夫曼编码完整代码Word下载.doc
《C++实现哈夫曼编码完整代码Word下载.doc》由会员分享,可在线阅读,更多相关《C++实现哈夫曼编码完整代码Word下载.doc(10页珍藏版)》请在冰点文库上搜索。
if(HT[j].ch==HT[i].ch)
flag=0;
break;
}
returnflag;
//对输入的概率进行检测
intInput_Weight_Check(){
intflag=0;
doublesum=0.0;
for(inti=1;
i++) {
if(!
(HT[i].weight>
0&
HT[i].weight<
1))//概率越界
{ flag=1;
returnflag;
}
else{ sum+=HT[i].weight;
continue;
}
}
if(sum>
1)//概率之和超过1
{
flag=2;
returnflag;
voidSelect(inta,int*p1,int*p2)/*Select函数,选出HT树到a为止,权值最小和次小且parent为0的2个节点*/
inti,j,x,y;
for(j=1;
=a;
++j)
if(HT[j].parent==0)
{
x=j;
break;
for(i=j+1;
++i)
{
if(HT[i].weight<
HT[x].weight&
HT[i].parent==0)
{
x=i;
//选出权值最小的节点
++j)
if(HT[j].parent==0&
x!
=j)
{
y=j;
HT[y].weight&
HT[i].parent==0&
=i)
y=i;
//选出权值次小的节点
if(x>
y)
{
*p1=y;
*p2=x;
else
*p1=x;
*p2=y;
}/*初始化n个叶子节点及其余节点*/
voidInit_htnode()
{
inti;
chartemp_ch;
doubletemp_w;
I:
cout<
<
"
请输入信源发出的消息字符个数:
;
cin>
>
n;
if(sizeof(n)!
=sizeof(int)||n<
=1)//若输入的不是整数,则报错
cout<
您输入的数据有误,程序终止!
endl;
exit(0);
code_length=newint[n+1];
for(i=1;
code_length[i]=0;
//初始化码长为0
m=2*n-1;
HT=(hfmtree)malloc((m+1)*sizeof(htnode));
printf("
请输入字符信息,,字符对应的概率:
);
++i)//初始化n个叶子结点
// printf("
请输入第%d个字符信息:
i);
cin>
temp_ch;
请输入第%d个字符对应的概率:
temp_w;
HT[i].ch=temp_ch;
HT[i].weight=temp_w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
} intflag1=Input_Char_Check();
//检测输入的字符是否重复
intflag2=Input_Weight_Check();
//检测输入的概率是否越界
if(!
flag1)
出现相同字符,输入错误,请重新输入!
gotoI;
if(flag2==1)
概率越界,输入错误,请重新输入!
if(flag2==2)
概率之和超过1,输入错误,请重新输入!
for(;
=m;
++i)//初始化其余的结点
HT[i].ch='
*'
//用*表示新生成根节点的字符域
HT[i].weight=0;
}//建立霍夫曼树
voidCreate_hfmtree()
intp1,p2;
//用于记录权值最小及次小节点的下标
for(i=n+1;
++i)//建立霍夫曼树
Select(i-1,&
p1,&
p2);
HT[p1].parent=i;
HT[p2].parent=i;
HT[i].lchild=p1;
HT[i].rchild=p2;
HT[i].weight=HT[p1].weight+HT[p2].weight;
voidHfm_coding()//求出n个字符的霍夫曼编码HC及码长
inti,start;
intc;
//当前字符下标
intf;
//当前字符的父节点下标
char*cd;
HC=(hfmcode)malloc((n+1)*sizeof(char*));
cd=(char*)malloc(n*sizeof(char));
cd[n-1]='
\0'
++i)//给n个字符编码
start=n-1;
for(c=i,f=HT[i].parent;
f!
=0;
c=f,f=HT[f].parent)
if(HT[f].lchild==c)
{
cd[--start]='
0'
}
else
{
1'
}
code_length[i]+=1;
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&
cd[start]);
free(cd);
}//初始化
/*功能:
从终端读入字符集大小n,以及n个字符和n个权值,建立霍夫曼树,并将它存于文件hfmTree中。
*/
intInitialization()
Init_htnode();
Create_hfmtree();
Hfm_coding();
return0;
/*****************************编码效率分析模块*****************************///求平均编码长度
doubleAve_Code_Length()
doubleAve_L=0.0;
Ave_L+=code_length[i]*HT[i].weight;
returnAve_L;
}//求信源熵
doubleTo_Get_H()
doubleH=0.0;
i++)
H+=-1*HT[i].weight*log(HT[i].weight)/log
(2);
returnH;
}//求编码效率
doubleTo_Get_Code_Efficiency()
doubleH2,H,Ave_L;
H=To_Get_H();
Ave_L=Ave_Code_Length();
H2=H/Ave_L;
returnH2;
}//分析结果输出
voidOutput()
H2=To_Get_Code_Efficiency();
霍夫曼编码结果如下:
(消息字符--码长--码字)"
HT[i].ch<
-->
code_length[i]<
HC[i]<
平均编码长度Ave_L=L1*p1+L2*p2+...+Ln*pn="
Ave_L<
(码元/消息)"
信源熵H=-(p1*log(p1)+p2*log(p2)+...+pn*log(pn))/log
(2)="
H<
(bit/消息)"
码元熵H2=H/Ave_L="
H2<
(bit/码元)"
编码效率E=(H2/H2max)*100%="
H2*100<
%"
}/*****************************编码模块*****************************/
//字符串合理性检测
intMessage_Str_Check(stringtemp)
intflag=1;
//先假设输入的消息串不含非法字符
for(inti=0;
temp[i]!
='
for(j=1;
j++)
if(temp[i]==HT[j].ch)
break;
}
if(j>
n)//表示出现非法字符
flag=0;
//获取待编码消息串
stringGet_Message_Str()
stringtemp;
intflag;
A:
输入待编码的消息串:
\n"
temp;
flag=Message_Str_Check(temp);
if(flag==0)//输入的消息串含非法字符
输入的消息串含非法字符,请重新输入!
gotoA;
returntemp;
}//对输入的消息串进行编码
stringGet_All_Code_Str(stringMessage_Str)
stringAll_Code_Str="
Message_Str[i]!
j++)
if(Message_Str[i]==HT[j].ch)
All_Code_Str+=HC[j];
returnAll_Code_Str;
//输出得到的二进制序列
voidOutput_All_Code_Str(stringAll_Code_Str)
该消息串对应的编码序列如下:
All_Code_Str<
}//编码
voidEncoding()
stringMessage_Str,All_Code_Str;
Message_Str=Get_Message_Str();
All_Code_Str=Get_All_Code_Str(Message_Str);
Output_All_Code_Str(All_Code_Str);
}/**********************译码模块**********************///检测输入的二进制序列是否含有非法字符
intBinary_Str_Check(stringtemp)
//假设不含非法字符
(temp[i]=='
||temp[i]=='
))
//获取待译的二进制序列
stringGet_Binary_Str()
B:
输入待译的二进制序列:
flag=Binary_Str_Check(temp);
if(flag==0)//输入的二进制序列含非法字符
输入的二进制序列含非法字符,请重新输入!
gotoB;
}//获取源码
stringGet_Original_Message_Str(stringBinary_Str,int*flag)
stringtemp="
*flag=1;
stringOriginal_Message_Str="
Binary_Str[i]!
temp+=Binary_Str[i];
if(HC[j]==temp)
Original_Message_Str+=HT[j].ch;
temp="
//重置
temp;
}
if(temp!
="
)
您输入的二进制序列不可译,请重新输入!
*flag=0;
returnOriginal_Message_Str;
}//输出得到的源码
voidOutput_Original_Message_Str(stringOriginal_Message_Str)
该二进制序列对应的源码如下:
Original_Message_Str<
//译码
voidDecoding()
stringBinary_Str,Original_Message_Str;
D:
Binary_Str=Get_Binary_Str();
Original_Message_Str=Get_Original_Message_Str(Binary_Str,&
flag);
flag)
gotoD;
Output_Original_Message_Str(Original_Message_Str);
/*****************************主函数*****************************/
intmain()
charchoice='
'
/*用于记录初始化情况*/
while(choice!
Q'
choice!
q'
)//当choice的值不为q且不为Q时循环
C:
"
*************************霍夫曼编码/译码器*************************\n"
1.编码"
"
2.译码"
3.退出程序"
请输入您要操作的步骤:
choice;
if(choice=='
)//进行编码
flag)
flag=1;
Initialization();
Output();
elseif(choice=='
2'
)//译码
flag)
cout<
操作错误!
请执行编码操作后再进行本操作!
gotoC;
Decoding();
3'
)//退出程序
else//如果选了选项之外的就让用户重新选择
您没有输入正确的步骤,请重新输入!
gotoC;
10
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C+ 实现 哈夫曼 编码 完整 代码