哈夫曼编码c语言

以下是基于哈夫曼编码的简单C语言实现：

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

#define MAX_TREE_HT 100

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

// 定义哈夫曼编码表
struct HuffmanTable {
    char data;
    char code[MAX_TREE_HT];
};

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

// 交换两个哈夫曼树节点的位置
void swapHuffmanNodes(struct HuffmanNode** a, struct HuffmanNode** b) {
    struct HuffmanNode* t = *a;
    *a = *b;
    *b = t;
}

// 对哈夫曼树节点按照频率排序
void sortHuffmanNodes(struct HuffmanNode** nodes, int size) {
    int i, j;
    for (i = 0; i < size - 1; i++) {
        for (j = 0; j < size - i - 1; j++) {
            if (nodes[j]->freq > nodes[j + 1]->freq) {
                swapHuffmanNodes(&nodes[j], &nodes[j + 1]);
            }
        }
    }
}

// 判断当前哈夫曼树节点是否为叶子节点
int isLeafNode(struct HuffmanNode* node) {
    return !(node->left) && !(node->right);
}

// 打印哈夫曼编码表
void printHuffmanTable(struct HuffmanTable* table, int size) {
    int i;
    printf("Huffman Table:\n");
    for (i = 0; i < size; i++) {
        printf("%c: %s\n", table[i].data, table[i].code);
    }
}

// 生成哈夫曼编码表
void generateHuffmanTable(struct HuffmanNode* root, char code[], int length, struct HuffmanTable table[], int* index) {
    if (root->left) {
        code[length] = '0';
        generateHuffmanTable(root->left, code, length + 1, table, index);
    }
    if (root->right) {
        code[length] = '1';
        generateHuffmanTable(root->right, code, length + 1, table, index);
    }
    if (isLeafNode(root)) {
        table[*index].data = root->data;
        memcpy(table[*index].code, code, length);
        table[*index].code[length] = '\0';
        (*index)++;
    }
}

// 生成哈夫曼树
struct HuffmanNode* generateHuffmanTree(char data[], unsigned freq[], int size) {
    struct HuffmanNode *left, *right, *top;
    struct HuffmanNode* nodes[MAX_TREE_HT];
    int i, topIndex = 0;

    // 初始化哈夫曼树节点
    for (i = 0; i < size; i++) {
        nodes[i] = createHuffmanNode(data[i], freq[i]);
    }

    // 对哈夫曼树节点按照频率排序
    sortHuffmanNodes(nodes, size);

    // 构建哈夫曼树
    while (size > 1) {
        left = nodes[0];
        right = nodes[1];
        top = createHuffmanNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        nodes[0] = top;
        size--;
        for (i = 1; i < size; i++) {
            nodes[i] = nodes[i + 1];
        }
        sortHuffmanNodes(nodes, size);
    }

    return nodes[0];
}

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

    // 生成哈夫曼编码表
    struct HuffmanTable table[size];
    char code[MAX_TREE_HT];
    int index = 0;
    generateHuffmanTable(root, code, 0, table, &index);

    // 打印哈夫曼编码表
    printHuffmanTable(table, index);

    return 0;
}

以上代码实现了一个简单的哈夫曼编码，在生成哈夫曼编码表时，通过递归遍历哈夫曼树，对每个叶子节点生成对应的编码。