c语言代码实现霍夫曼树和霍夫曼编码

霍夫曼树和霍夫曼编码是一种常用的数据压缩算法，以下是用C语言实现霍夫曼树和霍夫曼编码的代码。

首先，定义霍夫曼树的节点结构体：

typedef struct node {
    int weight;           // 权重
    int parent, lchild, rchild;  // 父节点、左右孩子节点的下标
}HuffmanNode, *HuffmanTree;

定义霍夫曼编码的结构体：

typedef struct {
    int bit[MaxBit];   // 存放霍夫曼编码的数组
    int start;         // 编码的起始位置
}HuffmanCode;

接下来，定义霍夫曼树的创建函数：

void createHuffmanTree(HuffmanTree ht, int n) {
    int i, j, min1, min2;
    // 初始化
    for (i = 0; i < 2 * n - 1; i++) {
        ht[i].parent = ht[i].lchild = 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;
        ht[i].weight = 0;
        for (j = 0; j < i; j++) {
            if (ht[j].parent == -1) {
                if (ht[j].weight < min1) {
                    min2 = min1;
                    min1 = ht[j].weight;
                    ht[i].lchild = j;
                }
                else if (ht[j].weight < min2) {
                    min2 = ht[j].weight;
                    ht[i].rchild = j;
                }
            }
        }
        ht[i].weight = ht[ht[i].lchild].weight + ht[ht[i].rchild].weight;
        ht[ht[i].lchild].parent = i;
        ht[ht[i].rchild].parent = i;
    }
}

接下来，定义霍夫曼编码的生成函数：

void getHuffmanCode(HuffmanTree ht, HuffmanCode* hc, int n) {
    int i, j, c, p;
    HuffmanCode hc_tmp;
    for (i = 0; i < n; i++) {
        hc[i].start = n;
        c = i;
        p = ht[c].parent;
        while (p != -1) {
            if (ht[p].lchild == c) {
                hc_tmp.bit[hc_tmp.start--] = 0;
            }
            else {
                hc_tmp.bit[hc_tmp.start--] = 1;
            }
            c = p;
            p = ht[c].parent;
        }
        hc[i].start = hc_tmp.start + 1;
        for (j = hc[i].start; j < n; j++) {
            hc[i].bit[j] = hc_tmp.bit[j];
        }
    }
}

最后，可以在主函数中调用以上函数来实现霍夫曼树和霍夫曼编码的创建：

int main() {
    int n;
    scanf("%d", &n);
    HuffmanTree ht = (HuffmanTree)malloc(sizeof(HuffmanNode) * 2 * n - 1);
    HuffmanCode* hc = (HuffmanCode*)malloc(sizeof(HuffmanCode) * n);
    createHuffmanTree(ht, n);
    getHuffmanCode(ht, hc, n);
    // 输出霍夫曼编码
    for (int i = 0; i < n; i++) {
        printf("%d: ", ht[i].weight);
        for (int j = hc[i].start; j < n; j++) {
            printf("%d", hc[i].bit[j]);
        }
        printf("\n");
    }
    return 0;
}

这样，就可以实现霍夫曼树和霍夫曼编码的创建了。