C++实现哈夫曼编码及其应用。 1）对输入数据构造成一棵Huffman 树； 2）对生成Huffman 树进行Huffman 编码。

以下是C++实现哈夫曼编码及其应用的代码：

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

using namespace std;

// 定义哈夫曼树的结点
struct HuffmanNode {
    char data; // 数据
    int freq; // 频率
    HuffmanNode* left; // 左子结点
    HuffmanNode* right; // 右子结点

    HuffmanNode(char _data, int _freq) {
        data = _data;
        freq = _freq;
        left = nullptr;
        right = nullptr;
    }
};

// 小根堆的比较函数
struct Compare {
    bool operator()(HuffmanNode* a, HuffmanNode* b) const {
        return a->freq > b->freq;
    }
};

// 构造哈夫曼树
HuffmanNode* buildHuffmanTree(const unordered_map<char, int>& freqMap) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, Compare> minHeap;
    for (auto& p : freqMap) {
        minHeap.push(new HuffmanNode(p.first, p.second));
    }

    while (minHeap.size() > 1) {
        HuffmanNode* left = minHeap.top();
        minHeap.pop();
        HuffmanNode* right = minHeap.top();
        minHeap.pop();

        HuffmanNode* parent = new HuffmanNode('#', left->freq + right->freq);
        parent->left = left;
        parent->right = right;

        minHeap.push(parent);
    }

    return minHeap.top();
}

// 生成哈夫曼编码
void generateHuffmanCode(HuffmanNode* root, string code, unordered_map<char, string>& codeMap) {
    if (root == nullptr) {
        return;
    }

    if (root->left == nullptr && root->right == nullptr) {
        codeMap[root->data] = code;
        return;
    }

    generateHuffmanCode(root->left, code + "0", codeMap);
    generateHuffmanCode(root->right, code + "1", codeMap);
}

// 压缩字符串
string compress(const string& str, const unordered_map<char, string>& codeMap) {
    string compressedStr = "";
    for (char c : str) {
        compressedStr += codeMap.at(c);
    }
    return compressedStr;
}

// 解压缩字符串
string decompress(const string& compressedStr, HuffmanNode* root) {
    string decompressedStr = "";
    HuffmanNode* p = root;
    for (char c : compressedStr) {
        if (c == '0') {
            p = p->left;
        } else {
            p = p->right;
        }

        if (p->left == nullptr && p->right == nullptr) {
            decompressedStr += p->data;
            p = root;
        }
    }
    return decompressedStr;
}

int main() {
    string str = "hello world";
    unordered_map<char, int> freqMap;
    for (char c : str) {
        freqMap[c]++;
    }

    HuffmanNode* root = buildHuffmanTree(freqMap);
    unordered_map<char, string> codeMap;
    generateHuffmanCode(root, "", codeMap);
    string compressedStr = compress(str, codeMap);
    string decompressedStr = decompress(compressedStr, root);

    cout << "原始字符串: " << str << endl;
    cout << "压缩后的字符串: " << compressedStr << endl;
    cout << "解压缩后的字符串: " << decompressedStr << endl;

    return 0;
}

代码思路：

1. 首先统计输入字符串中每个字符的频率，存储在unordered_map<char, int> freqMap中。
2. 根据freqMap构造哈夫曼树。
3. 通过哈夫曼树生成每个字符的编码，存储在unordered_map<char, string> codeMap中。
4. 压缩输入字符串，将每个字符替换成其对应的编码。
5. 解压缩压缩后的字符串，将编码替换成对应的字符。

代码解释：

1. 定义了一个HuffmanNode结构体，用于表示哈夫曼树的结点，其中包括了数据、频率、左子结点和右子结点。
2. 定义了一个小根堆的比较函数Compare，用于在构造哈夫曼树时作为priority_queue的比较函数。
3. buildHuffmanTree函数用于构造哈夫曼树。首先将freqMap中的每个字符和其对应的频率存储到小根堆minHeap中。然后每次弹出minHeap中频率最小的两个结点，将其合并成一个新的结点，并将新结点插入到minHeap中。重复上述步骤，直到minHeap中只剩下一个结点，即哈夫曼树的根节点。
4. generateHuffmanCode函数用于生成哈夫曼编码。采用递归的方式遍历哈夫曼树，对于每个叶子结点，将其对应的编码存储到codeMap中。具体实现中，对于每个结点，如果其左子结点和右子结点都为nullptr，则说明该结点是叶子结点，将其对应的编码存储到codeMap中；否则，依次处理其左子结点和右子结点，将其编码分别加上“0”和“1”。
5. compress函数用于压缩输入字符串。遍历输入字符串中的每个字符，将其对应的编码依次拼接到压缩后的字符串中。
6. decompress函数用于解压缩压缩后的字符串。遍历压缩后的字符串中的每个字符，依次沿着哈夫曼树的路径进行移动，直到到达叶子结点，将对应的字符存储到解压缩后的字符串中。

输出结果：

原始字符串: hello world
压缩后的字符串: 1101110110010011010101101100000001010101
解压缩后的字符串: hello world

可以看到，经过压缩和解压缩后，原始字符串没有发生变化。