算法笔记练习 题解合集

本题链接

题目

题目描述
哈弗曼编码大家一定很熟悉吧（不熟悉也没关系，自己查去。。。）。现在给你一串字符以及它们所对应的权值，让你构造哈弗曼树，从而确定每个字符的哈弗曼编码。当然，这里有一些小规定：

1.规定哈弗曼树的左子树编码为0，右子树编码为1；

2.若两个字符权值相同，则ASCII码值小的字符为左孩子，大的为右孩子；

3.创建的新节点所代表的字符与它的做孩子的字符相同；

4.所有字符为ASCII码表上32-96之间的字符（即“ ”到“`”之间的字符）。

输入
输入包含多组数据（不超过100组）
每组数据第一行一个整数n，表示字符个数。接下来n行，每行有一个字符ch和一个整数weight，表示字符ch所对应的权值，中间用空格隔开。
输入数据保证每组测试数据的字符不会重复。

输出
对于每组测试数据，按照输入顺序输出相应的字符以及它们的哈弗曼编码结果，具体格式见样例。

样例输入

3
a 10
b 5
c 8
4
a 1
b 1
c 1
d 1

样例输出

a:0
b:10
c:11
a:00
b:01
c:10
d:11

思路

代码主体框架用的是这道题的：问题 B: 算法6-13：自顶向下的赫夫曼编码。

因为答案中需要输出字符，所以用额外的成员ch存储字符即可，其他完全一致。

代码

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
struct Node {
int w, parent, lchild, rchild;
char ch;
};
void findMinTwo(std::vector<Node>& huffman, int& min1, int& min2) {
int i = 1, w1, w2;
while (huffman[i++].parent != 0)
continue;
min1 = i - 1;
while (huffman[i++].parent != 0)
continue;
min2 = i - 1;
for ( ; i < huffman.size(); ++i) {
if (huffman[i].parent == 0 && huffman[i].w < std::max(huffman[min1].w, huffman[min2].w)) {
if (huffman[min1].w != huffman[min2].w)
(huffman[min1].w > huffman[min2].w ? min1 : min2) = i;
else
(min1 > min2 ? min1 : min2) = i;
}
}
if (min1 > min2)
std::swap(min1, min2);
}
int main() {
char inputChar;
int n, input, min1, min2;
std::vector<Node> huffmanTree;
std::vector<std::string> huffmanCode;
while (scanf("%d", &n) != EOF) {
getchar();
if (n == 1) {
scanf("%c%d", &inputChar, &input);
printf("%c 0n", inputChar);
continue;
}
huffmanTree.clear();
huffmanTree.resize(n + 1);
huffmanTree[0] = {0, 0, 0, 0, ''};
huffmanCode.clear();
huffmanCode.resize(n + 1);
for (int i = 1; i <= n; ++i) {
scanf("%c%d", &inputChar, &input);
getchar();
huffmanTree[i] = {input, 0, 0, 0, inputChar};
}
for (int i = n + 1; i <= 2 * n - 1; ++i) {
findMinTwo(huffmanTree, min1, min2);
huffmanTree[min1].parent = huffmanTree[min2].parent = i;
huffmanTree.push_back( {huffmanTree[min1].w + huffmanTree[min2].w, 0, min1, min2} );
}
for (int i = 1; i <= 2 * n - 1; ++i)
huffmanTree[i].w = 0;
int c = 2 * n - 1;
std::string temp;
while (c) {
if (huffmanTree[c].w == 0) {
huffmanTree[c].w = 1;
if (huffmanTree[c].lchild != 0) {
c = huffmanTree[c].lchild;
temp += '0';
} else if (huffmanTree[c].rchild == 0) {
huffmanCode[c] = temp;
}
} else if (huffmanTree[c].w == 1) {
huffmanTree[c].w = 2;
if (huffmanTree[c].rchild != 0) {
c = huffmanTree[c].rchild;
temp += '1';
}
} else {
huffmanTree[c].w = 0;
c = huffmanTree[c].parent;
temp = temp.substr(0, temp.size() - 1);
}
}
for (int i = 1; i <= n; ++i)
std::cout << huffmanTree[i].ch << ":" << huffmanCode[i] << 'n';
}
return 0;
}

最后

以上就是虚幻舞蹈为你收集整理的算法笔记练习 9.8 哈夫曼树 问题 D: Haffman编码算法笔记练习 题解合集题目思路代码的全部内容，希望文章能够帮你解决算法笔记练习 9.8 哈夫曼树 问题 D: Haffman编码算法笔记练习 题解合集题目思路代码所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。