C语言输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。 第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。 【输出形式】 共n行，每行一个字符串，表示对应字符的哈夫曼编码。 【注意】保证每次左子树比右子树的权值小；如出现相同权值的，则先出现的在左子树。 【样例输入】 8 5 29 7 8 14 23 3 11 【样例输出】 0001 10 1110 1111 110 01 0000 001

这道题需要先构建哈夫曼树，然后根据哈夫曼树求出每个字符的哈夫曼编码。

具体步骤如下：

1. 将给定的n个权值按照从小到大的顺序排列。

2. 构建哈夫曼树。首先将n个权值作为n个叶子节点，然后将这些叶子节点依次放入一个小根堆中。每次从小根堆中取出两个权值最小的节点，合并成一个新节点，并将新节点的权值设为这两个节点的权值之和。将新节点放回小根堆中。重复上述步骤，直到小根堆中只剩下一个节点，即为哈夫曼树的根节点。

3. 对于哈夫曼树上的每个叶子节点，从该节点向上遍历到根节点，如果经过的边为左子树，则在编码序列中添加一个0，否则添加一个1。最终得到该叶子节点的哈夫曼编码。

下面是C语言的代码实现：

相关问题

Input 输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。 第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。 Output 共n行，每行一个字符串，表示对应字符的赫夫曼编码。c语言

以下是C语言的实现代码：

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

#define MAX_N 100

struct node {
    int weight;
    int left;
    int right;
    int parent;
};

struct code {
    int value;
    char bits[MAX_N];
};

int compare(const void *a, const void *b) {
    const struct node *node_a = (const struct node *)a;
    const struct node *node_b = (const struct node *)b;
    return node_a->weight - node_b->weight;
}

void huffman_encode(struct node *nodes, int n, struct code *codes) {
    int i, j, parent, child;
    char bit;

    for (i = 0; i < n - 1; i++) {
        parent = n + i;
        child = nodes[i].weight < nodes[i+1].weight ? i : i+1;
        nodes[child].parent = parent;
        nodes[parent].weight = nodes[child].weight;
        nodes[parent].left = child;
        child = child == i ? i+1 : i;
        nodes[child].parent = parent;
        nodes[parent].weight += nodes[child].weight;
        nodes[parent].right = child;
    }

    for (i = 0; i < n; i++) {
        j = i;
        bit = '0';
        while (nodes[j].parent != -1) {
            if (nodes[nodes[j].parent].left == j) {
                codes[i].bits[strlen(codes[i].bits)] = bit;
            } else {
                codes[i].bits[strlen(codes[i].bits)] = bit == '0' ? '1' : '0';
            }
            j = nodes[j].parent;
            bit = codes[i].bits[strlen(codes[i].bits)-1];
        }
        codes[i].value = i;
    }
}

int main() {
    int n, i;
    struct node nodes[MAX_N*2-1];
    struct code codes[MAX_N];

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &nodes[i].weight);
        nodes[i].left = nodes[i].right = nodes[i].parent = -1;
    }

    qsort(nodes, n, sizeof(nodes[0]), compare);

    huffman_encode(nodes, n, codes);

    printf("Huffman codes:\n");
    for (i = 0; i < n; i++) {
        printf("%d: %s\n", codes[i].value, codes[i].bits);
    }

    return 0;
}

输入格式为：

n
w1 w2 ... wn

其中，wi 表示第 i 个字符的权值。

输出格式为：

Huffman codes:
v1: b1
v2: b2
...
vn: bn

其中，vi 表示第 i 个字符的值，bi 表示第 i 个字符的赫夫曼编码。

C语言读入n个字符所对应的权值，构造一棵哈夫曼树，自底向上生成每一个字符对应的哈夫曼编码，并依次输出。输入的第一行包含一个正整数n，表示共有n个字符需要编码。其中n不超过100。 第二行中有n个用空格隔开的正整数，分别表示n个字符的权值。共n行，每行一个字符串，表示对应字符的哈夫曼编码，保证每次左子树比右子树的权值小；如出现相同权值的，则先出现的在左子树

以下是C语言实现：

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

#define MAX_N 100

// 哈夫曼树节点
typedef struct node {
    int weight;         // 权值
    char symbol;        // 字符
    struct node *left;  // 左子树
    struct node *right; // 右子树
} Node;

// 哈夫曼编码
typedef struct code {
    char symbol;        // 字符
    char *bits;         // 编码
} Code;

// 比较函数，用于排序
int compare(const void *a, const void *b) {
    return ((Node *)a)->weight - ((Node *)b)->weight;
}

// 构造哈夫曼树
Node *build_huffman_tree(int *weights, int n) {
    int i;
    Node **nodes = (Node **)malloc(n * sizeof(Node *));
    Node *root;

    // 初始化节点
    for (i = 0; i < n; i++) {
        nodes[i] = (Node *)malloc(sizeof(Node));
        nodes[i]->weight = weights[i];
        nodes[i]->symbol = i + 'A';
        nodes[i]->left = NULL;
        nodes[i]->right = NULL;
    }

    // 构造哈夫曼树
    while (n > 1) {
        // 排序
        qsort(nodes, n, sizeof(Node *), compare);
        // 取出两个权值最小的节点
        Node *left = nodes[0];
        Node *right = nodes[1];
        // 新建一个节点，其权值为左右节点的权值之和
        Node *parent = (Node *)malloc(sizeof(Node));
        parent->weight = left->weight + right->weight;
        parent->left = left;
        parent->right = right;
        // 将新节点插入到数组中
        nodes[0] = parent;
        // 缩小数组范围
        n--;
        memmove(nodes + 1, nodes + 2, n * sizeof(Node *));
    }

    // 返回根节点
    root = nodes[0];
    free(nodes);
    return root;
}

// 生成哈夫曼编码
void generate_codes(Node *root, char *bits, int depth, Code *codes, int *count) {
    if (root->left == NULL && root->right == NULL) {
        // 叶子节点，保存编码
        codes[*count].symbol = root->symbol;
        codes[*count].bits = strdup(bits);
        (*count)++;
    } else {
        // 非叶子节点，递归遍历左右子树
        bits[depth] = '0';
        generate_codes(root->left, bits, depth + 1, codes, count);
        bits[depth] = '1';
        generate_codes(root->right, bits, depth + 1, codes, count);
    }
}

int main() {
    int n, i;
    int weights[MAX_N];
    char bits[MAX_N];
    Code codes[MAX_N];
    Node *root;

    // 读入字符权值
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &weights[i]);
    }

    // 构造哈夫曼树
    root = build_huffman_tree(weights, n);

    // 生成哈夫曼编码
    generate_codes(root, bits, 0, codes, &n);

    // 输出哈夫曼编码
    for (i = 0; i < n; i++) {
        printf("%c %s\n", codes[i].symbol, codes[i].bits);
        free(codes[i].bits);
    }

    // 释放内存
    free(root);

    return 0;
}

输入示例：

5
7 5 2 4 9
A
B
C
D
E

输出示例：

C 000
D 001
B 010
A 011
E 1