dev c++基于哈夫曼树的数据压缩算法代码

#include <iostream>
#include <queue>
#include <vector>
#include <string>
#include <fstream>
using namespace std;

struct Node {
    char ch;
    int freq;
    Node* left;
    Node* right;
    Node(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
    Node(int f) : freq(f), left(nullptr), right(nullptr) {}
    bool operator>(const Node& n) const {
        return freq > n.freq;
    }
};

void getFreq(string& s, vector<int>& freq) {
    for (char c : s) {
        freq[c]++;
    }
}

Node* buildHuffmanTree(vector<int>& freq) {
    priority_queue<Node, vector<Node>, greater<Node>> pq;
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            pq.push(Node(i, freq[i]));
        }
    }
    while (pq.size() > 1) {
        Node* left = new Node(pq.top().ch, pq.top().freq);
        pq.pop();
        Node* right = new Node(pq.top().ch, pq.top().freq);
        pq.pop();
        Node* parent = new Node(left->freq + right->freq);
        parent->left = left;
        parent->right = right;
        pq.push(*parent);
    }
    Node* root = new Node(pq.top().ch, pq.top().freq);
    return root;
}

void getHuffmanCode(Node* root, vector<string>& code, string path) {
    if (!root) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        code[root->ch] = path;
    }
    getHuffmanCode(root->left, code, path + "0");
    getHuffmanCode(root->right, code, path + "1");
}

void compress(string& s, vector<string>& code, string& compressed) {
    for (char c : s) {
        compressed += code[c];
    }
}

void writeToFile(string& compressed, string& filename) {
    ofstream out(filename, ios::binary);
    int len = compressed.length();
    out.write((char*)&len, sizeof(int));
    int pos = 0;
    while (pos < len) {
        char c = 0;
        for (int i = 0; i < 8; i++) {
            if (pos + i >= len) {
                break;
            }
            if (compressed[pos + i] == '1') {
                c |= (1 << (7 - i));
            }
        }
        pos += 8;
        out.write(&c, sizeof(char));
    }
    out.close();
}

void readFromFile(string& compressed, string& filename) {
    ifstream in(filename, ios::binary);
    int len;
    in.read((char*)&len, sizeof(int));
    char c;
    while (in.read(&c, sizeof(char))) {
        for (int i = 7; i >= 0; i--) {
            if (compressed.length() == len) {
                break;
            }
            if (c & (1 << i)) {
                compressed += '1';
            }
            else {
                compressed += '0';
            }
        }
    }
    in.close();
}

void decompress(Node* root, string& compressed, string& decompressed) {
    Node* p = root;
    for (char c : compressed) {
        if (c == '0') {
            p = p->left;
        }
        else {
            p = p->right;
        }
        if (p->left == nullptr && p->right == nullptr) {
            decompressed += p->ch;
            p = root;
        }
    }
}

int main() {
    string s = "This is a test string for Huffman coding.";
    vector<int> freq(256, 0);
    getFreq(s, freq);
    Node* root = buildHuffmanTree(freq);
    vector<string> code(256);
    getHuffmanCode(root, code, "");
    string compressed;
    compress(s, code, compressed);
    writeToFile(compressed, "compressed.bin");
    string compressed2;
    readFromFile(compressed2, "compressed.bin");
    string decompressed;
    decompress(root, compressed2, decompressed);
    cout << "Original string: " << s << endl;
    cout << "Compressed string: " << compressed << endl;
    cout << "Decompressed string: " << decompressed << endl;
    return 0;
}