1 / 18
文档名称:

哈弗曼编码程序说明书.doc

格式:doc   大小:223KB   页数:18页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

哈弗曼编码程序说明书.doc

上传人:799474576 2020/3/16 文件大小:223 KB

下载得到文件列表

哈弗曼编码程序说明书.doc

文档介绍

文档介绍:哈弗码编码程序说明书姓名:班级:学号:目录一、问题定义………………………………………………1二、可行性分析……………………………………………2三、概要设计………………………………………………3四、详细设计及源码………………………………………4五、测试结果………………………………………………15六、使用手册………………………………………………16一、问题定义目前,进行快速远距离通信的主要手段之一是电报,即将需传送的文字转换为由二进制的字符组成的字符串。例如,假设需传送的电文为‘DA’,它只有4种字符,只需两个字符的串便可分辨。假设A、B、C、D的编码分别00、01、10和11,则上述7个字符的电文便为‘000**********’,总长为14位,对方接收时,可按二位一分进行译码。在传送电文时希望总长尽可能的短,如果对每个字符设计长度不等的编码,且让电文中出现次数较多的字符采用尽可能短的编码,则传送电文的总长便可减少。若要设计长短不等的编码,则必须是任一个字符的编码都不是另一个字符的编码的前缀,这种编码称为前缀编码。假设有n个权值{w[1],w[2],……,w[n]},试构造一棵有n个叶子结点的二叉树,每个叶子结点带权为w[i],则其中带权路径长度最小的二叉树称作最优二叉树或哈夫曼树。设计电文总长最短的二进制前缀编码即为以n中字符出现的频率作权,设计一棵哈夫曼树的问题,由此得到二进制前缀编码便称为哈夫曼编码。哈夫曼编码是广泛应用数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表达方式。关键字:哈弗曼编码字符权值二叉树二、可行性分析哈夫曼算法如下::typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;(或输入的字符及对应权值)结合相关算法得出各字符(或叶子结点)的权值。{w[1],w[2],……,w[n]}构成n棵二叉树的集合F={HT[1],HT[2],……,HT[n]},其中每棵二叉树T[i]中只有一个带权为w[i]的根结点,其左右子树均空。,且置新的二叉树的根结点的权值为两个小权值结点的权值之和,两个小权值结点则为新节点的左右孩子。,同时将新得到的二叉树加入F中。,直到F中只含一棵树为止。这棵树便是哈夫曼树。应用贪心算法原理可知,通过此方法得到哈夫曼编码能够使电文总长最短。三、概要设计哈弗曼编码有两种方式,第一种是已知字符及其相应权值,然后对字符编码,第二种方式是对输入的字符串进行处理,得出其中具有的的字符,并求出相应权值,然后再谁字符串编码。程序主框架如下:输入字符串统计不同字符和各个字符出现次数(作为权值)编码译码调用子过程求哈夫曼编码输出权值和编码主窗体调用子过程求哈夫曼编码输入字符及相应权值,确定编码编码译码窗体一窗体二四、++,新工程名称为“”HuffmanCode,在Step1中选择“Dialogbased”选项,其他按照默认设置。选择“Finish”。AppWizard将会自动建立一个作为应用程序主窗口的对话框模板IDD_HUFFMANCODE_DIALOG,及其对应的对话框类CHufffmanCodeDlg。。选择Insert->Resource,打开InsertResource对话框,在ResourceType中选择“Bitmap”选项,单击Import按钮,打开ImportResource对话框,浏览并选择要添加的bmp文件,单击Import按钮。依次将需要用到的位图和图标添加进去。,删除该模板上除Cancel按钮外的所有控件并根据要求和如下表的内容,向对话框模板中加入控件。控件类型ID标题其他属性静态图片IDC_STATICType列表框选择Bitmap静态图片IDC_STATICType列表框选择Bitmap选中命令按钮IDC_VALUE字符权值输入编码/译码选中Defaultbutton命令按钮IDC_TEXT文本输入编码/译码选中Defaultbutton命令按钮IDCANCEL退出选中Defaultbutton如下图:,并添加相关控件,关联成员变