c++实现哈夫曼编码

要在C语言中实现哈夫曼编码，你可以按照以下步骤进行操作：
1. 创建数据结构来表示哈夫曼树和哈夫曼编码表。
2. 统计待编码的数据中每个字符的频率，并根据频率构建哈夫曼树。
3. 根据哈夫曼树生成哈夫曼编码表，即每个字符对应的二进制编码。
4. 使用哈夫曼编码表将原始数据编码为二进制数据。
5. 将二进制数据写入输出文件。

相关问题

C++实现哈夫曼编码译码

哈夫曼编码是一种常用的数据压缩算法，它可以根据数据出现的频率构建不等长的编码，从而达到压缩数据的目的。以下是使用C++实现哈夫曼编码和译码的示例代码。

首先，需要实现哈夫曼树的构建和编码表的生成。定义一个Node结构体表示哈夫曼树的节点，其中weight表示节点的权值，left和right分别表示节点的左右子节点，code表示节点对应的编码。

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;
    }
};

然后，实现哈夫曼树的构建函数buildHuffmanTree，该函数接受一个表示字符出现频率的数组freq和字符集合大小n作为参数，返回哈夫曼树的根节点。

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作为参数，返回一个表示字符编码的数组。

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作为参数，返回一个表示编码后的二进制串。

string encode(string text, string codes[]) {
    string result;
    for (char ch: text) {
        result += codes[ch];
    }
    return result;
}

最后，实现哈夫曼译码的函数decode，该函数接受一个表示编码后的二进制串code和一个表示哈夫曼树的根节点root作为参数，返回一个表示译码后的原始文本字符串。

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;
}

完整代码如下：

#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;
}

c++实现哈夫曼编码压缩

哈夫曼编码是一种常用的数据压缩算法，可以通过将频率较高的字符用较短的二进制位来表示，从而有效地减小数据存储的大小。下面是一个简单的C++实现，实现对字符串的哈夫曼编码压缩和解压缩：

#include <iostream>
#include <queue>
#include <unordered_map>

using namespace std;

// 哈夫曼树节点结构体
struct HuffmanNode {
    char ch; // 节点对应的字符
    int freq; // 字符出现的频率
    HuffmanNode* left; // 左子节点
    HuffmanNode* right; // 右子节点
    HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};

// 定义哈夫曼树节点比较函数，用于优先队列排序
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq > b->freq;
    }
};

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(string s) {
    unordered_map<char, int> freqMap;
    for (char c : s) {
        freqMap[c]++;
    }

    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> pq;
    for (auto& p : freqMap) {
        pq.push(new HuffmanNode(p.first, p.second));
    }

    while (pq.size() > 1) {
        HuffmanNode* left = pq.top(); pq.pop();
        HuffmanNode* right = pq.top(); pq.pop();
        HuffmanNode* parent = new HuffmanNode('$', left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(parent);
    }

    return pq.top();
}

// 将哈夫曼树转换为哈夫曼编码表
void buildHuffmanCodeTable(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
    if (!root) return;
    if (root->ch != '$') {
        codeMap[root->ch] = code;
    }
    buildHuffmanCodeTable(root->left, code + "0", codeMap);
    buildHuffmanCodeTable(root->right, code + "1", codeMap);
}

// 压缩字符串
string compress(string s) {
    HuffmanNode* root = buildHuffmanTree(s);

    unordered_map<char, string> codeMap;
    buildHuffmanCodeTable(root, "", codeMap);

    string compressed = "";
    for (char c : s) {
        compressed += codeMap[c];
    }

    return compressed;
}

// 解压缩字符串
string decompress(string s, HuffmanNode* root) {
    string decompressed = "";
    HuffmanNode* node = root;
    for (char c : s) {
        if (c == '0') {
            node = node->left;
        } else {
            node = node->right;
        }
        if (node->ch != '$') {
            decompressed += node->ch;
            node = root;
        }
    }
    return decompressed;
}

int main() {
    string s = "hello world";
    cout << "Original string: " << s << endl;

    string compressed = compress(s);
    cout << "Compressed string: " << compressed << endl;

    HuffmanNode* root = buildHuffmanTree(s);
    string decompressed = decompress(compressed, root);
    cout << "Decompressed string: " << decompressed << endl;

    return 0;
}

在上面的代码中，我们首先定义了一个 `HuffmanNode` 结构体，用于表示哈夫曼树的节点。然后，我们通过统计字符串中每个字符出现的频率来构建哈夫曼树，并通过哈夫曼树构建哈夫曼编码表。接着，我们可以将原始字符串使用哈夫曼编码进行压缩，并使用哈夫曼树进行解压缩。最后，我们将压缩后的字符串和解压缩后的字符串打印出来，以验证算法的正确性。