输入一段100—200字的英文短文，存入一文件a中，编写一段C语言代码实现写函数统计短文出现的字母个数n及每个字母的出现次数，写函数以字母出现次数作权值，建Haffman树（n个叶子），给出每个字母的Haffman编码，用每个字母编码对原短文进行编码，码文存入文件b中，用Haffman树对b中码文进行译码，结果存入文件c中，比较a,c是否一致，以检验编码、译码的正确性。

The quick brown fox jumps over the lazy dog. This is a common phrase used to test typewriters and computer keyboards, as it contains every letter of the English alphabet. It is also a popular example of a pangram, a sentence that uses every letter of the alphabet at least once. ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_CHARACTERS 256 typedef struct Node { int freq; char letter; struct Node* left; struct Node* right; } Node; typedef struct MinHeap { int size; Node** array; } MinHeap; Node* create_node(char letter, int freq) { Node* node = (Node*) malloc(sizeof(Node)); node->letter = letter; node->freq = freq; node->left = NULL; node->right = NULL; return node; } MinHeap* create_min_heap(int capacity) { MinHeap* heap = (MinHeap*) malloc(sizeof(MinHeap)); heap->array = (Node**) malloc(capacity * sizeof(Node*)); heap->size = 0; return heap; } void swap_nodes(Node** node1, Node** node2) { Node* temp = *node1; *node1 = *node2; *node2 = temp; } void min_heapify(MinHeap* heap, int index) { int smallest = index; int left_child = 2 * index + 1; int right_child = 2 * index + 2; if (left_child < heap->size && heap->array[left_child]->freq < heap->array[smallest]->freq) { smallest = left_child; } if (right_child < heap->size && heap->array[right_child]->freq < heap->array[smallest]->freq) { smallest = right_child; } if (smallest != index) { swap_nodes(&heap->array[index], &heap->array[smallest]); min_heapify(heap, smallest); } } int is_size_one(MinHeap* heap) { return heap->size == 1; } Node* extract_min(MinHeap* heap) { Node* node = heap->array[0]; heap->array[0] = heap->array[heap->size - 1]; heap->size--; min_heapify(heap, 0); return node; } void insert_node(MinHeap* heap, Node* node) { heap->size++; int index = heap->size - 1; while (index && node->freq < heap->array[(index - 1) / 2]->freq) { heap->array[index] = heap->array[(index - 1) / 2]; index = (index - 1) / 2; } heap->array[index] = node; } void build_min_heap(MinHeap* heap) { int n = heap->size - 1; for (int i = (n - 1) / 2; i >= 0; i--) { min_heapify(heap, i); } } Node* build_huffman_tree(char* text) { int freq[MAX_CHARACTERS] = {0}; for (int i = 0; i < strlen(text); i++) { freq[(int) text[i]]++; } MinHeap* heap = create_min_heap(MAX_CHARACTERS); for (int i = 0; i < MAX_CHARACTERS; i++) { if (freq[i]) { insert_node(heap, create_node((char) i, freq[i])); } } build_min_heap(heap); while (!is_size_one(heap)) { Node* left = extract_min(heap); Node* right = extract_min(heap); Node* parent = create_node('$', left->freq + right->freq); parent->left = left; parent->right = right; insert_node(heap, parent); } return extract_min(heap); } void print_codes(Node* root, int arr[], int top) { if (root->left) { arr[top] = 0; print_codes(root->left, arr, top + 1); } if (root->right) { arr[top] = 1; print_codes(root->right, arr, top + 1); } if (!root->left && !root->right) { printf("%c: ", root->letter); for (int i = 0; i < top; i++) { printf("%d", arr[i]); } printf("\n"); } } void encode_text(Node* root, char* text, char* encoded_text) { int index = 0; for (int i = 0; i < strlen(text); i++) { Node* current = root; while (current->letter != text[i]) { if (current->left && strchr(current->left->letter, text[i])) { current = current->left; encoded_text[index++] = '0'; } else { current = current->right; encoded_text[index++] = '1'; } } } encoded_text[index] = '\0'; } void decode_text(Node* root, char* encoded_text, char* decoded_text) { int index = 0; Node* current = root; for (int i = 0; i < strlen(encoded_text); i++) { if (encoded_text[i] == '0') { current = current->left; } else { current = current->right; } if (!current->left && !current->right) { decoded_text[index++] = current->letter; current = root; } } decoded_text[index] = '\0'; } int main() { char text[201]; printf("Enter a short text (100-200 characters):\n"); fgets(text, sizeof(text), stdin); text[strcspn(text, "\n")] = '\0'; Node* root = build_huffman_tree(text); int codes[MAX_CHARACTERS], top = 0; printf("Huffman Codes:\n"); print_codes(root, codes, top); char encoded_text[1000]; encode_text(root, text, encoded_text); printf("Encoded Text: %s\n", encoded_text); char decoded_text[201]; decode_text(root, encoded_text, decoded_text); printf("Decoded Text: %s\n", decoded_text); if (strcmp(text, decoded_text) == 0) { printf("Encoding and decoding successful!\n"); } else { printf("Encoding and decoding failed!\n"); } return 0; } ``` 首先，我们需要创建一个结构体 `Node` 来表示一个节点。这个结构体包含一个 `freq` 字段表示该节点对应的字符在文本中出现的次数，一个 `letter` 字段表示该节点对应的字符，以及两个指向左右子节点的指针。 ```c typedef struct Node { int freq; char letter; struct Node* left; struct Node* right; } Node; ``` 接下来，我们需要创建一个结构体 `MinHeap` 来表示一个最小堆。这个结构体包含一个 `size` 字段表示堆的大小，以及一个指向节点数组的指针。 ```c typedef struct MinHeap { int size; Node** array; } MinHeap; ``` 我们需要实现一些基本操作来维护这个最小堆，包括创建新节点、交换节点、调整堆、提取最小值、插入节点和构建堆。 ```c Node* create_node(char letter, int freq); void swap_nodes(Node** node1, Node** node2); void min_heapify(MinHeap* heap, int index); int is_size_one(MinHeap* heap); Node* extract_min(MinHeap* heap); void insert_node(MinHeap* heap, Node* node); void build_min_heap(MinHeap* heap); ``` 我们还需要实现一个函数来构建哈夫曼树。 ```c Node* build_huffman_tree(char* text); ``` 在构建哈夫曼树之后，我们需要输出每个字符的哈夫曼编码。 ```c void print_codes(Node* root, int arr[], int top); ``` 接着，我们需要实现一个函数来对文本进行编码。 ```c void encode_text(Node* root, char* text, char* encoded_text); ``` 最后，我们需要实现一个函数来对编码后的文本进行解码。 ```c void decode_text(Node* root, char* encoded_text, char* decoded_text); ``` 现在，我们可以编写主函数来测试这些函数。 ```c int main() { char text[201]; printf("Enter a short text (100-200 characters):\n"); fgets(text, sizeof(text), stdin); text[strcspn(text, "\n")] = '\0'; Node* root = build_huffman_tree(text); int codes[MAX_CHARACTERS], top = 0; printf("Huffman Codes:\n"); print_codes(root, codes, top); char encoded_text[1000]; encode_text(root, text, encoded_text); printf("Encoded Text: %s\n", encoded_text); char decoded_text[201]; decode_text(root, encoded_text, decoded_text); printf("Decoded Text: %s\n", decoded_text); if (strcmp(text, decoded_text) == 0) { printf("Encoding and decoding successful!\n"); } else { printf("Encoding and decoding failed!\n"); } return 0; } ``` 在主函数中，我们首先读入一个字符串，并使用 `build_huffman_tree` 函数构建哈夫曼树。然后，我们使用 `print_codes` 函数输出每个字符的哈夫曼编码。接着，我们使用 `encode_text` 函数对文本进行编码，并输出编码后的文本。最后，我们使用 `decode_text` 函数对编码后的文本进行解码，并输出解码后的文本。如果解码后的文本与原始文本相同，则说明编码和解码都成功了。 下面是完整的代码：