贪心法解决文件压缩问题C++代码

文件压缩问题可以使用哈夫曼编码算法解决，而哈夫曼编码算法可以用贪心法来实现。下面是使用贪心法实现哈夫曼编码的C++代码：

首先是定义哈夫曼树节点的结构体：

struct TreeNode {
    char ch;  // 字符
    int freq; // 频率
    TreeNode *left, *right; // 左右子节点
    TreeNode(char _ch, int _freq) : ch(_ch), freq(_freq), left(nullptr), right(nullptr) {}
    ~TreeNode() { delete left; delete right; }
};

接着是比较函数，用于排序：

struct cmp {
    bool operator()(const TreeNode* a, const TreeNode* b) const {
        return a->freq > b->freq;
    }
};

然后是构建哈夫曼树的函数：

TreeNode* buildHuffmanTree(const string& str) {
    unordered_map<char, int> freqMap;
    for (char ch : str) {
        freqMap[ch]++;
    }

    priority_queue<TreeNode*, vector<TreeNode*>, cmp> pq;
    for (auto it : freqMap) {
        pq.push(new TreeNode(it.first, it.second));
    }

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

    return pq.top();
}

接下来是构建哈夫曼编码表的函数：

unordered_map<char, string> buildHuffmanTable(TreeNode* root) {
    unordered_map<char, string> huffmanTable;
    function<void(TreeNode*, string)> dfs = [&](TreeNode* node, string code) {
        if (node->left == nullptr && node->right == nullptr) {
            huffmanTable[node->ch] = code;
            return;
        }
        dfs(node->left, code + '0');
        dfs(node->right, code + '1');
    };
    dfs(root, "");
    return huffmanTable;
}

最后是压缩和解压缩的函数：

string compress(const string& str) {
    TreeNode* root = buildHuffmanTree(str);
    unordered_map<char, string> huffmanTable = buildHuffmanTable(root);
    string compressedStr;
    for (char ch : str) {
        compressedStr += huffmanTable[ch];
    }
    delete root;
    return compressedStr;
}

string decompress(const string& compressedStr, TreeNode* root) {
    string decompressedStr;
    TreeNode* node = root;
    for (char ch : compressedStr) {
        node = (ch == '0') ? node->left : node->right;
        if (node->left == nullptr && node->right == nullptr) {
            decompressedStr += node->ch;
            node = root;
        }
    }
    return decompressedStr;
}

以上就是使用贪心法实现哈夫曼编码的C++代码。