Huffman课程设计.doc

中南林业科技大学 本科课程设计说明书 学　 院： 理学院 专业年级： 信息与计算科学 课 程： 信息论与编码 设计(论文)题目： Huffman编码的设计与实现 指导教师： 龚志伟老师 2011年05月 学生姓名： 丁洁 学 号： 分 工： 学生姓名： 李慧芳 学 号： 分 工： 学生姓名： 张瑜 学 号： 分 工： 学生姓名： 黄文亮 学 号： 分 工： 学生姓名： 唐明章 学 号： 分 工： 引言 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。它在很多领域有着广泛的应用，是一种带权路径长度最短的树。从中你会发现一些数据出现的频率作为权值赋给哈弗曼树中的结点。根据建立好的哈夫曼树我们进行编码，从根据结点出发在左子树则标为0，右则标为1。直到到指定的叶子结点，然后将遍历过程中标记的0,1代码存在一个数组中。以此实现将使用频率高的字符的编码尽可能的少，也就使得总的长度减少。在哈夫曼编码的基础上进行编码，就可以还原压缩的数据。 哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩通常在20%~90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。 哈夫曼算法构造的扩充二叉树称为哈夫曼编码树或哈夫曼树。当然，还有编码和译码部分。本系统的前端开发工具是Visual C++6.0。具有输入字符集大小及权值大小，构造哈夫曼树，并对用户输入的字符串进行编码以及译码还有退出四种功能。本程序经过测试后，功能均能实现，运行稳定。 哈夫曼编码是最佳变长编码的一种。 目录 一.设计目的 3 二.需求分析 5 2.1哈夫曼编码/译码器简介 5 2.2需求分析 5 三. Huffman内容简介.........................................................5 四.概要设计 6 4.1问题分析哈夫曼树的定义 6 4.2 流程图....................................................................7 五.详细设计 8 5.1 源代码 8 5.2运行结果 9 六.总结 10 七.参考文献........................................................................10 一、设计目的： 了解Huffman编码的基本原理及其特点 熟练掌握Huffman编码 哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，在编码中若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。 数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。