哈弗曼编码程序说明书

《哈弗曼编码程序说明书》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、哈弗码编码程序说明书姓名：班级：学号：16目录一、问题定义………………………………………………1二、可行性分析……………………………………………2三、概要设计………………………………………………3四、详细设计及源码………………………………………4五、测试结果………………………………………………15六、使用手册………………………………………………1616一、问题定义目前，进行快速远距离通信的主要手段之一是电报，即将需传送的文字转换为由二进制的字符组成的字符串。例如，假设需传送的电文为‘ABCCDA

2、’，它只有4种字符，只需两个字符的串便可分辨。假设A、B、C、D的编码分别00、01、10和11，则上述7个字符的电文便为‘00010010101100’，总长为14位，对方接收时，可按二位一分进行译码。在传送电文时希望总长尽可能的短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。假设有n个权值{w[1]，w[2]，……，w[n]}，试

3、构造一棵有n个叶子结点的二叉树，每个叶子结点带权为w[i]，则其中带权路径长度最小的二叉树称作最优二叉树或哈夫曼树。设计电文总长最短的二进制前缀编码即为以n中字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到二进制前缀编码便称为哈夫曼编码。哈夫曼编码是广泛应用数据文件压缩的十分有效的编码方法。其压缩率通常在20%~90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表达方式。关键字：哈弗曼编码字符权值二叉树16二、可行性分析哈夫曼算法如下：1．构造哈弗曼树

4、结点结构如下：typedefstruct{unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;2．根据输入的字符串（或输入的字符及对应权值）结合相关算法得出各字符（或叶子结点）的权值。3．根据得到的n个权值{w[1]，w[2]，……，w[n]}构成n棵二叉树的集合F={HT[1]，HT[2]，……，HT[n]}，其中每棵二叉树T[i]中只有一个带权为w[i]

5、的根结点，其左右子树均空。4．在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为两个小权值结点的权值之和，两个小权值结点则为新节点的左右孩子。5．在F中删除这两棵树，同时将新得到的二叉树加入F中。6．重复4和5，直到F中只含一棵树为止。这棵树便是哈夫曼树。应用贪心算法原理可知，通过此方法得到哈夫曼编码能够使电文总长最短。16三、概要设计哈弗曼编码有两种方式，第一种是已知字符及其相应权值，然后对字符编码，第二种方式是对输入的字符串进行处理，得出其中具有

6、的的字符，并求出相应权值，然后再谁字符串编码。程序主框架如下：输入字符串统计不同字符和各个字符出现次数（作为权值）编码译码调用子过程求哈夫曼编码输出权值和编码主窗体调用子过程求哈夫曼编码输入字符及相应权值，确定编码编码译码窗体一窗体二16四、详细设计及源码1．利用VC++6.0的AppWizard建立一个MFC工程，新工程名称为“”HuffmanCode，在Step1中选择“Dialogbased”选项，其他按照默认设置。选择“Finish”。AppWizard将会自动建立一个作为应用程序主窗口

7、的对话框模板IDD_HUFFMANCODE_DIALOG，及其对应的对话框类CHufffmanCodeDlg。2．利用InsertResource对话框为应用程序添加位图和图标。选择Insert->Resource，打开InsertResource对话框，在ResourceType中选择“Bitmap”选项，单击Import按钮，打开ImportResource对话框，浏览并选择要添加的bmp文件，单击Import按钮。依次将需要用到的位图和图标添加进去。3．设计IDD_HUFFMANCODE_

8、DIALOG对话框模板，删除该模板上除Cancel按钮外的所有控件并根据要求和如下表的内容，向对话框模板中加入控件。控件类型ID标题其他属性静态图片IDC_STATICType列表框选择Bitmap静态图片IDC_STATICType列表框选择Bitmap选中命令按钮IDC_VALUE字符权值输入编码/译码选中Defaultbutton命令按钮IDC_TEXT文本输入编码/译码选中Defaultbutton命令按钮IDCANCEL退出选中Defaultbutton如下图：4.插入新对话框如图所示