简单实现哈夫曼编码c语言

哈夫曼编码是一种常用的数据压缩算法，它通过将出现频率较高的字符用较短的编码表示，从而实现数据的压缩。以下是一个简单实现哈夫曼编码的C语言代码示例：

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

// 定义哈夫曼树节点结构体
typedef struct HuffmanNode {
    char data;  // 字符数据
    int freq;   // 字符出现频率
    struct HuffmanNode *left;
    struct HuffmanNode *right;
} HuffmanNode;

// 创建哈夫曼树节点
HuffmanNode* createNode(char data, int freq) {
    HuffmanNode* node = (HuffmanNode*)malloc(sizeof(HuffmanNode));
    node->data = data;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 构建哈夫曼树
HuffmanNode* buildHuffmanTree(char data[], int freq[], int size) {
    // 创建叶子节点数组
    HuffmanNode* nodes[size];
    for (int i = 0; i < size; i++) {
        nodes[i] = createNode(data[i], freq[i]);
    }

    // 构建哈夫曼树
    while (size > 1) {
        // 找到频率最小的两个节点
        int min1 = 0, min2 = 1;
        if (nodes[min1]->freq > nodes[min2]->freq) {
            int temp = min1;
            min1 = min2;
            min2 = temp;
        }
        for (int i = 2; i < size; i++) {
            if (nodes[i]->freq < nodes[min1]->freq) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->freq < nodes[min2]->freq) {
                min2 = i;
            }
        }

        // 创建新节点，合并两个最小频率的节点
        HuffmanNode* newNode = createNode('$', nodes[min1]->freq + nodes[min2]->freq);
        newNode->left = nodes[min1];
        newNode->right = nodes[min2];

        // 删除已合并的节点
        nodes[min1] = newNode;
        for (int i = min2; i < size - 1; i++) {
            nodes[i] = nodes[i + 1];
        }

        size--;
    }

    // 返回根节点
    return nodes;
}

// 打印哈夫曼编码
void printHuffmanCodes(HuffmanNode* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printHuffmanCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printHuffmanCodes(root->right, arr, top + 1);
    }
    if (root->left == NULL && root->right == NULL) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

// 哈夫曼编码主函数
void huffmanEncoding(char data[], int freq[], int size) {
    HuffmanNode* root = buildHuffmanTree(data, freq, size);
    int arr[100], top = 0;
    printHuffmanCodes(root, arr, top);
}

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

    huffmanEncoding(data, freq, size);

    return 0;
}

以上是一个简单的哈夫曼编码的C语言实现示例。该示例中，首先定义了哈夫曼树节点的结构体，然后通过构建哈夫曼树来生成编码，并最终打印出每个字符对应的哈夫曼编码。