输入n个叶子结点的权值构造哈夫曼树；根据哈夫曼树构造哈夫曼编码，并对密文完成解码工作。用C语言实现

以下是 C 语言实现哈夫曼树和哈夫曼编码的示例代码：

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

#define MAX_LEN 100

typedef struct _HuffmanTreeNode {
    int weight;
    char ch;
    struct _HuffmanTreeNode *left;
    struct _HuffmanTreeNode *right;
} HuffmanTreeNode;

typedef struct _HuffmanTree {
    HuffmanTreeNode *root;
} HuffmanTree;

typedef struct _HuffmanCode {
    char ch;
    char code[MAX_LEN];
} HuffmanCode;

void huffman_tree_create(int *weights, int n, HuffmanTree *tree);
void huffman_tree_traverse(HuffmanTreeNode *root, char *code, int depth, HuffmanCode *codes);
void huffman_code_encode(char *msg, HuffmanCode *codes, char *encoded_msg);
void huffman_code_decode(char *encoded_msg, HuffmanTreeNode *root, char *decoded_msg);

int main() {
    int n, i;
    int *weights;
    char *msg;
    char *encoded_msg, *decoded_msg;
    HuffmanTree tree;
    HuffmanCode codes[26];

    printf("Enter the number of leaf nodes: ");
    scanf("%d", &n);

    weights = (int *) malloc(sizeof(int) * n);
    msg = (char *) malloc(sizeof(char) * (n + 1));
    encoded_msg = (char *) malloc(sizeof(char) * MAX_LEN * (n + 1));
    decoded_msg = (char *) malloc(sizeof(char) * (n + 1));

    printf("Enter the weights of leaf nodes: ");
    for (i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }

    printf("Enter the message to be encoded: ");
    scanf("%s", msg);

    huffman_tree_create(weights, n, &tree);

    huffman_tree_traverse(tree.root, "", 0, codes);

    printf("Huffman codes:\n");
    for (i = 0; i < 26; i++) {
        if (codes[i].ch != '\0') {
            printf("%c: %s\n", codes[i].ch, codes[i].code);
        }
    }

    huffman_code_encode(msg, codes, encoded_msg);
    printf("Encoded message: %s\n", encoded_msg);

    huffman_code_decode(encoded_msg, tree.root, decoded_msg);
    printf("Decoded message: %s\n", decoded_msg);

    free(weights);
    free(msg);
    free(encoded_msg);
    free(decoded_msg);

    return 0;
}

void huffman_tree_create(int *weights, int n, HuffmanTree *tree) {
    int i, j, k;
    HuffmanTreeNode *nodes, *p1, *p2, *parent;

    nodes = (HuffmanTreeNode *) malloc(sizeof(HuffmanTreeNode) * n);

    for (i = 0; i < n; i++) {
        nodes[i].weight = weights[i];
        nodes[i].left = NULL;
        nodes[i].right = NULL;
    }

    for (i = 0; i < n - 1; i++) {
        p1 = p2 = NULL;
        for (j = 0; j < n; j++) {
            if (nodes[j].weight != -1 && (p1 == NULL || nodes[j].weight < p1->weight)) {
                p1 = &nodes[j];
            }
        }
        for (k = 0; k < n; k++) {
            if (nodes[k].weight != -1 && &nodes[k] != p1 && (p2 == NULL || nodes[k].weight < p2->weight)) {
                p2 = &nodes[k];
            }
        }
        parent = (HuffmanTreeNode *) malloc(sizeof(HuffmanTreeNode));
        parent->weight = p1->weight + p2->weight;
        parent->left = p1;
        parent->right = p2;
        p1->weight = -1;
        p2->weight = -1;
        nodes[i] = *parent;
    }

    tree->root = &nodes[n - 2];
    free(nodes);
}

void huffman_tree_traverse(HuffmanTreeNode *root, char *code, int depth, HuffmanCode *codes) {
    if (root == NULL) {
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        int i;
        for (i = 0; i < 26; i++) {
            if (codes[i].ch == '\0') {
                codes[i].ch = root->ch;
                strncpy(codes[i].code, code, MAX_LEN);
                codes[i].code[depth] = '\0';
                break;
            }
        }
    } else {
        code[depth] = '0';
        huffman_tree_traverse(root->left, code, depth + 1, codes);
        code[depth] = '1';
        huffman_tree_traverse(root->right, code, depth + 1, codes);
    }
}

void huffman_code_encode(char *msg, HuffmanCode *codes, char *encoded_msg) {
    int i, j, len;
    char code[MAX_LEN];

    len = strlen(msg);
    encoded_msg[0] = '\0';
    for (i = 0; i < len; i++) {
        for (j = 0; j < 26; j++) {
            if (codes[j].ch == msg[i]) {
                strcat(encoded_msg, codes[j].code);
                break;
            }
        }
    }
}

void huffman_code_decode(char *encoded_msg, HuffmanTreeNode *root, char *decoded_msg) {
    int i, len;
    HuffmanTreeNode *p;

    len = strlen(encoded_msg);
    decoded_msg[0] = '\0';
    p = root;
    for (i = 0; i < len; i++) {
        if (encoded_msg[i] == '0') {
            p = p->left;
        } else {
            p = p->right;
        }
        if (p->left == NULL && p->right == NULL) {
            strncat(decoded_msg, &(p->ch), 1);
            p = root;
        }
    }
}

以上代码通过 `huffman_tree_create` 函数构造哈夫曼树，通过 `huffman_tree_traverse` 函数遍历哈夫曼树并生成哈夫曼编码，通过 `huffman_code_encode` 函数将消息编码为密文，通过 `huffman_code_decode` 函数将密文解码为原消息。