Satellite Huffman Coding Project

Author

POPOVICI Andrei-Razvan

Overview

This project implements a Huffman coding system for a set of satellite nodes. It reads node frequencies from a file, constructs a Huffman tree, and performs various tasks such as:

1. Printing the tree in BFS order.
2. Decoding satellite paths from binary codes.
3. Finding Huffman codes for specific satellites.
4. Finding the lowest common ancestor of multiple satellites in the Huffman tree.

Files

• satelite.c – Main C program implementing the Huffman tree, BFS, encoding, decoding, and ancestor search functionalities.
• Input files – Contain satellite names, frequencies, and/or codes for specific tasks.
• Output files – Generated by the program based on the task.
• Makefile - Used to compile the program

Compilation

Run makefile build rule:

$ make

OR use gcc to compile the program:

$ gcc satelite.c -o satelite

Usage

The program requires three command-line arguments:

$ ./satelite -c[n] input_file output_file

-c[n]– Task code, where [n] is the task number (1, 2, 3, or 4):

• -c1 – Print the Huffman tree in BFS order.

• -c2 – Decode satellite paths from binary codes.

• -c3 – Find the Huffman code for a specific satellite.

• -c4 – Find the common parent node (lowest common ancestor) of given satellites.

input_file – File containing the necessary input for the selected task.

output_file – File where the program writes the results.

Example

$ ./satelite -c1 test.in test.out

Input Format

Initialisation:

• First line: number of satellite nodes N.

• Next N lines: Frequency Name (e.g.,10 SAT1).

After the node definitions, additional lines contain either:

Decode Satellite Paths:

• Number of binary codifications to be decoded.
• Binary codes for decoding (one binary codification may represent more than one satellite).

Find Huffman Codes:

• Number of satellites to find codes for.
• Names of satellites to find codes for.

Find Lowest Common Ancestor:

Names of satellites for which to find the common parent (findLowestCommonAncestor).

Some examples for each case are found in the input directory.

Output

Huffman Tree BFS: BFS traversal of the Huffman tree with frequency and name (Frequency-Name).

Decode Satellite Paths: Satellite names decoded from binary codes.

Find Huffman Codes: Huffman code strings for given satellite names.

Lowest Common Ancestor: Name of the lowest common ancestor of the specified satellites.

Memory Management

All dynamically allocated memory for the Huffman tree, queues, and node names is freed before the program terminates.