实现一个简单的哈夫曼编码器，能根据给定的权值构造哈夫曼树，并根据建立好的哈夫曼树求出哈夫曼编码及WPL。c语言

要实现一个简单的哈夫曼编码器，首先需要了解哈夫曼编码的基本原理。哈夫曼编码是一种自底向上的贪心算法，用于构建最优前缀码。以下是使用C语言实现的一个简化版本：

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

// 结点结构体
typedef struct {
    int data;
    int freq;
    struct node* left;
    struct node* right;
} Node;

// 创建一个新的结点
Node* newNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->freq = 0;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 比较两个结点的频率
int compare(const void *a, const void *b) {
    return ((Node*)a)->freq - ((Node*)b)->freq;
}

// 插入结点到堆
void insert(Node** heap, Node* newNode) {
    if (*heap == NULL || ((*heap)->freq <= newNode->freq)) {
        newNode->left = *heap;
        *heap = newNode;
    } else {
        Node* temp = *heap;
        while (temp != NULL && newNode->freq < temp->freq) {
            *heap = temp;
            temp = temp->left;
        }
        newNode->left = temp->left;
        temp->left = newNode;
    }
}

// 构建哈夫曼树
Node* buildHuffmanTree(Node** heap) {
    if (*heap == NULL || (*heap)->left == NULL)
        return *heap;
    
    Node* temp = newNode(0);
    temp->left = buildHuffmanTree(heap);
    temp->right = buildHuffmanTree(&(*heap)->left);
    free(*heap);
    *heap = temp;
    return temp;
}

// 打印哈夫曼编码
void printCodes(Node* root, char* code, int index) {
    if (root == NULL) return;
    if (root->left == NULL && root->right == NULL) {
        printf("%d: %s", root->data, code + index);
        index += strlen(code + index);
        printf("\n");
    } else {
        printCodes(root->left, code, index);
        printCodes(root->right, code, index);
    }
}

// 计算每个字符的WPL（Weighted Path Length）
double calculateWPL(Node* root) {
    if (root == NULL) return 0;
    return root->freq + calculateWPL(root->left) + calculateWPL(root->right);
}

int main() {
    // 示例输入：字符及其频率
    const char* input = "abracadabra";
    int freqs[] = {5, 2, 2, 1, 3, 1, 4, 2, 1};
    int numChars = sizeof(freqs) / sizeof(freqs[0]);

    // 初始化堆
    Node* heap[2] = {NULL, NULL};

    // 将字符及其频率插入堆
    for (int i = 0; i < numChars; i++) {
        Node* newNode = newNode(i);
        newNode->freq = freqs[i];
        insert(heap, newNode);
    }

    // 构建哈夫曼树
    Node* huffmanRoot = buildHuffmanTree(heap);

    // 获取哈夫曼编码
    char codes[256];
    memset(codes, 0, sizeof(codes));
    printCodes(huffmanRoot, codes, 0);

    // 计算WPL
    double wpl = calculateWPL(huffmanRoot);
    printf("Weighted Path Length (WPL): %.2f\n", wpl);

    return 0;
}

这个程序首先创建了一个哈夫曼堆，然后按照频率先将字符加入堆。接着通过递归构建哈夫曼树并打印编码。最后计算WPL作为整个编码系统的压缩效率。