用C语言编写完成输入n个字母及其权值，对其进行哈夫曼编码，编写完整代码并完成实验报告

实验报告

一、实验目的

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

二、实验原理

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

三、实验步骤

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

四、实验代码

```c
#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
```

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