哈夫曼编码课程设计报告().docVIP

《数据结构与算法分析》课程设计报告 课题名称： 哈夫曼编码 课题设计人： 李慧杰 学号： 指导教师： 朱宏 评阅成绩：____________________________ 评阅意见：________________________________________________________________________________________________________________________________________________________________________________________________ 提交报告时间：20 13 年 12 月 25 日 哈夫曼编码 计算机科学与技术 学生 李慧杰 指导老师 朱宏 实验三哈夫曼编码 目的与要求 .要求对文件进行Huffman编码的算法,以及对一编码文件进行解码的算法。 2.熟练掌握二叉树的应用 三、环境 1.硬件环境：Intel(R) Celeron?m CPU 520 @1.60 GHz 0.99GB 内存 2.软件环境： 操作系统：WIN 7 编译软件：MicroSoft Visual C++ 6.0 算法 1.概要设计 1. bool InitFromFile(string fileadd) 从文件中初始化哈夫曼树函数 2. void HTCreat(HTNode ht[],int n) 构造哈夫曼树函数 3. void HCCreat(HTNode ht[],HCode hcd[],int n) 构造哈夫曼编码函数 4. void ConvertFile(HCode hcd[],string fileadd,string fileadd2) 压缩and写入文件函数 5. void DecompressionFile(string fileadd2,string fileadd3) 文件解压函数 6. string Compression(string fileadd) 压缩函数 7. string Decompression(string fileadd2) 解压函数 2.压缩算法： 那么转化为Huffman树就是 Huffman树 层数 Root ┌┴┐ ACDEH BFG 1 ┌┴┐┌┴┐ CDEH A B FG 2 ┌┴┐ ┌┴┐ DEH C F G 3 ┌┴┐ DH E 4 ┌┴┐ D H 5 取左面是1 右面是0 则有。 注：层数就是位数或者说是代码长度，权值=代码长度*该字的统计次数。 代码 位数 权值 A = 10 2 16 B = 01 2 12 C = 110 3 12 D = 11111 5 5 E = 1110 4 8 F = 001 3 9 G = 000 2 6 H = 11110 5 5 可以看出Huffman代码是唯一可解的(uniquely decodable)，如果你读到110就一定是C ，不会有任何一个编码是以110开始的。 如果不使用Huffman算法，而使用普通的编码，结果是什么呢？ Huffman树 层数 Root ┌┴┐ ABCD EFGH 1 ┌┴┐ ┌┴┐ AB CD EF GH