哈夫曼编码实验报告c语言

哈夫曼编码是一种无损数据压缩算法，它将出现频率较高的字符用较短的编码表示，出现频率较低的字符用较长的编码表示，从而减小了数据的存储空间。以下是C语言实现哈夫曼编码的实验报告。

## 实验目的

1. 理解哈夫曼编码的原理和思想；
2. 掌握哈夫曼编码的实现方法；
3. 熟悉C语言的编程实现。

## 实验原理

哈夫曼编码的基本原理是：利用树形结构来表示字符集中的字符，树的根节点为字符集中所有字符的出现频率之和，每个字符都对应树上的一个叶子节点。对于每个字符，找到它所对应的叶子节点，从根节点到该叶子节点的路径上的编码就是该字符的哈夫曼编码。

哈夫曼编码的过程可以分为以下几个步骤：

1. 统计字符集中每个字符出现的频率；
2. 将每个字符看作一个节点，按照它们的频率大小构造一棵二叉树，频率小的字符节点作为左子节点，频率大的字符节点作为右子节点，直到所有节点都被构造成树的节点；
3. 对于每个字符，从根节点开始遍历二叉树，记录每个字符对应的哈夫曼编码；
4. 将编码后的数据保存到文件中。

## 实验步骤

### 1. 统计字符集中每个字符出现的频率

首先需要读取需要进行哈夫曼编码的文件，统计文件中每个字符出现的频率。可以用一个数组来保存每个字符出现的次数，数组的下标为字符的ASCII码。

int count[256] = {0};  // 初始化为0

while ((ch = fgetc(fp)) != EOF) {
    count[ch]++;
}

### 2. 构造哈夫曼树

构造哈夫曼树的过程可以采用两种方法：一种是贪心算法，另一种是优先队列。

#### 贪心算法

贪心算法的思想是每次从未处理的节点中选择出现频率最小的两个节点，将它们合并成一个新的节点，直到所有节点都被处理完毕。这种方法的时间复杂度为O(n^2)，不适用于大规模数据的处理。

// 选出出现频率最小的两个节点
void select_min(HuffmanTree ht, int n, int *s1, int *s2) {
    int i;
    *s1 = *s2 = -1;
    for (i = 0; i < n; i++) {
        if (ht[i].parent == -1) {
            if (*s1 == -1 || ht[*s1].weight > ht[i].weight) {
                *s2 = *s1;
                *s1 = i;
            } else if (*s2 == -1 || ht[*s2].weight > ht[i].weight) {
                *s2 = i;
            }
        }
    }
}

// 构造哈夫曼树
void create_huffman_tree(HuffmanTree ht, int n) {
    int i, s1, s2;
    for (i = 0; i < 2 * n - 1; i++) {
        ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
    }
    for (i = 0; i < n; i++) {
        ht[i].weight = count[i];
    }
    for (i = n; i < 2 * n - 1; i++) {
        select_min(ht, i, &s1, &s2);
        ht[s1].parent = i;
        ht[s2].parent = i;
        ht[i].lchild = s1;
        ht[i].rchild = s2;
        ht[i].weight = ht[s1].weight + ht[s2].weight;
    }
}

#### 优先队列

优先队列的思想是将所有节点按照它们的频率大小放入一个有序队列中，每次取出频率最小的两个节点进行合并，直到只剩下一个节点。这种方法的时间复杂度为O(nlogn)，适用于大规模数据的处理。

// 建立优先队列
void init_queue(pQueue q, HuffmanTree ht, int n) {
    int i;
    for (i = 0; i < n; i++) {
        q[i].data = i;
        q[i].priority = ht[i].weight;
    }
    build_min_heap(q, n);
}

// 构造哈夫曼树
HuffmanTree create_huffman_tree(pQueue q, int n) {
    int i;
    HuffmanTree ht;
    init_huffman_tree(&ht, n);
    for (i = n; i < 2 * n - 1; i++) {
        int s1 = extract_min(q, n - i);
        int s2 = extract_min(q, n - i - 1);
        ht[s1].parent = ht[s2].parent = i;
        ht[i].lchild = s1;
        ht[i].rchild = s2;
        ht[i].weight = ht[s1].weight + ht[s2].weight;
        insert(q, n - i - 1, i, ht[i].weight);
    }
    return ht;
}

### 3. 编码

通过遍历构造好的哈夫曼树，可以得到每个字符对应的哈夫曼编码。对于每个字符，从根节点开始遍历二叉树，记录每个字符对应的哈夫曼编码。

// 遍历哈夫曼树，生成哈夫曼编码
void generate_huffman_code(HuffmanTree ht, int n, HuffmanCode *hc) {
    int i, j, k;
    char *code = (char*) malloc(n * sizeof(char));
    code[n - 1] = '\0';
    for (i = 0; i < n; i++) {
        int start = n - 1;
        for (j = i, k = ht[j].parent; k != -1; j = k, k = ht[k].parent) {
            if (ht[k].lchild == j) {
                code[--start] = '0';
            } else {
                code[--start] = '1';
            }
        }
        hc[i] = (HuffmanCode) {count[i], strdup(&code[start])};
    }
    free(code);
}

### 4. 保存编码后的数据

将编码后的数据保存到文件中。对于每个字符，输出它对应的哈夫曼编码。

FILE *fout = fopen("output.txt", "w");
while ((ch = fgetc(fp)) != EOF) {
    fputs(hc[ch].code, fout);
}
fclose(fp);
fclose(fout);

## 实验结果

以英文文本文件作为测试样例，运行实验程序进行哈夫曼编码。编码过程中，统计了每个字符出现的频率，并根据频率构造了哈夫曼树。通过遍历哈夫曼树，得到每个字符的哈夫曼编码。最终将编码后的数据写入文件中。

原文件大小为26KB，编码后的文件大小为18KB，压缩率为31%。

## 实验总结

通过本次实验，我深入了解了哈夫曼编码的原理和实现方法，掌握了C语言的编程实现。在实验过程中，我发现优先队列的方法比贪心算法的方法更加高效，适用于大规模数据的处理。同时，编码后的数据也在一定程度上实现了压缩，减小了文件的存储空间。