1、目 录一、实验内容2二、实验说明2三、结构体定义和程序结构的说明31.结构体定义的说明32.程序结构的说明3四、程序设计的基本思想、部分源代码及注释31.选择权值最小的两个结点4.判断结点是否已经被使用过4.选出权值为最小的结点4.选出另一个权值为最小的结点5.判断两个选出的最小权值的大小52构建哈夫曼树6.判断能否构建成哈夫曼树6.对需要处理的结点和哈夫曼树的结点进行初始化6.构建哈夫曼树6.对构建好的哈夫曼树进行遍历确定每个结点的编码73输出设置7.输出每个结点的父亲、左孩子、右孩子结点7.输出每个结点的哈夫曼编码8五、流程图六、实验结果演示七、在编写程序过程中遇到的困难和解决的方法一、实 。

2、验内容根据输入的n个带权结点 ， 构造出哈夫曼树 ， 并且把构造结果输出到屏幕 。
二、实验说明哈夫曼数 ， 也称最优二叉树 ， 是指对于一组带有确定权值的叶结点 ， 构造的具有最小带权路径长度的二叉树 。
设二叉树具有n个带权值的叶结点 ， 那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL ， 记作： WPL= 。
在给定一组具有确定权值的叶结点 ， 可以构造出不同的带权二叉树 。
根据哈夫曼树的定义 ， 一棵二叉树要使其WPL值最小 ， 必须使权值越大的叶结点越靠近根结点 ， 而权值越小的叶结点越远离根结点 。
在数据通讯中 ， 经常需要将传送的文字转换成由二进制字符0 ， 1组成的二进制串 ， 我们称之为编码 。
例如 ， 假设要 。

3、传送的电文为ABACCDA ， 电文中只含有A ， B ， C ， D四种字符 ， 若这四种字符采用下表所示的编码 ， 则电文的代码为0100111 000 ， 长度为21 。
在传送电文时 ， 我们总是希望传送时间尽可能短 ， 这就要求电文代码尽可能短 。
如果在编码时考虑字符出现的频率 ， 让出现频率高的字符采用尽可能短的编码 ， 出现频率低的字符采用稍长的编码 ， 构造一种不等长编码 ， 则电文的代码就可能更短 。
并且在建立不等长编码时 ， 必须使任何一个字符的编码都不是另一个字符编码的前缀 ， 以避免反译成原文时 ， 编码出现多义性 。
在哈夫曼编码树中 ， 树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和 ， 也就是电文的代码总长 ， 所以采用哈夫曼树构造的编 。

4、码是一种能使电文代码总长最短的不等长编码 。
采用哈夫曼树进行编码 ， 也不会产生上述二义性问题 。
因为 ， 在哈夫曼树中 ， 每个字符结点都是叶结点 ， 它们不可能在根结点到其它字符结点的路径上 ， 所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀 ， 从而保证了译码的非二义性 。
三、结构体定义和程序结构的说明1、结构体定义的说明哈夫曼树重点在于如何排列权值大小不同的结点的顺序 ， 所以定义结构体如下：typedef structint weight;
/*weight存储结点的权值*/int parent;
int lchild;
int rchild;
/*分别保存父亲、左孩子、右孩子结点*/HTNode,*Hu 。

5、ffmanTree;
而另一个重点在于将两个权值为最小的结点分别作为左、右子树 ， 所以定义结构体如下：typedef structunsigned int s1;
unsigned int s2;
/*分别存储最小和次小的结点*/MinCode;
2、程序结构的说明程序主要由以下几部分组成：结构体 struct HTNode,*Huffmantree结构体 struct MinCode函数 Select 用以选择结点中权值最小的两个结点函数 CreateTree 将选出来的结点按规律逐步建成哈夫曼树函数 main 主函数四、程序设计的基本思想、部分源代码及注释根据哈夫曼树的定义 ， 一棵二叉树要使其WPL 。

6、值最小 ， 必须使权值越大的叶结点越靠近根结点 ， 而权值越小的叶结点越远离根结点 。
因此 ， 构造哈夫曼树有此种方法：1、由给定的n个权值W1 ， W2 ， Wn构造n棵只有一个叶结点的二叉树 ， 从而得到一个二叉树的集合FT1 ， T2 ， Tn；2、在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树 ， 这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；3、在集合F中删除作为左、右子树的两棵二叉树 ， 并将新建立的二叉树加入到集合F中；4、重复（2）（3）两步 ， 当F中只剩下一棵二叉树时 ， 这棵二叉树便是所要建立的哈夫曼树 。
所以 ， 构造哈夫曼树主要由两个步骤组成：一是选择所有结点中权值最小的两个结点 ， 二 。

来源：(未知)

【学习资料】网址：/a/2021/0318/0021711234.html

标题：哈夫曼|哈夫曼编码实验报告