用C++完成一下操作：给定一组结点及对应的权值，创建一棵哈夫曼树，输出每个结点的哈夫曼编码，和整棵树的WPL值。 测试数据：(数据以数组赋值的形式给出，不要手动输入) 1组：结点为：A，B，C，D，E 分别对应的权值为：6，4，8，5，7 2组：结点为：A，B，C，D，E，F，G，H 分别对应的权值为：0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10 要求，代码给出详细注释：上传代码贴图，运行结果贴图，上传源代码文件。

注：本题解中的代码使用了C++的部分特性，但实现思路是C的。

哈夫曼树是一种树形结构，它的每个非叶子节点都有两个子节点，每个叶子节点都代表一个字符。哈夫曼树的构建过程是基于字符出现频率的，出现频率高的字符在树中离根节点近，出现频率低的字符在树中离根节点远。哈夫曼编码是一种前缀编码，它对于每个字符都有唯一的编码，而且任意一个编码都不是另一个编码的前缀。哈夫曼编码的长度是字符出现频率的加权平均值，也称为WPL（Weighted Path Length）。

以下是实现哈夫曼树及编码的C代码：

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

#define MAX_SIZE 100

// 定义哈夫曼树的节点
typedef struct {
    char data; // 节点表示的字符
    float weight; // 节点的权值
    int parent, lchild, rchild; // 父节点、左子节点、右子节点在数组中的下标
} HTNode;

// 定义哈夫曼编码表的节点
typedef struct {
    char data; // 被编码的字符
    char code[MAX_SIZE]; // 哈夫曼编码
} CodeNode;

// 选择两个权值最小的节点
void select(HTNode *ht, int n, int *s1, int *s2)
{
    float min1 = 1e9, min2 = 1e9; // 初始化为一个大数
    *s1 = *s2 = 0;
    for (int i = 1; i <= n; i++) {
        if (ht[i].weight < min1 && ht[i].parent == 0) {
            min2 = min1;
            min1 = ht[i].weight;
            *s2 = *s1;
            *s1 = i;
        } else if (ht[i].weight < min2 && ht[i].parent == 0) {
            min2 = ht[i].weight;
            *s2 = i;
        }
    }
}

// 创建哈夫曼树
void createHT(HTNode *ht, int n)
{
    int m = 2 * n - 1; // 哈夫曼树的总节点数
    for (int i = 1; i <= m; i++) {
        ht[i].parent = ht[i].lchild = ht[i].rchild = 0;
    }
    for (int i = n + 1; i <= m; i++) {
        int s1, s2;
        select(ht, i - 1, &s1, &s2);
        ht[s1].parent = i;
        ht[s2].parent = i;
        ht[i].lchild = s1;
        ht[i].rchild = s2;
        ht[i].weight = ht[s1].weight + ht[s2].weight;
    }
}

// 生成哈夫曼编码
void createCode(HTNode *ht, int n, CodeNode *hc)
{
    char *cd = (char *)malloc(n * sizeof(char));
    cd[n - 1] = '\0'; // 编码结束符
    for (int i = 1; i <= n; i++) {
        int start = n - 1;
        int c = i;
        int p = ht[c].parent;
        while (p != 0) {
            if (ht[p].lchild == c) {
                cd[--start] = '0';
            } else {
                cd[--start] = '1';
            }
            c = p;
            p = ht[c].parent;
        }
        strcpy(hc[i].code, &cd[start]);
        hc[i].data = ht[i].data;
    }
    free(cd);
}

// 计算哈夫曼树的WPL
float calcWPL(HTNode *ht, int n)
{
    float wpl = 0;
    for (int i = 1; i <= n; i++) {
        int c = i;
        int p = ht[c].parent;
        while (p != 0) {
            if (ht[p].lchild == c) {
                wpl += 0 * ht[c].weight;
            } else {
                wpl += 1 * ht[c].weight;
            }
            c = p;
            p = ht[c].parent;
        }
    }
    return wpl;
}

int main()
{
    // 测试数据1
    char chars1[] = {'A', 'B', 'C', 'D', 'E'};
    float weights1[] = {6, 4, 8, 5, 7};
    int n1 = sizeof(chars1) / sizeof(chars1[0]);
    HTNode ht1[MAX_SIZE];
    CodeNode hc1[MAX_SIZE];
    for (int i = 1; i <= n1; i++) {
        ht1[i].data = chars1[i - 1];
        ht1[i].weight = weights1[i - 1];
    }
    createHT(ht1, n1);
    createCode(ht1, n1, hc1);
    printf("Test case 1:\n");
    printf("Char\tWeight\tCode\n");
    for (int i = 1; i <= n1; i++) {
        printf("%c\t%.0f\t%s\n", hc1[i].data, ht1[i].weight, hc1[i].code);
    }
    printf("WPL = %.0f\n", calcWPL(ht1, n1));

    // 测试数据2
    char chars2[] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
    float weights2[] = {0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10};
    int n2 = sizeof(chars2) / sizeof(chars2[0]);
    HTNode ht2[MAX_SIZE];
    CodeNode hc2[MAX_SIZE];
    for (int i = 1; i <= n2; i++) {
        ht2[i].data = chars2[i - 1];
        ht2[i].weight = weights2[i - 1];
    }
    createHT(ht2, n2);
    createCode(ht2, n2, hc2);
    printf("Test case 2:\n");
    printf("Char\tWeight\tCode\n");
    for (int i = 1; i <= n2; i++) {
        printf("%c\t%.2f\t%s\n", hc2[i].data, ht2[i].weight, hc2[i].code);
    }
    printf("WPL = %.2f\n", calcWPL(ht2, n2));

    return 0;
}

运行结果：


注意事项：

1. 在选择两个权值最小的节点时，要排除已经有父节点的节点。
2. 在生成哈夫曼编码时，要从叶子节点往根节点遍历。
3. 在计算WPL时，要按节点的深度加权，而不是按节点的编码长度加权。