Write a C program to implement file compression using Huffman coding, output the compression ratio, and conduct testing. 并用中文附上详细注释

编写一个C程序，使用Huffman编码实现文件压缩，并计算压缩比，最后进行测试。以下是详细的步骤和代码示例： ```c #include <stdio.h> #include <stdlib.h> #include <limits.h> #include <stdbool.h> #include <string.h> // 定义树节点结构体 typedef struct Node { char data; int freq; // 频率 struct Node *left, *right; } Node; // 创建新节点 Node* newNode(char data, int freq) { Node* node = (Node*)malloc(sizeof(Node)); node->data = data; node->freq = freq; node->left = NULL; node->right = NULL; return node; } // 比较两个节点的频率 int compare(const void* a, const void* b) { return ((Node*)a)->freq - ((Node*)b)->freq; } // 构建Huffman树并返回根节点 Node* huffmanTree(char arr[], int n) { // 对字符按频率排序 qsort(arr, n, sizeof(arr[0]), compare); // 初始化堆 priority_queue<Node*, vector<Node*>, greater<Node*>> pq; for(int i=0; i<n; i++) { pq.push(newNode(arr[i], 1)); // 将每个字符作为独立的节点放入堆中，频率初始化为1 } while(pq.size() > 1) { // 取出两个频率最低的节点合并成新的节点 Node* left = pq.top(); pq.pop(); Node* right = pq.top(); pq.pop(); // 新节点的频率是左右节点之和 Node* newNode = newNode('\0', left->freq + right->freq); newNode->left = left; newNode->right = right; // 将新节点插入堆 pq.push(newNode); } return pq.top(); // 返回构建完成的Huffman树根节点 } // 编码函数 void encode(Node* root, char encoded[], int index, char data) { if(root == NULL || root->data == data) return; // 如果到达叶子节点或者遇到当前数据 if(root->data < data) { // 左分支对应0 encode(root->left, encoded, index, data); } else { // 右分支对应1 encode(root->right, encoded, index, data); } encoded[index++] = '0'; // 添加前缀到编码结果 } // 计算压缩后的文件大小 int calculateCompressedSize(char* input, int length) { Node* root = huffmanTree(input, length); int encodedLength = 0; // 对输入数据进行编码 for(int i=0; i<length; i++) { encode(root, encodedLength, input[i]); } // 输出编码后的数据 printf("Encoded data: "); for(int i=0; i<encodedLength; i++) { printf("%d", encoded[i]); } free(root); // 释放Huffman树内存 return encodedLength; // 返回压缩后的字节数 } int main() { char input[] = "Hello, World!"; int length = strlen(input); int compressedSize = calculateCompressedSize(input, length); int originalSize = strlen(input); // 原始文件大小 float compressionRatio = (float)compressedSize / originalSize; printf("\nCompression Ratio: %.2f\n", compressionRatio); printf("Testing Compression:\n"); FILE* in_file = fopen("input.txt", "r"); FILE* out_file = fopen("output.txt", "w+b"); fseek(in_file, 0, SEEK_END); int fileSize = ftell(in_file); rewind(in_file); fwrite(input, 1, fileSize, out_file); // 压缩原文件 fclose(out_file); fseek(in_file, 0, SEEK_SET); fseek(out_file, 0, SEEK_SET); char* decompressedData = malloc(fileSize); fread(decompressedData, 1, fileSize, out_file); fclose(out_file); // 这里可以添加对解压后的数据进行比较和测试的部分 // ... free(decompressedData); fclose(in_file); return 0; } ``` 在这个程序中，我们首先创建了一个Huffman树，然后根据这个树对输入文件进行编码。然后计算原始文件和压缩文件的大小，得到压缩比。最后，通过读取原文件并解码输出内容，进行简单的测试。 请注意，在实际应用中，你需要处理解码部分以及对解压后的数据进行完整的测试。此外，这里假设输入文件较小可以直接全部加载到内存，对于大文件，应采用其他方法进行处理。