哈夫曼编码译码器.doc

哈夫曼编码译码器.doc

ID:55927038

大小:261.67 KB

页数:20页

时间:2020-06-15

哈夫曼编码译码器.doc_第1页
哈夫曼编码译码器.doc_第2页
哈夫曼编码译码器.doc_第3页
哈夫曼编码译码器.doc_第4页
哈夫曼编码译码器.doc_第5页
资源描述:

《哈夫曼编码译码器.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;

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。