c语言构造哈夫曼编码

下面是C语言构造哈夫曼编码的步骤：

1.定义哈夫曼树的结构体：

typedef struct node{
    int weight; // 权重
    int parent; // 父节点
    int lchild; // 左孩子
    int rchild; // 右孩子
}HuffmanTree;

2.定义哈夫曼编码的结构体：

typedef struct{
    int bit[MAXBIT]; // 该字符的哈夫曼编码
    int start; // 该编码在数组bit中的开始位置
    char ch_value; // 对应字符
}HuffmanCode;

3.构造哈夫曼树：

void CreateHuffmanTree(HuffmanTree *HT, int n){
    int i, j, k, min1, min2;
    for(i = 0; i < 2 * n - 1; i++){
        HT[i].parent = -1;
        HT[i].lchild = -1;
        HT[i].rchild = -1;
    }
    for(i = 0; i < n; i++){
        scanf("%d", &HT[i].weight);
    }
    for(i = n; i < 2 * n - 1; i++){
        min1 = min2 = MAXVALUE;
        k = 0;
        for(j = 0; j < i; j++){
            if(HT[j].parent == -1){
                if(HT[j].weight < min1){
                    min2 = min1;
                    min1 = HT[j].weight;
                    k = j;
                }
                else if(HT[j].weight < min2){
                    min2 = HT[j].weight;
                }
            }
        }
        HT[k].parent = i;
        HT[i].lchild = k;
        HT[i].rchild = -1;
        HT[i].weight = min1 + min2;
    }
}

4.生成哈夫曼编码：

void CreateHuffmanCode(HuffmanTree *HT, HuffmanCode *HC, int n){
    int i, j, c, p;
    for(i = 0; i < n; i++){
        HC[i].ch_value = i + 'a';
        c = i;
        p = HT[c].parent;
        j = 0;
        while(p != -1){
            if(HT[p].lchild == c){
                HC[i].bit[j] = 0;
            }
            else{
                HC[i].bit[j] = 1;
            }
            j++;
            c = p;
            p = HT[c].parent;
        }
        HC[i].start = j - 1;
    }
}

5.完整代码：

#include <stdio.h>
#include <stdlib.h>
#define MAXVALUE 10000
#define MAXBIT 100

typedef struct node{
    int weight; // 权重
    int parent; // 父节点
    int lchild; // 左孩子
    int rchild; // 右孩子
}HuffmanTree;

typedef struct{
    int bit[MAXBIT]; // 该字符的哈夫曼编码
    int start; // 该编码在数组bit中的开始位置
    char ch_value; // 对应字符
}HuffmanCode;

void CreateHuffmanTree(HuffmanTree *HT, int n){
    int i, j, k, min1, min2;
    for(i = 0; i < 2 * n - 1; i++){
        HT[i].parent = -1;
        HT[i].lchild = -1;
        HT[i].rchild = -1;
    }
    for(i = 0; i < n; i++){
        scanf("%d", &HT[i].weight);
    }
    for(i = n; i < 2 * n - 1; i++){
        min1 = min2 = MAXVALUE;
        k = 0;
        for(j = 0; j < i; j++){
            if(HT[j].parent == -1){
                if(HT[j].weight < min1){
                    min2 = min1;
                    min1 = HT[j].weight;
                    k = j;
                }
                else if(HT[j].weight < min2){
                    min2 = HT[j].weight;
                }
            }
        }
        HT[k].parent = i;
        HT[i].lchild = k;
        HT[i].rchild = -1;
        HT[i].weight = min1 + min2;
    }
}

void CreateHuffmanCode(HuffmanTree *HT, HuffmanCode *HC, int n){
    int i, j, c, p;
    for(i = 0; i < n; i++){
        HC[i].ch_value = i + 'a';
        c = i;
        p = HT[c].parent;
        j = 0;
        while(p != -1){
            if(HT[p].lchild == c){
                HC[i].bit[j] = 0;
            }
            else{
                HC[i].bit[j] = 1;
            }
            j++;
            c = p;
            p = HT[c].parent;
        }
        HC[i].start = j - 1;
    }
}

int main(){
    int n, i, j;
    HuffmanTree *HT;
    HuffmanCode *HC;
    printf("请输入字符个数：");
    scanf("%d", &n);
    HT = (HuffmanTree*)malloc(sizeof(HuffmanTree) * (2 * n - 1));
    HC = (HuffmanCode*)malloc(sizeof(HuffmanCode) * n);
    CreateHuffmanTree(HT, n);
    CreateHuffmanCode(HT, HC, n);
    printf("哈夫曼编码如下：\n");
    for(i = 0; i < n; i++){
        printf("%c: ", HC[i].ch_value);
        for(j = HC[i].start; j >= 0; j--){
            printf("%d", HC[i].bit[j]);
        }
        printf("\n");
    }
    free(HT);
    free(HC);
    return 0;
}