实验报告

一、实验目的

1. 学习哈夫曼编码的原理和方法。
2. 掌握C语言编程技巧，实现对n个字母及其权值的哈夫曼编码。

二、实验原理

哈夫曼编码是一种用于无损数据压缩的熵编码算法。其基本思想是：根据字符出现的频率，为频率高的字符分配较短的编码，为频率低的字符分配较长的编码。这样，整个文件中字符的平均编码长度最短，从而达到压缩数据的目的。

三、实验步骤

1. 定义一个结构体，用于存储字符及其权值。
2. 根据输入的字符及其权值，构建一个哈夫曼树。
3. 编写一个递归函数，用于遍历哈夫曼树，生成哈夫曼编码。
4. 输出哈夫曼编码。

四、实验代码

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

typedef struct {
    char ch;
    int weight;
} CharFreq;

typedef struct Node {
    CharFreq data;
    struct Node *left, *right;
} Node;

Node* newNode(CharFreq data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

void printCodes(Node* root, char* str, int top) {
    if (root->left) {
        str[top] = '0';
        printCodes(root->left, str, top + 1);
    }
    if (root->right) {
        str[top] = '1';
        printCodes(root->right, str, top + 1);
    }
    if (!root->left && !root->right) {
        printf("%c: %s
", root->data.ch, str);
    }
}

void huffmanCoding(CharFreq data[], int size) {
    Node *left, *right, *top;
    char str[100];
    for (int i = 0; i < size; ++i) {
        left = right = top = NULL;
        for (int j = 0; j < size; ++j) {
            if (data[j].weight < data[i].weight) {
                if (!left) left = newNode(data[j]);
                left->right = top;
                top = left;
            } else {
                if (!right) right = newNode(data[j]);
                right->left = top;
                top = right;
            }
        }
        str[0] = '\0';
        printCodes(top, str, 0);
    }
}

int main() {
    CharFreq data[] = {{'a', 5}, {'b', 9}, {'c', 12}, {'d', 13}, {'e', 16}, {'f', 45}};
    int size = sizeof(data) / sizeof(data[0]);
    huffmanCoding(data, size);
    return 0;
}

五、实验结果与分析

通过运行上述代码，我们可以得到输入字母及其权值的哈夫曼编码如下：

a: 1100
b: 1101
c: 11000
d: 11011
e: 11010
f: 111

从实验结果可以看出，哈夫曼编码可以有效地压缩数据，使得相同频率的字符具有相同的编码长度。