哈夫曼编码译码报告

烟台大学计算机与控制工程学院课程设计（数据结构与OOP）设计题目：班级姓名学号指导教师成绩目录题目3TOC\o"1-5"\h\z问题描述3...基本要求3...进一步完成3...内容3基本需求3....我的设计4...算法设计4数据的存储结构4...存放哈夫曼树的存储结构：4..存放哈夫曼编码的存储结构：4..存放哈夫曼树每个节点位置的存储结构：5.生成哈弗曼树的算法5...生成哈弗曼编码的算法6..译码的算法8...打印哈弗曼树的算法9...其他算法1..0.程序正确性验证1..0.输入数据的控制1..0.打印哈弗曼树1..1.哈弗曼编码11哈弗曼译码12遇到的问题12课程设计的主要收获12对今后课程设计的建议121题目问题描述设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理项目，直到选择退出为止。基本要求1)将权值数据存放在数据文件(文件名为data.txt,位于执行程序的当前目中2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树编码：利用建好的哈夫曼树生成哈夫曼编码输出编码设字符集及频度如下表：字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811611.3进一步完成译码功能显示哈夫曼树界面设计的优化内容基本需求编写一个哈夫曼编码/译码器，次编码/译码器有两大主要功能：一是对一段文本进行编码，比如在利用电报机发送信息时，需要将文字“ABACCDA”转换成类似“00110111001”这样的二进制组成的字符串；二是对一段密文进行译码，比如在接收电报后，需要对“0101110100101”这样的二进制密文通过某种标准译码成看得懂的文字信息。另外还有一些辅助功能，比如可以打印一些简单的哈夫曼树的简图、有基本的主菜单、简洁的操作界面、文件的读写。.我的设计哈夫曼编码/译码器主要有五个功能：初步编码、文件编码、手动译码、文件译码、退出。初步编码：实现基本的编码，打印简单的哈夫曼树。输入N个字符和N个权值，输出每个字符对应的编码并打印哈夫曼树。注意此功能只是对哈夫曼编码的初探，只完成了生成哈夫曼树和哈夫曼编码的功能并没有实现文件的编码。文件编码：对一个特定的文件进行编码，注意编码标准可以使用保存在data.txt中的默认标准也可以使用自己定义的标准。手动译码：对手动输入的密文进行译码，译码标准可自定义或默认。文件译码：对存放密文的文件进行译码，与手动译码的主要区别就是在密文的获取方法上。退出：哈夫曼编码/译码器运行结束。算法设计数据的存储结构存放哈夫曼树的存储结构：typedefstruct//存放树节点{chardata;//节点代表的字符intweight;//权值intparent;//父节点intlchild;//左孩子节点intrchild;//右孩子节点}HTNode;存放哈夫曼编码的存储结构：typedefstruct//存放编码{charcd[60];//intstart;//编码在数组中的开始下标}HCode;存放哈夫曼树每个节点位置的存储结构:typedefstruct〃节点位置|chardata;intn;〃在完全二叉树中的位置序号}tree;此存储结构的主要目的是记录哈弗曼树的每一个节点在完全二叉树上的位置序号，便于输出哈弗曼树的大致图形。生成哈弗曼树的算法算法思想：先将存有每个节点权值和数据的数组初始化，将每个节点的左右节点和父节点初始化为-1,保证每个节点都是独立的。假设有n个节点，在建树时需要比较n-l次；在每一次的比较中，先找出两个权值最小的节点，将这两个节点作为孩子节点形成一个双亲节点并修改相应的属性值，形成的双亲节点的权值等于两孩子节点的和，双亲节点继续参加下一次的比较。最后得到的那个节点就是树的根节点。算法流程图：代码实现:voidCreateHT(intn,HTNodeht[60])//构造哈夫曼树{inti,k,lnode,rnode;intmin1,min2;for(i=0;i<2*n-1;i++){ht[i].parent=ht[i].lchild=ht[i].rchild=-1;}for(i=n;i<2*n-1;i++){min1=min2=32767;lnode=rnode=-1;for(k=0;k<=i-1;k++)if(ht[k].parent==-1){if(ht[k].weight<min1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}elseif(ht[k].weight<min2){min2=ht[k].weight;rnode=k;}}ht[lnode].parent=i;ht[rnode].parent=i;ht[i].weight=ht[lnode].weight+ht[rnode].weight;ht[i].lchild=lnode;ht[i].rchild=rnode;}}生成哈弗曼编码的算法算法思想：算法前提是哈弗曼树已经建立完成，假设有n个节点，这时每个节点都是叶子节点，只需从叶子节点向上找到根节点就可得到哈弗曼编码；此过程需要进行n次循环，在每次循环中顺着叶子节点向上遍历。如果它为左孩子它所代表的编码数组增加一个字符1，右孩子则增加一个字符0，以此规律直到找到根节点，注意编码数组是从下标为n的位置开始依次向前存的。算法流程图:算法流程图:代码实现：voidCreateHCode(intn,HTNodeht[60],HCode辰~[60])〃得到哈弗曼编码{inti,f,c;HCodehc;for(i=0;i<n;i++){hc.start=n;c=i;f=ht[i].parent;while(f!=-1){if(ht[f].lchild==c)hc.cd[hc.start--]='0';elsehc.cd[hc.start--]='1';c=f;f=ht[f].parent;)hc.start++;hcd[i]=hc;))译码的算法算法思想：算法前提是哈弗曼树已经建立完成，假设待译码的密文为"01010101001010",这时就可以利用密文和哈弗曼树进行译码；密文从开头开始，哈弗曼树从根节点开始一一对应向前向下推进，如果密文为0则向该节点的右节点推进，为1则向左节点推进，当走到叶子节点时说明译码出了一个字符;之后再次返回根节点继续上一次的操作直到密文结束，注意密文必须连续且不重复使用。算法流程图:代码实现:voiddecipher(intn,HTNodeht[60],stringcode)//解码{inti,j=0;i=2*n-2;//根节点的下标cout<<"译码结果：\n";intmi=1;for(intj=0;j<code.length();j++){if(code[j]=='0')i=ht[i].lchild;//向下左elseif(code[j]=='1')i=ht[i].rchild;//向下右else{mi=0;break;}if(ht[i].lchild==-1){cout<<ht[i].data;i=2*n-2;}}if(mi==0)cout<<"密文有误也”；if(ht[i].lchild!=-1&&i!=2*n-2)cout<<"密文不完整\n”;}打印哈弗曼树的算法算法思想:要想打印哈弗曼树的大致图形，首先要计算出哈弗曼树的每个节点在相应的二叉树中的序号，然后是控制节点间的空格和每行开始的空格。节点位置通过哈弗曼编码得到，位置f初始为1,对于每个节点从编码的第一个开始依次向后，如果为0则f=f*2+1，为1则f=f*2,一直到编码结束即可算出最终位置。空格的解决方法是从最后一行到第一行节点间空格的数量分别是1、3、7.•…2%-1个，每行开头的空格分别是1、4、8……27个。算法流程图:算法流程图:其他算法除了以上复杂的算法，还有一些简单的算法。比如限制输入的算法，只有当控制台输入某几个特定的字符时才会做出相应的反应;数据拆分算法，将从文件读入的数据进行拆分,把数字和非数字分别存入各自的数组里。4程序正确性验证输入数据的控制图1:主界面选择控制；1：返回主界面2.退出I请选择；图2：返回界面控制图3：编码标准选择控制运行解释：在主界面只有输入0-4中的数程序才会执行，返回界面也是如此;在选择Y或N时只有输入Y或N时程序才能。打印哈弗曼树图3:哈弗曼树的简图运行解释：我写的算法只有当节点较少时，才能看出哈弗曼树的大致图形。详情请见3.5。哈弗曼编码图4：哈弗曼编码运行解释：当文件不存在时程序会提示重试，data.txt文件中存的是字符和字符的权值，也可以用自定义的编码标准，data3.txt中存的是待编码的字符。哈弗曼译码请输入您的选择:4待译码文件（格式例如山出、一、文件名或文件名£在程序目录下codel.txt科X译码标准存放在*七a.七*七文件中是否使用该标准N/N3*码保存至《格式例如「：3、・・、文件名或文件名《在程序目录下〉〉:yin仇・tKt译码结果；小£小完整运行解释：如果要翻译的密文不完整，则会提示;5遇到的问题这次的实验还算顺利，没有遇到太大的问题。刚开始对哈弗曼编码/译码的算法不是太了解，入手比较困难，但通过努力现在已经熟练掌握；再一个是文件读写的知识有点遗忘，浪费了点时间。我觉得打印哈弗曼树的那部分比较麻烦点，因为有些规律需要找，比如每行开头空几个空格才合适、节点间的空格是几个、节点什么时候输出才正确。最后我要强调一个重