哈夫曼编码译码器.doc

《哈夫曼编码译码器.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、哈夫曼编码译码器学院班级:信息工程学院软件1501指导教师:朱俊武小组成员:刘洋蒋佳烨冀若含本人学号:151303107报告书写:冀若含学生成绩:20/20目录一、总体介绍·····························03-04二、详细设计·····························04-11三、运行测试·····························11-12四、课设总结·····························13-13五、附录代码·····················

2、········13-1920/20一、总体介绍1.1任务概述我们小组做了两个版本，其中一个为文件操作版，另一个为键盘操作版。两个版本都实现了哈夫曼编码/译码操做。我主要负责的是构造哈夫曼树，给出各个字符的哈夫曼编码，加密操做，整个键盘操作版系统的代码重组、编辑。开发的过程中使用了Codelite、Dev、Vc等软件。参考书籍为《数据结构》（c语言版）。其中文件操作版的具体实现为：能够实现对26个小写字母外加空格进行哈夫曼编码，并能够对一整篇文章（有小写字母和空格组成）进行加密，生成密码文件。最后根据生成的密码翻译出原文并存档。

3、在使用程序时，使用者只需要对ToBetran20/20文件进行原文的输入（使用小写字母或空格），加密和解密功能由程序自主来完成。程序运行的过程中会输出进行编码的26个小写字母和空格（字符型），并输出其对应的权值（整型）。还输出字符的编码及生成的密文。最后输出解密后的原文。键盘操作版为：要求从键盘输入字符集和字符的权值，大部分字符均可输入，需要各个字符的权值不能相同。利用输入的权值建立哈夫曼树，得到每个字符的前缀编码。输入字符串，程序对其进行加密。输入密文（1010101……………..）对密文进行解密。两个版本都利用了哈夫曼树解决

4、问题，通过建立哈夫曼树，得出每个字符的独特前缀编码，也就是密文，然后利用密文对明文进行加密得到密文。密文转换为明文则是通过对哈夫曼树的遍历。（之前想过字符串的匹配得到明文但是算法太为复杂）。1.2系统功能框图本系统分为三个大的模块：构造哈夫曼树，编码，译码。20/201.3功能难点本系统的实现难点在于哈夫曼树的构造。编码、译码功能的实现都是基于哈夫曼树的。二、详细设计2.1哈夫曼树的构造哈夫曼树，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。哈夫曼树的构造过程如下：1.初始化：根据给定的n个权值{w1,w2,…wn}构

5、成n棵二叉树的集合F={T1,T2,..,Tn}，其中每棵二叉树Ti中只有一个带权wi的根节点，左右子树均空。2.找最小树：在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3.删除与加入：在F中删除这两棵树，并将新的二叉树加入F中。4.判断：重复前两步（2和3），直到F中只含有一棵树为止。该树即为哈夫曼树。2.2代码实现哈夫曼树和哈夫曼编码的储存表示typedefstruct{intweight;intparent,lchild,rchild;}HTNo

6、de,*HuffmanTree;//动态分配数组储存哈夫曼树20/20typedefchar**HuffmanCode;//动态分配数组储存哈夫曼编码表voidSelect(HuffmanTreeHT,intp,int*s1,int*s2)该函数的功能为：找出HT[1….i-1]中parent为0且weight最小的两个结点，其序号为s1，s2。voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a)该函数的功能为构造哈夫曼树HT，并求出n个字符的哈夫曼编码

7、HC。以下为两个函数的流程图或详细设计。voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a)20/20指针a指向输入的字符集，指针w指向字符集的度，n为字符集的大小。注：具体程序中加入了输出各个字符的哈夫曼编码的功能，在流程图没有显示。没画完下面还有哟！！！！20/20详细代码：voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a){intm=0;intc;intf;intstar

8、t;char*cd;int*s1;int*s2;inti;s1=(int*)malloc(sizeof(int));s2=(int*)malloc(sizeof(int));m=2*n-1;if(n<=1){printf("字符的个数过少");return;