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

一、实验名称:霍夫曼编码二、实验环境软件环境:Windows 202 3 , M i cros o ft Visual C+6. 0硬件环境:P 4, 2.4GHz,256内存，IBM-PC及兼容机三、实验目的掌握霍夫曼编码、译码原理，并可以通过程序模拟其编码、译码功能。四、实验原理1、消息按其出现的概率由大到小地排成一个概率序列；2、把概率最小两个消息提成一组，其中一个消息编为0,另一个编为1,然后求 其概率和,并把这个新概率与其他尚未解决过的概率重新按概率由大到小排成一 个新的概率序列；3、反复环节，直到所有概率都已联合解决完为止。五、实验过程与实验结果源程序：# inclu d e <ios t ream>i n cl u de<s t r i ng>using n amespace s t d ;#inc 1 ude<ma t h.h> typedef s t ruct霍夫曼树的结构体c h ar c h；d o ub 1 e weight； /权值，此处为概率®i n t par e nt,Ichi 1 d ,rch i 1 d ；)htn o d e,*hfmt r e e ;* * * * * * *type d ef char *hfmc o de;* * * 全局变量* * * * * * * * * * * *doubl e H= 0 .0;®for(int i= 1 ;i<=n； i+)。H+ = - 1 *HT i .w e i ght*log(HT i .weig h t) / log( 2 )；retu r n H;)/求编码效率do u blc To_Get_Code_Effie i ency ()dou b 1c H 2 ,H,Av e _L;oH=T o _Get_H();®Ave_L=Ave_Cod e _L e ng t h();H2=H/ Ave_L；® r et u rn II2;)/分析结果输出void Outpu t ()(®dou b le H2,H, A v e _ L ；H=To_Get_H()；Av e _L= A ve_Code_ L eng t h()；H 2=To_Ge t _Code_E f fic i enc y ();co ui<<"霍夫曼编码结果如下：(消息字符一一码长一一码字)”endl ;»for(int i= 1 ； i<=n;i+)co u t « II Ti.c h < < "> " « c ode_ 1 ength i «', 一>"«HCi«endl;。c outvv”平均编码长度 A V e_L=Ll* p 1+L2 * p2 + . + Ln* p n="«A v e_L<<（码元/消息）” «en d 1;cout«"信源懒 H=-( p l*lo g (pl) + p 2 * 1 o g(p2)+.+pn * log( p n)/l o g (2)="«H«" (bit/消息)"<<e n dl;c out« "码元焙 H2=H / A ve_L="<<H 2 <<"( b it/码元)"«e n d 1 ;-co u 编码效率 E= (H 2 / H2m a x)*100%="«H2*100« " %"«e n dl；/* * * * * *编码模块 * * * * * * * * * */字符串合理性检测int M e ssa g e_S t r_Che c k(st r in g temp)(。而fl a g=l;/先假设输入的消息串不含非法字符 in t j;®for(i n t i=0;tempi! =、()' ；i + +) f o r(j=l;j<= n ； j+)° 。i f(temp i=HTj.ch)oo©break；0)表达出现非法字符。f lag=0;。b r e a k ；Oft o r eturn flag;/获取待编码消息串s t r ing G et_M e s s ag e _Str()(®str i ng temp；«int fl a g;A:out«”输入待编码的消息串:n "；*cin»tem p ;f lag=Me s sagc_St r _Chcck( t cmp)；°if(flag=O)输入的消息串含非法字符(8cout<<”输入的消息串含非法字符，请重新输入！" <<endl;8 g o to A;return temp；)/对输入的消息串进行编码str i ng Ge t _All_Cod e _S tr ( s t r in g Message_S t r)(% t r in g Al 1 _Co d e_Str=',n;Antj；f o r (in t i=O;Message_Stri!-O'； i+)efbr(j=l ； j<=n; j +)b»if (Messa g e _S t r i=H T j .ch)A 1 1_C o de_St r +=HCj;b re a k;r etur n Al 1 _C o de_ S tr;输出得到的二进制序列void Output_All_Cod e _Str(string A11_C o de_Str)cout<<”该消息串相应的编码序列如下:“ <<end 1 ；®cout<<Al 1 _Cod e _S t r«e n dl；/编码void E n cod i n g ()®str i ng Message_S tr,A 1 l_Code_ S tr;Mess age _Str=Get_Mes sag e _S t r ()；A 1 1 _Code_Str=Get_All_ C ode_St r (Me s sag e _Str);oOu t p u t_A 1 l_Code_St r (All_Code_S t r)；/* * * * *译码模块* * * * * * */ /检测输入的二进制序列是否具有非法字符int Bin a ry_Str_C he c k(stri ng t emp)-int f lag=l，假设不含非法字符fo r (i n t i = 0 ;tempi!=,0,； i+)i f ( ! (temp i = =rO'|temp i =-1*)o ofla g =0;。，b reak;°)°)return f 1 ag;)/获取待译的二进制序列string Get_Bi n a r y_Str()(s t r ing t e m p ;®in t f 1 ag;B :y o utV<”输入待译的二进制序列：、nM;c i n>> t emp;f 1 ag= B inar y _S t r_Che c k( t emp)；oif(flag=0) /输入的二进制序列含非法字符(。c out« "输入的二进制序列含非法字符，请重新输入!”V e ndl;oogot o B;® r e turn temp;)/获取源码s tring Get_Ori g inal_Mess a ge_Str ( s tr i ng B inary_ S tr,in t * flag)t r ing tern p =,n,;。* f lag= 1 ;st r ing O r iginaI_Message_Str=""。i n t j ;f or( i n t i= 0 ;B i n a r y_S t r i! ='0'； i+)。 temp +=B i na r y_St r i;8f o r(j= 1 ;j<=n;j+ )° (。i f (HCj=temp)00。Origin a 1_M e s s ag e _St r +=HT j .c h ;lemp= '* *'重置 tempbr e a k;00 |0)-if(temp! =" ")cout<<”您输入的二进制序列不可译，请重新输入！" <<e n dl;*flag= 0 ；Ir e tu r n Origin a l_Message_Str;1输出得到的源码void Output_Original.Mes s age_Str( s t r ing Orig i n a 1_Me s sag e _Str) ocout<V"该二进制序列相应的源码如下:“<Vendl;cou t <<0r i gina 1 _Messa g e_Slr« e ndl;)译码v oid D e c odin g ()(int f 1 a g；st r i n g B i nary_ S tr,Orig i n al_Messa g e_Str;D : B inary_Str= G ct_B i nary_Str();O riginal_M e s s a ge_ S tr=G e t _O r iginalMes s age_Str(B i nary_Str, & f la g );oi f (! f 1 ag)® goto D；Outpu t _ 0 r i ginal_Mess age _Str(O r ig i n a 1_M e ssag e _St r );)/* * * * * * * * * * * 主函数* * * * * * * * * /int main() ®char choice='/*用于记录初始化情况*/»in t flag=0;0cout«"nowhi 1 e ( c h oice! =,Q'&&c h oic e !-q') / / 当 c h o i ce 的值不为 q 且不为 Q 时循环C：you t <<"<< ,* * * * * * * * * * *霍夫曼编码,译码器* * * * * * * * * * *nc ou t <<"" Vv" I .输入建立“v<”n «nE.编码"«"'« n D.译码”Vv码"«"'« n D.译码”Vv,« " Q.退出n”;-cout<< ”请输入您要操作的环节：”;8 c in» cho i ce；。 i f (ch o i c e = = z I，c hoice=T) 初始化霍夫曼树。 if(! f lag) /初次执行初始化操作8 oflag=l;00o 。I nitial i zation()；8 Out put();) e Ise if( c hoic e =' E '|ch o ice=' e 9 / / 进行编码(。 if(!tlag)6 。 cout« ”操作错误！请执行输入建立操作后再进行本操作！ n«e n dl；0。 goto C：00 o EncodingO;°)®e 1 s e if(choice=-Dz |c h oice=, d ' ) / /译码°“f (fag)。ocoutvv”操作错误!请执行输入建立操作后再进行本操作！" vve n dl;g 。g oto C ；00 IDecoding ()；00 。 else if( c h oi c e="Q, | c ho i ce=- q *) /退出程序° (。ex it (0);)。 e 1 se假如选了选项之外的就让用户重新选择(c oul<<"您没有输入对的的环节，请重新输入！ " «end 1 ;。got o C;。»ocout«endl；1re t u m 0；I运营结果：1、输入消息及其相应概率,建立霍夫曼编码树，并打印输出编码效率分析结果你第第第第第第凄 入入入入入入入入入入曼 主星周青主星皇皇月主皇皇装对信.口芋a概b概C概d MJ 向 向 勺< 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、译码:注意区分可译序列和不可译序列hfmt r ee HT;hfmcode HC;i nt n= 0 ;霍夫曼树叶节点个数int m=0;霍夫曼树所有节点个数int * c ode_le n g t h;/ /用于记录每个消息字符的码长/*大* * * 霍夫曼编石马模块 * * * * * */对输入的字符进行检查i n t Inp u t_C h ar_ C hcck()i nt f lag=l;-nt j ;f o r(int i= 1 ； i<n&&fla g ; i +)(o for(j=i+1 ;j<=n;j+)o«if (HT j ,ch =HT i J.c h )ooo 8。f 1 ag= 0 ;。 break；° Iretur n f 1 a g;1/对输入的概率进行检测int I n p ut_Weig h t_Chee k ()(int flag= 0 ；B"B"您译01的译20二译11制 入待01人待20的待01进 欠01200入入10二dbEKJMUV 圣序 建的制Al s i- 制二 1 0进年”；黑生霍夫曼编码E.编码 D.请重新输入？，请重新输入，Q.退出4、退出*霍夫曼编 码/译码器*I .输入建立E.编码 D.译码Q.退出请输入您要攥作的步骤：qPress any key to continueodou b 1 e sum=0.0;®for( i nt i = 1 ； i<=n;i+)°(。旗! (HTi.we i ght>O&&HT i .we i ghtV 1) / /概率越界(® fl a g=1;。return flag;else8osum+二HT i. wei g ht;o »c o n t i n u e ;0)®if(sum> 1 ) 概率之和超过1o (1 a g =2;6) re turn f 1 ag;)void S e 1 ect (int a,int *p 1 ,i n t *p2)/"Select函数，选出HT树到a为止，权值最小和次小且P a r ent为0的2个节占*/(®in t i,j,x, y；®for(j=l;j<=a； +j)i f(HT j . paren t =0) 83X =j ；。 b r e ak;° I)for ( i =j+l ； i<= a ;+ + i) 时 f (HT i.weight<HT x .weight&&HT i .pare n t=0)"&x = i;选出权值最小的节点° 0) for(j=l;j<=a;+j)。if(HT|j. paren t =0&&x! =j)0 (。产j；8b r eak;0)®fo r ( i = j +1 ； i<= a ； +i)(oi f (HT i .weight<H Ty.weigh t &&HTi.p a rent=0&& x ! = i ) 。 y=i;选出权值次小的节点0) if(x>y) »®*pl= y;p 2 =x;6)el s e6*pl= x;0" p2=y;)/*初始化n个叶子节点及其余节点* /v oid I ni t _htnode()in t i;h ar tem p _ c h ;do u b 1 e t em p _w;I：cou t Vv”请输入信源发出的消息字符个数：*'；ci n >>n;if( s izeof(n)!= s i zeof(int) | I n<=l) / / 若输入的不是整数，则报错“COU t « "您输入的数据有误，程序终止!”v<endl;e xit(O);°)o c odejeng t h=new i ntn+ 1 ;for( i =l;i<= n ;i+) oocode_leng t h i =0;初始化码长为 00 m=2 * n- 1 ;oHT二(h fmtree)ma 1 1 o c (m+ l)*s i z e of( h tno d e)；初始化n个叶子结点of o r ( i = 1 ； i <=n;+i)。print f ("请输入第d个字符信息：”，i );c i n »t e mp_ch;。pr i ntf("请输入第d个字符相应的概率：i);o cin»temp_w;»HTi . c h =tcm p _ c h;o HTfil.weight=temp_w；oHT i. p arcnt=0;HTfi.lchi 1 d= 0 ;。HTiJ. r c h i 1 d=0；)int fl a gl =In p ut_Char_Check();检测输入的字符是否反复i n t f lag2=Input_W e ight_Ch e c k ();/ /检测输入的概率是否越界 oif(!flagl)。(-co u t<v”出现相同字符，输入错误，请重新输入！" <<endl；go t o I ;(i f(flag2 = = l)(-c o ul<v”概率越界，输入错误,请重新输入!”<ve n dl;0 goto I;oif(flag2 = =2)-c o u t <<”概率之和超过1 ,输入错误，请重新输入!”wen d 1;goto I ;)for(;i<=m； +i)/初始化其余的结点。H T i.ch=w；用*表达新生成根节点的字符域oHTi .w e i g h t =0;«HTil. par e nt=0;«HTi.lchild=0;HTfi .rc h ild=0；)/建立霍夫曼树void Create_hfmtrce()int i;。i n t pl,p 2 ;用于记录权值最小及次小节点的下标肃or (i=n+l;i<=m; + + i )/建立霍夫曼树(«Se 1 e ct( i - 1 ,&pl,&p2);HT pl. p are n t=i;HT p 2.par e nt=i;T i.lchild=p 1 ;H T i. r c hild=p 2 ;HTi.weight=HTp 1 .weight+HT p2. w e i g ht;1vo i d Hfm_co d i ng() / /求出n个字符的霍夫曼编码HC及码长。i n t i,star tointc; 当前字符下标in t f;/当前字符的父节点下标c h ar *c d ;®HC=(hfmco d e)malloc( n +1) *si z eof ( c har *);d =(ch a r *)ma 1 1 o c (n*sizeof( c har)；cd n- 1 ='0,;®for( i =1； i<=n； +i) 给 n 个字符编码(o start=n-l;o f or(c=i,f=HTi. p ar e nt； f !=O;c = f, f =HTf. par e n t)° «i f (HT f . 1c h ild=c)6 (o g c d -s t artJ=,O'° 8 elseOd ocds t art=' 1o codeJen g t h i +=1;6 )»HC i = (char*)mal 1 oc( n -star t ) * s izeof(char);a® s t rcpy(HCi,&cdsta r t);0)®free(cd)；初始化/*功能：从终端读入字符集大小n,以及n个字符和n个权值，建立霍夫曼树，并将它存于文献hfmTree中。*/int I nitializat i on ()(Init_ h t no d e ();C re a tc_h f m t r e e ();Hfm_c o di n g ()；»ret u m 0 ;)/ * * * * * * * * * * * * * * *编码效率分析模块 * * * * * * * * * * */求平均编码长度do u ble Ave_C o de_L e n gth()dou b le Ave_L=0. 0；for(in t i =1； i<= n ； i +)。 Ave_L+= c o d e _le n g t hi * H T i . weight;。但 t u r n AveL;1求信源燧doubleTo_Ge t_H()