哈夫曼编码和译码系统

题目：哈夫曼编码和译码系统院系：专业：姓名：学号：指导教师：日期：实训报告目录一、前言..............................................1二、需求分析.........................................11.问题描述..............................................12.基本要求.............................................13.根据需求，该系统应具备以下功能......................2.三、概要设计.........................................21.哈夫曼编码和译码的方法概述..............................22.流程图.................................................3四、详细设计.........................................41.用类来定义变量和函数................................42.构造哈夫曼树.........................................53.根据哈夫曼树进行哈夫曼编码..........................64.输出对应的哈夫曼编码表..............................75.对输入的字符进行编码................................86.对输入的编码进行译码................................97.主函数..............................................10五、调试分析........................................13六、实验总结........................................161一、前言在这个信息高速发展的时代，每时每刻都进行着大量的信息传递，到处都离不开信息，它贯穿在人们日常的生活之中，对人们产生的影响日趋扩大，而利用哈夫曼码进行通信则可以大大提高信道利用率，缩短通信传输时间，降低传输成本。在生产中则可以更大可能的降低成本从而获得更大里润，这也是信息时代发展的趋势所在。本次实训设计的是哈夫曼编码和译码系统，建立一个简易的系统，对于给定的一篇英文文章，统计字符出现的概率，并根据概率建立Huffman树，利用Huffman编码对文章进行编码和译码。掌握Huffman树的建立与应用，并进一步熟练掌握程序的设计流程。这是个拥有完整功能的系统程序，对将所学到的知识运用到实践中，在设计的同时，培养了学生各方面的能力。二、需求分析1.问题描述在传送电文时，人们总是希望传送时间尽可能短，这就是要求使电文代码长度尽可能短。利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统能够对待传输数据预先编码，在接收端将传来的数据进行译码，所以为这样的信息收发站写一个哈夫曼的编译码系统。2.基本要求输入一段英文原文，构造哈夫曼树，生成对应的编码表，输出原文对应的编码，或者是根据已生成的编码表，输入一段二进制数编码，得2到对应的字符原文。3.根据需求，该系统应具备以下功能对给出的字符以及字符的权值构造哈夫曼树，生成对应的编码表输入一段原文，对原文进行编码输入二进制编码，输出对应的原文三、概要设计1.哈夫曼编码和译码的方法概述初始化，每个字符就是一个结点，对应节点的权值大小，选取权值最小的两个结点，以它们为儿子，构造出一个新的结点；新结点的权值就是它两个儿子的权值之和；构造之后，从原来的结点序列里删除刚才选出的那两个结点，但同时将新生成的结点加进去；如果结点序列里只剩下一个结点，表示构造完毕，退出。否则回到第一步。对某个结点而言，其左孩子在当前阶段的编码为0，右孩子的编码为1，这样就可以通过遍历树来生成字符一一对应的编码表来到这里，基本上艰苦的已经完成了，对某个具体的字符串编码和解码就只是简单的“查表——替换”的工作了。译码：译码也是个简单的查表--替换过程。如果利用该种编码发送字符串，则它的“字符——编码”对应表也必须发送过去，然后对给出的一串编码，从左向右，将编码组合起来并查表，一旦找到有匹配的字符，则将当前的编码替换为对应的字符。因为该编码是不会出现”某一个字符的编码是另一个字符编码的3缀”这种情况的，也就是不会出现类似于“A为00而B为0010”这样的情况，所以译码出来的字符串是唯一的，而且就是原来进行编码的那一个。2.流程图CreateHCodeDispHCodeeditHCodeCreatHTHuffmanMenu()deHCode权值相加For循环直到添加完所有的节点值构成哈夫曼树取权值最小的两个节点节点新的节点权值小的至于左边，大的置于右边4四、详细设计1.用类来定义变量和函数classNode//节点类{public:friendHafuman;chardata;//结点值intweight;//权值intparent;//双亲结点intlchild;//左孩子结点intrchild;//右孩子结点voidCreateHT(Nodeht[],intn);voidCreateHCode(Nodeht[],Hafumanhcd[],intn);};classHafuman{public:friendNode;charcd[N];//存放哈夫曼码intstart;//从start开始读cd中的哈夫曼码5voidDispHCode(Nodeht[],Hafumanhcd[],intn);voideditHCode(Nodeht[],Hafumanhcd[],intn);voiddeHCode(Nodeht[],Hafumanhcd[],intn);};2.构造哈夫曼树voidNode::CreateHT(Nodeht[],intn){inti,k,lnode,rnode;intmin1,min2;for(i=0;i2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;//所有结点的相关域置初值-1for(i=n;i2*n-1;i++)//构造哈夫曼树{min1=min2=32767;//int的范围是-32768—32767lnode=rnode=-1；//记录最小权值的两个结点位置for(k=0;k=i-1;k++){if(ht[k].parent==-1)//只在尚未构造二叉树的结点中查找{if(ht[k].weightmin1)//若权值小于最小的左节点的权值{min2=min1;rnode=lnode;6min1=ht[k].weight;lnode=k;}elseif(ht[k].weightmin2){min2=ht[k].weight;rnode=k;}}}ht[lnode].parent=i;ht[rnode].parent=i;//两个最小节点的父节点是iht[i].weight=ht[lnode].weight+ht[rnode].weight;//两个最小节点的父节点权值为两个最小节点权值之和ht[i].lchild=lnode;ht[i].rchild=rnode;//父节点的左节点和右节点}}3.根据哈夫曼树进行哈夫曼编码voidNode::CreateHCode(Nodeht[],Hafumanhcd[],intn){inti,f,c;Hafumanhc;for(i=0;in;i++)//根据哈夫曼树求哈夫曼编码7{hc.start=n;c=i;f=ht[i].parent;while(f!=-1)//循序直到树根结点结束循环{if(ht[f].lchild==c)//处理左孩子结点hc.cd[hc.start--]='0';else//处理右孩子结点hc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;//start指向哈夫曼编码hc.cd[]中最开始字符hcd[i]=hc;}}4.输出对应的哈夫曼编码表voidHafuman::DispHCode(Nodeht[],Hafumanhcd[],intn){inti,k;cout输出哈夫曼编码:\n;for(i=0;in;i++)//输出data中的所有数据，即A-Z8{cout\tht[i].data:;for(k=hcd[i].start;k=n;k++)//输出所有data中数据的编码{couthcd[i].cd[k];}cout\n;}}5.对输入的字符进行编码voidHafuman::editHCode(Nodeht[],Hafumanhcd[],intn){charstring[MAXSIZE];inti,j,k;cinstring;//把要进行编码的字符串存入string数组中cout\n输出编码结果:\n;for(i=0;string[i]!='#';i++)//#为终止标志{for(j=0;jn;j++){if(string[i]==ht[j].data||string[i]==ht[j].data+32)//循环查找与输入字符相同的编号，相同的就输出这个字符的编码{for(k=hcd[j].start;k=n;k++){9couthcd[j].cd[k];}break;//输出完成后跳出当前for循环}}}}6.对输入的编码进行译码voidHafuman::deHCode(Nodeht[],Hafumanhcd[],intn)//译码函数{charcode[MAXSIZE];inti,j,k,m,x,Knum=50;cincode;//把要进行译码的字符串存入code数组中while(code[0]!='#')for(i=0;in;i++){m=0;//m为想同编码个数的计数器for(k=hcd[i].start,j=0;k=n;k++,j++)//j为记录所存储这个字符的编码个数if(code[j]==hcd[i].cd[k])//当有相同编码时m值加110m++;}if(m==j)//当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据{coutht[i].data;for(x=0;code[x-1]!='#';x++)//把已经使用过的code数组里的字符串删除{code[x]=code[x+j];}}Knum--;if(Knum1){code[0]='#';}}}7.主函数voidmain(){intn=26,i;intx,flag=1;11Nodea;Hafumanb;Charstr[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};//初始化Intfnum[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};//初始化Nodeht[M];Hafumanhcd[N];for(i=0;in;i++)//把初始化的数据存入ht结构体中{ht[i].data=str[i];ht[i].weight=fnum[i];}while(flag)//菜单函数，当flag为0时跳出循环{cout\n;cout\n*************************************************;cout\n**1--