用c语言写一个关于哈夫曼树和哈夫曼编码的代码

好的，下面是一个基于C语言实现的简单的哈夫曼编码和译码程序：

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

#define MAX_TREE_HT 100

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

// 定义哈夫曼编码表结构体
struct HuffmanCode {
    char data;
    char *code;
};

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

// 交换两个哈夫曼树节点
void swapNodes(struct HuffmanNode **a, struct HuffmanNode **b) {
    struct HuffmanNode *temp = *a;
    *a = *b;
    *b = temp;
}

// 对哈夫曼树节点数组进行排序（根据频率从小到大）
void sortNodes(struct HuffmanNode **nodes, int n) {
    int i, j;
    for (i = 0; i < n - 1; i++) {
        for (j = 0; j < n - i - 1; j++) {
            if (nodes[j]->freq > nodes[j + 1]->freq) {
                swapNodes(&nodes[j], &nodes[j + 1]);
            }
        }
    }
}

// 构建哈夫曼树
struct HuffmanNode *buildHuffmanTree(char data[], int freq[], int n) {
    // 创建哈夫曼树节点数组
    struct HuffmanNode **nodes = (struct HuffmanNode **) malloc(n * sizeof(struct HuffmanNode *));
    int i;
    for (i = 0; i < n; i++) {
        nodes[i] = createHuffmanNode(data[i], freq[i]);
    }

    // 对哈夫曼树节点数组进行排序
    sortNodes(nodes, n);

    // 构建哈夫曼树
    while (n > 1) {
        // 选取最小的两个节点作为左右子节点
        struct HuffmanNode *left = nodes[0];
        struct HuffmanNode *right = nodes[1];
        // 创建新节点，其频率为左右子节点频率之和
        struct HuffmanNode *node = createHuffmanNode('\0', left->freq + right->freq);
        node->left = left;
        node->right = right;
        // 将新节点插入到节点数组中
        nodes[0] = node;
        // 对节点数组进行排序，继续构建哈夫曼树
        sortNodes(nodes, n);
        n--;
    }

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

// 生成哈夫曼编码表
void generateHuffmanCodeTable(struct HuffmanNode *root, char *prefix, int prefixLen, struct HuffmanCode *table, int *size) {
    if (!root) {
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        // 叶子节点，将编码存入哈夫曼编码表
        table[*size].data = root->data;
        table[*size].code = (char *) malloc((prefixLen + 1) * sizeof(char));
        strcpy(table[*size].code, prefix);
        (*size)++;
    } else {
        // 非叶子节点，递归生成左右子树的编码
        prefix[prefixLen] = '0';
        prefix[prefixLen + 1] = '\0';
        generateHuffmanCodeTable(root->left, prefix, prefixLen + 1, table, size);

        prefix[prefixLen] = '1';
        prefix[prefixLen + 1] = '\0';
        generateHuffmanCodeTable(root->right, prefix, prefixLen + 1, table, size);
    }
}

// 将字符串编码为哈夫曼编码
char *encodeString(char *str, struct HuffmanCode *table, int size) {
    int len = strlen(str);
    char *code = (char *) malloc(MAX_TREE_HT * sizeof(char));
    code[0] = '\0';
    int i, j;
    for (i = 0; i < len; i++) {
        for (j = 0; j < size; j++) {
            if (table[j].data == str[i]) {
                strcat(code, table[j].code);
                break;
            }
        }
    }
    return code;
}

// 将哈夫曼编码解码为字符串
char *decodeCode(char *code, struct HuffmanNode *root) {
    char *str = (char *) malloc(MAX_TREE_HT * sizeof(char));
    str[0] = '\0';
    struct HuffmanNode *current = root;
    int i;
    for (i = 0; code[i] != '\0'; i++) {
        if (code[i] == '0') {
            current = current->left;
        } else if (code[i] == '1') {
            current = current->right;
        }
        if (current->left == NULL && current->right == NULL) {
            // 找到叶子节点，将其对应的字符加入解码字符串
            str[strlen(str)] = current->data;
            current = root;
        }
    }
    return str;
}

int main() {
    char data[] = {'a', 'b', 'c', 'd', 'e'};
    int freq[] = {5, 3, 2, 4, 1};
    int n = sizeof(data) / sizeof(data[0]);

    // 构建哈夫曼树
    struct HuffmanNode *root = buildHuffmanTree(data, freq, n);

    // 生成哈夫曼编码表
    struct HuffmanCode table[n];
    char prefix[MAX_TREE_HT];
    prefix[0] = '\0';
    int size = 0;
    generateHuffmanCodeTable(root, prefix, 0, table, &size);

    // 输出哈夫曼编码表
    printf("Huffman Code Table:\n");
    int i;
    for (i = 0; i < size; i++) {
        printf("  %c: %s\n", table[i].data, table[i].code);
    }

    // 编码字符串
    char *str = "abacabad";
    char *code = encodeString(str, table, size);
    printf("Encoded string: %s\n", code);

    // 解码哈夫曼编码
    char *decodedStr = decodeCode(code, root);
    printf("Decoded string: %s\n", decodedStr);

    return 0;
}

在这个程序中，我们首先定义了哈夫曼树节点和哈夫曼编码表的结构体。然后，我们用 `createHuffmanNode` 函数创建哈夫曼树节点，用 `swapNodes` 和 `sortNodes` 函数对哈夫曼树节点数组进行排序，用 `buildHuffmanTree` 函数构建哈夫曼树。接着，我们用 `generateHuffmanCodeTable` 函数生成哈夫曼编码表，用 `encodeString` 函数将字符串编码为哈夫曼编码，用 `decodeCode` 函数将哈夫曼编码解码为字符串。最后，在 `main` 函数中，我们演示了如何使用这些函数来进行哈夫曼编码和译码。