《数据结构课程设计》赫夫曼编码实验报告

《《数据结构课程设计》赫夫曼编码实验报告》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、《数据结构课程设计》实验报告赫夫曼编码实验课程名称数据结构课程设计专业班级11级计科（2）班学生姓名王琦学号6指导教师冯韵实验时间：2013年9月24日2013至2014学年第1学期第1至9周-2-目录一、概述1二、系统分析1三、概要设计2四、详细设计44.1赫夫曼树的建立44.1.1选择选择parent为0且权值最小的两个根结点的算法54.1.2统计字符串中字符的种类以及各类字符的个数74.1.3构造赫夫曼树84.2赫夫曼编码104.2.1赫夫曼编码算法104.2.2建立正文的编码文件11五、运行与测试12六、总结与心得13-2-一、概述本设计是对输入的一

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

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

4、文件的译码；三、概要设计voidmain()voidHufffmanEncoding(HuffmanTreeHT,HuffmanCodeHC)//编码部分char*decode(HuffmanCodeHc)//译码voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[])//生成Huffman树voidselect(HufmanTreeHT,intk,int&s1,int&s2)//找寻parent为0,权最小的两个节点13其流程图如下：进行相应的操作输出结果结束构造赫夫曼树程序结束退出对

5、编码串译码对字符串编码开始进行相应的操作13四、详细设计4.1赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含根节点的二叉树。算法的第二步是：将当前森林中的两颗根节点的二叉树，合并成一颗新的二叉树；每合并一次，森林中就减少一棵树，产生一个新节点。显然要进行n-1次合并，所以共产生n-1个新节点，它们都是具有两个孩子分支结点。由此可知，最新求得的赫夫曼树中一共有2n-1个结点，其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们可用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。因此，赫夫曼树的存储结构描述为：#de

6、finen100#definem2*n-1typedefstruct{intweight;intlchild,rchild,parent;}HTNode;TtypedefHTNodeHuffmanTree[m+1];13开始结束第i个结点权值i=num?创建赫夫曼树输出字符统计情况第i个根结点i=2*num-1?i=num?否是否是否是4.1.1选择选择parent为0且权值最小的两个根结点的算法voidselect(HuffmanTreeT,intk,int*s1,int*s2){//在HT[1……k]中选择parent为0且权值最小的两个根结点，其序号分

7、别为S1和S213inti,j;intmin1=100;for(i=1;i<=k;i++)//查找s1if(T[i].weight

8、法的实现思想是：先定义一个含有26个元素的临时整型数