哈夫曼编码译码器.doc

哈夫曼编码译码器学院班级:信息工程学院软件1501指导教师:朱俊武小组成员:刘洋蒋佳烨冀若含本人学号:151303107报告书写:冀若含学生成绩:目录一、总体介绍·····························03-04二、详细设计·····························04-11三、运行测试·····························11-12四、课设总结·····························13-13五、附录代码·····························13-19一、 我们小组做了两个版本,其中一个为文件操作版,另一个为键盘操作版。两个版本都实现了哈夫曼编码/译码操做。我主要负责的是构造哈夫曼树,给出各个字符的哈夫曼编码,加密操做,整个键盘操作版系统的代码重组、编辑。开发的过程中使用了Codelite、Dev、Vc等软件。参考书籍为《数据结构》(c语言版)。其中文件操作版的具体实现为:能够实现对26个小写字母外加空格进行哈夫曼编码,并能够对一整篇文章(有小写字母和空格组成)进行加密,生成密码文件。最后根据生成的密码翻译出原文并存档。在使用程序时,使用者只需要对ToBetran文件进行原文的输入(使用小写字母或空格),加密和解密功能由程序自主来完成。程序运行的过程中会输出进行编码的26个小写字母和空格(字符型),并输出其对应的权值(整型)。还输出字符的编码及生成的密文。最后输出解密后的原文。键盘操作版为:要求从键盘输入字符集和字符的权值,大部分字符均可输入,需要各个字符的权值不能相同。利用输入的权值建立哈夫曼树,得到每个字符的前缀编码。输入字符串,程序对其进行加密。输入密文(1010101……………..)对密文进行解密。 两个版本都利用了哈夫曼树解决问题,通过建立哈夫曼树,得出每个字符的独特前缀编码,也就是密文,然后利用密文对明文进行加密得到密文。密文转换为明文则是通过对哈夫曼树的遍历。(之前想过字符串的匹配得到明文但是算法太为复杂)。:构造哈夫曼树,编码,译码。 本系统的实现难点在于哈夫曼树的构造。编码、译码功能的实现都是基于哈夫曼树的。二、 哈夫曼树,又称最优树,是一类带权路径长度最短的树,有着广泛的应用。哈夫曼树的构造过程如下::根据给定的n个权值{w1,w2,…wn}构成n棵二叉树的集合F={T1,T2,..,Tn},其中每棵二叉树Ti中只有一个带权wi的根节点,左右子树均空。:在F中选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树,且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。:在F中删除这两棵树,并将新的二叉树加入F中。:重复前两步(2和3),直到F中只含有一棵树为止。该树即为哈夫曼树。{ intweight; intparent,lchild,rchild;}HTNode,*HuffmanTree;//动态分配数组储存哈夫曼树typedefchar**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个字符的哈夫曼编码HC。以下为两个函数的流程图或详细设计。voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a)指针a指向输入的字符集,指针w指向字符集的度,n为字符集的大小。注:具体程序中加入了输出各个字符的哈夫曼编码的功能,在流程图没有显示。没画完下面还有哟!!!!详细代码:voidHuffmanCoding(HuffmanTreeHT,HuffmanCodeHC,int*w,intn,char*a){ intm=0;intc;intf; intstart; 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("字符的个数过少\n"); return; } HuffmanTreep;