用C语言代码编写程序实现“哈夫曼树构成和编码”

哈夫曼树是一种带权路径长度最短的二叉树，常用于数据压缩算法如Huffman编码。下面是使用C语言的一个简单示例，展示如何构建哈夫曼树并生成编码：

首先，我们需要结构体来表示字符及其频率，并创建优先队列：

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

typedef struct Node {
    char ch;
    int freq;
    struct Node* left;
    struct Node* right;
} Node;

typedef struct Queue {
    Node** data;
    int front;
    int rear;
    int size;
} Queue;

接下来，我们定义构建哈夫曼树的函数：

Node* newNode(char ch, int freq) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->ch = ch;
    node->freq = freq;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void enqueue(Queue* q, Node* node) {
    if (q->size == q->rear) {
        q->data = realloc(q->data, sizeof(Node*) * (q->size + 1));
        q->rear++;
    }
    q->data[q->rear] = node;
    q->size++;
}

Node* dequeue(Queue* q) {
    if (q->size == 0)
        return NULL;
    Node* temp = q->data[q->front];
    q->data[q->front] = q->data[q->size - 1];
    q->size--;
    q->front++;
    if (q->front >= q->size)
        q->front = 0;
    return temp;
}

然后，创建一个合并两个最小节点的函数，用于构建哈夫曼树：

Node* mergeNodes(Node* node1, Node* node2) {
    if (!node1 || !node2)
        return node1 ? node1 : node2;

    if (node1->freq < node2->freq) {
        node1->right = mergeNodes(node1->right, node2);
        return node1;
    } else {
        node2->left = mergeNodes(node1, node2->left);
        return node2;
    }
}

最后，生成编码并打印出来：

void huffmanCoding(Node* root, char* code, int ch) {
    if (!root->left && !root->right)
        code[root->ch] = '0';
    else {
        huffmanCoding(root->left, code, ch + 1);
        huffmanCoding(root->right, code, ch + 1);

        // 根据左、右子树将当前节点的编码设置为较浅的那个加上前缀
        code[root->ch] = code[root->left->ch] + code[root->right->ch];
    }
}

// 主函数
int main() {
    ... // 初始化字符及其频率数组，创建优先队列，插入元素等
    Node* huffTree = mergeNodes(dequeue(&q), dequeue(&q)); // 构建哈夫曼树

    // 生成编码
    char* codebook = malloc(strlen(codebook) + 1); // 初始为空字符串
    huffmanCoding(huffTree, codebook, 0);
    for (char c : codebook) {
        printf("%c ", c);
    }

    return 0;
}