手机网站做成app,安阳网络教研平台官网,网站开发用户需求分析,网站建设 常州题目
Huffman编码是通信系统中常用的一种不等长编码#xff0c;它的特点是#xff1a;能够使编码之后的电文长度最短。
更多关于Huffman编码的内容参考教材第十章。
输入#xff1a; 第一行为要编码的符号数量n 第二行#xff5e;第n1行为每个符号出现的频率
输…题目
Huffman编码是通信系统中常用的一种不等长编码它的特点是能够使编码之后的电文长度最短。
更多关于Huffman编码的内容参考教材第十章。
输入 第一行为要编码的符号数量n 第二行第n1行为每个符号出现的频率
输出 对应哈夫曼树的带权路径长度WPL
解释
①哈夫曼树的构造
哈夫曼树也称为最优二叉树是一种带权路径长度WPL最短的二叉树。这里的带权路径长度就是叶子节点的权值与它到根节点的路径长度之积的总和。
哈夫曼树的构造方法是基于贪心算法步骤如下
1. 将每个权值看作是独立的一棵树这些权值通常来自要编码字符的频率。
2. 在所有未构造二叉树的集合中选出两个权值最小的树作为左右子树构造出一棵新的二叉树同时这两个权值之和作为新的父节点的权值。
3. 在集合中删除这两个已经被使用的节点将新构造的二叉树父节点加入到集合中。
4. 重复其中的步骤2-3直到集合中只剩下一棵树这棵树就是最终的哈夫曼树。
哈夫曼树常见的应用是哈夫曼编码它是一种被广泛用于数据压缩的编码方式。根据哈夫曼树我们可以为叶子节点分配相应的哈夫曼编码使得编码长度短的更常见这样可以有效地减少编码的总长度达到数据压缩的目的。
②WPL的计算
带权路径长度Weighted Path Length简称 WPL它是所有叶子节点的权值乘以其到根节点的路径长度之和。
以二叉树为例叶子节点是没有子节点的节点而根节点是最顶层的节点。路径长度则是从一个节点到另一个节点之间的边的数量。
具体计算过程如下
1. 对每个叶子节点计算根节点到该叶子节点的路径长度即从根节点到叶子节点所经过的边的数量。
2. 将每个叶子节点的权值与其对应的路径长度相乘。
3. 将上述所有的乘积相加得到的总和就是这棵树的带权路径长度。
在哈夫曼编码中我们通常希望带权路径长度尽可能的小这样可以让编码更加高效。
C代码
#include iostream
#include queue using namespace std;struct Node { // 定义节点结构体int freq; // 频率Node* left; // 左子节点Node* right; // 右子节点
};// 创建新的节点
Node* newNode(int freq) // 定义新节点的创建函数输入是频率值返回创建的新节点的指针
{Node* node new Node(); // 动态创建新节点node-left node-right NULL; // 初始化左右子节点为空node-freq freq; // 设置新节点的频率return (node); // 返回新节点的指针
}// 比较节点的频率
struct compare { // 定义比较结构体作为优先级队列的比较函数bool operator()(Node* l, Node* r) // 重载括号运算符用以比较两个节点的频率{return (l-freq r-freq); // 如果第一个节点频率大于第二个返回真否则假}
};// 计算哈夫曼树的权值路径长度
int calculateWPL(Node* root, int depth 0) // 定义计算WPL的函数输入是根节点的指针和路径深度默认为0返回路径长度值
{if (!root) return 0; // 如果节点为空返回0if (!root-left !root-right) return depth * root-freq; // 如果是叶子节点无左右子节点返回当前深度乘以节点频率// 如果不是叶子节点递归计算左右子树的WPL返回两者之和return calculateWPL(root-left, depth 1) calculateWPL(root-right, depth 1);
}int main() { int n;cin n; priority_queueNode*, vectorNode*, compare pq; // 定义一个优先队列用于存储节点指针利用 compare 结构体比较节点频率for (int i 0; i n; i){int freq;cin freq; // 输入每个节点的频率值pq.push(newNode(freq)); // 创建新的节点并将其添加到优先队列中}while (pq.size() ! 1) { // 当优先队列中只有一个元素时结束循环Node* left pq.top(); // 获取频率最小的节点作为左子节点pq.pop(); // 将该节点从优先队列中移除Node* right pq.top(); // 获取频率次小的节点作为右子节点pq.pop(); // 将该节点从优先队列中移除int sum left-freq right-freq; // 计算左右子节点频率之和Node* top newNode(sum); // 以这个频率和创建新节点top-left left; // 将左子节点连接到新节点top-right right; // 将右子节点连接到新节点pq.push(top); // 将新节点添加到优先队列中}cout WPL calculateWPL(pq.top()) endl; // 输出哈夫曼树的带权路径长度return 0; // 程序执行成功返回0
}
