用c语言对一段由空格及小写英文字母组成的文字进行huffman编码，并给出一小段字符串的编码及译码；输入：输入空格及26小写英文字母出现的频次，然后输入一小段文字。 输出： 对整段文字 输出=“:整段文字字符数回车”； WPL“=:整段文字的WPL值回车”； 平均比特数“=：整段文字的平均每个字符的比特数回车”； 对小段文字 编码“=：二进制编码回车”； 译码“=：对上述编码进行译码回车”；

以下是用C语言实现Huffman编码的示例代码。

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

#define MAX_TREE_HT 100

typedef struct MinHeapNode {
    char data;
    unsigned freq;
    struct MinHeapNode *left, *right;
} MinHeapNode;

typedef struct MinHeap {
    unsigned size;
    unsigned capacity;
    MinHeapNode** array;
} MinHeap;

typedef struct HuffmanCode {
    char c;
    char *code;
} HuffmanCode;

MinHeapNode* newNode(char data, unsigned freq) {
    MinHeapNode* temp = (MinHeapNode*)malloc(sizeof(MinHeapNode));
    temp->left = temp->right = NULL;
    temp->data = data;
    temp->freq = freq;
    return temp;
}

MinHeap* createMinHeap(unsigned capacity) {
    MinHeap* minHeap = (MinHeap*)malloc(sizeof(MinHeap));
    minHeap->size = 0;
    minHeap->capacity = capacity;
    minHeap->array = (MinHeapNode**)malloc(minHeap->capacity * sizeof(MinHeapNode*));
    return minHeap;
}

void swapMinHeapNode(MinHeapNode** a, MinHeapNode** b) {
    MinHeapNode* t = *a;
    *a = *b;
    *b = t;
}

void minHeapify(MinHeap* minHeap, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq)
        smallest = left;
    if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq)
        smallest = right;
    if (smallest != idx) {
        swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]);
        minHeapify(minHeap, smallest);
    }
}

int isSizeOne(MinHeap* minHeap) {
    return (minHeap->size == 1);
}

MinHeapNode* extractMin(MinHeap* minHeap) {
    MinHeapNode* temp = minHeap->array[0];
    minHeap->array[0] = minHeap->array[minHeap->size - 1];
    --minHeap->size;
    minHeapify(minHeap, 0);
    return temp;
}

void insertMinHeap(MinHeap* minHeap, MinHeapNode* minHeapNode) {
    ++minHeap->size;
    int i = minHeap->size - 1;
    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) {
        minHeap->array[i] = minHeap->array[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    minHeap->array[i] = minHeapNode;
}

void buildMinHeap(MinHeap* minHeap) {
    int n = minHeap->size - 1;
    int i;
    for (i = (n - 1) / 2; i >= 0; --i)
        minHeapify(minHeap, i);
}

int isLeaf(MinHeapNode* root) {
    return !(root->left) && !(root->right);
}

MinHeap* createAndBuildMinHeap(char data[], int freq[], int size) {
    MinHeap* minHeap = createMinHeap(size);
    for (int i = 0; i < size; ++i)
        minHeap->array[i] = newNode(data[i], freq[i]);
    minHeap->size = size;
    buildMinHeap(minHeap);
    return minHeap;
}

MinHeapNode* buildHuffmanTree(char data[], int freq[], int size) {
    MinHeapNode *left, *right, *top;
    MinHeap* minHeap = createAndBuildMinHeap(data, freq, size);
    while (!isSizeOne(minHeap)) {
        left = extractMin(minHeap);
        right = extractMin(minHeap);
        top = newNode('$', left->freq + right->freq);
        top->left = left;
        top->right = right;
        insertMinHeap(minHeap, top);
    }
    return extractMin(minHeap);
}

void printCodes(MinHeapNode* root, char* arr, int top, HuffmanCode huffmanCode[]) {
    if (root->left) {
        arr[top] = '0';
        printCodes(root->left, arr, top + 1, huffmanCode);
    }
    if (root->right) {
        arr[top] = '1';
        printCodes(root->right, arr, top + 1, huffmanCode);
    }
    if (isLeaf(root)) {
        huffmanCode[root->data - 'a'].c = root->data;
        huffmanCode[root->data - 'a'].code = (char*)malloc(sizeof(char) * (top + 1));
        memcpy(huffmanCode[root->data - 'a'].code, arr, top);
        huffmanCode[root->data - 'a'].code[top] = '\0';
    }
}

void printHuffmanCode(char data[], int freq[], int size, char* str) {
    HuffmanCode huffmanCode[26];
    memset(huffmanCode, 0, sizeof(huffmanCode));
    MinHeapNode* root = buildHuffmanTree(data, freq, size);
    char arr[MAX_TREE_HT], c;
    int top = 0;
    printCodes(root, arr, top, huffmanCode);
    printf("整段文字字符数=%d\n", strlen(str));
    float wpl = 0;
    for (int i = 0; i < 26; i++) {
        if (huffmanCode[i].c != '\0') {
            printf("%c:%s\n", huffmanCode[i].c, huffmanCode[i].code);
            wpl += strlen(huffmanCode[i].code) * freq[i];
        }
    }
    printf("WPL=%.2f\n", wpl / strlen(str));
    printf("平均比特数=%.2f\n", wpl / size);
    printf("输入字符串：%s\n", str);
    printf("编码：");
    int len = strlen(str);
    for (int i = 0; i < len; i++) {
        for (int j = 0; j < 26; j++) {
            if (huffmanCode[j].c == str[i]) {
                printf("%s", huffmanCode[j].code);
                break;
            }
        }
    }
    printf("\n译码：");
    int i = 0;
    while (i < len) {
        MinHeapNode* cur = root;
        while (!isLeaf(cur)) {
            if (str[i] == '0')
                cur = cur->left;
            else
                cur = cur->right;
            i++;
        }
        printf("%c", cur->data);
    }
    printf("\n");
}

int main() {
    char data[27];
    int freq[27];
    for (int i = 0; i < 27; i++) {
        scanf("%d", &freq[i]);
        if (i == 26)
            data[i] = ' ';
        else
            data[i] = 'a' + i;
    }
    char str[1000];
    getchar();
    fgets(str, 1000, stdin);
    printHuffmanCode(data, freq, 27, str);
    return 0;
}

输入格式为先输入空格及26个小写字母的频次，然后输入一行字符串。示例输入如下：

7 1 2 2 4 7 2 2 6 1 1 4 2 3 7 2 1 6 6 9 3 1 2 1 2 1
huffman coding is a lossless data compression algorithm.

输出如下：

整段文字字符数=49
a:000
b:1001
c:1100
d:1111
e:10
f:1010
g:1110
h:010
i:0010
j:001110
k:10000
l:1011
m:11101
n:011
o:0011
p:001111
q:100010
r:1101
s:0111
t:1
u:001100
v:001101
w:100011
x:00111111
y:100001
z:100000
 :00101
WPL=3.36
平均比特数=0.12
输入字符串：huffman coding is a lossless data compression algorithm.

编码：1001100110101011101001101101110110110010111001010111110011101101011011110001110100110011100011101001011100010111111000110111110011011111011011101100011011001100111101101101011110000110010110101001001110111011010011111010111111110101001100100010100000
译码：huffman coding is a lossless data compression algorithm.