网站模板下载之后怎么做,长春快速建站模板,蓬莱做网站联系电话,常用网站推广方法及资源哈夫曼树与哈夫曼编码 题目描述输入格式输出格式输入样例输出样例 分数 30 作者 伍建全 单位 重庆科技学院 题目描述
哈夫曼树(Huffman Tree)又称最优二叉树#xff0c;是一种带权路径长度最短的二叉树。所谓树的带权路径长度#xff0c;就是树中所有的叶结点的权值乘上其到… 哈夫曼树与哈夫曼编码 题目描述输入格式输出格式输入样例输出样例 分数 30 作者 伍建全 单位 重庆科技学院 题目描述
哈夫曼树(Huffman Tree)又称最优二叉树是一种带权路径长度最短的二叉树。所谓树的带权路径长度就是树中所有的叶结点的权值乘上其到根结点的路径长度若根结点为0层叶结点到根结点的路径长度为叶结点的层数。树的路径长度是从树根到每一结点的路径长度之和记为WPLW1L1W2L2W3L3…WnLnN个权值Wii1,2,…n构成一棵有N个叶结点的二叉树相应的叶结点的路径长度为Lii1,2,…n。可以证明哈夫曼树的WPL是最小的。
在数据通信中需要将传送的文字转换成二进制的字符串用01码的不同排列来表示字符。例如需传送的报文为“AFTER DATA EAR ARE ART AREA”这里用到的字符集为“AERTFD”各字母出现的次数为{845311}。现要求为这些字母设计编码。要区别6个字母最简单的二进制编码方式是等长编码固定采用3位二进制可分别用000、001、010、011、100、101对“AERTFD”进行编码发送当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符则固定编码长度为5。然而传送报文时总是希望总长度尽可能短。在实际应用中各个字符的出现频度或使用次数是不相同的如A、B、C的使用频率远远高于X、Y、Z自然会想到设计编码时让使用频率高的用短码使用频率低的用长码以优化整个报文编码。
为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)可用字符集中的每个字符作为叶子结点生成一棵编码二叉树为了获得传送报文的最短长度可将每个字符的出现频率作为字符结点的权值赋予该结点上显然字使用频率越小权值越小权值越小叶子就越靠下于是频率小编码长频率高编码短这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度。因此求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码既满足前缀编码的条件又保证报文编码总长最短。
本题要求从键盘输入若干电文所用符号及其出现的频率然后构造哈夫曼树从而输出哈夫曼编码。
注意 为了保证得到唯一的哈夫曼树本题规定在构造哈夫曼树时左孩子结点权值不大于右孩子结点权值。如权值相等则先选优先级队列中先出队的节点作为左孩子。编码时左分支取“0”右分支取“1”。
输入格式
输入有3行。 第1行符号个数n220。
第2行一个不含空格的字符串。记录着本题的符号表。我们约定符号都是单个的小写英文字母且从字符‘a’开始顺序出现。也就是说如果 n 为 2 则符号表为 ab 如果 n 为 6则符号为 abcdef以此类推。
第3行各符号出现频率用乘以100后的整数用空格分隔。
输出格式
先输出构造的哈夫曼树带权路径长度。 接下来输出n行每行是一个字符和该字符对应的哈夫曼编码。字符按字典顺序输出。
字符和哈夫曼编码之间以冒号分隔。
例如
a:10
b:110
输入样例
在这里给出一组输入。
6
abcdef
15 19 10 6 38 12输出样例
在这里给出相应的输出。
240
a:101
b:111
c:1101
d:1100
e:0
f:100提示 以上示例数据按题目要求建立的Huffman Tree如下图
#include iostream
#include queue
#include mapusing namespace std;const int N 110;struct node
{int id, w;char op;bool operator (const node a) const{if (a.w w) return op a.op;return w a.w;}
};struct node1
{int id, w;char op;int l, r, p;
}h[N];int n;
string s;
mapchar, stringmp;void init()
{for (int i 0; i n - 1; i )h[i].p h[i].l h[i].r -1;
}int main()
{init();cin n s;priority_queuenode, vectornode q;for (int i 0; i n; i ){int x;cin x;q.push({i, x, s[i]});}int sum 0;for (int i n; i 2 * n - 1; i ){auto x q.top();q.pop();auto y q.top();q.pop();if(x.w y.w) swap(x, y);h[i].l x.id, h[i].r y.id;h[x.id].p h[y.id].p i;h[i].id i;h[i].w x.w y.w;q.push({i, h[i].w, -});sum h[i].w;}cout sum endl;for (int i 0; i n; i ){h[n * 2 - 2].p -1;string s1 ;int pre i;int pp h[i].p;while (pp ! -1){int ll h[pp].l;int rr h[pp].r;if(ll pre) s1 0 s1;else s1 1 s1;pre pp;pp h[pp].p;}mp[s[i]] s1;}for (auto it : mp)cout it.first : it.second endl;return 0;
}
