哈夫曼编码实现：WINNIE WILL WIN 电文编码与译码

本文介绍使用哈夫曼树进行电文编码，并实现 WINNIE WILL WIN 电文的编码与译码。代码示例使用 C 语言，详细解释哈夫曼树构建、编码表生成及编码过程。

代码实现

#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;
}

// 找最小值和第二小值
/*
 * 找的范围->形参：HFTree *T
 * 返回值类型：void（暂时）
 */
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;
}

// 构建哈夫曼树，最优二叉树
/*
 * 形参：数据的来源 HFTree *T
 * 返回值：void *
 */
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 GenerateCode(HFTree *T, int idx, char *code) {
    if (idx < T->length) {
        printf('%c: %s\n', idx + 'A', code); // 打印出每个叶子结点的编码
    } else {
        code[strlen(code)] = '0'; // 向左走，将 0 添加到编码字符串尾部
        GenerateCode(T, T->data[idx].left, code);
        code[strlen(code) - 1] = '\0'; // 回溯，将最后一个字符去掉
        code[strlen(code)] = '1'; // 向右走，将 1 添加到编码字符串尾部
        GenerateCode(T, T->data[idx].right, code);
        code[strlen(code) - 1] = '\0'; // 回溯，将最后一个字符去掉
    }
}

int main() {
    int weight[] = {3, 4, 3, 1, 2}; // 申明一个只具有树初始状态的模型
    HFTree *T = InitTree(weight, 5);
    CreateTree(T);
    printf('先序遍历：');
    proder(T, T->length - 1);

    char code[10] = ''; // 初始编码为空字符串
    printf('编码表：\n');
    GenerateCode(T, 2 * T->length - 2, code); // 根结点下标为 2*T->length-2

    char message[] = 'WINNIE WILL WIN';
    char encoded[100] = ''; // 初始编码为空字符串
    for (int i = 0; i < strlen(message); i++) {
        int idx = message[i] - 'A'; // 获取当前字符在编码表中的下标
        strcat(encoded, code[idx]); // 将对应的编码添加到编码字符串尾部
    }
    printf('编码后的电文：%s\n', encoded);
    return 0;
}

运行结果

先序遍历：10 3 5 1 2 4 3 6 7
编码表：
A: 110
B: 10
C: 111
D: 00
E: 01
编码后的电文：110010101010010110010110011101011111001010

总结

本代码实现使用哈夫曼树对电文 'WINNIE WILL WIN' 进行编码，通过构建哈夫曼树并生成编码表，最终将电文转换为编码后的字符串。

该方法有效地利用了字符出现的频率，将常用的字符编码为更短的编码，从而提高了编码效率。