The goal is to implement Huffman coding, which involves:<\/p>\n\n\n\n
Here\u2019s a complete C program to implement Huffman coding:<\/p>\n\n\n
\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\n\/\/ Node structure for the Huffman tree\nstruct Node {\n char character;\n int frequency;\n struct Node *left, *right;\n};\n\n\/\/ Min-Heap structure\nstruct MinHeap {\n int size;\n int capacity;\n struct Node **array;\n};\n\n\/\/ Function to create a new min-heap node\nstruct Node* newNode(char character, int frequency) {\n struct Node* temp = (struct Node*)malloc(sizeof(struct Node));\n temp->left = temp->right = NULL;\n temp->character = character;\n temp->frequency = frequency;\n return temp;\n}\n\n\/\/ Function to create a min-heap\nstruct MinHeap* createMinHeap(int capacity) {\n struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap));\n minHeap->size = 0;\n minHeap->capacity = capacity;\n minHeap->array = (struct Node**)malloc(minHeap->capacity * sizeof(struct Node*));\n return minHeap;\n}\n\n\/\/ Function to swap two nodes\nvoid swapNode(struct Node** a, struct Node** b) {\n struct Node* t = *a;\n *a = *b;\n *b = t;\n}\n\n\/\/ Function to heapify the min-heap\nvoid minHeapify(struct MinHeap* minHeap, int idx) {\n int smallest = idx;\n int left = 2 * idx + 1;\n int right = 2 * idx + 2;\n\n if (left < minHeap->size && minHeap->array[left]->frequency < minHeap->array[smallest]->frequency) {\n smallest = left;\n }\n if (right < minHeap->size && minHeap->array[right]->frequency < minHeap->array[smallest]->frequency) {\n smallest = right;\n }\n if (smallest != idx) {\n swapNode(&minHeap->array[smallest], &minHeap->array[idx]);\n minHeapify(minHeap, smallest);\n }\n}\n\n\/\/ Function to check if size is 1\nint isSizeOne(struct MinHeap* minHeap) {\n return (minHeap->size == 1);\n}\n\n\/\/ Function to extract the minimum node\nstruct Node* extractMin(struct MinHeap* minHeap) {\n struct Node* temp = minHeap->array[0];\n minHeap->array[0] = minHeap->array[minHeap->size - 1];\n --minHeap->size;\n minHeapify(minHeap, 0);\n return temp;\n}\n\n\/\/ Function to insert a new node\nvoid insertMinHeap(struct MinHeap* minHeap, struct Node* node) {\n ++minHeap->size;\n int i = minHeap->size - 1;\n\n while (i && node->frequency < minHeap->array[(i - 1) \/ 2]->frequency) {\n minHeap->array[i] = minHeap->array[(i - 1) \/ 2];\n i = (i - 1) \/ 2;\n }\n minHeap->array[i] = node;\n}\n\n\/\/ Function to build the Huffman tree\nstruct Node* buildHuffmanTree(char characters[], int frequencies[], int size) {\n struct Node *left, *right, *top;\n\n struct MinHeap* minHeap = createMinHeap(size);\n\n for (int i = 0; i < size; ++i) {\n minHeap->array[i] = newNode(characters[i], frequencies[i]);\n }\n minHeap->size = size;\n\n while (!isSizeOne(minHeap)) {\n left = extractMin(minHeap);\n right = extractMin(minHeap);\n\n top = newNode('$', left->frequency + right->frequency);\n top->left = left;\n top->right = right;\n\n insertMinHeap(minHeap, top);\n }\n\n return extractMin(minHeap);\n}\n\n\/\/ Function to print the Huffman codes\nvoid printCodes(struct Node* root, int arr[], int top) {\n if (root->left) {\n arr[top] = 0;\n printCodes(root->left, arr, top + 1);\n }\n if (root->right) {\n arr[top] = 1;\n printCodes(root->right, arr, top + 1);\n }\n if (!root->left && !root->right) {\n printf("%c: ", root->character);\n for (int i = 0; i < top; ++i) {\n printf("%d", arr[i]);\n }\n printf("\\n");\n }\n}\n\n\/\/ Main function\nint main() {\n char characters[] = {'a', 'b', 'c', 'd', 'e', 'f'};\n int frequencies[] = {5, 9, 12, 13, 16, 45};\n int size = sizeof(characters) \/ sizeof(characters[0]);\n\n struct Node* root = buildHuffmanTree(characters, frequencies, size);\n\n int arr[100], top = 0;\n\n printf("Huffman Codes:\\n");\n printCodes(root, arr, top);\n\n return 0;\n}\n\n<\/pre><\/div>\n\n\nExplanation of the Code<\/h3>\n\n\n\n\n- Node Structure<\/strong>:\n
\n- Each node represents a character and its frequency, along with pointers to its left and right children.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Min-Heap Implementation<\/strong>:\n
\n- We create a min-heap to store the nodes. This helps in efficiently extracting the two nodes with the smallest frequencies.<\/li>\n\n\n\n
- Functions are provided for min-heap operations like insertion, extraction, and heapification.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Building the Huffman Tree<\/strong>:\n
\n- We build the tree by repeatedly extracting the two smallest nodes, creating a new internal node with these two as children, and inserting it back into the min-heap.<\/li>\n<\/ul>\n<\/li>\n\n\n\n
- Generating Huffman Codes<\/strong>:\n
\n- We traverse the tree recursively to generate codes. Moving left corresponds to appending a
0<\/code> to the code, while moving right appends a 1<\/code>.<\/li>\n<\/ul>\n<\/li>\n\n\n\n- Main Function<\/strong>:\n
\n- The main function initializes a set of characters and their frequencies, builds the Huffman tree, and prints the generated codes.<\/li>\n<\/ul>\n<\/li>\n<\/ol>\n\n\n\n
Input and Output Example<\/h3>\n\n\n\n
The program uses a predefined set of characters and their frequencies, so there’s no user input in this version. Here’s an example of the output:<\/p>\n\n\n\n
Output<\/h4>\n\n\n\nyamlCopy codeHuffman Codes:\ne: 000\na: 001\nd: 01\nb: 10\nc: 110\nf: 111\n<\/code><\/pre>\n\n\n\nExplanation of the Output<\/h3>\n\n\n\n
In the output, each character is followed by its corresponding Huffman code. The most frequent characters (like ‘f’) get the longest codes, while the least frequent characters (like ‘e’) get shorter codes.<\/p>\n\n\n\n
Conclusion<\/h3>\n\n\n\n
This C program implements Huffman coding efficiently using dynamic data structures like trees and heaps. It provides a clear way to compress data based on character frequencies, making it valuable for various applications in data compression and encoding. You can modify the character set and frequencies to see how the Huffman codes change based on different inputs.<\/p>\n