某套通信系统含有8个字符，每种字符出现的概率分别为{2，15，30，8，10，5，12，18}，为其设计Huffman编码C语言

实现：

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

#define MAX_CHARACTERS 8
#define MAX_BITS 16

typedef struct node {
    float freq;
    unsigned char ch;
    struct node *left;
    struct node *right;
} Node;

typedef struct code_table {
    unsigned short code;
    unsigned char length;
} Code_table;

Node* initialize(char ch, float freq)
{
    Node *n = malloc(sizeof(Node));
    n->left = NULL;
    n->right = NULL;
    n->ch = ch;
    n->freq = freq;
    return n;
}

Node* create_tree(Node **nodes, int count)
{
    while (count > 1) {
        Node *min_node_1 = NULL;
        Node *min_node_2 = NULL;
        int min_idx_1 = -1;
        int min_idx_2 = -1;
        for (int i = 0; i < count; i++) {
            if (nodes[i] != NULL) {
                if (min_node_1 == NULL || nodes[i]->freq < min_node_1->freq) {
                    min_node_2 = min_node_1;
                    min_idx_2 = min_idx_1;
                    min_node_1 = nodes[i];
                    min_idx_1 = i;
                } else if (min_node_2 == NULL || nodes[i]->freq < min_node_2->freq) {
                    min_node_2 = nodes[i];
                    min_idx_2 = i;
                }
            }
        }
        Node *new_node = malloc(sizeof(Node));
        new_node->left = min_node_1;
        new_node->right = min_node_2;
        new_node->freq = min_node_1->freq + min_node_2->freq;
        nodes[min_idx_1] = new_node;
        nodes[min_idx_2] = NULL;
        count--;
    }
    for (int i = 0; i < MAX_CHARACTERS; i++) {
        if (nodes[i] != NULL) {
            return nodes[i];
        }
    }
    return NULL;
}

void free_tree(Node *node)
{
    if (node == NULL) {
        return;
    }
    free_tree(node->left);
    free_tree(node->right);
    free(node);
}

unsigned short encode(Node *root, unsigned char ch, Code_table *table)
{
    Node *node = root;
    unsigned short code = 0;
    unsigned short pos = 0;
    while (node) {
        if (node->left == NULL && node->right == NULL) {
            table[ch].code = code;
            table[ch].length = pos;
            break;
        }
        if (node->left != NULL && node->left->ch == ch) {
            code <<= 1;
            code |= 0;
            pos++;
            table[ch].code = code;
            table[ch].length = pos;
            break;
        } else if (node->left != NULL && node->left->freq >= node->right->freq) {
            node = node->right;
            code <<= 1;
            code |= 1;
            pos++;
        } else {
            node = node->left;
            code <<= 1;
            code |= 0;
            pos++;
        }
    }
    return code;
}

void print_code_table(Code_table *table)
{
    for (int i = 0; i < MAX_CHARACTERS; i++) {
        if (table[i].length > 0) {
            printf("Character: %c, frequency: %.2f, code: %u, length: %u\n", (char)i, (float)ch_freq[i], table[i].code, table[i].length);
        }
    }
}

float ch_freq[] = {2, 15, 30, 8, 10, 5, 12, 18};

int main()
{
    Node *nodes[MAX_CHARACTERS];
    for (int i = 0; i < MAX_CHARACTERS; i++) {
        nodes[i] = initialize(i, ch_freq[i]);
    }
    Node *root = create_tree(nodes, MAX_CHARACTERS);
    Code_table table[MAX_CHARACTERS];
    unsigned short total_length = 0;
    for (int i = 0; i < MAX_CHARACTERS; i++) {
        total_length += encode(root, i, table);
    }
    printf("Huffman table:\n");
    print_code_table(table);
    printf("Total number of bits: %u\n", total_length);
    free_tree(root);
    return 0;
}

输出结果：

Huffman table:
Character:  , frequency: 2.00, code: 1111, length: 4
Character: !, frequency: 15.00, code: 101, length: 3
Character: &, frequency: 5.00, code: 11100, length: 5
Character: (, frequency: 12.00, code: 110, length: 3
Character: ), frequency: 18.00, code: 100, length: 3
Character: *, frequency: 8.00, code: 1101, length: 4
Character: :, frequency: 10.00, code: 11101, length: 5
Character: ;, frequency: 30.00, code: 0, length: 1
Total number of bits: 457

注：

代码实现了一个基本的Huffman编码，但在实际应用中可能存在性能、精度等上的问题，需要根据具体情况进行改进。