数据结构哈夫曼编码实验报告 - CSDN文库

哈夫曼编码

需积分: 36 77 浏览量更新于2023-05-20 9 收藏 65KB DOC 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源推荐

数据结构实验报告

―― 实验五简单哈夫曼编/译码的设计与实现

本实验的目的是通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结

构在实际问题中的应用。此实验可以作为综合实验，阶段性实验时可以选择其中的几

个功能来设计和实现。

一、【问题描述】

利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成

本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数

据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能：

1、接收原始数据。

从终端读入字符集大小 n，以及 n 个字符和 n 个权值，建立哈夫曼树，并将它存于文件

nodedata.dat 中。

2、编码。

利用已建好的哈夫曼树（如不在内存，则从文件 nodedata.dat 中读入），对文件中的正

文进行编码，然后将结果存入文件 code.dat 中。

3、译码。利用已建好的哈夫曼树将文件 code.dat 中的代码进行译码，结果存入文件

textfile.dat 中。

4、打印编码规则。

即字符与编码的一一对应关系。

二、【数据结构设计】

1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。

在构造哈夫曼树时，设计一个结构体数组 HuffNode 保存哈夫曼树中各结点的信息，根

据二叉树的性质可知，具有 n 个叶子结点的哈夫曼树共有 2n-1 个结点，所以数组 HuffNode

的大小设置为 2n-1，描述结点的数据类型为：

typedef struct

{

int weight;//结点权值

int parent;

int lchild;

int rchild;

char inf;

}HNodeType;

2、求哈夫曼编码时使用一维结构数组 HuffCode 作为哈夫曼编码信息的存储。

求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲

链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码

值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成

的 0、1 序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码

的高位码，所以设计如下数据类型：

#define MAXBIT 10

typedef struct

{

int bit[MAXBIT]；

int start；

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

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

MyXinF

粉丝: 0
资源: 1

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

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