哈夫曼编码实验报告.docx资源-CSDN文库

版权申诉

12 浏览量 2022-10-30 17:49:16 上传评论收藏 157KB DOCX 举报

资源推荐

资源详情

资源评论

实验一哈夫曼编码

一、实验目的

1、掌握哈夫曼编码原理；

2、熟练掌握哈夫曼树的生成方法；

3、理解数据编码压缩和译码输出编码的实现。

二、实验要求

实现哈夫曼编码和译码的生成算法。

三、实验内容

先统计要压缩编码的文件中的字符字母出现的次数，按字符字母和空格出现的概率对其

进行哈夫曼编码，然后读入要编码的文件，编码后存入另一个文件；接着再调出编码后的文

件，并对其进行译码输出，最后存入另一个文件中。

五、实验原理

1、哈夫曼树的定义：假设有n 个权值，试构造一颗有 n 个叶子节点的二叉树，每个叶子带

权值为 wi，其中树带权路径最小的二叉树成为哈夫曼树或者最优二叉树；

2、哈夫曼树的构造：

weight 为输入的频率数组，把其中的值赋给依次建立的HT Node 对象中的 data 属性，

即每一个 HT Node 对应一个输入的频率。然后根据 data 属性按从小到大顺序排序，每次从

data 取出两个最小和此次小的 HT Node，将他们的 data 相加，构造出新的 HTNode 作为

他们的父节点，指针 parent，leftchild，rightchild 赋相应值。在把这个新的节点插入最小堆。

按此步骤可以构造构造出一棵哈夫曼树。

通过已经构造出的哈夫曼树，自底向上，由频率节点开始向上寻找parent,直到 parent

为树的顶点为止。这样，根据每次向上搜索后，原节点为父节点的左孩子还是右孩子，来记

录 1 或 0，这样，每个频率都会有一个 01 编码与之唯一对应，并且任何编码没有前局部是

同其他完整编码一样的。

六、实验流程

① 初始化，统计文本文件中各字符的个数作为权值,生成哈夫曼树；

② 根据符号概率的大小按由大到小顺序对符号进行排序；

③ 把概率最小的两个符号组成一个节点；

④ 重复步骤〔2〕〔3〕，直到概率和为 1；

⑤ 从根节点开始到相应于每个符号的“树叶〞，概率大的标“0〞，概率小的标“1〞；

⑥ 从根节点开始，对符号进行编码；

⑦ 译码时流程逆向进行，从文件中读出哈夫曼树,并利用哈夫曼树将编码序列解码。

七、实验程序

#include<iostream>

#include<fstream>

#include<iomanip>

#include<vector>

1

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余6页未读，立即下载

内容反馈

版权申诉

G11176593

粉丝: 6690
资源: 3万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip