c++实现哈夫曼编码
时间: 2023-11-10 18:01:42 浏览: 83
要在C语言中实现哈夫曼编码,你可以按照以下步骤进行操作:
1. 创建数据结构来表示哈夫曼树和哈夫曼编码表。
2. 统计待编码的数据中每个字符的频率,并根据频率构建哈夫曼树。
3. 根据哈夫曼树生成哈夫曼编码表,即每个字符对应的二进制编码。
4. 使用哈夫曼编码表将原始数据编码为二进制数据。
5. 将二进制数据写入输出文件。
相关问题
c++实现哈夫曼编码译码
对于C++实现哈夫曼编码和译码,可以按照以下步骤进行:
1. 定义哈夫曼树的节点结构,包括字符、权重和左右子节点等信息。
2. 构建哈夫曼树:
- 创建一个优先队列(最小堆),用于存储节点,并按照权重进行排序。
- 将每个字符作为一个节点插入到优先队列中。
- 从优先队列中取出权重最小的两个节点,合并为一个新节点,并将新节点插入到优先队列中。
- 重复上述步骤,直到优先队列中只剩下一个节点,即为哈夫曼树的根节点。
3. 生成哈夫曼编码表:
- 从根节点开始,遍历哈夫曼树的每个节点。
- 对于每个节点,记录从根节点到该节点的路径,0表示左子节点,1表示右子节点。
- 将每个字符与对应的路径组成的编码表进行关联。
4. 进行编码:
- 读取待编码的文本。
- 对于每个字符,根据编码表找到对应的哈夫曼编码。
- 将编码后的二进制序列保存起来。
5. 进行译码:
- 读取待译码的二进制序列。
- 从根节点开始,根据序列中的每个位进行遍历。
- 如果是0,移动到当前节点的左子节点;如果是1,移动到当前节点的右子节点。
- 当遍历到叶子节点时,输出对应的字符,并回到根节点。
下面是一个C++实现哈夫曼编码和译码的简单示例:
```cpp
// 定义哈夫曼树节点结构
struct Node {
char data;
int weight;
Node* left;
Node* right;
};
// 构建哈夫曼树
Node* buildHuffmanTree(vector<Node*>& nodes) {
while (nodes.size() > 1) {
sort(nodes.begin(), nodes.end(), [](Node* a, Node* b) {
return a->weight < b->weight;
});
Node* left = nodes[0];
Node* right = nodes[1];
Node* parent = new Node();
parent->weight = left->weight + right->weight;
parent->left = left;
parent->right = right;
nodes.erase(nodes.begin(), nodes.begin() + 2);
nodes.push_back(parent);
}
return nodes[0];
}
// 生成哈夫曼编码表
void generateHuffmanCode(Node* root, string code, unordered_map<char, string>& codeTable) {
if (root->left == nullptr && root->right == nullptr) {
codeTable[root->data] = code;
return;
}
generateHuffmanCode(root->left, code + "0", codeTable);
generateHuffmanCode(root->right, code + "1", codeTable);
}
// 进行编码
string encode(string text, unordered_map<char, string>& codeTable) {
string encodedText;
for (char c : text) {
encodedText += codeTable[c];
}
return encodedText;
}
// 进行译码
string decode(string encodedText, Node* root) {
string decodedText;
Node* current = root;
for (char bit : encodedText) {
if (bit == '0') {
current = current->left;
} else {
current = current->right;
}
if (current->left == nullptr && current->right == nullptr) {
decodedText += current->data;
current = root;
}
}
return decodedText;
}
// 示例用法
int main() {
string text = "hello world";
vector<Node*> nodes;
for (char c : text) {
Node* node = new Node();
node->data = c;
node->weight = count(text.begin(), text.end(), c);
node->left = nullptr;
node->right = nullptr;
nodes.push_back(node);
}
Node* root = buildHuffmanTree(nodes);
unordered_map<char, string> codeTable;
generateHuffmanCode(root, "", codeTable);
string encodedText = encode(text, codeTable);
string decodedText = decode(encodedText, root);
cout << "Encoded text: " << encodedText << endl;
cout << "Decoded text: " << decodedText << endl;
return 0;
}
```
C++实现哈夫曼编码译码
哈夫曼编码是一种常用的数据压缩算法,它可以根据数据出现的频率构建不等长的编码,从而达到压缩数据的目的。以下是使用C++实现哈夫曼编码和译码的示例代码。
首先,需要实现哈夫曼树的构建和编码表的生成。定义一个Node结构体表示哈夫曼树的节点,其中weight表示节点的权值,left和right分别表示节点的左右子节点,code表示节点对应的编码。
```cpp
struct Node {
int weight;
Node* left;
Node* right;
string code;
Node(int w, Node* l, Node* r): weight(w), left(l), right(r) {}
};
```
接下来,定义一个比较函数用于在优先队列中对节点按照权值从小到大排序。
```cpp
struct cmp {
bool operator()(Node* a, Node* b) {
return a->weight > b->weight;
}
};
```
然后,实现哈夫曼树的构建函数buildHuffmanTree,该函数接受一个表示字符出现频率的数组freq和字符集合大小n作为参数,返回哈夫曼树的根节点。
```cpp
Node* buildHuffmanTree(int freq[], int n) {
priority_queue<Node*, vector<Node*>, cmp> pq;
for (int i = 0; i < n; i++) {
if (freq[i] > 0) {
pq.push(new Node(freq[i], nullptr, nullptr));
}
}
while (pq.size() > 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
Node* parent = new Node(left->weight + right->weight, left, right);
pq.push(parent);
}
return pq.top();
}
```
接下来,实现生成编码表的函数generateCodes,该函数接受一个哈夫曼树的根节点和一个表示字符集合的数组chSet作为参数,返回一个表示字符编码的数组。
```cpp
void generateCodes(Node* root, string code, string codes[]) {
if (root->left == nullptr && root->right == nullptr) {
codes[root->weight] = code;
root->code = code;
return;
}
generateCodes(root->left, code + '0', codes);
generateCodes(root->right, code + '1', codes);
}
```
接下来,实现哈夫曼编码的函数encode,该函数接受一个表示原始文本的字符串text和一个表示字符编码的数组codes作为参数,返回一个表示编码后的二进制串。
```cpp
string encode(string text, string codes[]) {
string result;
for (char ch: text) {
result += codes[ch];
}
return result;
}
```
最后,实现哈夫曼译码的函数decode,该函数接受一个表示编码后的二进制串code和一个表示哈夫曼树的根节点root作为参数,返回一个表示译码后的原始文本字符串。
```cpp
string decode(string code, Node* root) {
Node* p = root;
string result;
for (char ch: code) {
if (ch == '0') {
p = p->left;
} else {
p = p->right;
}
if (p->left == nullptr && p->right == nullptr) {
result += char(p->weight);
p = root;
}
}
return result;
}
```
完整代码如下:
```cpp
#include <iostream>
#include <queue>
using namespace std;
struct Node {
int weight;
Node* left;
Node* right;
string code;
Node(int w, Node* l, Node* r): weight(w), left(l), right(r) {}
};
struct cmp {
bool operator()(Node* a, Node* b) {
return a->weight > b->weight;
}
};
Node* buildHuffmanTree(int freq[], int n) {
priority_queue<Node*, vector<Node*>, cmp> pq;
for (int i = 0; i < n; i++) {
if (freq[i] > 0) {
pq.push(new Node(freq[i], nullptr, nullptr));
}
}
while (pq.size() > 1) {
Node* left = pq.top();
pq.pop();
Node* right = pq.top();
pq.pop();
Node* parent = new Node(left->weight + right->weight, left, right);
pq.push(parent);
}
return pq.top();
}
void generateCodes(Node* root, string code, string codes[]) {
if (root->left == nullptr && root->right == nullptr) {
codes[root->weight] = code;
root->code = code;
return;
}
generateCodes(root->left, code + '0', codes);
generateCodes(root->right, code + '1', codes);
}
string encode(string text, string codes[]) {
string result;
for (char ch: text) {
result += codes[ch];
}
return result;
}
string decode(string code, Node* root) {
Node* p = root;
string result;
for (char ch: code) {
if (ch == '0') {
p = p->left;
} else {
p = p->right;
}
if (p->left == nullptr && p->right == nullptr) {
result += char(p->weight);
p = root;
}
}
return result;
}
int main() {
int freq[256] = {0};
string text = "hello world";
for (char ch: text) {
freq[ch]++;
}
Node* root = buildHuffmanTree(freq, 256);
string codes[256];
generateCodes(root, "", codes);
string code = encode(text, codes);
cout << "Encoded: " << code << endl;
string decoded = decode(code, root);
cout << "Decoded: " << decoded << endl;
return 0;
}
```