C++ 使用哈夫曼编码压缩图片的代码

哈夫曼编码是一种无损压缩方法，可以用于对图片进行压缩。下面是一个使用哈夫曼编码压缩图片的示例代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODE 256

typedef struct Node {
    unsigned char ch;
    int freq;
    struct Node *left, *right;
} Node;

typedef struct Heap {
    int size;
    Node *array[MAX_NODE];
} Heap;

typedef struct Code {
    unsigned char *bits;
    int size;
} Code;

typedef struct Table {
    Code codes[MAX_NODE];
} Table;

Node *createNode(unsigned char ch, int freq) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = node->right = NULL;
    return node;
}

Heap *createHeap() {
    Heap *heap = (Heap*) malloc(sizeof(Heap));
    heap->size = 0;
    return heap;
}

void swap(Node **a, Node **b) {
    Node *tmp = *a;
    *a = *b;
    *b = tmp;
}

void heapify(Heap *heap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;

    if (left < heap->size && heap->array[left]->freq < heap->array[smallest]->freq)
        smallest = left;

    if (right < heap->size && heap->array[right]->freq < heap->array[smallest]->freq)
        smallest = right;

    if (smallest != idx) {
        swap(&heap->array[idx], &heap->array[smallest]);
        heapify(heap, smallest);
    }
}

int isLeaf(Node *node) {
    return !node->left && !node->right;
}

Node *extractMin(Heap *heap) {
    Node *node = heap->array[0];
    heap->array[0] = heap->array[heap->size - 1];
    heap->size--;
    heapify(heap, 0);
    return node;
}

void insertHeap(Heap *heap, Node *node) {
    heap->size++;
    int i = heap->size - 1;

    while (i && node->freq < heap->array[(i - 1) / 2]->freq) {
        heap->array[i] = heap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }

    heap->array[i] = node;
}

Heap *buildHeap(int *freq) {
    Heap *heap = createHeap();

    for (int i = 0; i < MAX_NODE; i++)
        if (freq[i])
            insertHeap(heap, createNode(i, freq[i]));

    while (heap->size > 1) {
        Node *left = extractMin(heap);
        Node *right = extractMin(heap);
        Node *node = createNode('$', left->freq + right->freq);
        node->left = left;
        node->right = right;
        insertHeap(heap, node);
    }

    return heap;
}

void encode(Node *root, Code code, Table *table) {
    if (root) {
        if (isLeaf(root)) {
            table->codes[root->ch] = code;
        } else {
            Code leftCode = code;
            leftCode.bits[code.size++] = '0';
            encode(root->left, leftCode, table);
            Code rightCode = code;
            rightCode.bits[code.size++] = '1';
            encode(root->right, rightCode, table);
        }
    }
}

void writeHeader(FILE *fp, int *freq) {
    fwrite(freq, sizeof(int), MAX_NODE, fp);
}

void writeBits(FILE *fp, Code code, int *pos) {
    int bytePos = *pos / 8;
    int bitPos = *pos % 8;

    for (int i = 0; i < code.size; i++) {
        if (code.bits[i] == '1')
            fp[bytePos] |= 1 << bitPos;

        bitPos++;
        (*pos)++;

        if (bitPos == 8) {
            bytePos++;
            bitPos = 0;
        }
    }
}

void compress(char *filename) {
    FILE *fp = fopen(filename, "rb");
    char outFilename[256];
    strcpy(outFilename, filename);
    strcat(outFilename, ".huff");
    FILE *outFp = fopen(outFilename, "wb");

    int freq[MAX_NODE] = {0};
    unsigned char ch;

    while (fread(&ch, sizeof(unsigned char), 1, fp))
        freq[ch]++;

    Heap *heap = buildHeap(freq);
    Node *root = extractMin(heap);
    Table *table = (Table*) malloc(sizeof(Table));

    for (int i = 0; i < MAX_NODE; i++)
        table->codes[i].bits = (unsigned char*) malloc(256);

    Code code;
    code.bits = (unsigned char*) malloc(256);
    code.size = 0;
    encode(root, code, table);

    writeHeader(outFp, freq);

    fseek(fp, 0, SEEK_SET);

    int pos = 0;
    unsigned char buffer = 0;

    while (fread(&ch, sizeof(unsigned char), 1, fp)) {
        Code code = table->codes[ch];
        writeBits(&buffer, code, &pos);

        while (pos >= 8) {
            fwrite(&buffer, sizeof(unsigned char), 1, outFp);
            buffer = buffer >> 8;
            pos -= 8;
        }
    }

    if (pos)
        fwrite(&buffer, sizeof(unsigned char), 1, outFp);

    fclose(fp);
    fclose(outFp);
}

int main(int argc, char *argv[]) {
    if (argc != 2) {
        printf("Usage: %s <filename>\n", argv[0]);
        return 1;
    }

    compress(argv[1]);

    return 0;
}

这个程序将输入的图片文件进行压缩，并将压缩后的数据写入一个新的文件中。输出的文件名为原文件名加上 ".huff" 后缀。程序使用了哈夫曼编码来压缩数据。在压缩过程中先统计每个字节出现的频率，然后使用哈夫曼树来构建编码表，并将编码表写入输出文件的头部。接着遍历输入文件的每个字节，并将其对应的编码写入输出文件中。最后，如果最后一个字节的编码不足一个字节，将其填充为 0 后写入输出文件中。