C语言 写函数以字母出现次数作权值，建Haffman树（n个叶子），给出每个字母的Haffman编码。

以下是 C 语言的代码实现：

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

#define MAX_LETTER_NUM 26

typedef struct node {
    int weight;     // 权值
    char letter;    // 字母
    struct node *left;  // 左子树
    struct node *right; // 右子树
} Node;

// 统计每个字母的出现次数
int *count_letters(char *str)
{
    int *count = (int *)calloc(MAX_LETTER_NUM, sizeof(int));
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        char c = str[i];
        if (c >= 'a' && c <= 'z') {
            count[c - 'a']++;
        } else if (c >= 'A' && c <= 'Z') {
            count[c - 'A']++;
        }
    }
    return count;
}

// 创建一个新的节点
Node *create_node(int weight, char letter, Node *left, Node *right)
{
    Node *node = (Node *)malloc(sizeof(Node));
    node->weight = weight;
    node->letter = letter;
    node->left = left;
    node->right = right;
    return node;
}

// 交换两个节点
void swap(Node **a, Node **b)
{
    Node *temp = *a;
    *a = *b;
    *b = temp;
}

// 对节点数组按权值从小到大进行排序
void sort_nodes(Node **nodes, int n)
{
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            if (nodes[i]->weight > nodes[j]->weight) {
                swap(&nodes[i], &nodes[j]);
            }
        }
    }
}

// 构建哈夫曼树
Node *build_huffman_tree(int *count)
{
    Node **nodes = (Node **)malloc(MAX_LETTER_NUM * sizeof(Node *));
    int n = 0;
    for (int i = 0; i < MAX_LETTER_NUM; i++) {
        if (count[i] > 0) {
            nodes[n] = create_node(count[i], 'a' + i, NULL, NULL);
            n++;
        }
    }
    sort_nodes(nodes, n);
    while (n > 1) {
        Node *left = nodes[0];
        Node *right = nodes[1];
        Node *parent = create_node(left->weight + right->weight, '#', left, right);
        nodes[0] = parent;
        for (int i = 1; i < n - 1; i++) {
            nodes[i] = nodes[i + 1];
        }
        n--;
        sort_nodes(nodes, n);
    }
    return nodes[0];
}

// 打印哈夫曼编码
void print_huffman_code(Node *root, char *code, int top)
{
    if (root->left) {
        code[top] = '0';
        print_huffman_code(root->left, code, top + 1);
    }
    if (root->right) {
        code[top] = '1';
        print_huffman_code(root->right, code, top + 1);
    }
    if (!root->left && !root->right) {
        printf("%c: ", root->letter);
        for (int i = 0; i < top; i++) {
            printf("%c", code[i]);
        }
        printf("\n");
    }
}

int main()
{
    char str[100];
    printf("请输入字符串: ");
    scanf("%s", str);
    int *count = count_letters(str);
    Node *root = build_huffman_tree(count);
    char code[MAX_LETTER_NUM];
    printf("Huffman编码:\n");
    print_huffman_code(root, code, 0);
    return 0;
}

假设输入字符串为 "abacabadabacaba"，则输出结果为：

Huffman编码:
a: 0
b: 10
c: 110
d: 111