一、實(shí)驗(yàn)名稱:霍夫曼編碼二、實(shí)驗(yàn)環(huán)境軟件環(huán)境:Windows2023,MicrosoftVisualC++6.0硬件環(huán)境:P4,2.4GHz,256內(nèi)存，IBM-PC及兼容機(jī)三、實(shí)驗(yàn)?zāi)康恼莆栈舴蚵幋a、譯碼原理，并可以通過程序模擬其編碼、譯碼功能。四、實(shí)驗(yàn)原理1、消息按其出現(xiàn)的概率由大到小地排成一個(gè)概率序列；2、把概率最小兩個(gè)消息提成一組，其中一個(gè)消息編為0,另一個(gè)編為1,然后求其概率和,并把這個(gè)新概率與其他尚未解決過的概率重新按概率由大到小排成一個(gè)新的概率序列；3、反復(fù)環(huán)節(jié)，直到所有概率都已聯(lián)合解決完為止。。五、實(shí)驗(yàn)過程與實(shí)驗(yàn)結(jié)果源程序：include<iostream>include<string>usingnamespacestd;#inc1ude<math.h>typedefstruct{〃霍夫曼樹的結(jié)構(gòu)體charch；doub1eweight；//權(quán)值，此處為概率?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;)//分析結(jié)果輸出voidOutput()(?doubleH2,H,Ave_L；H=To_Get_H()；Ave_L=Ave_Code_Length()；H2=To_Get_Code_Efficiency();coui<<"霍夫曼編碼結(jié)果如下：(消息字符一一碼長(zhǎng)一一碼字)”《endl;?for(inti=1；i<=n;i++)cout?IIT[i].ch<<">"?code_1ength[i]?',一—>"?HC[i]?endl;。coutvv”平均編碼長(zhǎng)度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；/****************************※編碼模塊****************************//字符串合理性檢測(cè)intMessage_Str_Check(stringtemp)(。而flag=l;//先假設(shè)輸入的消息串不含非法字符intj;?for(inti=0;temp[i]!=、()'；i++){for(j=l;j<=n；j++)°{。if(temp[i]==HT[j].ch)oo?break；0)〃表達(dá)出現(xiàn)非法字符。{。flag=0;。break；Oft}}oreturnflag;//獲取待編碼消息串stringGet_Message_Str()(?stringtemp；?intflag;A:℃out?”輸入待編碼的消息串:\n"；*cin?temp;flag=Messagc_Str_Chcck(tcmp)；°if(flag==O)〃輸入的消息串含非法字符(8cout<<”輸入的消息串含非法字符，請(qǐng)重新輸入！"<<endl;8gotoA;returntemp；)//對(duì)輸入的消息串進(jìn)行編碼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;〃輸出得到的二進(jìn)制序列voidOutput_All_Code_Str(stringA11_Code_Str)cout<<”該消息串相應(yīng)的編碼序列如下:“<<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)；/**********************譯碼模塊**********************///檢測(cè)輸入的二進(jìn)制序列是否具有非法字符intBinary_Str_Check(stringtemp)-intflag=l，假設(shè)不含非法字符for(inti=0;temp[i]!=,\0,；i++)if(!(temp[i]==rO'||temp[i]=-1*))ooflag=0;。。，break;°)°)returnf1ag;)//獲取待譯的二進(jìn)制序列stringGet_Binary_Str()(stringtemp;?intf1ag;B:youtV<”輸入待譯的二進(jìn)制序列：、nM;cin>>temp;f1ag=Binary_Str_Check(temp)；oif(flag==0)//輸入的二進(jìn)制序列含非法字符(。cout?"輸入的二進(jìn)制序列含非法字符，請(qǐng)重新輸入!”〈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<<”您輸入的二進(jìn)制序列不可譯，請(qǐng)重新輸入！"<<endl;*flag=0；IreturnOriginal_Message_Str;1〃輸出得到的源碼voidOutput_Original.Message_Str(stringOrigina1_Message_Str)ocout<V"該二進(jìn)制序列相應(yīng)的源碼如下:“<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);)/*****************************主函數(shù)*****************************/intmain(){?charchoice='/*用于記錄初始化情況*/?intflag=0;0cout?"\nowhi1e(choice!=,Q'&&choice!-q')//當(dāng)choice的值不為q且不為Q時(shí)循環(huán)

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){//初次執(zhí)行初始化操作8oflag=l;00}o。Initialization()；8Output();)◎eIseif(choice=='E'||choice=='e9//進(jìn)行編碼(。if(!tlag)6{。。cout?”操作錯(cuò)誤！請(qǐng)執(zhí)行輸入建立操作后再進(jìn)行本操作！n?endl；0。gotoC：00}oEncodingO;°)?e1seif(choice=-Dz||choice==,d')//譯碼°{“f(fag)。ocoutvv”操作錯(cuò)誤!請(qǐng)執(zhí)行輸入建立操作后再進(jìn)行本操作！"vvendl;g。gotoC；00I^Decoding()；00}。elseif(choice="Q,||choice=-q*)//退出程序°(。exit(0);)。e1se〃假如選了選項(xiàng)之外的就讓用戶重新選擇(coul<<"您沒有輸入對(duì)的的環(huán)節(jié)，請(qǐng)重新輸入！"?end1;。。gotoC;。}?ocout?endl；1retum0；I運(yùn)營(yíng)結(jié)果：1、輸入消息及其相應(yīng)概率,建立霍夫曼編碼樹，并打印輸出編碼效率分析結(jié)果你第第第第第第凄入入入入入入入入入入曼主星周青主星皇皇月主皇皇裝對(duì)信.口芋a概b概C概dMJ向向勺<V居曹心應(yīng)息應(yīng)息應(yīng)息應(yīng)F::1可、￥士一一s-f77x±5-h^-syT0.0.符3L?D出退■Q平均編碼長(zhǎng)度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、編碼：輸入的消息字符串中應(yīng)只含信源可以發(fā)出的幾個(gè)字符，否則，報(bào)錯(cuò)?F:\TOD啜據(jù)結(jié)構(gòu)TOD判程、信息論'霍夫曼編碼\Debug暹夫曼潟碼.exe"4T「日同「￡??蜜?篁懿康誨**********霍夫曼編碼/譯碼器***********E.編碼D.譯碼Q.退出eabbbdbs黔鰻懿盒箍字符，請(qǐng)重新輸入'輸入待編碼的扉息串:abbdbbbcbbdb該消息串對(duì)應(yīng)的編碼序列如下：請(qǐng)輸入您罐情券驟:******霍夫曼編碼/譯碼器***********

E.編碼D.譯碼Q.退出3、譯碼:注意區(qū)分可譯序列和不可譯序列hfmtreeHT;hfmcodeHC;intn=0;〃霍夫曼樹葉節(jié)點(diǎn)個(gè)數(shù)intm=0;〃霍夫曼樹所有節(jié)點(diǎn)個(gè)數(shù)int*code_length;//用于記錄每個(gè)消息字符的碼長(zhǎng)/*******大*********************霍夫曼編石馬模塊*****************************///對(duì)輸入的字符進(jìn)行檢查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//對(duì)輸入的概率進(jìn)行檢測(cè)intInput_Weight_Cheek()(intflag=0；

B"B"B"您譯01的譯20二譯11制入待01人待20的待01B"您譯01的譯20二譯11制入待01人待20的待01進(jìn)欠01200入入10二dbEKJMUV圣序建的制Alsi--制二」10進(jìn)年”；黑生霍夫曼編碼E.編碼D.請(qǐng)重新輸入？，請(qǐng)重新輸入，Q.退出*************************霍夫曼編碼/譯碼器…********I.輸入建立E.編碼D.譯碼Q.退出請(qǐng)輸入您要攥作的步驟：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函數(shù)，選出HT樹到a為止，權(quán)值最小和次小且Parent為0的2個(gè)節(jié)占*/(?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){時(shí)f(HT[i].weight<HT[x].weight&&HT[i].parent==0){"&x=i;〃選出權(quán)值最小的節(jié)點(diǎn)°}0)for(j=l;j<=a;++j){。if(HT|j].parent==0&&x!=j)0(。產(chǎn)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;〃選出權(quán)值次小的節(jié)點(diǎn)}0)if(x>y){??*pl=y;p2=x;6)else6*pl=x;0"p2=y;))/*初始化n個(gè)葉子節(jié)點(diǎn)及其余節(jié)點(diǎn)*/voidInit_htnode(){inti;hartemp_ch;doub1etemp_w;I：^coutVv”請(qǐng)輸入信源發(fā)出的消息字符個(gè)數(shù)：*'；cin>>n;if(sizeof(n)!=sizeof(int)|In<=l)//若輸入的不是整數(shù)，則報(bào)錯(cuò)“COUt?"您輸入的數(shù)據(jù)有誤，程序終止!”v<endl;exit(O);°)ocodejength=newint[n+1];for(i=l;i<=n;i++){oocode_length[i]=0;〃初始化碼長(zhǎng)為00m=2*n-1;oHT二(hfmtree)ma11oc((m+l)*sizeof(htnode))；〃初始化n個(gè)葉子結(jié)點(diǎn)ofor(i=1；i<=n;++i)。。printf("請(qǐng)輸入第％d個(gè)字符信息：〃初始化n個(gè)葉子結(jié)點(diǎn)cin?temp_ch;。printf("請(qǐng)輸入第％d個(gè)字符相應(yīng)的概率：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();〃檢測(cè)輸入的字符是否反復(fù)intflag2=Input_Weight_Check();//檢測(cè)輸入的概率是否越界oif(!flagl)。(-cout<v”出現(xiàn)相同字符，輸入錯(cuò)誤，請(qǐng)重新輸入！"<<endl；gotoI;(if(flag2==l)(-coul<v”概率越界，輸入錯(cuò)誤,請(qǐng)重新輸入!”<vendl;0gotoI;oif(flag2==2)-cout<<”概率之和超過1,輸入錯(cuò)誤，請(qǐng)重新輸入!”wend1;gotoI;)for(;i<=m；++i)//初始化其余的結(jié)點(diǎn)。HT[i].ch=w；〃用*表達(dá)新生成根節(jié)點(diǎn)的字符域oHT[i].weight=0;?HT[il.parent=0;?HT[i].lchild=0;HTfi].rchild=0；))//建立霍夫曼樹voidCreate_hfmtrce(){inti;。intpl,p2;〃用于記錄權(quán)值最小及次小節(jié)點(diǎn)的下標(biāo)肅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個(gè)字符的霍夫曼編碼HC及碼長(zhǎng)