数据结构哈夫曼树实验C语言

下面是一个简单的哈夫曼树实验的C语言代码示例：

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

#define MAX_LEAF_NODE 100

typedef struct huffman_node {
    int weight;
    struct huffman_node *left_child;
    struct huffman_node *right_child;
} HuffmanNode;

// 初始化叶子节点
void init_leaf_nodes(HuffmanNode **leaf_nodes, int *weights, int n) {
    for (int i = 0; i < n; i++) {
        leaf_nodes[i] = (HuffmanNode *) malloc(sizeof(HuffmanNode));
        leaf_nodes[i]->weight = weights[i];
        leaf_nodes[i]->left_child = NULL;
        leaf_nodes[i]->right_child = NULL;
    }
}

// 合并两个节点为一个新节点
HuffmanNode *merge_nodes(HuffmanNode *node1, HuffmanNode *node2) {
    HuffmanNode *new_node = (HuffmanNode *) malloc(sizeof(HuffmanNode));
    new_node->weight = node1->weight + node2->weight;
    new_node->left_child = node1;
    new_node->right_child = node2;
    return new_node;
}

// 建立哈夫曼树
HuffmanNode *build_huffman_tree(HuffmanNode **leaf_nodes, int n) {
    while (n > 1) {
        // 找到权值最小的两个节点
        int min_index1 = 0, min_index2 = 1;
        if (leaf_nodes[min_index1]->weight > leaf_nodes[min_index2]->weight) {
            min_index1 = 1;
            min_index2 = 0;
        }
        for (int i = 2; i < n; i++) {
            if (leaf_nodes[i]->weight < leaf_nodes[min_index1]->weight) {
                min_index2 = min_index1;
                min_index1 = i;
            } else if (leaf_nodes[i]->weight < leaf_nodes[min_index2]->weight) {
                min_index2 = i;
            }
        }
        // 合并两个节点
        HuffmanNode *new_node = merge_nodes(leaf_nodes[min_index1], leaf_nodes[min_index2]);
        leaf_nodes[min_index1] = new_node;
        leaf_nodes[min_index2] = leaf_nodes[n - 1];
        n--;
    }
    return leaf_nodes[0];
}

// 打印哈夫曼编码
void print_huffman_code(HuffmanNode *node, int *code, int depth) {
    if (node->left_child == NULL && node->right_child == NULL) {
        printf("node weight: %d, code: ", node->weight);
        for (int i = 0; i < depth; i++) {
            printf("%d", code[i]);
        }
        printf("\n");
        return;
    }
    code[depth] = 0;
    print_huffman_code(node->left_child, code, depth + 1);
    code[depth] = 1;
    print_huffman_code(node->right_child, code, depth + 1);
}

int main() {
    int n;
    printf("Please input the number of leaf nodes: ");
    scanf("%d", &n);
    if (n <= 0 || n > MAX_LEAF_NODE) {
        printf("Invalid input!\n");
        return 0;
    }
    int *weights = (int *) malloc(n * sizeof(int));
    HuffmanNode **leaf_nodes = (HuffmanNode **) malloc(n * sizeof(HuffmanNode *));
    printf("Please input the weights of leaf nodes: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }
    init_leaf_nodes(leaf_nodes, weights, n);
    HuffmanNode *root_node = build_huffman_tree(leaf_nodes, n);
    int *code = (int *) malloc(n * sizeof(int));
    print_huffman_code(root_node, code, 0);
    return 0;
}

在这个代码示例中，我们定义了一个HuffmanNode结构体表示哈夫曼树中的节点。另外，我们首先初始化叶子节点，然后依次合并两个权值最小的节点构建哈夫曼树，最后输出每个叶子节点的哈夫曼编码。