哈夫曼编码算法c++

哈夫曼编码是一种无损压缩算法，常用于数据压缩和传输。下面是一个简单的C语言实现示例：

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

// 哈夫曼树节点结构体
typedef struct HuffmanNode {
    unsigned char data;  // 字符
    int freq;  // 频率
    struct HuffmanNode* left;
    struct HuffmanNode* right;
} HuffmanNode;

// 创建哈夫曼树节点
HuffmanNode* createNode(unsigned 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(unsigned char data[], int freq[], int size) {
    // 构建初始节点数组
    HuffmanNode** nodes = (HuffmanNode**)malloc(size * sizeof(HuffmanNode*));
    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* parent = createNode('$', nodes[min1]->freq + nodes[min2]->freq);
        parent->left = nodes[min1];
        parent->right = nodes[min2];

        // 从节点数组中删除已合并的节点，将父节点插入
        nodes[min1] = parent;
        for (int i = min2; i < size - 1; i++) {
            nodes[i] = nodes[i + 1];
        }

        size--;
    }

    // 返回根节点
    return nodes[0];
}

// 生成哈夫曼编码表
void generateHuffmanCodes(HuffmanNode* root, int code[], int top) {
    static int huffmanCodes[256][100];
    if (root->left) {
        code[top] = 0;
        generateHuffmanCodes(root->left, code, top + 1);
    }
    if (root->right) {
        code[top] = 1;
        generateHuffmanCodes(root->right, code, top + 1);
    }
    if (!root->left && !root->right) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; i++) {
            huffmanCodes[root->data][i] = code[i];
            printf("%d", code[i]);
        }
        printf("\n");
    }
}

// 哈夫曼编码
void huffmanEncode(unsigned char data[], int freq[], int size) {
    HuffmanNode* root = buildHuffmanTree(data, freq, size);
    int code[100];
    int top = 0;
    generateHuffmanCodes(root, code, top);
}

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

以上是一个简单的哈夫曼编码的C语言实现示例。它包括了构建哈夫曼树、生成哈夫曼编码表和对指定数据进行哈夫曼编码的功能。你可以根据实际需求进行修改和扩展。