使用c语言根据哈夫曼树求哈夫曼编码代码实现

在C语言中，根据哈夫曼树（Huffman Tree）求哈夫曼编码通常涉及到构建二叉树、计算频率、构建优先队列以及生成编码等步骤。以下是一个简单的示例代码，展示了如何使用堆（Priority Queue）来实现：

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

// 结构体表示字符及其频率
typedef struct Node {
    char ch;
    int freq;
    struct Node* left, *right;
} Node;

// 比较函数用于堆操作
int compare(const void* a, const void* b) {
    return ((Node*)a)->freq - ((Node*)b)->freq;
}

// 创建一个新的节点
Node* newNode(char ch, int freq) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 构建最小堆
void heapify(Node** heap, int size, int i) {
    int smallest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;

    if (l < size && ((Node*)heap[l])->freq < ((Node*)heap[smallest])->freq)
        smallest = l;

    if (r < size && ((Node*)heap[r])->freq < ((Node*)heap[smallest])->freq)
        smallest = r;

    if (smallest != i) {
        Node* temp = heap[i];
        heap[i] = heap[smallest];
        heap[smallest] = temp;
        heapify(heap, size, smallest);
    }
}

// 哈夫曼编码生成
void huffmanCoding(Node* root, char* code, int* freq, int n) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        code[root->ch] = '0';
        printf("%c:%s ", root->ch, code[root->ch]);
    } else {
        huffmanCoding(root->left, code, freq, n);
        huffmanCoding(root->right, code, freq, n);
    }
}

// 主函数
int main() {
    // 假设输入字符及其频率
    char chars[] = {'A', 'B', 'C', 'D'};
    int freqs[] = {5, 3, 4, 2};
    int n = sizeof(chars) / sizeof(chars[0]);

    // 创建节点数组并排序
    Node** heap = malloc(n * sizeof(Node*));
    for (int i = 0; i < n; i++) {
        heap[i] = newNode(chars[i], freqs[i]);
        heapify(heap, n, i);
    }

    // 生成哈夫曼树
    while (n > 1) {
        Node* left = heap[0];
        heap[0] = heap[n - 1];
        n--;
        heapify(heap, n, 0);

        Node* right = heap[0];
        heap[0] = left;
        left->right = right;
        left->freq += right->freq;
        heapify(heap, n, 0);
    }

    char code[256];
    memset(code, '\0', sizeof(code));
    huffmanCoding(heap[0], code, freqs, n);

    // 输出哈夫曼编码
    printf("\nHuffman Codes:\n");
    for (char ch : chars)
        printf("%c: %s\n", ch, code[ch]);

    return 0;
}

这个例子展示了如何从给定的字符频率创建哈夫曼树，并生成对应的编码。注意，这只是一个基础版本，实际应用中可能需要处理更复杂的输入数据结构。