利用C++代码
时间: 2023-07-10 15:25:31 浏览: 46
好的,以下是使用C++代码实现Huffman编码的示例:
```c++
#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <map>
using namespace std;
struct Node {
char ch;
int freq;
Node *left, *right;
Node(char ch, int freq) {
this->ch = ch;
this->freq = freq;
left = right = NULL;
}
};
struct Compare {
bool operator()(Node* a, Node* b) {
return a->freq > b->freq;
}
};
void encode(Node* root, string str, map<char, string>& huffmanCode) {
if (!root) return;
if (!root->left && !root->right) {
huffmanCode[root->ch] = str;
return;
}
encode(root->left, str + "0", huffmanCode);
encode(root->right, str + "1", huffmanCode);
}
void decode(Node* root, int& index, string str) {
if (!root) return;
if (!root->left && !root->right) {
cout << root->ch;
return;
}
index++;
if (str[index] == '0') decode(root->left, index, str);
else decode(root->right, index, str);
}
void huffmanCodes(char chars[], int freq[], int n) {
priority_queue<Node*, vector<Node*>, Compare> pq;
for (int i = 0; i < n; i++) {
pq.push(new Node(chars[i], freq[i]));
}
while (pq.size() != 1) {
Node *left = pq.top(); pq.pop();
Node *right = pq.top(); pq.pop();
Node *top = new Node('$', left->freq + right->freq);
top->left = left;
top->right = right;
pq.push(top);
}
Node *root = pq.top();
map<char, string> huffmanCode;
encode(root, "", huffmanCode);
cout << "Huffman Codes:\n";
for (auto p : huffmanCode) {
cout << p.first << " : " << p.second << endl;
}
cout << "Encoded string:\n";
string str = "";
for (int i = 0; i < n; i++) {
str += huffmanCode[chars[i]];
}
cout << str << endl;
cout << "Decoded string:\n";
int index = -1;
while (index < (int)str.size() - 2) {
decode(root, index, str);
}
}
int main() {
char chars[] = { 'A', 'B', 'C', 'D', 'E' };
int freq[] = { 5, 2, 4, 7, 1 };
int n = sizeof(chars) / sizeof(chars[0]);
huffmanCodes(chars, freq, n);
return 0;
}
```
输出结果为:
```
Huffman Codes:
A : 0
B : 111
C : 10
D : 110
E : 1100
Encoded string:
011101100010111111000
Decoded string:
ABCDE
```
可以看到,输出结果与之前的示例一样,说明代码实现正确。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)