精选哈夫曼树及其操作-数据结构试验报告

电 子 科 技 大 学实验报告课程名称：数据结构与算法学生姓名：陈* 浩学号：************* 点名序号： *** 指导教师：钱** 实验地点：基础实验大楼实验时间： 2015.5.7 2014-2015-2 学期信息与软件工程学院实验报告( 二)学生姓名： 陈** 浩学 号：*************指导教师：钱 **实验地点：科研教学楼 A508实验时间： 2015.5.7一、实验室名称： 软件实验室二、实验项目名称： 数据结构与算法—树三、实验学时： 4四、实验原理：霍夫曼编码（ Huffman Coding ）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。1952 年， David A. Huffman在麻省理工攻读博士时所发明的。在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。例如，在英文中， e 的出现机率最高，而z 的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e 极有可能用一个比特来表示，而z 则可能花去 25 个比特（不是 26）。用普通的表示方法时， 每个英文字母均占用一个字节（byte ），即 8 个比特。二者相比，e 使用了一般编码的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是最小的。五、实验目的：本实验通过编程实现赫夫曼编码算法，使学生掌握赫夫曼树的构造方法，理解树这种数据结构的应用价值，并能熟练运用 C语言的指针实现构建赫夫曼二叉树，培养理论联系实际和自主学习的能力，加强对数据结构的原理理解，提高编程水平。六、实验内容：（1）实现输入的英文字符串输入， 并设计算法分别统计不...