已知下列字符A、B、C、D、E、F、G的权值分别是3、12、7、4、2、8、11。绘制以该权值为叶子结点的Huffman树，并求出树的带权路径长度值WPL和压缩率，并写出以上每个字符的编码。c语言代码

绘制的Huffman树如下：

       45
     /    \
    23    22
   /  \   /  \
  11  12  7   15
 /  \    /   /  \
E    F  C   D   G

其中，45是所有权值之和，WPL为3\*4 + 12\*2 + 7\*3 + 4\*4 + 2\*5 + 8\*3 + 11\*3 = 123。压缩率为(7\*8)/123 ≈ 0.45。

以下是每个字符的编码：

A: 未出现在原始数据中
B: 10
C: 110
D: 1110
E: 000
F: 001
G: 1111

C语言代码实现：

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

#define MAX_NODE 100

typedef struct node {
    int weight;
    int parent;
    int lchild;
    int rchild;
} Node;

void huffman(Node *nodes, int n);
void get_codes(Node *nodes, int n, char (*codes)[20]);

int main() {
    Node nodes[MAX_NODE];
    char codes[MAX_NODE][20];
    int n = 7;

    // 初始化叶子结点
    nodes[0].weight = 3;  // A
    nodes[1].weight = 12; // B
    nodes[2].weight = 7;  // C
    nodes[3].weight = 4;  // D
    nodes[4].weight = 2;  // E
    nodes[5].weight = 8;  // F
    nodes[6].weight = 11; // G
    for (int i = 0; i < n; i++) {
        nodes[i].parent = -1;
        nodes[i].lchild = -1;
        nodes[i].rchild = -1;
    }

    huffman(nodes, n);
    get_codes(nodes, n, codes);

    for (int i = 0; i < n; i++) {
        printf("%c: %s\n", 'A'+i, codes[i]);
    }

    return 0;
}

void huffman(Node *nodes, int n) {
    // 构造Huffman树
    int min1, min2;
    for (int i = n; i < 2*n-1; i++) {
        min1 = min2 = -1;
        for (int j = 0; j < i; j++) {
            if (nodes[j].parent == -1) {
                if (min1 == -1 || nodes[j].weight < nodes[min1].weight) {
                    min2 = min1;
                    min1 = j;
                } else if (min2 == -1 || nodes[j].weight < nodes[min2].weight) {
                    min2 = j;
                }
            }
        }
        nodes[min1].parent = i;
        nodes[min2].parent = i;
        nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
        nodes[i].lchild = min1;
        nodes[i].rchild = min2;
    }
}

void get_codes(Node *nodes, int n, char (*codes)[20]) {
    // 获取每个字符的Huffman编码
    for (int i = 0; i < n; i++) {
        int j = i;
        int k = 0;
        while (nodes[j].parent != -1) {
            if (nodes[nodes[j].parent].lchild == j) {
                codes[i][k++] = '0';
            } else {
                codes[i][k++] = '1';
            }
            j = nodes[j].parent;
        }
        codes[i][k] = '\0';
        strrev(codes[i]); // 编码是从叶子到根，需要反转
    }
}