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

好的，下面是一个简单的哈夫曼树实现的代码示例：

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

typedef struct node {
    int weight;     // 权值
    char ch;        // 字符
    char *code;     // 编码
    struct node *left;      // 左子树
    struct node *right;     // 右子树
} Node;

// 交换两个节点
void swap(Node **a, Node **b) {
    Node *tmp = *a;
    *a = *b;
    *b = tmp;
}

// 构建哈夫曼树
Node *build_huffman_tree(Node **nodes, int n) {
    while (n > 1) {
        // 找到最小的两个节点
        int min1 = 0, min2 = 1;
        if (nodes[min1]->weight > nodes[min2]->weight) {
            swap(&nodes[min1], &nodes[min2]);
        }
        for (int i = 2; i < n; ++i) {
            if (nodes[i]->weight < nodes[min1]->weight) {
                min2 = min1;
                min1 = i;
            } else if (nodes[i]->weight < nodes[min2]->weight) {
                min2 = i;
            }
        }

        // 合并两个节点
        Node *new_node = (Node*)malloc(sizeof(Node));
        new_node->weight = nodes[min1]->weight + nodes[min2]->weight;
        new_node->left = nodes[min1];
        new_node->right = nodes[min2];

        // 删除旧的节点
        nodes[min1] = new_node;
        nodes[min2] = nodes[n-1];
        n--;
    }
    return nodes[0];
}

// 生成哈夫曼编码
void generate_huffman_code(Node *root, char *prefix, int len) {
    if (root->left == NULL && root->right == NULL) {
        root->code = (char*)malloc(sizeof(char) * (len+1));
        strcpy(root->code, prefix);
    } else {
        prefix[len] = '0';
        prefix[len+1] = '\0';
        generate_huffman_code(root->left, prefix, len+1);

        prefix[len] = '1';
        prefix[len+1] = '\0';
        generate_huffman_code(root->right, prefix, len+1);
    }
}

// 打印哈夫曼编码
void print_huffman_code(Node *root) {
    if (root->left == NULL && root->right == NULL) {
        printf("%c: %s\n", root->ch, root->code);
    } else {
        print_huffman_code(root->left);
        print_huffman_code(root->right);
    }
}

int main() {
    char str[] = "hello world";
    int freq[256] = {0};
    int len = strlen(str);

    // 统计每个字符出现的频率
    for (int i = 0; i < len; ++i) {
        freq[str[i]]++;
    }

    // 创建节点
    Node *nodes[256];
    int n = 0;
    for (int i = 0; i < 256; ++i) {
        if (freq[i] > 0) {
            nodes[n] = (Node*)malloc(sizeof(Node));
            nodes[n]->weight = freq[i];
            nodes[n]->ch = i;
            nodes[n]->left = nodes[n]->right = NULL;
            nodes[n]->code = NULL;
            n++;
        }
    }

    // 构建哈夫曼树
    Node *root = build_huffman_tree(nodes, n);

    // 生成哈夫曼编码
    char prefix[256];
    prefix[0] = '\0';
    generate_huffman_code(root, prefix, 0);

    // 打印哈夫曼编码
    print_huffman_code(root);

    return 0;
}

这个示例程序通过输入一个字符串，然后统计每个字符出现的频率，最后生成哈夫曼编码并打印出来。这只是一个简单的示例，实际应用中可能还需要考虑更多的情况。