哈夫曼编码c语言

哈夫曼编码是一种用于数据压缩的算法。下面是C语言实现哈夫曼编码的示例代码：

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

#define MAX_NODE_NUM 1000

typedef struct {
    int weight;
    int parent, lchild, rchild;
} HuffmanNode;

typedef struct {
    int bit[MAX_NODE_NUM];
    int start;
} HuffmanCode;

void HuffmanCoding(HuffmanNode *huffmanTree, HuffmanCode *huffmanCode, int n)
{
    int i, j, parent, left, right;
    for (i = 0; i < n; i++) {
        huffmanTree[i].parent = -1;
        huffmanTree[i].lchild = -1;
        huffmanTree[i].rchild = -1;
    }
    for (i = 0; i < n-1; i++) {
        int min1 = MAX_NODE_NUM, min2 = MAX_NODE_NUM;
        left = right = -1;
        for (j = 0; j < n+i; j++) {
            if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min1) {
                min2 = min1;
                right = left;
                min1 = huffmanTree[j].weight;
                left = j;
            } else if (huffmanTree[j].parent == -1 && huffmanTree[j].weight < min2) {
                min2 = huffmanTree[j].weight;
                right = j;
            }
        }
        huffmanTree[left].parent = n + i;
        huffmanTree[right].parent = n + i;
        huffmanTree[n + i].lchild = left;
        huffmanTree[n + i].rchild = right;
        huffmanTree[n + i].weight = min1 + min2;
    }
    for (i = 0; i < n; i++) {
        HuffmanCode *code = &huffmanCode[i];
        code->start = n - 1;
        parent = huffmanTree[i].parent;
        while (parent != -1) {
            if (huffmanTree[parent].lchild == i) {
                code->bit[code->start] = 0;
            } else {
                code->bit[code->start] = 1;
            }
            code->start--;
            i = parent;
            parent = huffmanTree[parent].parent;
        }
    }
}

int main()
{
    int i, n;
    HuffmanNode huffmanTree[MAX_NODE_NUM];
    HuffmanCode huffmanCode[MAX_NODE_NUM];
    printf("请输入叶子结点的个数：");
    scanf("%d", &n);
    printf("请输入每个叶子结点的权重：");
    for (i = 0; i < n; i++) {
        scanf("%d", &huffmanTree[i].weight);
    }
    HuffmanCoding(huffmanTree, huffmanCode, n);
    printf("哈夫曼编码表：\n");
    for (i = 0; i < n; i++) {
        printf("结点%d的哈夫曼编码为：", i);
        int j;
        for (j = huffmanCode[i].start + 1; j < n; j++) {
            printf("%d", huffmanCode[i].bit[j]);
        }
        printf("\n");
    }
    return 0;
}

该代码中定义了两个结构体：`HuffmanNode`表示哈夫曼树中的结点，包括权值、父结点、左孩子和右孩子；`HuffmanCode`表示哈夫曼编码，包括二进制位以及起始位置。

在`HuffmanCoding`函数中，首先初始化哈夫曼树的每个结点，然后依次求出每个非叶子结点，直到只剩下一个根结点。接着遍历每个叶子结点，求出其哈夫曼编码。最后输出哈夫曼编码表。

在主函数中，首先输入叶子结点的个数和权重，然后调用`HuffmanCoding`函数求出哈夫曼编码，最后输出哈夫曼编码表。