题目一:哈夫曼编码的应用十分广泛,最广为人知的是它在通信电文中的应用,可以大 大降低电文总长度,提升传输效率降低传输成本。请根据哈夫曼编码的原理,编写一个程序, 建立哈夫曼树,实现基于输入的字符及其权值求哈夫曼编码和进行编码解码的功能。 要求: 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++代码实现,且不可以使用stl里的容器
时间: 2023-07-19 13:06:42 浏览: 171
好的,我来帮你写一个哈夫曼编码的程序。首先,我们需要定义一个哈夫曼树的节点结构体,包括字符、权值、左右子节点等信息:
```c++
struct Node {
char c;
int weight;
Node *left, *right;
Node(char c, int weight): c(c), weight(weight), left(nullptr), right(nullptr) {}
};
```
然后,我们需要实现一个比较器,用于在后面的优先队列中比较节点的权值大小:
```c++
struct Compare {
bool operator() (const Node* a, const Node* b) {
return a->weight > b->weight;
}
};
```
接下来,我们可以开始实现建立哈夫曼树的函数。首先,我们需要统计每个字符出现的次数,用一个数组来记录:
```c++
int count[256] = {0};
for (char c : str) {
count[c]++;
}
```
然后,我们把每个字符及其对应的权值存储为一个节点,并加入一个优先队列中,按照权值从小到大排序:
```c++
priority_queue<Node*, vector<Node*>, Compare> pq;
for (int i = 0; i < 256; i++) {
if (count[i] > 0) {
pq.push(new Node(i, count[i]));
}
}
```
接下来,我们开始构建哈夫曼树。从优先队列中取出两个权值最小的节点,合并成一个新节点,权值为两个节点的权值之和,左右子节点分别为原来的两个节点。把新节点放回优先队列中,重复以上步骤,直到队列中只剩下一个节点,即为哈夫曼树的根节点:
```c++
while (pq.size() > 1) {
Node* left = pq.top(); pq.pop();
Node* right = pq.top(); pq.pop();
Node* parent = new Node('\0', left->weight + right->weight);
parent->left = left;
parent->right = right;
pq.push(parent);
}
Node* root = pq.top();
```
现在,我们已经建立了哈夫曼树,接下来可以根据哈夫曼树计算每个字符的编码。从根节点出发,如果往左走则在编码的末尾添加一个0,如果往右走则添加一个1。当走到叶子节点时,就得到了该字符的哈夫曼编码:
```c++
unordered_map<char, string> codes;
function<void(Node*, string)> traverse = [&](Node* node, string code) {
if (!node) return;
if (!node->left && !node->right) {
codes[node->c] = code;
return;
}
traverse(node->left, code + "0");
traverse(node->right, code + "1");
};
traverse(root, "");
```
现在,我们已经得到了每个字符的哈夫曼编码,可以输出答案了。对于输入的字符串,我们按照字符的顺序把它们的哈夫曼编码拼接起来,输出即可。对于输入的哈夫曼编码,我们从根节点开始往下遍历,遇到0就往左走,遇到1就往右走,直到走到叶子节点,就得到了一个字符,输出后重新回到根节点继续遍历,直到解码完整个字符串:
```c++
string encode(string str) {
string res = "";
for (char c : str) {
res += codes[c];
}
return res;
}
string decode(string code) {
string res = "";
Node* node = root;
for (char c : code) {
node = c == '0' ? node->left : node->right;
if (!node->left && !node->right) {
res += node->c;
node = root;
}
}
return res;
}
```
最后,我们把以上代码整合起来,就得到了完整的程序:
阅读全文