哈夫曼编码c语言

哈夫曼编码是一种数据压缩算法，可以将原始数据压缩为更小的数据，同时保持数据的完整性。下面是一个使用C语言实现哈夫曼编码的示例：

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

#define MAX_TREE_HT 100

/* 定义哈夫曼树节点结构体 */
struct node {
    char data;
    unsigned freq;
    struct node *left, *right;
};

/* 定义哈夫曼编码结构体 */
struct code {
    char data;
    char bits[MAX_TREE_HT];
};

/* 定义哈夫曼树节点堆结构体 */
struct heap {
    unsigned size;
    unsigned capacity;
    struct node **array;
};

/* 创建一个新的哈夫曼树节点 */
struct node* newNode(char data, unsigned freq)
{
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->left = node->right = NULL;
    node->data = data;
    node->freq = freq;
    return node;
}

/* 创建一个新的哈夫曼树节点堆 */
struct heap* createHeap(unsigned capacity)
{
    struct heap* heap = (struct heap*)malloc(sizeof(struct heap));
    heap->size = 0;
    heap->capacity = capacity;
    heap->array = (struct node**)malloc(heap->capacity * sizeof(struct node*));
    return heap;
}

/* 交换两个哈夫曼树节点 */
void swapNode(struct node** a, struct node** b)
{
    struct node* t = *a;
    *a = *b;
    *b = t;
}

/* 维护哈夫曼树节点堆的性质 */
void heapify(struct 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) {
        swapNode(&heap->array[smallest], &heap->array[idx]);
        heapify(heap, smallest);
    }
}

/* 判断堆是否为空 */
int isHeapEmpty(struct heap* heap)
{
    return heap->size == 0;
}

/* 取出堆中的最小元素 */
struct node* extractMin(struct heap* heap)
{
    struct node* temp = heap->array[0];
    heap->array[0] = heap->array[heap->size - 1];
    --heap->size;
    heapify(heap, 0);
    return temp;
}

/* 插入一个节点到堆中 */
void insertNode(struct heap* heap, struct 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;
}

/* 判断是否为叶子节点 */
int isLeaf(struct node* node)
{
    return !(node->left) && !(node->right);
}

/* 创建哈夫曼树 */
struct node* buildHuffmanTree(char data[], int freq[], int size)
{
    struct node *left, *right, *top;
    struct heap* heap = createHeap(size);
    for (int i = 0; i < size; ++i)
        insertNode(heap, newNode(data[i], freq[i]));
    while (heap->size > 1) {
        left = extractMin(heap);
        right = extractMin(heap);
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertNode(heap, top);
    }
    return extractMin(heap);
}

/* 设置哈夫曼编码 */
void setCode(struct node* node, char code[], int top, struct code codes[])
{
    if (node->left) {
        code[top] = '0';
        setCode(node->left, code, top + 1, codes);
    }
    if (node->right) {
        code[top] = '1';
        setCode(node->right, code, top + 1, codes);
    }
    if (isLeaf(node)) {
        struct code c = { node->data };
        strncpy(c.bits, code, top);
        codes[node->data] = c;
    }
}

/* 压缩数据 */
void compressData(char data[], struct code codes[], FILE *fp)
{
    int i = 0;
    while (data[i]) {
        struct code c = codes[data[i]];
        fwrite(c.bits, sizeof(char), strlen(c.bits), fp);
        ++i;
    }
}

/* 解压数据 */
void decompressData(struct node* root, char code[], int index, FILE *fp)
{
    if (!root)
        return;
    if (isLeaf(root)) {
        printf("%c", root->data);
        fwrite(&root->data, sizeof(char), 1, fp);
        return;
    }
    index++;
    if (code[index] == '0')
        decompressData(root->left, code, index, fp);
    else
        decompressData(root->right, code, index, fp);
}

/* 主函数 */
int main()
{
    char data[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    int freq[] = { 5, 9, 12, 13, 16, 45 };
    int size = sizeof(data) / sizeof(data[0]);
    struct node* root = buildHuffmanTree(data, freq, size);
    struct code codes[MAX_TREE_HT] = { 0 };
    char code[MAX_TREE_HT] = { 0 };
    int top = 0;
    setCode(root, code, top, codes);
    printf("Huffman Codes are:\n");
    for (int i = 0; i < size; ++i)
        printf("%c: %s\n", data[i], codes[data[i]].bits);
    FILE *fp = fopen("compressed.bin", "wb");
    compressData("abcdef", codes, fp);
    fclose(fp);
    fp = fopen("compressed.bin", "rb");
    fseek(fp, 0L, SEEK_END);
    int file_size = ftell(fp);
    rewind(fp);
    char *buffer = (char*)malloc(file_size);
    fread(buffer, sizeof(char), file_size, fp);
    printf("\nCompressed data:");
    for (int i = 0; i < file_size; ++i)
        printf("%c", buffer[i]);
    printf("\nDecompressed data:");
    FILE *fp1 = fopen("decompressed.bin", "wb");
    int index = -1;
    while (index < file_size - 2)
        decompressData(root, buffer, &index, fp1);
    fclose(fp1);
    fclose(fp);
    return 0;
}

在上面的示例中，我们定义了结构体 `node` 表示哈夫曼树节点，结构体 `code` 表示哈夫曼编码，结构体 `heap` 表示哈夫曼树节点堆。我们还定义了一些函数来操作这些结构体，如 `newNode` 创建一个新的哈夫曼树节点，`createHeap` 创建一个新的哈夫曼树节点堆，`heapify` 维护堆的性质，`extractMin` 取出堆中的最小元素等。

在主函数中，我们首先定义了一些数据和频率，然后使用 `buildHuffmanTree` 函数创建哈夫曼树。接着，我们使用 `setCode` 函数设置哈夫曼编码，并使用 `compressData` 函数压缩数据，并将压缩后的数据写入到文件中。最后，我们使用 `decompressData` 函数解压数据，并将解压后的数据写入到文件中。

这就是一个简单的哈夫曼编码的C语言实现。