基于哈夫曼树的数据压缩算法c语言

哈夫曼树是一种经典的数据压缩算法，可以有效地压缩文本、音频、图像等数据。下面是一个基于哈夫曼树的数据压缩算法的C语言实现：

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

#define MAX_SIZE 256

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

typedef struct MinHeap {
    int size;
    Node **nodes;
} MinHeap;

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

MinHeap *createMinHeap(int capacity) {
    MinHeap *minHeap = (MinHeap*)malloc(sizeof(MinHeap));
    minHeap->size = 0;
    minHeap->nodes = (Node**)malloc(capacity * sizeof(Node*));
    return minHeap;
}

void swapNodes(Node **a, Node **b) {
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

void minHeapify(MinHeap *minHeap, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    if (left < minHeap->size && minHeap->nodes[left]->freq < minHeap->nodes[smallest]->freq) {
        smallest = left;
    }
    if (right < minHeap->size && minHeap->nodes[right]->freq < minHeap->nodes[smallest]->freq) {
        smallest = right;
    }
    if (smallest != index) {
        swapNodes(&minHeap->nodes[index], &minHeap->nodes[smallest]);
        minHeapify(minHeap, smallest);
    }
}

int isSizeOne(MinHeap *minHeap) {
    return (minHeap->size == 1);
}

Node *extractMin(MinHeap *minHeap) {
    Node *temp = minHeap->nodes[0];
    minHeap->nodes[0] = minHeap->nodes[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

void insertMinHeap(MinHeap *minHeap, Node *node) {
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && node->freq < minHeap->nodes[(i - 1) / 2]->freq) {
        minHeap->nodes[i] = minHeap->nodes[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->nodes[i] = node;
}

void buildMinHeap(MinHeap *minHeap) {
    int n = minHeap->size - 1;
    for (int i = (n - 1) / 2; i >= 0; --i) {
        minHeapify(minHeap, i);
    }
}

void printCodes(Node *root, unsigned char *code, int top, unsigned char *codes[]) {
    if (root->left) {
        code[top] = '0';
        printCodes(root->left, code, top + 1, codes);
    }
    if (root->right) {
        code[top] = '1';
        printCodes(root->right, code, top + 1, codes);
    }
    if (!root->left && !root->right) {
        code[top] = '\0';
        codes[root->data] = (unsigned char*)malloc(strlen((char*)code) + 1);
        strcpy((char*)codes[root->data], (char*)code);
    }
}

void encodeFile(char *filename, unsigned char *codes[]) {
    FILE *inputFile = fopen(filename, "rb");
    FILE *outputFile = fopen(strcat(filename, ".huff"), "wb");
    unsigned char buffer = 0;
    int bitsWritten = 0;
    int bytesRead;
    while ((bytesRead = fread(&buffer, sizeof(unsigned char), 1, inputFile))) {
        for (int i = 0; i < strlen((char*)codes[buffer]); ++i) {
            if (codes[buffer][i] == '1') {
                buffer |= 1 << (7 - bitsWritten);
            } else {
                buffer &= ~(1 << (7 - bitsWritten));
            }
            ++bitsWritten;
            if (bitsWritten == 8) {
                fwrite(&buffer, sizeof(unsigned char), 1, outputFile);
                buffer = 0;
                bitsWritten = 0;
            }
        }
    }
    if (bitsWritten > 0) {
        fwrite(&buffer, sizeof(unsigned char), 1, outputFile);
    }
    fclose(inputFile);
    fclose(outputFile);
}

void decodeFile(char *filename, Node *root) {
    FILE *inputFile = fopen(filename, "rb");
    FILE *outputFile = fopen(strtok(filename, "."), "wb");
    unsigned char buffer = 0;
    int bitsRead = 0;
    Node *current = root;
    while (fread(&buffer, sizeof(unsigned char), 1, inputFile)) {
        for (int i = 0; i < 8; ++i) {
            if (buffer & (1 << (7 - bitsRead))) {
                current = current->right;
            } else {
                current = current->left;
            }
            if (!current->left && !current->right) {
                fwrite(&current->data, sizeof(unsigned char), 1, outputFile);
                current = root;
            }
            ++bitsRead;
        }
    }
    fclose(inputFile);
    fclose(outputFile);
}

void buildHuffmanTree(unsigned char *data, int *freq, int size, Node **root) {
    MinHeap *minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i) {
        insertMinHeap(minHeap, newNode(data[i], freq[i]));
    }
    buildMinHeap(minHeap);
    while (!isSizeOne(minHeap)) {
        Node *left = extractMin(minHeap);
        Node *right = extractMin(minHeap);
        Node *node = newNode(0, left->freq + right->freq);
        node->left = left;
        node->right = right;
        insertMinHeap(minHeap, node);
    }
    *root = extractMin(minHeap);
}

void compress(char *filename) {
    FILE *inputFile = fopen(filename, "rb");
    unsigned char data[MAX_SIZE];
    int freq[MAX_SIZE] = {0};
    int size = 0;
    unsigned char ch;
    while (fread(&ch, sizeof(unsigned char), 1, inputFile)) {
        if (freq[ch] == 0) {
            ++size;
        }
        ++freq[ch];
        data[strlen((char*)data)] = ch;
    }
    fclose(inputFile);
    Node *root;
    buildHuffmanTree(data, freq, size, &root);
    unsigned char *codes[MAX_SIZE] = {0};
    unsigned char code[MAX_SIZE];
    printCodes(root, code, 0, codes);
    encodeFile(filename, codes);
}

void decompress(char *filename) {
    FILE *inputFile = fopen(filename, "rb");
    unsigned char data[MAX_SIZE];
    int freq[MAX_SIZE] = {0};
    int size = 0;
    unsigned char ch;
    while (fread(&ch, sizeof(unsigned char), 1, inputFile)) {
        if (freq[ch] == 0) {
            ++size;
        }
        ++freq[ch];
        data[strlen((char*)data)] = ch;
    }
    fclose(inputFile);
    Node *root;
    buildHuffmanTree(data, freq, size, &root);
    decodeFile(filename, root);
}

int main() {
    char filename[MAX_SIZE];
    printf("Enter file name: ");
    scanf("%s", filename);
    compress(filename);
    decompress(strcat(filename, ".huff"));
    return 0;
}

该程序实现了对文件进行压缩和解压缩的功能，使用了哈夫曼树来构建编码表，并使用文件输入输出来进行读写。