香农编码并计算信源熵c语言实现

以下是香农编码并计算信源熵的C语言实现示例：

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

#define MAX_SYMBOLS 256 // 最大符号数

// 定义符号节点结构体（二叉树结点）
typedef struct symbol_node {
    int freq; // 频率
    char symbol; // 符号
    struct symbol_node* left_child; // 左子树
    struct symbol_node* right_child; // 右子树
} SymbolNode;

// 定义符号表结构体
typedef struct {
    SymbolNode* symbols[MAX_SYMBOLS]; // 符号节点指针数组
    int size; // 符号数
} SymbolTable;

// 创建符号节点
SymbolNode* create_symbol_node(int freq, char symbol, SymbolNode* left_child, SymbolNode* right_child) {
    SymbolNode* node = malloc(sizeof(SymbolNode));
    node->freq = freq;
    node->symbol = symbol;
    node->left_child = left_child;
    node->right_child = right_child;
    return node;
}

// 创建符号表
SymbolTable* create_symbol_Table() {
    SymbolTable* table = malloc(sizeof(SymbolTable));
    memset(table, 0, sizeof(SymbolTable));
    return table;
}

// 添加符号及其出现频率到符号表
void add_symbol_to_table(SymbolTable* table, char symbol) {
    for (int i = 0; i < table->size; i++) {
        if (table->symbols[i]->symbol == symbol) {
            table->symbols[i]->freq++;
            return;
        }
    }
    table->symbols[table->size++] = create_symbol_node(1, symbol, NULL, NULL);
}

// 比较函数
int compare(const void* a, const void* b) {
    SymbolNode* sn1 = *(SymbolNode**)a;
    SymbolNode* sn2 = *(SymbolNode**)b;
    return sn1->freq - sn2->freq;
}

// 构建哈夫曼树
SymbolNode* build_huffman_tree(SymbolTable* table) {
    qsort(table->symbols, table->size, sizeof(SymbolNode*), compare);
    int size = table->size;
    // 由小到大取出两个权重最小的节点，合并到一个新的节点中，形成二叉树
    for (int i = 0; i < size - 1; i++) {
        SymbolNode* new_node = create_symbol_node(table->symbols[0]->freq + table->symbols[1]->freq, 0, table->symbols[0], table->symbols[1]);
        // 将新节点添加到符号数组中
        table->symbols[0] = new_node;
        // 将后续节点依次前移，覆盖掉原来的节点
        for (int j = 1; j < size - i - 1; j++) {
            table->symbols[j] = table->symbols[j + 1];
        }
        size--; // 数组大小减一
        qsort(table->symbols, size, sizeof(SymbolNode*), compare);
    }
    return table->symbols[0];
}

// 通过哈夫曼树生成编码表
void generate_encoding_table(SymbolNode* root, int* code, int depth) {
    if (!root) return;
    // 叶子节点
    if (!root->left_child && !root->right_child) {
        printf("%c: ", root->symbol);
        for (int i = 0; i < depth; i++) {
            printf("%d", code[i]);
        }
        printf("\n");
    }
    // 左子树深度加一，并将 0 入栈（左子树为 0）
    code[depth] = 0;
    generate_encoding_table(root->left_child, code, depth + 1);
    // 右子树深度加一，并将 1 入栈（右子树为 1）
    code[depth] = 1;
    generate_encoding_table(root->right_child, code, depth + 1);
}

// 计算信源熵
double calculate_source_entropy(SymbolTable* table, int total) {
    double entropy = 0.0;
    for (int i = 0; i < table->size; i++) {
        SymbolNode* node = table->symbols[i];
        double probability = (double) node->freq / (double) total;
        entropy += probability * log2(1 / probability);
    }
    return entropy;
}

int main() {
    char input_str[100];
    printf("请输入信源字符串：\n");
    gets(input_str);
    SymbolTable* table = create_symbol_Table();
    int total_symbols = 0;
    // 统计每个字符的出现频率
    for (int i = 0; i < strlen(input_str); i++) {
        add_symbol_to_table(table, input_str[i]);
        total_symbols++;
    }
    SymbolNode* root = build_huffman_tree(table);
    int encoding_table[MAX_SYMBOLS] = {0};
    printf("各个字符的哈夫曼编码：\n");
    generate_encoding_table(root, encoding_table, 0);
    double entropy = calculate_source_entropy(table, total_symbols);
    printf("信源熵为：%.4lf\n", entropy);
    return 0;
}

这个程序可以接收用户输入的任意字符串，计算该字符串的信源熵，并生成各个字符的哈夫曼编码。程序的实现过程包括如下步骤：

1. 创建一个符号表，用于存储输入字符串中的每个字符及其出现频率。

2. 统计输入字符串中的每个字符的出现频率，更新符号表。

3. 根据符号表，构建哈夫曼树。

4. 通过哈夫曼树生成各个字符的编码表。

5. 计算输入字符串的信源熵。

程序的核心算法是哈夫曼编码算法，该算法主要包括构建哈夫曼树、生成各个字符的编码表两个步骤。这个示例程序通过递归遍历哈夫曼树的方式，生成了各个字符的编码表。计算信源熵的公式为：$H(S)=-\sum_{i}^{n}p_i\log_2{p_i}$，其中 $p_i$ 表示第 $i$ 个字符的出现概率，$n$ 表示字符数。