C++实现哈夫曼编码完整代码甄选

1、 #include#include #includetypedef struct/ 霍夫曼树的结构体 double weight; / 权值，此处为概率 htnode,*hfmtree;typedef char *hfmcode;/* / 用于记录每个消息字符的码长/*/ 对输入的字符进行检验 for(int i=1;in&flag;i+)全局变量 */霍夫曼编码模块 */ for(j=i+1;j=n;j+)if(HTj.ch=HTi.ch)flag=0; / 对输入的概率进行检测 for(int i=1;i0&HTi.weight1)/ 概率之和超过 1flag=2; void Select

2、(int a,int *p1,int *p2) /*Select 点*/ for(j=1;j=a;+j)if(HTj.parent=0) for(i=j+1;i=a;+i)if(HTi.weightHTx.weight&HTi.parent=0)x=i; / 选出权值最小的节点for(j=1;j=a;+j)if(HTj.parent=0&x!=j) for(i=j+1;i=a;+i) if(HTi.weightn; if(sizeof(n)!=sizeof(int)|n=1)/cout您输入的数据有误，程序终止若输入的不是整数，则报错 code_length=new intn+1;for(i=

3、1;i=n;i+)code_lengthi=0;/ 初始化码长为 0HT=(hfmtree)malloc(m+1)*sizeof(htnode); for(i=1;itemp_ch; cintemp_w;HTi.ch=temp_ch;HTi.weight=temp_w; int flag1=Input_Char_Check(); / 检测输入的字符是否重复int flag2=Input_Weight_Check(); / 检测输入的概率是否越界cout出现相同字符，输入错误，请重新输入 !endl; cout概率越界，输入错误，请重新输入 !endl; cout概率之和超过 1，输入错误，请重

4、新输入 !endl; void Create_hfmtree() / 初始化其余的结点/ 用*表示新生成根节点的字符域/ 建立霍夫曼树/ 用于记录权值最小及次小节点的 for(i=n+1;i=m;+i)Select(i-1,&p1,&p2);HTp1.parent=i;HTp2.parent=i;HTi.lchild=p1;HTi.rchild=p2;HTi.weight=HTp1.weight+HTp2.weight; HC=(hfmcode)malloc(n+1)*sizeof(char *);cd=(char *)malloc(n*sizeof(char);cdn-1=0;for(i=1

5、;i=n;+i)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c) / 建立霍夫曼树 / 当前字符的父节点下标 cd-start=0;cd-start=1;code_lengthi+=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd); Create_hfmtree(); /* double Ave_Code_Length() / 初始化 编码效率分析模块 */ 求平均编码长度 double Ave_L=0.0;fo

6、r(int i=1;i=n;i+)Ave_L+=code_lengthi*HTi.weight; return Ave_L; double To_Get_H() for(int i=1;i=n;i+)H+=-1*HTi.weight*log(HTi.weight)/log(2); double To_Get_Code_Efficiency() Ave_L=Ave_Code_Length(); / 分析结果输出void Output() Ave_L=Ave_Code_Length();H2=To_Get_Code_Efficiency(); for(int i=1;i=n;i+)coutHTi.

7、chcode_lengthiHCiendl; cout编码效率 E=（H2/H2max）*100%=H2*100%endl;/* 编码模块 */ 字符串合理性检测int Message_Str_Check(string temp)int flag=1; / 先假设输入的消息串不含非法字符for(int i=0;tempi!=0;i+)for(j=1;jn) / 表示出现非法字符flag=0; / 获取待编码消息串string Get_Message_Str()string temp; cintemp;flag=Message_Str_Check(temp);if(flag=0)/ 输入的消息串

8、含非法字符cout输入的消息串含非法字符 ,请重新输入 !endl;goto A; / 对输入的消息串进行编码string Get_All_Code_Str(string Message_Str)string All_Code_Str=; intj;for(int i=0;Message_Stri!=0;i+)for(j=1;j=n;j+)if(Message_Stri=HTj.ch) All_Code_Str+=HCj;return All_Code_Str;/ 输出得到的二进制序列void Output_All_Code_Str(string All_Code_Str)cout该消息串对应

9、的编码序列如下 :endl;coutAll_Code_Strendl; string Message_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);/* 译码模块 */ 检测输入的二进制序列是否含有非法字符int Binary_Str_Check(string temp) / 假设不含非法字符for(int i=0;tempi!=0;i+) if(!(tempi=0|tempi=1) / 获取待

10、译的二进制序列string Get_Binary_Str()string temp; B: couttemp;flag=Binary_Str_Check(temp);if(flag=0)/ 输入的二进制序列含非法字符cout输入的二进制序列含非法字符 ,请重新输入 !endl; goto B; string Get_Original_Message_Str(string Binary_Str,int *flag)string temp=;*flag=1; string Original_Message_Str=;for(int i=0;Binary_Stri!=0;i+)temp+=Binar

11、y_Stri;for(j=1;j=n;j+)if(HCj=temp)Original_Message_Str+=HTj.ch;temp=; cout您输入的二进制序列不可译，请重新输入 !endl; *flag=0;return Original_Message_Str;/ 输出得到的源码void Output_Original_Message_Str(string Original_Message_Str)cout该二进制序列对应的源码如下 :endl; coutOriginal_Message_Strendl; string Binary_Str,Original_Message_Str;D: Binary_Str=Get_Binary_Str();Original_Message_Str=Get_Original_Message_Str(Binary_Str,&flag); Output_Origin