C语言实现哈夫曼编码算法：从节点创建到代码生成全解析

Certainly! Let's continue with the implementation of the Huffman coding algorithm in C. We'll complete the `createhuffmannode` function and then proceed to implement the necessary functions for creating and managing the minimum heap, building the Huffman tree, and generating the Huffman codes. Step 1: Completing `createhuffmannode` Function ```c huffmannode* createhuffmannode(char character, int frequency) { huffmannode* node = (huffmannode*)malloc(sizeof(huffmannode)); if (node == NULL) { fprintf(stderr, "Memory allocation failed\n"); exit(EXIT_FAILURE); } node->character = character; node->frequency = frequency; node->left = NULL; node->right = NULL; return node; } ``` Step 2: Creating and Managing the Minimum Heap We need functions to create the heap, insert nodes into the heap, and extract the minimum node from the heap. ```c minheap* create_minheap(int capacity) { minheap* heap = (minheap*)malloc(sizeof(minheap)); if (heap == NULL) { fprintf(stderr, "Memory allocation failed\n"); exit(EXIT_FAILURE); } heap->size = 0; heap->capacity = capacity; heap->array = (huffmannode)malloc(capacity * sizeof(huffmannode*)); if (heap->array == NULL) { fprintf(stderr, "Memory allocation failed\n"); free(heap); exit(EXIT_FAILURE); } return heap; } void swap_huffmannodes(huffmannode a, huffmannode b) { huffmannode* temp = *a; *a = *b; *b = temp; } void min_heapify(minheap* heap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left < heap->size && heap->array[left]->frequency < heap->array[smallest]->frequency) smallest = left; if (right < heap->size && heap->array[right]->frequency < heap->array[smallest]->frequency) smallest = right; if (smallest != idx) { swap_huffmannodes(&heap->array[smallest], &heap->array[idx]); min_heapify(heap, smallest); } } void insert_minheap(minheap* heap, huffmannode* node) { if (heap->size == heap->capacity) { fprintf(stderr, "Heap is full\n"); exit(EXIT_FAILURE); } heap->size++; int i = heap->size - 1; heap->array[i] = node; while (i != 0 && heap->array[(i - 1) / 2]->frequency > heap->array[i]->frequency) { swap_huffmannodes(&heap->array[i], &heap->array[(i - 1) / 2]); i = (i - 1) / 2; } } huffmannode* extract_min(minheap* heap) { if (heap->size <= 0) return NULL; if (heap->size == 1) { heap->size--; return heap->array[0]; } huffmannode* root = heap->array[0]; heap->array[0] = heap->array[heap->size - 1]; heap->size--; min_heapify(heap, 0); return root; } ``` Step 3: Building the Huffman Tree We need a function to build the Huffman tree using the minimum heap. ```c huffmannode* build_huffman_tree(minheap* heap) { while (heap->size != 1) { huffmannode* left = extract_min(heap); huffmannode* right = extract_min(heap); huffmannode* internal_node = createhuffmannode('\0', left->frequency + right->frequency); internal_node->left = left; internal_node->right = right; insert_minheap(heap, internal_node); } return extract_min(heap); } ``` Step 4: Generating Huffman Codes We need a function to generate the Huffman codes from the Huffman tree. ```c void print_huffman_codes(huffmannode* root, int top, char* arr) { if (root->left) { arr[top] = '0'; print_huffman_codes(root->left, top + 1, arr); } if (root->right) { arr[top] = '1'; print_huffman_codes(root->right, top + 1, arr); } if (is_leaf(root)) { arr[top] = '\0'; printf("Character: %c, Code: %s\n", root->character, arr); } } int is_leaf(huffmannode* node) { return !(node->left) && !(node->right); } ``` Step 5: Main Function Finally, we need a main function to tie everything together. ```c int main() { char data[] = "example text for huffman coding"; int frequency[max_tree_nodes] = {0}; for (int i = 0; data[i]; ++i) { frequency[(unsigned char)data[i]]++; } minheap* heap = create_minheap(max_tree_nodes); for (int i = 0; i < max_tree_nodes; ++i) { if (frequency[i] > 0) { huffmannode* node = createhuffmannode((char)i, frequency[i]); insert_minheap(heap, node); } } huffmannode* root = build_huffman_tree(heap); char arr[max_code_length]; print_huffman_codes(root, 0, arr); // Free memory for (int i = 0; i < heap->size; ++i) { free(heap->array[i]); } free(heap->array); free(heap); return 0; } ``` This completes the implementation of the Huffman coding algorithm in C. The program reads a string, calculates the frequency of each character, builds a Huffman tree, and prints the Huffman codes for each character. ######[AI写代码神器 | 1367点数解答 | 2024-11-10 17:20:01]