C语言哈夫曼树编码输出

下面是一个简单的C语言程序，实现哈夫曼树的编码输出功能：

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

#define MAX_NODE_NUM 100 // 哈夫曼树最大节点数

// 定义哈夫曼树节点结构体
typedef struct HuffmanNode {
    char ch; // 字符
    float weight; // 权值
    int parent; // 父节点
    int left; // 左子节点
    int right; // 右子节点
    char code[MAX_NODE_NUM]; // 编码
} HuffmanNode;

// 初始化哈夫曼树
void initHuffmanTree(HuffmanNode *huffTree, int n) {
    int i;
    for (i = 0; i < n; i++) {
        huffTree[i].parent = -1;
        huffTree[i].left = -1;
        huffTree[i].right = -1;
        memset(huffTree[i].code, 0, sizeof(huffTree[i].code));
    }
}

// 选择权值最小的两个节点
void selectMin(HuffmanNode *huffTree, int n, int *p1, int *p2) {
    int i;
    float min1 = 1e9, min2 = 1e9;
    for (i = 0; i < n; i++) {
        if (huffTree[i].weight < min1 && huffTree[i].parent == -1) {
            min2 = min1;
            min1 = huffTree[i].weight;
            *p2 = *p1;
            *p1 = i;
        } else if (huffTree[i].weight < min2 && huffTree[i].parent == -1) {
            min2 = huffTree[i].weight;
            *p2 = i;
        }
    }
}

// 构建哈夫曼树
void createHuffmanTree(HuffmanNode *huffTree, float *weights, int n) {
    int i, p1, p2;
    initHuffmanTree(huffTree, n);
    for (i = 0; i < n; i++) {
        huffTree[i].weight = weights[i];
        huffTree[i].ch = 'A' + i;
    }
    for (i = 0; i < n - 1; i++) {
        selectMin(huffTree, n + i, &p1, &p2);
        huffTree[p1].parent = n + i;
        huffTree[p2].parent = n + i;
        huffTree[n + i].weight = huffTree[p1].weight + huffTree[p2].weight;
        huffTree[n + i].left = p1;
        huffTree[n + i].right = p2;
    }
}

// 编码
void encode(HuffmanNode *huffTree, int n) {
    int i, j, parent, current;
    for (i = 0; i < n; i++) {
        parent = huffTree[i].parent;
        current = i;
        while (parent != -1) {
            if (huffTree[parent].left == current) {
                strcat(huffTree[i].code, "0");
            } else {
                strcat(huffTree[i].code, "1");
            }
            current = parent;
            parent = huffTree[current].parent;
        }
        strrev(huffTree[i].code); // 将编码反转
    }
}

// 输出哈夫曼树编码
void printHuffmanCode(HuffmanNode *huffTree, int n) {
    int i;
    for (i = 0; i < n; i++) {
        printf("%c: %s\n", huffTree[i].ch, huffTree[i].code);
    }
}

int main() {
    float weights[] = {0.15, 0.1, 0.2, 0.3, 0.25};
    int n = sizeof(weights) / sizeof(weights[0]);
    HuffmanNode huffTree[MAX_NODE_NUM];
    createHuffmanTree(huffTree, weights, n);
    encode(huffTree, n);
    printHuffmanCode(huffTree, n);
    return 0;
}

这个程序实现了一个简单的哈夫曼树编码输出功能，可以参考它来理解哈夫曼树编码的实现过程。