对已知概率分布的字符进行霍夫曼编码的c语言程序

以下是对已知概率分布的字符进行霍夫曼编码的C语言程序的示例代码：

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

#define MAX_TREE_HT 100

// 霍夫曼树节点
struct HuffmanNode {
    char character;
    int frequency;
    struct HuffmanNode *left, *right;
};

// 霍夫曼编码表
struct HuffmanTable {
    char character;
    char code[MAX_TREE_HT];
};

// 创建霍夫曼树节点
struct HuffmanNode *createHuffmanNode(char character, int frequency) {
    struct HuffmanNode *node = malloc(sizeof(struct HuffmanNode));
    node->character = character;
    node->frequency = frequency;
    node->left = node->right = NULL;
    return node;
}

// 交换两个霍夫曼树节点
void swapHuffmanNode(struct HuffmanNode **a, struct HuffmanNode **b) {
    struct HuffmanNode *temp = *a;
    *a = *b;
    *b = temp;
}

// 建立最小堆
void minHeap(struct HuffmanNode **huffmanTree, int size, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    if (left < size && huffmanTree[left]->frequency < huffmanTree[smallest]->frequency) {
        smallest = left;
    }
    if (right < size && huffmanTree[right]->frequency < huffmanTree[smallest]->frequency) {
        smallest = right;
    }
    if (smallest != index) {
        swapHuffmanNode(&huffmanTree[index], &huffmanTree[smallest]);
        minHeap(huffmanTree, size, smallest);
    }
}

// 构建霍夫曼树
struct HuffmanNode *buildHuffmanTree(char characters[], int frequencies[], int size) {
    struct HuffmanNode **huffmanTree = malloc(size * sizeof(struct HuffmanNode *));
    for (int i = 0; i < size; i++) {
        huffmanTree[i] = createHuffmanNode(characters[i], frequencies[i]);
    }
    int n = size;
    for (int i = (n / 2) - 1; i >= 0; i--) {
        minHeap(huffmanTree, n, i);
    }
    while (n > 1) {
        struct HuffmanNode *left = huffmanTree[0];
        swapHuffmanNode(&huffmanTree[0], &huffmanTree[n - 1]);
        n--;
        minHeap(huffmanTree, n, 0);
        struct HuffmanNode *right = huffmanTree[0];
        swapHuffmanNode(&huffmanTree[0], &huffmanTree[n - 1]);
        n--;
        minHeap(huffmanTree, n, 0);
        struct HuffmanNode *parent = createHuffmanNode('$', left->frequency + right->frequency);
        parent->left = left;
        parent->right = right;
        huffmanTree[n] = parent;
        n++;
        minHeap(huffmanTree, n, n - 1);
    }
    return huffmanTree[0];
}

// 生成霍夫曼编码表
void generateHuffmanTable(struct HuffmanNode *root, char prefix[], int index, struct HuffmanTable huffmanTable[]) {
    if (root == NULL) {
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        huffmanTable[root->character].character = root->character;
        strcpy(huffmanTable[root->character].code, prefix);
    }
    prefix[index] = '0';
    prefix[index + 1] = '\0';
    generateHuffmanTable(root->left, prefix, index + 1, huffmanTable);
    prefix[index] = '1';
    prefix[index + 1] = '\0';
    generateHuffmanTable(root->right, prefix, index + 1, huffmanTable);
}

// 打印霍夫曼编码表
void printHuffmanTable(struct HuffmanTable huffmanTable[], int size) {
    printf("Huffman Table:\n");
    for (int i = 0; i < size; i++) {
        if (huffmanTable[i].character != '\0') {
            printf("%c: %s\n", huffmanTable[i].character, huffmanTable[i].code);
        }
    }
}

int main() {
    char characters[] = {'a', 'b', 'c', 'd', 'e', 'f'};
    int frequencies[] = {5, 9, 12, 13, 16, 45};
    int size = sizeof(characters) / sizeof(char);
    struct HuffmanNode *root = buildHuffmanTree(characters, frequencies, size);
    struct HuffmanTable huffmanTable[MAX_TREE_HT];
    char prefix[MAX_TREE_HT];
    prefix[0] = '\0';
    generateHuffmanTable(root, prefix, 0, huffmanTable);
    printHuffmanTable(huffmanTable, size);
    return 0;
}

在这个示例代码中，我们定义了一个 `HuffmanNode` 结构体，表示霍夫曼树的节点，包含字符和出现频率。我们还定义了一个 `HuffmanTable` 结构体，表示霍夫曼编码表，包含字符和编码。然后，我们实现了创建霍夫曼树节点的函数 `createHuffmanNode`，交换两个霍夫曼树节点的函数 `swapHuffmanNode`，建立最小堆的函数 `minHeap`，构建霍夫曼树的函数 `buildHuffmanTree`，生成霍夫曼编码表的函数 `generateHuffmanTable`，和打印霍夫曼编码表的函数 `printHuffmanTable`。

在 `main` 函数中，我们定义了字符集和出现频率，然后调用 `buildHuffmanTree` 函数构建霍夫曼树，调用 `generateHuffmanTable` 函数生成霍夫曼编码表，最后调用 `printHuffmanTable` 函数打印霍夫曼编码表。

请注意，这个示例代码中使用了递归来生成霍夫曼编码表。实际上，也可以使用栈来实现迭代方式的生成霍夫曼编码表。