2023年霍夫曼编码实验报告C++

一、实验名称:霍夫曼编码二、实验环境软件环境:Windows2023,MicrosoftVisualC++6.0硬件环境:P4,2.4GHz,256内存，IBM-PC及兼容机三、实验目的掌握霍夫曼编码、译码原理，并可以通过程序模拟其编码、译码功能。四、实验原理1、消息按其出现的概率由大到小地排成一个概率序列；2、把概率最小两个消息提成一组，其中一个消息编为0,另一个编为1,然后求其概率和,并把这个新概率与其他尚未解决过的概率重新按概率由大到小排成一个新的概率序列；3、反复环节，直到所有概率都已联合解决完为止。。五、实验过程与实验结果源程序：include<iostream>include<string>usingnamespacestd;#inc1ude<math.h>typedefstruct{〃霍夫曼树的结构体charch；doub1eweight；//权值，此处为概率®intparent,Ichi1d,rchi1d；)htnode,*hfmtree;************************************************typedefchar**hfmcode;*************全局变量******************************************doubleH=0.0;®for(inti=1;i<=n；i++)。H+=-1*HT[i].weight*log(HT[i].weight)/log(2)；returnH;)//求编码效率doublcTo_Get_Code_Effieiency(){doub1cH2,H,Ave_L;oH=To_Get_H();®Ave_L=Ave_Code_Length();H2=H/Ave_L；®returnII2;)//分析结果输出voidOutput()(®doubleH2,H,Ave_L；H=To_Get_H()；Ave_L=Ave_Code_Length()；H2=To_Get_Code_Efficiency();coui<<"霍夫曼编码结果如下：(消息字符一一码长一一码字)”《endl;»for(inti=1；i<=n;i++)cout«IIT[i].ch<<">"«code_1ength[i]«',一—>"«HC[i]«endl;。coutvv”平均编码长度AVe_L=Ll*p1+L2*p2+...+Ln*pn="«Ave_L<<（码元/消息）”«end1;cout«"信源懒H=-(pl*log(pl)+p2*1og(p2)+...+pn*log(pn))/log(2)="«H«"(bit/消息)"<<endl;cout«"码元焙H2=H/Ave_L="<<H2<<"(bit/码元)"«end1;-cou编码效率E=(H2/H2max)*100%="«H2*100«"%"«endl；/****************************※编码模块****************************//字符串合理性检测intMessage_Str_Check(stringtemp)(。而flag=l;//先假设输入的消息串不含非法字符intj;®for(inti=0;temp[i]!=、()'；i++){for(j=l;j<=n；j++)°{。if(temp[i]==HT[j].ch)oo©break；0)〃表达出现非法字符。{。flag=0;。break；Oft}}oreturnflag;//获取待编码消息串stringGet_Message_Str()(®stringtemp；«intflag;A:℃out«”输入待编码的消息串:\n"；*cin»temp;flag=Messagc_Str_Chcck(tcmp)；°if(flag==O)〃输入的消息串含非法字符(8cout<<”输入的消息串含非法字符，请重新输入！"<<endl;8gotoA;returntemp；)//对输入的消息串进行编码stringGet_All_Code_Str(stringMessage_Str)(%tringAl1_Code_Str=',n;Antj；for(inti=O;Message_Str[i]!-\O'；i++)efbr(j=l；j<=n;j++)b{»if(Message_Str[i]==HT[j].ch)A11_Code_Str+=HC[j];break;returnAl1_Code_Str;〃输出得到的二进制序列voidOutput_All_Code_Str(stringA11_Code_Str)cout<<”该消息串相应的编码序列如下:“<<end1；®cout<<Al1_Code_Str«endl；//编码voidEncoding()®stringMessage_Str,A1l_Code_Str;Message_Str=Get_Message_Str()；A11_Code_Str=Get_All_Code_Str(Message_Str);oOutput_A1l_Code_Str(All_Code_Str)；/**********************译码模块**********************///检测输入的二进制序列是否具有非法字符intBinary_Str_Check(stringtemp)-intflag=l，假设不含非法字符for(inti=0;temp[i]!=,\0,；i++)if(!(temp[i]==rO'||temp[i]=-1*))ooflag=0;。。，break;°)°)returnf1ag;)//获取待译的二进制序列stringGet_Binary_Str()(stringtemp;®intf1ag;B:youtV<”输入待译的二进制序列：、nM;cin>>temp;f1ag=Binary_Str_Check(temp)；oif(flag==0)//输入的二进制序列含非法字符(。cout«"输入的二进制序列含非法字符，请重新输入!”〈Vendl;oogotoB;}®returntemp;)//获取源码stringGet_Original_Message_Str(stringBinary_Str,int*flag)tringternp=,n,;。*flag=1;stringOriginaI_Message_Str="";。intj;for(inti=0;Binary_Str[i]!='\0'；i++){。temp+=Binary_Str[i];8for(j=1;j<=n;j++)°(。if(HC[j]==temp)00{。Origina1_Message_Str+=HT[j].ch;lemp='**';〃重置tempbreak;00|0)-if(temp!=""){cout<<”您输入的二进制序列不可译，请重新输入！"<<endl;*flag=0；IreturnOriginal_Message_Str;1〃输出得到的源码voidOutput_Original.Message_Str(stringOrigina1_Message_Str)ocout<V"该二进制序列相应的源码如下:“<Vendl;cout<<0rigina1_Message_Slr«endl;)〃译码voidDecoding()(intf1ag；stringBinary_Str,Original_Message_Str;D:Binary_Str=Gct_Binary_Str();Original_Message_Str=Get_Original—Message_Str(Binary_Str,&flag);oif(!f1ag)®gotoD；Output_0riginal_Message_Str(Origina1_Message_Str);)/*****************************主函数*****************************/intmain(){®charchoice='/*用于记录初始化情况*/»intflag=0;0cout«"\nowhi1e(choice!=,Q'&&choice!-q')//当choice的值不为q且不为Q时循环

C：yout<<"<<,**************************霍夫曼编码,译码器**C：yout<<cout<<""Vv"I.输入建立“v<”n«nE.编码码"«"'«nD.译码”Vv码"«"'«nD.码"«"'«nD.译码”Vv,«"Q.退出\n”;8cin»choice；。if(choice==zI，choice==T)〃初始化霍夫曼树。{。if(!flag){//初次执行初始化操作8oflag=l;00}o。Initialization()；8Output();)◎eIseif(choice=='E'||choice=='e9//进行编码(。if(!tlag)6{。。cout«”操作错误！请执行输入建立操作后再进行本操作！n«endl；0。gotoC：00}oEncodingO;°)®e1seif(choice=-Dz||choice==,d')//译码°{“f(fag)。ocoutvv”操作错误!请执行输入建立操作后再进行本操作！"vvendl;g。gotoC；00I^Decoding()；00}。elseif(choice="Q,||choice=-q*)//退出程序°(。exit(0);)。e1se〃假如选了选项之外的就让用户重新选择(coul<<"您没有输入对的的环节，请重新输入！"«end1;。。gotoC;。}»ocout«endl；1retum0；I运营结果：1、输入消息及其相应概率,建立霍夫曼编码树，并打印输出编码效率分析结果你第第第第第第凄入入入入入入入入入入曼主星周青主星皇皇月主皇皇装对信.口芋a概b概C概dMJ向向勺<V居曹心应息应息应息应F::1可、¥士一一s-f77x±5-h^-syT0.0.符3L?D出退■Q平均编码长度Aue_L=Ll*pl+L2*p2+...+Ln*pn=：L.9（码元/消息）信速嫡H=-（pl*log<pl>+p2*log<p2>+...+pn*log<pn>）Zlog<2>=l.84644（bit/消息）祠元嫡H2=H/Ave_L=0.97181（bit/码元）编码效率£=（H2/H2max）*100z=97.181x2、编码：输入的消息字符串中应只含信源可以发出的几个字符，否则，报错•F:\TOD啜据结构TOD判程、信息论'霍夫曼编码\Debug暹夫曼潟码.exe"4T「日同「£।・蜜•篁懿康诲**********霍夫曼编码/译码器***********E.编码D.译码Q.退出eabbbdbs黔鳗懿盒箍字符，请重新输入'输入待编码的扉息串:abbdbbbcbbdb该消息串对应的编码序列如下：请输入您罐情券骤:******霍夫曼编码/译码器***********

E.编码D.译码Q.退出3、译码:注意区分可译序列和不可译序列hfmtreeHT;hfmcodeHC;intn=0;〃霍夫曼树叶节点个数intm=0;〃霍夫曼树所有节点个数int*code_length;//用于记录每个消息字符的码长/*******大*********************霍夫曼编石马模块*****************************///对输入的字符进行检查intInput_Char_Chcck(){intflag=l;-ntj;for(inti=1；i<n&&flag;i++)(ofor(j=i+1;j<=n;j++)o«if(HT[j],ch==HT[iJ.ch)ooo{8。f1ag=0;。^break；°}Ireturnf1ag;1//对输入的概率进行检测intInput_Weight_Cheek()(intflag=0；

B"B"B"您译01的译20二译11制入待01人待20的待01B"您译01的译20二译11制入待01人待20的待01进欠01200入入10二dbEKJMUV圣序建的制Alsi--制二」10进年”；黑生霍夫曼编码E.编码D.请重新输入？，请重新输入，Q.退出*************************霍夫曼编码/译码器…********I.输入建立E.编码D.译码Q.退出请输入您要攥作的步骤：qPressanykeytocontinueodoub1esum=0.0;®for(inti=1；i<=n;i++)°(。旗!(HT[i].weight>O&&HT[i].weightV1))//概率越界(®flag=1;。。returnflag;}else{8osum+二HT[i].weight;o»continue;0)}®if(sum>1)〃概率之和超过1o(ag=2;6)◎returnf1ag;)voidSe1ect(inta,int*p1,int*p2)/"Select函数，选出HT树到a为止，权值最小和次小且Parent为0的2个节占*/(®inti,j,x,y；®for(j=l;j<=a；++j){if(HT[j].parent==0){83X=j；。break;°I)for(i=j+l；i<=a;++i){时f(HT[i].weight<HT[x].weight&&HT[i].parent==0){"&x=i;〃选出权值最小的节点°}0)for(j=l;j<=a;++j){。if(HT|j].parent==0&&x!=j)0(。产j；8break;0})®for(i=j+1；i<=a；++i)(oif(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i)。{。y=i;〃选出权值次小的节点}0)if(x>y){»®*pl=y;p2=x;6)else6*pl=x;0"p2=y;))/*初始化n个叶子节点及其余节点*/voidInit_htnode(){inti;hartemp_ch;doub1etemp_w;I：^coutVv”请输入信源发出的消息字符个数：*'；cin>>n;if(sizeof(n)!=sizeof(int)|In<=l)//若输入的不是整数，则报错“COUt«"您输入的数据有误，程序终止!”v<endl;exit(O);°)ocodejength=newint[n+1];for(i=l;i<=n;i++){oocode_length[i]=0;〃初始化码长为00m=2*n-1;oHT二(hfmtree)ma11oc((m+l)*sizeof(htnode))；〃初始化n个叶子结点ofor(i=1；i<=n;++i)。。printf("请输入第％d个字符信息：〃初始化n个叶子结点cin»temp_ch;。printf("请输入第％d个字符相应的概率：i);ocin»temp_w;»HT[i].ch=tcmp_ch;oHTfil.weight=temp_w；oHT[i].parcnt=0;HTfi].lchi1d=0;。HT[iJ.rchi1d=0；)intflagl=Input_Char_Check();〃检测输入的字符是否反复intflag2=Input_Weight_Check();//检测输入的概率是否越界oif(!flagl)。(-cout<v”出现相同字符，输入错误，请重新输入！"<<endl；gotoI;(if(flag2==l)(-coul<v”概率越界，输入错误,请重新输入!”<vendl;0gotoI;oif(flag2==2)-cout<<”概率之和超过1,输入错误，请重新输入!”wend1;gotoI;)for(;i<=m；++i)//初始化其余的结点。HT[i].ch=w；〃用*表达新生成根节点的字符域oHT[i].weight=0;«HT[il.parent=0;«HT[i].lchild=0;HTfi].rchild=0；))//建立霍夫曼树voidCreate_hfmtrce(){inti;。intpl,p2;〃用于记录权值最小及次小节点的下标肃or(i=n+l;i<=m;++i)//建立霍夫曼树(«Se1ect(i-1,&pl,&p2);HT[pl].parent=i;HT[p2].parent=i;T[i].lchild=p1;HT[i].rchild=p2;HT[i].weight=HT[p1].weight+HT[p2].weight;1voidHfm_coding()//求出n个字符的霍夫曼编码HC及码长