C++实现文件压缩工具 基本压缩算法实践解析

struct Node {
    uint8_t byte;
    int freq;
    Node *left, *right;
<pre class='brush:php;toolbar:false;'>Node(uint8_t b, int f) : byte(b), freq(f), left(nullptr), right(nullptr) {}

auto cmp = [](Node* a, Node* b) { return a->freq > b->freq; };
std::priority_queue<Node*, std::vector<Node*>, decltype(cmp)> pq(cmp);
<p>// 统计频率后，将每个字节作为叶子节点入队
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
pq.push(new Node(static_cast<uint8_t>(i), freq[i]));
}
}</p><p>// 构建树
while (pq.size() > 1) {
Node <em>left = pq.top(); pq.pop();
Node </em>right = pq.top(); pq.pop();
Node *parent = new Node(0, left->freq + right->freq);
parent->left = left;
parent->right = right;
pq.push(parent);
}</p>

void buildCode(std::string code, Node* node, std::string codes[256]) {
    if (!node) return;
    if (!node->left && !node->right) {
        codes[node->byte] = code.empty() ? "0" : code;
    }
    buildCode(code + "0", node->left, codes);
    buildCode(code + "1", node->right, codes);
}

uint8_t buffer = 0;
int bitCount = 0;
<p>void writeBit(std::ofstream& out, int bit) {
buffer |= (bit << (7 - bitCount));
bitCount++;
if (bitCount == 8) {
out.write(reinterpret_cast<char*>(&buffer), 1);
buffer = 0;
bitCount = 0;
}
}</p>

compress("input.txt", "output.bin");
decompress("output.bin", "restored.txt");