C++实现哈夫曼编码完整代码.doc

《C++实现哈夫曼编码完整代码.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#includeusingnamespacestd;#includetypedefstruct{//霍夫曼树的结构体charch;doubleweight;//权值，此处为概率intparent,lchild,rchild;}htnode,*hfmtree;typedefchar**hfmcode;/*****************************全局变量*****************************/hfmtreeHT;hfmcodeHC;int

2、n=0;//霍夫曼树叶节点个数intm=0;//霍夫曼树所有节点个数int*code_length;//用于记录每个消息字符的码长/*****************************霍夫曼编码模块*****************************///对输入的字符进行检验intInput_Char_Check(){intflag=1;intj;for(inti=1;i

3、lag;}//对输入的概率进行检测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为

4、止，权值最小和次小且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

5、ight&&HT[i].parent==0&&x!=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)

6、

7、n<=1)//若输入的不是整数，则报错{cout<<"您输入的数据有误，程序终止!"<

8、ode_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_c

9、h;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<<"出现相同字符，输入错误，请重新输入!"<

10、<<"概率之和超过1，输入错误，请重新输入!"<