基于.哈夫曼编码的通信系统的设计和实现的分析.docx
河北工业大学?数据构造?课程实验实验报告题目：基于哈夫曼编码的通信系统的设计与实现专业：计算机科学与技术班级：计1301班姓名：张路浩刘禄源刘磊波李浩川邹博睿王超完成日期：2015113一、试验内容1初始化处理：建设通信系统1建设有100句中文的信息集合，每个句子称为一条信息。2输入编码参数：从终端输入编码字符集大小n,字符编码长度m设n为4,m为8；从终端输入编码字符设为A,B,C,D；3生成每条信息的字符编码，构造字符编码集合；4计算每个字符在字符编码集合中出现的概率；5根据字符概率构造哈夫曼树，求出每个字符的二进制编码。2）发送端信息编码1用户从信息集合中选择一条信息，找到该信息对应的字符编码；2根据该信息的字符编码，哈夫曼树求出的每个字符的二进制编码，构造出该信息的二进制编码，记录该二进制编码。由于是软件模拟，没有发送设备，发送端的编码工作完成。3承受端信息译码1根据得到的信息的二进制编码，利用哈夫曼树求出的每个字符的二进制编码，复原出信息的字符编码；2根据信息的字符编码，找到对应的信息。5、实现提示1本试验涉及到通讯学科的编码理论和信息学科的数据压缩技术。2根据参数生成的通信系统的所有信息的有效存储问题。3信息字符编码可参考随机数的方式生成，且要求保持唯一性二、试验目的(叉树的存储构造及其相关操作。造哈夫曼树的基本思想，及其编码/译码过程O三、流程明设置随机数种子srand(time(NULL)通过随机数函数对汉字信息用字符集进展编码pswi定义汉字信息stringmessage10定义字符集大小n输入n输入字符集内容HT. HFMTree i. word用字符集对信息进展字符编码voidCreatCode(HCodeTypeAHT, int n)统计汉字信息字符编码中各字符出现输入编码长度P的频度HT. HFMTree k. weightV根据各字符构的频度构造哈夫曼树CreatHFMTree(HT, n)指针初始化HT. HFMTreei. parent - -1;HT. HFKTreei.rchiId = -1;HT. HFMTrfi. Inhild = -1:哈夫曼编码CreatHFMCode(HTtHFMCode, n);->将各信息的字符编码进展哈弗曼树编码链接父节点和兄弟结点.i+i<2n-l造逐个非叶结点构寻找具有最小,次小值的根建树父指针为空原来的最小变为次小,/四、吃完毕码记下新的最人记下新的次小值一比原来的次小还小比原来最小的肥小输出文字信息和对应的哈夫曼编码#incIude<iostream>#include<cstdlib>#include<ctime>#include<string>usingnamespacestd；constintn=4;/叶子节点个数constintMAXVALUE=9999;intm,p;编码参数stringI;intsize；构造哈夫曼树结点typedefstruct(intWeight；权值intParent；父节点intIChild；左子树intrchiId；/右子树charWOrd；/编码字符HNodeType;构造哈夫曼编码数组typedefstruct(HNodeTypeHFMTree2*nT；结点数intbitn；intstart；HCodeType;HCodeTypeHT；HCodeTypeHFMCoden；stringmessage10=("人之初"),"性本善性相近",("习相远苟不教性乃迁教之道贵以专"),("昔孟母择邻处“;stringpsw10;存储编码对信息进展编码voidCreatCode(HCodeType&HT,intn)(inti,j,k；charch；/存储编码的字符集权重初始化for(i=0;i<2*n-1；i+)HT.HFMTreei.weight=O;)CoUt<<"请输入编码字符集的大小：m=cin>>m;cout<<”请输入编码长度大小:P=cin>>p;CoUt<<"请输入编码字符："<<endI;for(i=0；i<m；i+)cin>>HT.HFMTreei.word；J对汉字信息进展编码srand(time(NULL)；CoUat«,*,endI;CoUt<<"生成的编码为：,<<endl;for(i=0；i<10;i+)for(j=0；j<p;j+)ch=HT.HFMTreerandO%m.word；pswi+=ch;for(k=O；k<m；k+)if(ch=HT.HFMTreek.word)HT.HFMTreek.weight+；)if(i>O&&pswi=pswi-1)i；)elsecout<<messagei<<":"<<pswi<<endI;JCoUt<<"各字符出现的频度为:"<<endI；for(i=O；i<m；i+)cout<<HT.HFMTreei.WOrd<<"出现的频度为:',<<HT.HFMTreei.weight<<endI；J)创立哈弗曼树voidCreatHFMTree(HCodeType&HT,intn)Iinti,j;intml,x1,m2,x2;for(i=0；i<2*n-1；i+)HT.HFMTreei.parent=-1；HT.HFMTreei.rchiId=-1;HT.HFMTreei.Ichild=-1;)for(i=0；i<n-1；i+)I×1=×2=maxvalue；m1=m2=O;for(j=0；j<n+i;j+)if(HT.HFMTreej.parent=-1&&HT.HFMTreej.weight<x1)x2=×1；m2=ml；×1=HT.HFMTreej.weight；ml=j;Jelseif(HT.HFMTreej.parent=-1&&HT.HFMTreej.weight<×2)×2=HT.HFMTreej.weight；m2=j；J)HT.HFMTreeml.parent=n+i；HT.HFMTreem2.parent=n+i;HT.HFMTreen+i.weight=HT.HFMTreeml.weight+HT.HFMTreem2.weight；HT.HFMTreen+i.IchiId=m1;HT.HFMTreen+i.rchiId=m2;JCOUt«"*"<<end；COUt<<"构造的哈弗曼树为八n"for(i=0；i<(2*n-1);i+)cout<<i<<,'字符"«HT.HFMTreei.word<<"的权重:',<<HT.HFMTreei.weight<<"父结点的位置为：',<<HT.HFMTreei.parent«"左孩子的位置为："«HT.HFMTreei.IchiId«"右孩子的位置为:"«HT.HFMTreei.rchild<<endI；)对字符集编码voidCreatHFMCode(HCodeType&HT,HCodeTypeHFMCode,intn)HCodeTypecd；inti,j,c,p；for(i=0；i<n;i+)cd.start=n-1;c=i；p=HT.HFMTreei.parent；whiIe(p!=-1)if(HT.HFMTreep.Ichild=c)cd.bitcd.start=O;elseif(HT.HFMTreep.rchiId=c)cd.bitcd.start=1；cd.start-；c=p;p=HT.HFMTreec.parent;Jfor(j=cd.start+1;j<n;j+)HFMCodei.bitj=cd.bitj;HFMCodei.start=cd.start+1；JCOUt<<,*,end;cout<<"各字符的编码为："<<endI;for(i=0；i<n;i+)cout<<"字符"<<HT.HFMTreei.word<<"的编码为"for(j=2；j<n;j+)cout<<HFMCodei.bitj；Jcout<<endl;)intmain()ICOUt«"*"<<end；cout«,*欢迎使用基于哈夫曼编码的通信系统*"<<enc.COUt«"*"<<endI;stringt10；CreatCode(HT,n);对信息进展编码CreatHFMTree(HT,n);CreatHFMCode(HT,HFMCodeln);将信息进展转码COUt«"*"<<endI;cout<<"编码结果为："<<endI;for(inti=0；i<10;i+)cout<<messagei«"<>"for(intj=O;j<p;j+)for(intk=O；k<m；k+)if(pswij=HT.HFMTreek.word)for(intI=2；Kn；I+)cout<<HFMCodek.bitl;)cout<<endI;Jreturn0；五、调试过程六、结果分析
