用C++实现赫夫曼编码及解码，并给出完整代码

以下是C++实现赫夫曼编码及解码的完整代码，注释比较详细，希望对您有帮助。

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <fstream>

using namespace std;

// 哈夫曼树节点结构体
struct HuffmanNode {
    char ch; // 字符
    int weight; // 权重
    HuffmanNode *left, *right; // 左右子节点

    HuffmanNode(char c, int w) : ch(c), weight(w), left(nullptr), right(nullptr) {}
    HuffmanNode(int w) : ch('\0'), weight(w), left(nullptr), right(nullptr) {}
};

// 用于哈夫曼树节点的比较，用于优先队列
struct cmp {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->weight > b->weight;
    }
};

// 建立哈夫曼树
HuffmanNode* buildHuffmanTree(map<char, int>& freq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, cmp> pq;
    // 将字符和对应的频率存入优先队列
    for (auto& p : freq) {
        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->weight + right->weight);
        parent->left = left;
        parent->right = right;
        // 将新节点加入优先队列
        pq.push(parent);
    }
    return pq.top();
}

// 哈夫曼编码表
map<char, string> HuffmanCodeTable;

// 生成哈夫曼编码表
void generateHuffmanCodeTable(HuffmanNode* root, string code) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        HuffmanCodeTable[root->ch] = code;
        return;
    }
    generateHuffmanCodeTable(root->left, code + '0');
    generateHuffmanCodeTable(root->right, code + '1');
}

// 哈夫曼编码
string huffmanEncode(string text) {
    string code;
    for (char c : text) {
        code += HuffmanCodeTable[c];
    }
    return code;
}

// 哈夫曼解码
string huffmanDecode(string code, HuffmanNode* root) {
    HuffmanNode* p = root;
    string text;
    for (char c : code) {
        if (c == '0') {
            p = p->left;
        }
        else {
            p = p->right;
        }
        if (p->left == nullptr && p->right == nullptr) {
            text += p->ch;
            p = root;
        }
    }
    return text;
}

int main() {
    // 统计字符频率
    map<char, int> freq;
    ifstream fin("input.txt");
    char c;
    while (fin >> noskipws >> c) {
        freq[c]++;
    }
    fin.close();
    // 建立哈夫曼树
    HuffmanNode* root = buildHuffmanTree(freq);
    // 生成哈夫曼编码表
    generateHuffmanCodeTable(root, "");
    // 读取要编码的文本
    fin.open("input.txt");
    string text;
    while (fin >> noskipws >> c) {
        text += c;
    }
    fin.close();
    // 哈夫曼编码
    string code = huffmanEncode(text);
    // 将编码结果写入文件
    ofstream fout("output.txt");
    fout << code;
    fout.close();
    // 读取要解码的文本
    fin.open("output.txt");
    code.clear();
    while (fin >> noskipws >> c) {
        code += c;
    }
    fin.close();
    // 哈夫曼解码
    string decodedText = huffmanDecode(code, root);
    // 将解码结果写入文件
    fout.open("decoded.txt");
    fout << decodedText;
    fout.close();
    return 0;
}