欢迎来到天天文库
浏览记录
ID:58875040
大小:140.50 KB
页数:13页
时间:2020-09-21
《哈夫曼树及其操作-数据结构实验报告(2).doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、..电子科技大学实验报告课程名称:数据结构与算法学生:*浩学号:*************点名序号:***指导教师:钱**实验地点:基础实验大楼实验时间:2015.5.72014-2015-2学期信息与软件工程学院.....实验报告(二)学生:**浩学号:*************指导教师:钱**实验地点:科研教学楼A508实验时间:2015.5.7一、实验室名称:软件实验室二、实验项目名称:数据结构与算法—树三、实验学时:4四、实验原理:霍夫曼编码(HuffmanCoding)是一种编码方式,是一种用于无损数据压缩的熵编码(权编码)算法。1952年,DavidA.Huf
2、fman在麻省理工攻读博士时所发明的。在计算机数据处理中,霍夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个比特。二者相比,e使用了一般编码
3、的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。霍夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明霍夫曼树的WPL是最小
4、的。.....五、实验目的:本实验通过编程实现赫夫曼编码算法,使学生掌握赫夫曼树的构造方法,理解树这种数据结构的应用价值,并能熟练运用C语言的指针实现构建赫夫曼二叉树,培养理论联系实际和自主学习的能力,加强对数据结构的原理理解,提高编程水平。六、实验容:(1)实现输入的英文字符串输入,并设计算法分别统计不同字符在该字符串中出现的次数,字符要区分大小写;(2)实现赫夫曼树的构建算法;(3)遍历赫夫曼生成每个字符的二进制编码;(4)显示输出每个字母的编码。七、实验器材(设备、元器件):PC机一台,装有C或C++语言集成开发环境。八、数据结构与程序:/*************
5、*********************************************************程序名称:哈夫曼树的相关操作****程序容:生成哈夫曼树及其编码表、对字符串进行编码等****编写作者:家浩****完成时间:2015.5.15********************************************************************/#include#include#include#defineMAXSIZE10000charfile_address[10
6、0];//全局通用文件地址typedefstructhnode//哈夫曼树的节点结构定义{intweight;intlchild,rchild,parent;}THNode,*TpHTree;typedefstructhuffman_code//哈夫曼编码表的元素结构定义{intweight;//编码对应的权值.....char*pcode;//指向编码字符串的指针}THCode,*TpHcodeTab;//*************************************************************//****声明函数//**********
7、***************************************************TpHcodeTabbuild_codesheet(TpHTreepht,intleaves_num);//根据哈夫曼树得到编码表TpHTreecreate_huffman_tree(intweights[],intn);//构造哈夫曼树voidselect_mintree(TpHTree,int,int*,int*);//从森林中选择权值最小的两棵子树voiddestroy_codesheet(TpHcodeTabcodes
此文档下载收益归作者所有