Huffman Encoding in DSA C - Build from Scratch

Huffman Encoding

📖 Scenario: You work for a company that compresses text files to save storage space. Huffman encoding is a method to compress data by assigning shorter codes to frequent characters and longer codes to rare characters.In this project, you will build a simple Huffman encoding setup in C. You will start by creating a frequency table for characters, then build the Huffman tree structure, and finally print the Huffman codes for each character.

🎯 Goal: Build a program that creates a frequency table for characters, builds a Huffman tree, and prints the Huffman codes for each character.

📋 What You'll Learn

Create a frequency table for given characters

Define a struct for Huffman tree nodes

Build a simple Huffman tree using the frequency table

Print the Huffman codes for each character

💡 Why This Matters

🌍 Real World

Huffman encoding is used in file compression tools like ZIP and image formats like JPEG to reduce file size.

💼 Career

Understanding Huffman encoding helps in roles related to data compression, storage optimization, and efficient data transmission.

1

Create the frequency table

Create an integer array called freq of size 5 and initialize it with these exact values: 5, 9, 12, 13, 16. These represent the frequencies of characters 'A', 'B', 'C', 'D', and 'E' respectively.

DSA C

# Create the frequency array freq with values 5, 9, 12, 13, 16
// Your code here

Hint

Use int freq[5] = {5, 9, 12, 13, 16}; to create the frequency array.

2

Define the Huffman tree node struct

Define a struct called Node with these exact members: char ch, int freq, struct Node *left, and struct Node *right.

DSA C

#include 

// Define the struct Node with members ch, freq, left, right
// Your code here

int main() {
    int freq[5] = {5, 9, 12, 13, 16};
    return 0;
}

Hint

Use struct Node { char ch; int freq; struct Node *left; struct Node *right; }; to define the node.

3

Create leaf nodes for each character

Create an array called nodes of 5 Node structs. Initialize each node with characters 'A', 'B', 'C', 'D', 'E' and their corresponding frequencies from freq. Set left and right pointers to NULL.

DSA C

#include 

struct Node {
    char ch;
    int freq;
    struct Node *left;
    struct Node *right;
};

int main() {
    int freq[5] = {5, 9, 12, 13, 16};

    // Create nodes array and initialize with characters and frequencies
    // Your code here

    return 0;
}

Hint

Initialize each node with {'A', freq[0], NULL, NULL} style syntax.

4

Print the characters and their frequencies

Use a for loop with variable i from 0 to 4 to print each node's ch and freq in the format: Character: X, Frequency: Y.

DSA C

#include 

struct Node {
    char ch;
    int freq;
    struct Node *left;
    struct Node *right;
};

int main() {
    int freq[5] = {5, 9, 12, 13, 16};

    struct Node nodes[5] = {
        {'A', freq[0], NULL, NULL},
        {'B', freq[1], NULL, NULL},
        {'C', freq[2], NULL, NULL},
        {'D', freq[3], NULL, NULL},
        {'E', freq[4], NULL, NULL}
    };

    // Print characters and frequencies
    // Your code here

    return 0;
}

Hint

Use for (int i = 0; i < 5; i++) and printf("Character: %c, Frequency: %d\n", nodes[i].ch, nodes[i].freq);.