霍夫曼树与编码

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;

// 霍夫曼树节点结构体
struct Node {
    int w;  // 权值
    int l, r;  // 左右子节点编号
} nodes[MAXN];

// 字符频率数组
int freq[256];
// 字符的霍夫曼编码
char code[256][MAXN];
// 临时编码
char tmp[MAXN];

// 查找权值最小的两个节点
void findMin(int& x, int& y, int n) {
    int min1 = 0x3f3f3f3f, min2 = 0x3f3f3f3f;
    for (int i = 0; i < n; i++) {
        if (nodes[i].w < min1) {
            min2 = min1;
            y = x;
            min1 = nodes[i].w;
            x = i;
        } else if (nodes[i].w < min2) {
            min2 = nodes[i].w;
            y = i;
        }
    }
}

// 构建霍夫曼树
int buildHuffmanTree(int n) {
    int idx = n;
    while (n > 1) {
        int x, y;
        findMin(x, y, n);
        nodes[idx].w = nodes[x].w + nodes[y].w;
        nodes[idx].l = x;
        nodes[idx].r = y;
        nodes[x].w = 0x3f3f3f3f;
        nodes[y].w = 0x3f3f3f3f;
        n--;
        idx++;
    }
    return idx - 1;
}

// 生成霍夫曼编码
void generateCodes(int u, int len) {
    if (nodes[u].l == -1 && nodes[u].r == -1) {
        for (int i = 0; i < len; i++) {
            code[u][i] = tmp[i];
        }
        code[u][len] = '\0';
        return;
    }
    tmp[len] = '0';
    generateCodes(nodes[u].l, len + 1);
    tmp[len] = '1';
    generateCodes(nodes[u].r, len + 1);
}

int main() {
    char s[MAXN];
    cin >> s;  // 读入字符串
    int len = strlen(s);
    // 统计字符频率
    for (int i = 0; i < len; i++) {
        freq[s[i]]++;
    }
    int n = 0;
    // 初始化节点
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            nodes[n].w = freq[i];
            nodes[n].l = nodes[n].r = -1;
            n++;
        }
    }
    // 构建霍夫曼树
    int root = buildHuffmanTree(n);
    // 生成霍夫曼编码
    generateCodes(root, 0);
    // 输出每个字符的霍夫曼编码
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            cout << (char)i << ": " << code[i] << endl;
        }
    }
    return 0;
}