内容发布更新时间 : 2024/11/20 2:28:11星期一 下面是文章的全部内容请认真阅读。

目 录

一、概述 ................................................. 1 二、系统分析 ............................................. 1 三、概要设计 ............................................. 2 四、详细设计 ............................................. 4 4.1 赫夫曼树的建立 .................................... 4 4.1.1 选择选择parent 为0 且权值最小的两个根结点的算法 ................................................. 5 4.1.2 统计字符串中字符的种类以及各类字符的个数 ..... 7 4.1.3构造赫夫曼树 .................................. 8 4.2赫夫曼编码 ....................................... 10 4.2.1赫夫曼编码算法 ............................... 10 4.2.2建立正文的编码文件 ........................... 11 4.3代码文件的译码 .................................... 12 五、运行与测试 .......................................... 14 六、总结与心得 .......................................... 14 参考文献 ................................................ 15 附录 .................................................... 15

一、概述

本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编

码生产的代码串进行译码，输出 电文字符串。

在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时 间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。

二、系统分析

赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。树中从根到 每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示 “1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。

通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式 的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。

假设每种字符在电文中出现的次数为W i ,编码长度为L i ，电文中有n 种字符，则电文编码总长为∑W i L i 。 若将此对应到二叉树上，W i 为叶节点的权 ，L i 为根节点到叶节点的路径长度。

1

那么，∑W i L i 恰好为二叉 树上带权路径长度。

因此，设计电文总长最短的二进制前缀编码，就是以n 种子符出现的频率作权，构造一刻赫夫曼树， 此构造过程成为赫夫曼编码。 根据设计要求和分析，要实现设计，必须实现以下方面的功能： （1） 赫夫曼树的建立； （2） 赫夫曼编码的生成； （3） 编码文件的译码；

三、概要设计

程序由哪些模块组成以及模块之间的层次结构、各模块的调用关

系；每个模块的功能。 void main()

void HufffmanEncoding(HuffmanTree HT,HuffmanCode HC)//编码部分

char *decode(HuffmanCode Hc)//译码 void

ChuffmanTree(HuffmanTree

HT,HuffmanCode

HC,int

cnt[],char str[]) //生成Huffman树

void select(HufmanTree HT,int k,int &s1,int &s2) //找寻parent为0,权最小的两个节点

2