构造哈夫曼树，并根据哈夫曼树构造哈夫曼编码用c语言

以下是用C语言实现构造哈夫曼树和哈夫曼编码的算法：

1.构造哈夫曼树

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

#define MAX 1000

typedef struct node {
    int weight;
    int parent, lchild, rchild;
} HTNode, *HuffmanTree;

void select(HuffmanTree HT, int n, int *s1, int *s2) {
    int i, min1 = MAX, min2 = MAX;
    for (i = 1; i <= n; i++) {
        if (HT[i].parent == 0) {
            if (HT[i].weight < min1) {
                min2 = min1;
                *s2 = *s1;
                min1 = HT[i].weight;
                *s1 = i;
            } else if (HT[i].weight < min2) {
                min2 = HT[i].weight;
                *s2 = i;
            }
        }
    }
}

void createHuffmanTree(HuffmanTree *HT, int *w, int n) {
    if (n <= 1) return;
    int m = 2 * n - 1;
    *HT = (HuffmanTree) malloc((m + 1) * sizeof(HTNode));
    HuffmanTree p;
    int i;
    for (p = *HT + 1, i = 1; i <= n; ++i, ++p, ++w) {
        p->weight = *w;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    for (; i <= m; ++i, ++p) {
        p->weight = 0;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    int s1, s2;
    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;
    }
}

2.构造哈夫曼编码

typedef char **HuffmanCode;

void getCode(HuffmanTree HT, HuffmanCode *HC, int n) {
    *HC = (char **) malloc((n + 1) * sizeof(char *));
    char *cd = (char *) malloc(n * sizeof(char));
    cd[n - 1] = '\0';
    int i, c, f;
    for (i = 1; i <= n; ++i) {
        int start = n - 1;
        for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {
            if (HT[f].lchild == c) {
                cd[--start] = '0';
            } else {
                cd[--start] = '1';
            }
        }
        (*HC)[i] = (char *) malloc((n - start) * sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }
    free(cd);
}

3.完整代码

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

#define MAX 1000

typedef struct node {
    int weight;
    int parent, lchild, rchild;
} HTNode, *HuffmanTree;

typedef char **HuffmanCode;

void select(HuffmanTree HT, int n, int *s1, int *s2) {
    int i, min1 = MAX, min2 = MAX;
    for (i = 1; i <= n; i++) {
        if (HT[i].parent == 0) {
            if (HT[i].weight < min1) {
                min2 = min1;
                *s2 = *s1;
                min1 = HT[i].weight;
                *s1 = i;
            } else if (HT[i].weight < min2) {
                min2 = HT[i].weight;
                *s2 = i;
            }
        }
    }
}

void createHuffmanTree(HuffmanTree *HT, int *w, int n) {
    if (n <= 1) return;
    int m = 2 * n - 1;
    *HT = (HuffmanTree) malloc((m + 1) * sizeof(HTNode));
    HuffmanTree p;
    int i;
    for (p = *HT + 1, i = 1; i <= n; ++i, ++p, ++w) {
        p->weight = *w;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    for (; i <= m; ++i, ++p) {
        p->weight = 0;
        p->parent = 0;
        p->lchild = 0;
        p->rchild = 0;
    }
    int s1, s2;
    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 getCode(HuffmanTree HT, HuffmanCode *HC, int n) {
    *HC = (char **) malloc((n + 1) * sizeof(char *));
    char *cd = (char *) malloc(n * sizeof(char));
    cd[n - 1] = '\0';
    int i, c, f;
    for (i = 1; i <= n; ++i) {
        int start = n - 1;
        for (c = i, f = HT[i].parent; f != 0; c = f, f = HT[f].parent) {
            if (HT[f].lchild == c) {
                cd[--start] = '0';
            } else {
                cd[--start] = '1';
            }
        }
        (*HC)[i] = (char *) malloc((n - start) * sizeof(char));
        strcpy((*HC)[i], &cd[start]);
    }
    free(cd);
}

int main() {
    int n, i;
    printf("请输入叶子结点个数：");
    scanf("%d", &n);
    int *w = (int *) malloc(n * sizeof(int));
    printf("请输入%d个权值：", n);
    for (i = 0; i < n; ++i) {
        scanf("%d", &w[i]);
    }
    HuffmanTree HT;
    createHuffmanTree(&HT, w, n);
    HuffmanCode HC;
    getCode(HT, &HC, n);
    printf("哈夫曼编码如下：\n");
    for (i = 1; i <= n; ++i) {
        printf("%d: %s\n", i, HC[i]);
    }
    return 0;
}