C++实现哈夫曼编码完整代码 甄选.docx
- 文档编号:15850411
- 上传时间:2023-07-08
- 格式:DOCX
- 页数:17
- 大小:18.09KB
C++实现哈夫曼编码完整代码 甄选.docx
《C++实现哈夫曼编码完整代码 甄选.docx》由会员分享,可在线阅读,更多相关《C++实现哈夫曼编码完整代码 甄选.docx(17页珍藏版)》请在冰点文库上搜索。
C++实现哈夫曼编码完整代码甄选
C++实现哈夫曼编码完整代码(优选.)
rd
#include
#include
usingnamespacestd;
#include
typedefstruct{//霍夫曼树的结构体
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;i { for(j=i+1;j<=n;j++) if(HT[j].ch==HT[i].ch) { flag=0; break; } } returnflag;} //对输入的概率进行检测 intInput_Weight_Check(){ intflag=0;doublesum=0.0; for(inti=1;i<=n;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;j<=a;++j) { if(HT[j].parent==0) { x=j;break; } } for(i=j+1;i<=a;++i) { if(HT[i].weight { x=i;//选出权值最小的节点 } } for(j=1;j<=a;++j) { if(HT[j].parent==0&&x! =j) { y=j;break; } } for(i=j+1;i<=a;++i) { if(HT[i].weight =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<<"您输入的数据有误,程序终止! "< 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)); printf("请输入字符信息,,字符对应的概率: "); for(i=1;i<=n;++i)//初始化n个叶子结点 { //printf("请输入第%d个字符信息: ",i); cin>>temp_ch; //printf("请输入第%d个字符对应的概率: ",i); cin>>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) { cout<<"出现相同字符,输入错误,请重新输入! "< gotoI; } if(flag2==1) { cout<<"概率越界,输入错误,请重新输入! "< gotoI; } if(flag2==2) { cout<<"概率之和超过1,输入错误,请重新输入! "< 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; 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'; 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; } /*****************************编码效率分析模块*****************************///求平均编码长度 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<<"霍夫曼编码结果如下: (消息字符--码长--码字)"< for(inti=1;i<=n;i++) cout< cout<<"平均编码长度Ave_L=L1*p1+L2*p2+...+Ln*pn="< cout<<"信源熵H=-(p1*log(p1)+p2*log(p2)+...+pn*log(pn))/log (2)="< cout<<"码元熵H2=H/Ave_L="< cout<<"编码效率E=(H2/H2max)*100%="< }/*****************************编码模块*****************************/ //字符串合理性检测 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(j>n)//表示出现非法字符 { flag=0; break; } } returnflag; } //获取待编码消息串 stringGet_Message_Str() { stringtemp; intflag;A: cout<<"输入待编码的消息串: \n"; cin>>temp; flag=Message_Str_Check(temp); if(flag==0)//输入的消息串含非法字符 { cout<<"输入的消息串含非法字符,请重新输入! "< 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) { All_Code_Str+=HC[j]; break; } } returnAll_Code_Str; } //输出得到的二进制序列 voidOutput_All_Code_Str(stringAll_Code_Str) { cout<<"该消息串对应的编码序列如下: "< cout< }//编码 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) { intflag=1; //假设不含非法字符 for(inti=0;temp[i]! ='\0';i++) { if(! (temp[i]=='0'||temp[i]=='1')) { flag=0;break; } } returnflag; } //获取待译的二进制序列 stringGet_Binary_Str() { stringtemp; intflag; B: cout<<"输入待译的二进制序列: \n"; cin>>temp; flag=Binary_Str_Check(temp); if(flag==0)//输入的二进制序列含非法字符 { cout<<"输入的二进制序列含非法字符,请重新输入! "< } returntemp; }//获取源码 stringGet_Original_Message_Str(stringBinary_Str,int*flag) { stringtemp=""; *flag=1; stringOriginal_Message_Str=""; intj; for(inti=0;Binary_Str[i]! ='\0';i++) { temp+=Binary_Str[i]; for(j=1;j<=n;j++) { if(HC[j]==temp) { Original_Message_Str+=HT[j].ch; temp=""; //重置 temp;break; } } } if(temp! ="") { cout<<"您输入的二进制序列不可译,请重新输入! "< } returnOriginal_Message_Str; }//输出得到的源码 voidOutput_Original_Message_Str(stringOriginal_Message_Str) { cout<<"该二进制序列对应的源码如下: "< } //译码 voidDecoding() { intflag; stringBinary_Str,Original_Message_Str; D: Binary_Str=Get_Binary_Str(); Original_Message_Str=Get_Original_Message_Str(Binary_Str,&flag); if(! flag) gotoD; Output_Original_Message_Str(Original_Message_Str); } /*****************************主函数*****************************/ intmain() { charchoice=''; /*用于记录初始化情况*/ intflag=0; cout<<"\n"; while(choice! ='Q'&&choice! ='q')//当choice的值不为q且不为Q时循环 { C: cout<<""<<"*************************霍夫曼编码/译码器*************************\n"; cout<<""<<"1.编码"<<""<<"2.译码"<<""<<"3.退出程序"< cout<<"请输入您要操作的步骤: "; cin>>choice; if(choice=='1')//进行编码 { if(! flag) { flag=1; } Initialization(); Output(); } elseif(choice=='2')//译码 { if(! flag) { cout<<"操作错误! 请执行编码操作后再进行本操作! "< gotoC; } Decoding(); } elseif(choice=='3')//退出程序 { exit(0); } else//如果选了选项之外的就让用户重新选择 { cout<<"您没有输入正确的步骤,请重新输入! "< gotoC; } cout< } return0; } 赠人玫瑰,手留余香。 感谢您使用本店文档您的满意是我们的永恒的追求! (本句可删) ------------------------------------------------------------------------------------------------------------
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- C+实现哈夫曼编码完整代码 甄选 C+ 实现 哈夫曼 编码 完整 代码
![提示](https://static.bingdoc.com/images/bang_tan.gif)