数据结构课程设计之赫夫曼编码的应用

《数据结构课程设计之赫夫曼编码的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、学生课程设计题目：赫夫曼编码的应用学生姓名：赵旺学号：124090102042所在院(系)：计算机与信息科学学院专业：2012级计算机科学与技术班级：(二）指导教师：冯韵2014年9月24日目录一、概述1二、系统分析1三、概要设计2四、详细设计44.1赫夫曼树的建立44.1.1选择选择parent为0且权值最小的两个根结点的算法54.1.2统计字符串中字符的种类以及各类字符的个数74.1.3构造赫夫曼树84.2赫夫曼编码104.2.1赫夫曼编码算法104.2.2建立正文的编码文件114.3代码文件的译码12五、运行与测试14六、总结与心得14参考文献15附

2、录15一、概述本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生产的代码串进行译码，输出电文字符串。在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。二、系统分析赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。

3、通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi,编码长度为Li，电文中有n种字符，则电文编码总长为∑WiLi。若将此对应到二叉树上，Wi为叶节点的权，Li14为根节点到叶节点的路径长度。那么，∑WiLi恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种子符出现的频率作权，构造一刻赫夫曼树，此构造过程成为赫夫曼编码。根据设计要求和分析，要实现设计，必须实现以下方面的功能：（1）赫夫曼树的建立

4、；（2）赫夫曼编码的生成；（3）编码文件的译码；三、概要设计程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。voidmain()voidHufffmanEncoding(HuffmanTreeHT,HuffmanCodeHC)//编码部分char*decode(HuffmanCodeHc)//译码voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[])//生成Huffman树voidselect(HufmanTreeHT,intk,int&s1,int&s2

5、)//找寻parent为0,权最小的两个节点14其流程图如下：进行相应的操作输出结果结束构造赫夫曼树程序结束退出对编码串译码对字符串编码开始进行相应的操作14四、详细设计4.1赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含根节点的二叉树。算法的第二步是：将当前森林中的两颗根节点的二叉树，合并成一颗新的二叉树；每合并一次，森林中就减少一棵树，产生一个新节点。显然要进行n-1次合并，所以共产生n-1个新节点，它们都是具有两个孩子分支结点。由此可知，最新求得的赫夫曼树中一共有2n-1个结点，其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度

6、数为1的分支结点。我们可用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。因此，赫夫曼树的存储结构描述为：#definen100#definem2*n-1typedefstruct{intweight;intlchild,rchild,parent;}HTNode;TtypedefHTNodeHuffmanTree[m+1];14开始结束第i个结点权值i=num?创建赫夫曼树输出字符统计情况第i个根结点i=2*num-1?i=num?否是否是否是4.1.1选择选择parent为0且权值最小的两个根结点的算法voidselect(HuffmanTreeT

7、,intk,int*s1,int*s2){//在HT[1……k]中选择parent为0且权值最小的两个根结点，其序号分别为S1和S214inti,j;intmin1=100;for(i=1;i<=k;i++)//查找s1if(T[i].weight

8、ht;}*s2=j;}144.1.2统计字符串中字符的种类以及各类