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

好的，这是一个比较复杂的问题，需要分步骤回答。首先是构造哈夫曼树的过程，可以按照以下步骤进行：

1. 定义一个结构体表示哈夫曼树的节点，包括权值、左右子树指针和父节点指针。

struct huff_node {
    int weight;
    struct huff_node *left;
    struct huff_node *right;
    struct huff_node *parent;
};

2. 定义一个比较函数，用于排序时比较节点的权值大小。

int cmp_node(const void *a, const void *b) {
    return ((struct huff_node *)a)->weight - ((struct huff_node *)b)->weight;
}

3. 定义一个函数，用于构造哈夫曼树。首先将所有叶子节点按权值从小到大排序，然后取出权值最小的两个节点作为左右子树，构造一个新的节点，权值为左右子树节点权值之和，将新节点插入到节点数组中，然后重复这个过程，直到只剩下一个节点，即为根节点。

struct huff_node *build_huff_tree(int *weights, int n) {
    struct huff_node *nodes = (struct huff_node *)malloc(n * sizeof(struct huff_node));
    for (int i = 0; i < n; i++) {
        nodes[i].weight = weights[i];
        nodes[i].left = NULL;
        nodes[i].right = NULL;
        nodes[i].parent = NULL;
    }
    qsort(nodes, n, sizeof(struct huff_node), cmp_node);
    for (int i = 0; i < n - 1; i++) {
        struct huff_node *new_node = (struct huff_node *)malloc(sizeof(struct huff_node));
        new_node->weight = nodes[i].weight + nodes[i+1].weight;
        new_node->left = &nodes[i];
        new_node->right = &nodes[i+1];
        new_node->parent = NULL;
        nodes[i+1].parent = nodes[i].parent = new_node;
        int j = i + 2;
        while (j < n && nodes[j].weight < new_node->weight) {
            nodes[j-1] = nodes[j];
            j++;
        }
        nodes[j-1] = *new_node;
    }
    return &nodes[n-1];
}

接下来是构造哈夫曼编码的过程，可以按照以下步骤进行：

1. 定义一个结构体表示哈夫曼编码，包括字符、编码字符串和编码长度。

struct huff_code {
    int c;
    char *code;
    int len;
};

2. 定义一个递归函数，用于从根节点开始遍历哈夫曼树，将叶子节点的编码存储到编码表中。

void build_huff_code(struct huff_node *node, char *buf, int len, struct huff_code *codes) {
    if (node->left == NULL && node->right == NULL) {
        codes[node->weight].c = node->weight;
        codes[node->weight].code = (char *)malloc((len+1) * sizeof(char));
        strncpy(codes[node->weight].code, buf, len);
        codes[node->weight].code[len] = '\0';
        codes[node->weight].len = len;
    } else {
        buf[len] = '0';
        build_huff_code(node->left, buf, len+1, codes);
        buf[len] = '1';
        build_huff_code(node->right, buf, len+1, codes);
    }
}

3. 调用上述函数，从根节点开始构造哈夫曼编码。

struct huff_code *build_huff_codes(struct huff_node *root, int n) {
    struct huff_code *codes = (struct huff_code *)malloc(n * sizeof(struct huff_code));
    char buf[n];
    build_huff_code(root, buf, 0, codes);
    return codes;
}

最后是解码的过程，可以按照以下步骤进行：

1. 定义一个函数，用于从编码字符串中取出一个字符的编码。

int get_code(char *buf, int *ptr, struct huff_node *node) {
    if (node->left == NULL && node->right == NULL) {
        return node->weight;
    } else if (buf[*ptr] == '0') {
        (*ptr)++;
        return get_code(buf, ptr, node->left);
    } else {
        (*ptr)++;
        return get_code(buf, ptr, node->right);
    }
}

2. 定义一个函数，用于解码密文。首先从编码表中找到每个字符的编码，然后遍历密文字符串，将连续的编码字符串转换成字符。

void decode_huff(char *cipher, struct huff_code *codes, int n) {
    struct huff_node *root = build_huff_tree(codes, n);
    int len = strlen(cipher);
    char buf[len];
    int ptr = 0;
    for (int i = 0; i < len; i++) {
        buf[ptr++] = cipher[i];
        for (int j = 0; j < n; j++) {
            if (strncmp(buf, codes[j].code, ptr) == 0) {
                printf("%c", codes[j].c);
                ptr = 0;
                break;
            }
        }
    }
    if (ptr > 0) {
        fprintf(stderr, "Error: invalid cipher\n");
    }
}

完整的代码如下：