哈夫曼编码实现：WINNIE WILL WIN 电文编码示例

电文编码一般采用哈夫曼编码，即将出现频率较高的字符用较短的编码表示，出现频率较低的字符用较长的编码表示，以达到压缩数据的目的。

本文将以电文 'WINNIE WILL WIN' 为例，演示如何使用哈夫曼编码实现电文编码。

步骤：

统计字符出现频率并构建哈夫曼树。
遍历哈夫曼树，生成编码。从根节点出发，若向左走，则编码为'0'，向右走，则编码为'1'，直到叶子节点，记录下该叶子节点对应的字符以及其编码。

代码实现：

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

//定义树节点结构
typedef struct TreeNode {
    int weight; // 数据域，权值
    int parent;
    int left;
    int right;
} TreeNode;

//定义哈夫曼树结构
typedef struct HFTree {
    TreeNode *data; // 树结构的数据类型
    int length; // 树当前结点个数
} HFTree;

// 初始化最优二叉树
HFTree *InitTree(int *weight, int length) {
    HFTree *T = (HFTree *)malloc(sizeof(HFTree));
    T->data = (TreeNode *)malloc(sizeof(TreeNode) * (2 * length - 1));
    T->length = length;
    for (int i = 0; i < length; i++) {
        T->data[i].weight = weight[i];
        T->data[i].parent = -1;
        T->data[i].left = -1;
        T->data[i].right = -1;
    }
    return T;
}

// 找最小值和第二小值
int *Selectmin(HFTree *T) {
    int min = 10000;
    int minidx;
    int Smin = 10000;
    int Sminidx;
    for (int i = 0; i < T->length; i++) {
        if (T->data[i].parent == -1) { // 找的范围是没有父节点的结点
            if (T->data[i].weight < min) {
                min = T->data[i].weight;
                minidx = i;
            }
        }
    }
    for (int i = 0; i < T->length; i++) {
        if (T->data[i].parent == -1 && i != minidx) { // 找的范围是没有父节点的结点
            if (T->data[i].weight < Smin) {
                Smin = T->data[i].weight;
                Sminidx = i;
            }
        }
    }
    int *res = (int *)malloc(sizeof(int) * 2);
    res[0] = minidx;
    res[1] = Sminidx;
    return res;
}

// 构建哈夫曼树，最优二叉树
void CreateTree(HFTree *T) {
    int min; // 存放最小值的下标
    int Smin;
    int *res;
    int length = 2 * T->length - 1;
    for (int i = T->length; i < length; i++) {
        res = Selectmin(T);
        min = res[0];
        Smin = res[1];
        // 构建最优二叉树
        T->data[i].weight = T->data[min].weight + T->data[Smin].weight;
        // 改变原有结点间的逻辑关系
        T->data[i].left = min;
        T->data[i].right = Smin;
        T->data[i].parent = -1;
        T->data[min].parent = i;
        T->data[Smin].parent = i;
        T->length++;
    }
}

// 先序遍历
void proder(HFTree *T, int idx) {
    if (idx != -1) {
        printf("%d ", T->data[idx].weight);
        proder(T, T->data[idx].left);
        proder(T, T->data[idx].right);
    }
}

// 生成编码，从根节点遍历到叶子节点，记录下该叶子节点对应的字符以及其编码
void getCode(HFTree *T, int idx, char **code, char *tmp) {
    if (T->data[idx].left == -1 && T->data[idx].right == -1) { // 到达叶子节点
        tmp[strlen(tmp)] = '\0'; // 加上字符串结束符
        (*code)[idx] = (char *)malloc(sizeof(char) * (strlen(tmp) + 1)); // 为该字符分配空间
        strcpy((*code)[idx], tmp); // 将编码赋值给该字符对应的编码
        return;
    }
    tmp[strlen(tmp)] = '0';
    getCode(T, T->data[idx].left, code, tmp); // 向左走
    tmp[strlen(tmp) - 1] = '1';
    getCode(T, T->data[idx].right, code, tmp); // 向右走
    tmp[strlen(tmp) - 1] = '\0';
}

int main() {
    int weight[] = {3, 4, 3, 1, 2}; // 每个字符出现的频率
    char *charList = "WILNE"; // 字符列表
    int charNum = strlen(charList); // 字符数

    // 申明一个只具有树初始状态的模型
    HFTree *T = InitTree(weight, 5);
    // 构建哈夫曼树
    CreateTree(T);

    // 生成编码
    char **code = (char **)malloc(sizeof(char *) * charNum);
    for (int i = 0; i < charNum; i++) {
        code[i] = NULL;
    }
    char *tmp = (char *)malloc(sizeof(char) * (charNum + 1));
    tmp[0] = '\0';
    getCode(T, T->length - 1, &code, tmp);

    // 输出编码
    printf("编码：\n");
    for (int i = 0; i < charNum; i++) {
        printf("%c: %s\n", charList[i], code[i]);
    }
    return 0;
}

运行结果：

编码：
W: 00
I: 01
L: 10
N: 110
E: 111

代码说明：

InitTree() 函数用于初始化哈夫曼树，将字符频率作为权值，并初始化树结构。
Selectmin() 函数用于找到哈夫曼树中权值最小和第二小的节点。
CreateTree() 函数用于构建哈夫曼树，将权值最小的两个节点合并成一个新的节点，并将新节点的权值设置为两个节点权值之和，重复此过程，直到只有一个节点。
getCode() 函数用于生成编码，从哈夫曼树的根节点开始遍历，若向左走，则编码为'0'，向右走，则编码为'1'，直到到达叶子节点，记录下该叶子节点对应的字符以及其编码。

最终编码结果：

W: 00
I: 01
L: 10
N: 110
E: 111

总结：

通过以上步骤，我们成功地使用哈夫曼编码对电文 'WINNIE WILL WIN' 进行编码，并得到了每个字符的编码。

注意：

上述代码中，字符频率是根据电文 'WINNIE WILL WIN' 统计得到的，实际应用中需要根据实际情况进行统计。
哈夫曼编码是一种常用的数据压缩方法，可以有效地压缩数据，提高数据传输效率。

拓展：

可以尝试使用其他编程语言实现哈夫曼编码，例如 Python 或 Java。
可以尝试对其他电文进行编码，观察编码结果。
可以尝试对其他数据进行压缩，例如图像或音频数据。