编写构造哈夫曼树和求哈夫曼编码的算法

好的，下面是构造哈夫曼树和求哈夫曼编码的算法。

构造哈夫曼树算法：

1. 初始化一个权值数组 `w[]`，其中 `w[i]` 表示第 `i` 个叶子节点的权值。
2. 创建一个哈夫曼树森林，即将每个叶子节点看作是一个单独的树。
3. 从哈夫曼树森林中选取两个根节点权值最小的树，合并成一棵新的树，根节点的权值为两个子树根节点权值之和。
4. 将新的树插入哈夫曼树森林中，并删除原来的两棵树。
5. 重复步骤3和步骤4，直到哈夫曼树森林中只剩下一棵树，即为哈夫曼树。

下面是求哈夫曼编码的算法：

1. 对于哈夫曼树中每个叶子节点，将其从叶子节点向上遍历到根节点的路径上的所有边进行编号，规定左孩子为0，右孩子为1，得到该叶子节点的哈夫曼编码。
2. 对于哈夫曼树中的每个叶子节点，将其权值和哈夫曼编码存储在一个编码表中。

下面是 C 语言代码实现：

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

#define MAXLEN 100   // 最大编码长度

typedef struct {
    int weight;          // 权值
    int parent, lchild, rchild;  // 双亲和左右孩子指针
} HTNode, *HuffmanTree;

typedef char *HuffmanCode[MAXLEN];   // 动态数组存储哈夫曼编码

// 选择权值最小的两个节点
void Select(HuffmanTree HT, int n, int *s1, int *s2) {
    int i, min1, min2;
    min1 = min2 = 0;
    for (i = 1; i <= n; i++) {
        if (HT[i].parent == 0) {
            if (HT[i].weight < HT[min1].weight) {
                min2 = min1;
                min1 = i;
            } else if (HT[i].weight < HT[min2].weight) {
                min2 = i;
            }
        }
    }
    *s1 = min1;
    *s2 = min2;
}

// 构造哈夫曼树
void CreateHuffmanTree(HuffmanTree *HT, int n) {
    int i, s1, s2;
    if (n <= 1) {
        return;
    }
    int m = 2 * n - 1;
    *HT = (HuffmanTree) malloc((m + 1) * sizeof(HTNode));   // 分配空间
    for (i = 1; i <= m; i++) {   // 初始化
        (*HT)[i].parent = (*HT)[i].lchild = (*HT)[i].rchild = 0;
        (*HT)[i].weight = 0;
    }
    for (i = 1; i <= n; i++) {   // 输入权值
        scanf("%d", &(*HT)[i].weight);
    }
    for (i = n+1; i <= m; i++) {   // 构造哈夫曼树
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = i;
        (*HT)[s2].parent = i;
        (*HT)[i].lchild = s1;
        (*HT)[i].rchild = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
    }
}

// 生成哈夫曼编码
void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n) {
    char *cd = (char *) malloc(n * sizeof(char));   // 暂存编码
    cd[n-1] = '\0';
    int i, c, p;
    for (i = 1; i <= n; i++) {   // 逐个叶子节点求哈夫曼编码
        int start = n - 1;
        for (c = i, p = HT[i].parent; p != 0; c = p, p = HT[p].parent) {
            if (HT[p].lchild == c) {
                cd[--start] = '0';
            } else {
                cd[--start] = '1';
            }
        }
        HC[i-1] = (char *) malloc((n - start) * sizeof(char));
        strcpy(HC[i-1], &cd[start]);   // 复制编码
    }
    free(cd);   // 释放空间
}

int main() {
    int n, i;
    printf("请输入叶子节点的个数：");
    scanf("%d", &n);
    HuffmanTree HT;
    HuffmanCode HC;
    CreateHuffmanTree(&HT, n);
    HuffmanCoding(HT, HC, n);
    printf("哈夫曼编码如下：\n");
    for (i = 0; i < n; i++) {
        printf("%d: %s\n", i+1, HC[i]);
    }
    free(HT);
    for (i = 0; i < n; i++) {
        free(HC[i]);
    }
    return 0;
}

输入格式：

第一行输入叶子节点的个数 `n`。

接下来一行输入 `n` 个整数，表示每个叶子节点的权值。

输出格式：

输出每个叶子节点的哈夫曼编码。

希望对您有所帮助！