C 语言实现的 Huffman 编码完整示例

这是一个完整的 Huffman 编码实现的 C 语言代码示例，涵盖了数据结构、最小堆操作、Huffman 树构建、编码表生成和文本编码等功能。

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

// 数据结构：Huffman 树的节点
struct Node {
    char data;
    unsigned int freq;
    struct Node* left;
    struct Node* right;
};

// 数据结构：最小堆
struct MinHeap {
    unsigned int size;
    unsigned int capacity;
    struct Node** array;
};

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

// 创建一个新的最小堆
struct MinHeap* createMinHeap(unsigned int capacity) {
    struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (struct Node**)malloc(capacity * sizeof(struct Node*));
    return minHeap;
}

// 交换两个节点
void swapNodes(struct Node** a, struct Node** b) {
    struct Node* temp = *a;
    *a = *b;
    *b = temp;
}

// 下溢最小堆
void minHeapify(struct MinHeap* minHeap, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

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

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

    if (smallest != index) {
        swapNodes(&minHeap->array[smallest], &minHeap->array[index]);
        minHeapify(minHeap, smallest);
    }
}

// 检查最小堆是否只有一个节点
int isSizeOne(struct MinHeap* minHeap) {
    return (minHeap->size == 1);
}

// 检查当前节点是否是叶子节点
int isLeaf(struct Node* root) {
    return !(root->left) && !(root->right);
}

// 创建一个最小堆并插入节点
void insertMinHeap(struct MinHeap* minHeap, struct Node* node) {
    ++minHeap->size;
    int i = minHeap->size - 1;

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

    minHeap->array[i] = node;
}

// 从最小堆中提取最小频率的节点
struct Node* extractMin(struct MinHeap* minHeap) {
    struct Node* temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

// 构建 Huffman 树
struct Node* buildHuffmanTree(char data[], unsigned int freq[], unsigned int size) {
    struct Node *left, *right, *top;

    // 创建一个空的最小堆
    struct MinHeap* minHeap = createMinHeap(size);

    // 将字符和频率转换为节点，并插入到最小堆中
    for (int i = 0; i < size; ++i) {
        insertMinHeap(minHeap, createNode(data[i], freq[i]));
    }

    // 直到堆中只剩下一个节点为止
    while (!isSizeOne(minHeap)) {
        // 提取两个最小频率的节点
        left = extractMin(minHeap);
        right = extractMin(minHeap);

        // 创建一个新的内部节点，作为两个提取的节点的父节点
        top = createNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;

        // 插入新的节点到最小堆中
        insertMinHeap(minHeap, top);
    }

    // Huffman 树的根节点
    return extractMin(minHeap);
}

// 生成编码表的递归辅助函数
void generateCodes(struct Node* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        generateCodes(root->left, arr, top + 1);
    }

    if (root->right) {
        arr[top] = 1;
        generateCodes(root->right, arr, top + 1);
    }

    // 当遇到叶子节点时，输出字符和编码
    if (isLeaf(root)) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; ++i) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

// 生成编码表
void generateCodeTable(struct Node* root) {
    int arr[100], top = 0;
    generateCodes(root, arr, top);
}

// 对文本进行编码
void encodeText(struct Node* root, char text[]) {
    if (root == NULL) {
        return;
    }

    // 遍历输入的文本
    for (int i = 0; text[i] != '\0'; ++i) {
        // 当遇到叶子节点时，输出编码
        if (isLeaf(root) && root->data != '$') {
            printf("%c", root->data);
            continue;
        }

        // 根据当前字符是 0 还是 1，移动到相应的子节点
        if (text[i] == '0') {
            root = root->left;
        } else {
            root = root->right;
        }
    }

    // 当遍历完整个文本后，输出最后一个叶子节点的字符
    if (isLeaf(root) && root->data != '$') {
        printf("%c", root->data);
    }
}

int main() {
    char data[] = { 'a', 'b', 'c', 'd', 'e', 'f' };
    unsigned int freq[] = { 5, 9, 12, 13, 16, 45 };
    unsigned int size = sizeof(data) / sizeof(data[0]);

    struct Node* root = buildHuffmanTree(data, freq, size);

    printf("生成的 Huffman 编码为：\n");
    generateCodeTable(root);

    printf("\n编码后的文本为：\n");
    encodeText(root, "efcab");

    return 0;
}

示例代码的使用方法：

1. 在 Code::Blocks 中创建一个新的 C 项目。
2. 将以上代码复制到 main.c 文件中。
3. 编译并运行代码。

输出结果：

代码运行后，会输出生成的 Huffman 编码表和编码后的文本。

自定义字符频率：

您可以根据需要自定义 data 和 freq 数组的内容，来改变字符和频率的对应关系。

注意：

• 代码中的 encodeText 函数只对编码后的文本进行解码，不进行实际的编码操作。
• 编码后的文本需要使用相应的解码器进行解码。
• 该代码示例只提供了一种基本的 Huffman 编码实现，具体的应用场景可能需要根据实际情况进行调整。

希望这个完整的代码示例能够帮助您进行 Huffman 编码的实现！如果您有任何进一步的问题，请随时提问。