霍夫曼编码实验报告(C++)

计算机科学与工程系一、实验名称：霍夫曼编码二、实验环境软件环境：Windows2000，MicrosoftVisualC++6.0硬件环境：P4，2.4GHz，256内存，IBM-PC及兼容机三、实验目的掌握霍夫曼编码、译码原理，并能够通过程序模拟其编码、译码功能。四、实验原理1、消息按其出现的概率由大到小地排成一个概率序列；2、把概率最小两个消息分成一组，其中一个消息编为0，另一个编为1，然后求其概率和，并把这个新概率与其他尚未处理过的概率重新按概率由大到小排成一个新的概率序列；3、重复步骤，直到所有概率都已联合处理完为止。五、实验过程与实验结果源程序：#includeiostream#includestringusingnamespacestd;#includemath.htypedefstruct{//霍夫曼树的结构体charch;doubleweight;//权值，此处为概率intparent,lchild,rchild;}htnode,*hfmtree;typedefchar**hfmcode;/*****************************全局变量*****************************/hfmtreeHT;hfmcodeHC;intn=0;//霍夫曼树叶节点个数intm=0;//霍夫曼树所有节点个数int*code_length;//用于记录每个消息字符的码长/*****************************霍夫曼编码模块*****************************///对输入的字符进行检验intInput_Char_Check(){intflag=1;intj;for(inti=1;in&&flag;i++){for(j=i+1;j=n;j++)if(HT[j].ch==HT[i].ch){flag=0;break;计算机科学与工程系2}}returnflag;}//对输入的概率进行检测intInput_Weight_Check(){intflag=0;doublesum=0.0;for(inti=1;i=n;i++){if(!(HT[i].weight0&&HT[i].weight1))//概率越界{flag=1;returnflag;}else{sum+=HT[i].weight;continue;}}if(sum1)//概率之和超过1{flag=2;}returnflag;}voidSelect(inta,int*p1,int*p2)/*Select函数，选出HT树到a为止，权值最小和次小且parent为0的2个节点*/{inti,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].weightHT[x].weight&&HT[i].parent==0){x=i;//选出权值最小的节点}}for(j=1;j=a;++j){if(HT[j].parent==0&&x!=j)计算机科学与工程系3{y=j;break;}}for(i=j+1;i=a;++i){if(HT[i].weightHT[y].weight&&HT[i].parent==0&&x!=i){y=i;//选出权值次小的节点}}if(xy){*p1=y;*p2=x;}else{*p1=x;*p2=y;}}/*初始化n个叶子节点及其余节点*/voidInit_htnode(){inti;chartemp_ch;doubletemp_w;I:cout请输入信源发出的消息字符个数：;cinn;if(sizeof(n)!=sizeof(int)||n=1)//若输入的不是整数，则报错{cout您输入的数据有误，程序终止!endl;exit(0);}code_length=newint[n+1];for(i=1;i=n;i++){code_length[i]=0;//初始化码长为0}m=2*n-1;HT=(hfmtree)malloc((m+1)*sizeof(htnode));for(i=1;i=n;++i)//初始化n个叶子结点{printf(请输入第%d个字符信息：,i);计算机科学与工程系4cintemp_ch;printf(请输入第%d个字符对应的概率：,i);cintemp_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){cout出现相同字符，输入错误，请重新输入!endl;gotoI;}if(flag2==1){cout概率越界，输入错误，请重新输入!endl;gotoI;}if(flag2==2){cout概率之和超过1，输入错误，请重新输入!endl;gotoI;}for(;i=m;++i)//初始化其余的结点{HT[i].ch='*';//用*表示新生成根节点的字符域HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}}//建立霍夫曼树voidCreate_hfmtree(){inti;intp1,p2;//用于记录权值最小及次小节点的下标for(i=n+1;i=m;++i)//建立霍夫曼树{Select(i-1,&p1,&p2);HT[p1].parent=i;HT[p2].parent=i;计算机科学与工程系5HT[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';for(i=1;i=n;++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{cd[--start]='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;}计算机科学与工程系6/*****************************编码效率分析模块*****************************///求平均编码长度doubleAve_Code_Length(){doubleAve_L=0.0;for(inti=1;i=n;i++)Ave_L+=code_length[i]*HT[i].weight;returnAve_L;}//求信源熵doubleTo_Get_H(){doubleH=0.0;for(inti=1;i=n;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(){doubleH2,H,Ave_L;H=To_Get_H();Ave_L=Ave_Code_Length();H2=To_Get_Code_Efficiency();cout霍夫曼编码结果如下:（消息字符——码长——码字）endl;for(inti=1;i=n;i++)coutHT[i].ch——code_length[i]——HC[i]endl;cout平均编码长度Ave_L=L1*p1+L2*p2+...+Ln*pn=Ave_L（码元/消息）endl;cout信源熵H=-（p1*log(p1)+p2*log(p2)+...+pn*log(pn)）/log(2)=H（bit/消息）endl;cout码元熵H2=H/Ave_L=H2（bit/码元）endl;cout编码效率E=（H2/H2max）*100%=H2*100%endl;}计算机科学与工程系7/*****************************编码模块*****************************///字符串合理性检测intMessage_Str_Check(stringtemp){intflag=1;//先假设输入的消息串不含非法字符intj;for(inti=0;temp[i]!='\0';i++){for(j=1;j=n;j++){if(temp[i]==HT[j].ch)break;}if(jn)//表示出现非法字符{flag=0;break;}}returnflag;}//获取待编码消息串stringGet_Message_Str(){stringtemp;intflag;A:cout输入待编码的消息串:\n;cintemp;flag=Message_Str_Check(temp);if(flag==0)//输入的消息串含非法字符{cout输入的消息串含非法字符,请重新输入!endl;gotoA;}returntemp;}//对输入的消息串进行编码stringGet_All_Code_Str(stringMessage_Str){stringAll_Code_Str=;intj;for(inti=0;Message_Str[i]!='\0';i++)for(j=1;j=n;j++){if(Message_Str[i]==HT[j].ch)计算机科学与工程系8{All_Code_Str+=HC[j];break;}}returnAll_Code_Str;}//输出得到的二进制序列voidOutput_All_Code_Str(stringAll_Code_Str){cout该消息串对应的编码序列如下:endl;coutAll_Code_Strendl;}//编码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){intfla