1、 - 1 - 数据结构课程设计 实验报告 赫夫曼编码 实验课程名称 数据结构课程设计 专 业 班 级 11 级计科（2）班 学 生 姓 名 学 号 指 导 教 师 实 验 时 间 ： 2013 年 9 月 24 日 2013 至 2014 学年第 1 学期第 1 至 9 周 - 2 - 目目 录录 一、概述 1 二、系统分析 1 三、概要设计 2 四、详细设计 4 4.1 赫夫曼树的建立 4 4.1.1 选择选择 parent 为 0 且权值最小的两个根结点的算 法 5 4.1.2 统计字符串中字符的种类以及各类字符的个数 . 6 4.1.3 构造赫夫曼树 8 4.2 赫夫曼编码 9 4.2.
2、1 赫夫曼编码算法 . 10 4.2.2 建立正文的编码文件 . 11 五、运行与测试 . 12 六、总结与心得 . 13 1 一、概述一、概述 本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编 码生产的代码串进行译码，输出 电文字符串。 在当今信息爆炸时代， 如何采用有效的数据压缩技术节省数据文 件的存储空间和计算机网络的传送时 间越来越引起人们的重视，赫 夫曼编码正是一种应用广泛且非常有效的数据压缩技术。 二、系统分析二、系统分析 赫夫曼编码的应用很广泛， 利用赫夫曼树求得的用于通信的二进 制编码成为赫夫曼编码。树中从根到 每个叶子都有一条路径，对路 径上的各分支约定：指向左子树的
3、分支表示“0”码，指向右子树的 分支表示 “1”码，取每条路径上的“0”或“1”的序列作为和每个 叶子对应的字符的编码，这就是赫夫曼编码。 通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。 电报通信是传递文字的二进制码形式 的字符串，但在信息传递时， 总希望总长度能尽可能短，即采用最短码。 假设每种字符在电文中出现的次数为 W i ,编码长度为 L i ，电 文中有 n 种字符，则电文编码总长为W i L i 。 若将此对应到二 叉树上，W i 为叶节点的权 ，L i 为根节点到叶节点的路径长度。 2 那么，W i L i 恰好为二叉 树上带权路径长度。 因此，设计电文总长最短的二进制
4、前缀编码，就是以 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) /生
5、成 Huffman 树 void select(HufmanTree HT,int k,int int lchild,rchild,parent; HTNode; T typedef HTNode HuffmanTreem+1; 5 4.1.1 选择选择选择选择 parent 为为 0 且权值最小的两个根结点的算且权值最小的两个根结点的算 法法 void select(HuffmanTree T,int k,int *s1,int *s2) /在 HT1k中选择 parent 为 0 且权值最小的两个根结点，其 开始 结束 第 i 个结点权值 i=num? 创建赫夫曼树 输出字符统计情 第 i
6、 个根结点 i=2*num-1? i=num? 否 是 否 是 否 是 6 序号分别为 S1 和 S2 int i,j; int min1=100; for(i=1;i=k;i+)/查找 s1 if(Ti.weightmin1 min1=Ti.weight; *s1=j; min1=32767; for(i=1;i=k;i+)/查找 s2,不和 s1 相同 if(Ti.weightmin1 min1=Ti.weight; *s2=j; 4.1.2 统计字符串中字符的种类以及各类字符的个数统计字符串中字符的种类以及各类字符的个数 假设电子文件字符串全是大写字母，那么该算法的实现思想是： 先定义一个含有 26 个元素的临时整型数组，用来存储各种字母出现 7 的次数。应为大写字母的 ASCII 码与整数 126 个元素之间相差 64， 因此在算法中使用字母减去 64 作为统计数
