哈夫曼编码译码报告

烟台大学计算机与控制工程学院课程设计（数据结构与OOP）设计题目：班级姓名学号指导教师成绩年月日目录1题目............................................................................................................................31.1问题描述..........................................................................................................31.2基本要求..........................................................................................................31.3进一步完成......................................................................................................32内容............................................................................................................................32.1基本需求..........................................................................................................32.2.我的设计.........................................................................................................43算法设计....................................................................................................................43.1数据的存储结构..............................................................................................43.1.1存放哈夫曼树的存储结构：................................................................43.1.2存放哈夫曼编码的存储结构：............................................................43.1.3存放哈夫曼树每个节点位置的存储结构：........................................53.2生成哈弗曼树的算法......................................................................................53.3生成哈弗曼编码的算法..................................................................................63.4译码的算法......................................................................................................83.5打印哈弗曼树的算法......................................................................................93.6其他算法........................................................................................................104程序正确性验证......................................................................................................104.1输入数据的控制............................................................................................104.2打印哈弗曼树................................................................................................114.3哈弗曼编码....................................................................................................114.4哈弗曼译码....................................................................................................125遇到的问题..............................................................................................................126课程设计的主要收获..............................................................................................127对今后课程设计的建议..........................................................................................121题目1.1问题描述设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理项目，直到选择退出为止。1.2基本要求1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目中2)分别采用动态和静态存储结构3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树4)编码：利用建好的哈夫曼树生成哈夫曼编码5)输出编码6)设字符集及频度如下表：字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811611.3进一步完成1)译码功能2)显示哈夫曼树3)界面设计的优化2内容2.1基本需求编写一个哈夫曼编码/译码器，次编码/译码器有两大主要功能：一是对一段文本进行编码，比如在利用电报机发送信息时，需要将文字“ABACCDA”转换成类似“00110111001”这样的二进制组成的字符串；二是对一段密文进行译码，比如在接收电报后，需要对“0101110100101”这样的二进制密文通过某种标准译码成看得懂的文字信息。另外还有一些辅助功能，比如可以打印一些简单的哈夫曼树的简图、有基本的主菜单、简洁的操作界面、文件的读写。2.2.我的设计哈夫曼编码/译码器主要有五个功能：初步编码、文件编码、手动译码、文件译码、退出。初步编码：实现基本的编码，打印简单的哈夫曼树。输入N个字符和N个权值，输出每个字符对应的编码并打印哈夫曼树。注意此功能只是对哈夫曼编码的初探，只完成了生成哈夫曼树和哈夫曼编码的功能并没有实现文件的编码。文件编码：对一个特定的文件进行编码，注意编码标准可以使用保存在data.txt中的默认标准也可以使用自己定义的标准。手动译码：对手动输入的密文进行译码，译码标准可自定义或默认。文件译码：对存放密文的文件进行译码，与手动译码的主要区别就是在密文的获取方法上。退出：哈夫曼编码/译码器运行结束。3算法设计3.1数据的存储结构3.1.1存放哈夫曼树的存储结构：typedefstruct//存放树节点{chardata;//节点代表的字符intweight;//权值intparent;//父节点intlchild;//左孩子节点intrchild;//右孩子节点}HTNode;3.1.2存放哈夫曼编码的存储结构：typedefstruct//存放编码{charcd[60];//intstart;//编码在数组中的开始下标}HCode;3.1.3存放哈夫曼树每个节点位置的存储结构：typedefstruct//节点位置{chardata;intn;//在完全二叉树中的位置序号}tree;此存储结构的主要目的是记录哈弗曼树的每一个节点在完全二叉树上的位置序号，便于输出哈弗曼树的大致图形。3.2生成哈弗曼树的算法算法思想：先将存有每个节点权值和数据的数组初始化，将每个节点的左右节点和父节点初始化为-1，保证每个节点都是独立的。假设有n个节点，在建树时需要比较n-1次；在每一次的比较中，先找出两个权值最小的节点，将这两个节点作为孩子节点形成一个双亲节点并修改相应的属性值，形成的双亲节点的权值等于两孩子节点的和，双亲节点继续参加下一次的比较。最后得到的那个节点就是树的根节点。算法流程图：代码实现:voidCreateHT(intn,HTNodeht[60])//构造哈夫曼树{inti,k,lnode,rnode;intmin1,min2;for(i=0;i2*n-1;i++){ht[i].parent=ht[i].lchild=ht[i].rchild=-1;}for(i=n;i2*n-1;i++){min1=min2=32767;lnode=rnode=-1;for(k=0;k=i-1;k++)if(ht[k].parent==-1){if(ht[k].weightmin1){min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k;}elseif(ht[k].weightmin2){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;}}3.3生成哈弗曼编码的算法算法思想：算法前提是哈弗曼树已经建立完成，假设有n个节点，这时每个节点都是叶子节点，只需从叶子节点向上找到根节点就可得到哈弗曼编码；此过程需要进行n次循环，在每次循环中顺着叶子节点向上遍历。如果它为左孩子它所代表的编码数组增加一个字符1，右孩子则增加一个字符0，以此规律直到找到根节点，注意编码数组是从下标为n的位置开始依次向前存的。算法流程图：代码实现:voidCreateHCode(intn,HTNodeht[60],HCodehcd[60])//得到哈弗曼编码{inti,f,c;HCodehc;for(i=0;in;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