哈夫曼树和哈夫曼编码:从终端输入若干个字符,统计字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。
时间: 2023-04-26 15:02:15 浏览: 118
哈夫曼树和哈夫曼编码是一种用于数据压缩的算法。该算法通过统计字符出现的频率,建立哈夫曼树,并对每个字符进行哈夫曼编码,从而实现数据压缩的目的。具体实现过程为:从终端输入若干个字符,统计字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各字符进行哈夫曼编码。最后打印哈夫曼树和对应的哈夫曼编码。
相关问题
从键盘输入一字符串,统计出现的字符和每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树。对各个字符进行哈夫曼编码,最后打印输出字符及每个字符对应的哈夫曼编码。
### 回答1:
首先,我们需要从键盘输入一个字符串,并统计每个字符出现的频率。然后,将每个字符出现的频率作为结点的权值,建立哈夫曼树。接着,对每个字符进行哈夫曼编码,并打印输出字符及每个字符对应的哈夫曼编码。
具体实现可以参考以下步骤:
1. 从键盘输入一个字符串,使用哈希表或数组统计每个字符出现的频率。
2. 将每个字符出现的频率作为结点的权值,建立哈夫曼树。可以使用优先队列或堆来实现。
3. 对每个字符进行哈夫曼编码。从根节点开始,遍历哈夫曼树,当遇到左子树时,将编码加上0,当遇到右子树时,将编码加上1,直到遍历到叶子节点,记录下该字符的哈夫曼编码。
4. 打印输出字符及每个字符对应的哈夫曼编码。
注意,如果字符串中只有一个字符,那么哈夫曼编码就是0。如果字符串中只有两个字符,那么哈夫曼编码可以是0和1,也可以是1和0,因为哈夫曼编码是没有规定顺序的。
### 回答2:
题目要求输入一个字符串,并对其中的字符进行哈夫曼编码,输出字符及对应编码。
首先,需要统计字符串中每个字符出现的频率。可以定义一个数组,用于存储每个字符的出现次数。每当遍历到一个字符时,将该字符在数组中对应的位置的值加1。遍历完整个字符串后,就可以得到每个字符出现的频率。
接下来,需要根据每个字符的频率建立哈夫曼树。可以先将每个字符及对应的频率作为一个节点,构成一颗森林。然后,选取频率最小的两个节点作为左右子节点,构建一个新的父节点,父节点的权值就是其左右节点的权值之和。将这个新的父节点加入到原先的森林中,重复此步骤,直到只剩下一个节点,即哈夫曼树的根节点。
最后,对每个字符进行哈夫曼编码。从根节点开始,如果向左走则编码为0,如果向右走则编码为1,直到遍历到该字符节点,将所走路径上的编码记录下来即可。
输出时,对于每个字符,输出其对应的编码即可。
通过上述步骤,我们可以将字符串中的每个字符编码成一串‘0’和‘1’的序列,实现信息的压缩和传输。
### 回答3:
哈夫曼编码是一种用于压缩数据的编码方法,它通过对出现频率高的字符使用短的编码,而对出现频率低的字符使用长的编码,从而达到压缩数据的目的。本题需要完成的是对一个字符串进行哈夫曼编码。
首先,需要统计字符串中每个字符出现的频率。可以使用一个哈希表来记录每个字符的频率,然后将哈希表中的元素按照频率从小到大排列,将字符出现的频率作为权值,创建哈夫曼树。哈夫曼树的建立可以使用贪心算法,每次选择权值最小的两个节点合并为一个节点,直到只剩下一个根节点为止。
建立好哈夫曼树之后,就可以为每个字符生成哈夫曼编码了。从根节点开始遍历哈夫曼树,左子树编码为0,右子树编码为1,将每个字符的编码记录下来。这里可以使用递归函数来实现。
最后,打印输出字符及每个字符对应的哈夫曼编码。
以下是具体实现的伪代码:
```
// 统计字符串中每个字符出现的频率
hash_map<char, int> freq_map;
for (char c in string) {
freq_map[c]++;
}
// 将哈希表中的元素按照频率从小到大排列,将字符出现的频率作为权值,创建哈夫曼树
priority_queue<Node> node_queue;
for (auto& entry : freq_map) {
Node node(entry.first, entry.second);
node_queue.push(node);
}
while (node_queue.size() > 1) {
Node left = node_queue.top(); node_queue.pop();
Node right = node_queue.top(); node_queue.pop();
Node parent(0, left.freq + right.freq);
parent.left = &left;
parent.right = &right;
node_queue.push(parent);
}
Node root = node_queue.top();
// 为每个字符生成哈夫曼编码
hash_map<char, string> code_map;
function<void(Node*, string)> generate_code = [&](Node* node, string code) {
if (node->left == nullptr && node->right == nullptr) {
code_map[node->ch] = code;
return;
}
if (node->left) {
generate_code(node->left, code + "0");
}
if (node->right) {
generate_code(node->right, code + "1");
}
};
generate_code(&root, "");
// 打印输出字符及每个字符对应的哈夫曼编码
for (auto& entry : code_map) {
cout << entry.first << ": " << entry.second << endl;
}
```
总之,哈夫曼编码这个问题本质上是构建一棵树,并通过遍历树来获得每个字符的编码。因此,要能够处理这个问题,需要对树和递归有一定的理解。
请根据哈夫曼编码的原理,编写一个C++程序,只允许使用iostream和stdio.h头文件建立哈夫曼树,实现基于输入的字符及其权值求哈夫曼编码和进行编码解码的功能。 要求: 1. 输出每个字符的哈夫曼编码。 2. 输入由上述若干字符组成的字符串,对电文进行编码并输出。 3. 输入一串哈夫曼编码,进行解码并输出字符串。 样例: 输入: 请输入哈夫曼树叶子结点的个数: 5 请输入每个字符及其权值: P 5 L 9 A 15 N 25 T 11 请输入需要编码的字符串: PLAN 请输入需要解码的哈夫曼编码: 0100111011 输出: (1)字符P的哈夫曼编码为: (后面自己填)字符L的哈夫曼编码为: 字符A的哈夫曼编码为: 字符N的哈夫曼编码为: 字符T的哈夫曼编码为: (2)字符串PLAN的哈夫曼编码为: (3)编码0100111011 的解码后字符串为:
以下是基于输入的字符及其权值求哈夫曼编码和进行编码解码的C++程序,请参考:
```c++
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 1005; // 最大叶子结点个数
const int MAXM = 2 * MAXN - 1; // 最大结点个数
struct Node {
int value; // 权值
int lson, rson; // 左右儿子结点编号
int parent; // 父亲结点编号
char ch; // 叶子结点存储的字符
} node[MAXM]; // 结点数组
struct Code {
char ch; // 字符
char code[MAXN]; // 哈夫曼编码
} code[MAXN]; // 编码数组
int n; // 叶子结点个数
char str[MAXN]; // 需要编码的字符串
char huffmanCode[MAXN]; // 需要解码的哈夫曼编码
// 建立哈夫曼树
void buildHuffman() {
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
for (int i = 1; i <= n; i++) {
q.push(make_pair(node[i].value, i));
}
int cnt = n + 1;
while (q.size() > 1) {
pair<int, int> p1 = q.top();
q.pop();
pair<int, int> p2 = q.top();
q.pop();
int lson = p1.second, rson = p2.second;
int parent = cnt;
cnt++;
node[lson].parent = node[rson].parent = parent;
node[parent].lson = lson;
node[parent].rson = rson;
node[parent].value = node[lson].value + node[rson].value;
q.push(make_pair(node[parent].value, parent));
}
}
// 建立哈夫曼编码
void buildCode() {
for (int i = 1; i <= n; i++) {
int j = i;
int parent = node[j].parent;
int k = 0;
while (parent != 0) {
if (node[parent].lson == j) {
code[i].code[k] = '0';
} else {
code[i].code[k] = '1';
}
k++;
j = parent;
parent = node[j].parent;
}
code[i].code[k] = '\0';
reverse(code[i].code, code[i].code + strlen(code[i].code));
code[i].ch = node[i].ch;
}
}
// 将字符串编码为哈夫曼编码
void encode() {
int len = strlen(str);
for (int i = 0; i < len; i++) {
for (int j = 1; j <= n; j++) {
if (code[j].ch == str[i]) {
printf("%s", code[j].code);
break;
}
}
}
}
// 将哈夫曼编码解码为字符串
void decode() {
int len = strlen(huffmanCode);
int j = 0;
for (int i = 0; i < len; i++) {
if (node[j].lson == 0 && node[j].rson == 0) {
printf("%c", node[j].ch);
j = 0;
}
if (huffmanCode[i] == '0') {
j = node[j].lson;
} else {
j = node[j].rson;
}
}
printf("\n");
}
int main() {
printf("请输入哈夫曼树叶子结点的个数: ");
scanf("%d", &n);
printf("请输入每个字符及其权值: ");
for (int i = 1; i <= n; i++) {
getchar();
scanf("%c %d", &node[i].ch, &node[i].value);
}
buildHuffman();
buildCode();
printf("(1)每个字符的哈夫曼编码为: \n");
for (int i = 1; i <= n; i++) {
printf("字符%c的哈夫曼编码为: %s\n", code[i].ch, code[i].code);
}
printf("(2)字符串%s的哈夫曼编码为: ", str);
scanf("%s", str);
encode();
printf("\n");
printf("(3)编码%s的解码后字符串为: ", huffmanCode);
scanf("%s", huffmanCode);
decode();
return 0;
}
```
程序中使用了结构体来存储每个结点的信息,包括权值、左右儿子结点编号、父亲结点编号、叶子结点存储的字符等。在建立哈夫曼树时使用了优先队列来存储结点信息,每次取出最小的两个结点进行合并。在建立哈夫曼编码时,从叶子结点开始,一直到根结点,记录下每个结点所对应的哈夫曼编码。在将字符串编码为哈夫曼编码时,遍历字符串中的每个字符,找到对应的哈夫曼编码输出即可。在将哈夫曼编码解码为字符串时,从根结点开始,根据哈夫曼编码依次走到叶子结点,输出叶子结点存储的字符即可。