Program to Implement Huffman Encoding in C Assignment Solutions

July 02, 2024

Sarah Williams

🇨🇦 Canada

Sarah is a skilled C programmer with a bachelor's degree in computer science and over 600 completed orders. Specializing in data structure implementation, she delivers meticulously crafted solutions that leverage arrays, linked lists, trees, and hash tables for effective mapping operations.

Hire Now

Key Topics

Instructions
Requirements and Specifications

Submit Your C Assignment

Get a FREE Quote

Tip of the day

Break your program into small classes and functions instead of writing everything in main(). Use STL containers like vector and string, and compile with warnings enabled to catch errors early. This keeps your C++ code cleaner and easier to debug.

News

Wilfrid Laurier University unveiled its first-ever Bachelor of Engineering in Software Engineering with concentrations in Biology or Psychology and optional co-op

Instructions

Objective

To complete your C assignment, you are required to write a program that implements Huffman encoding in the C language. Huffman encoding is a widely used technique for data compression, which assigns variable-length codes to characters based on their frequency of occurrence in the input. The program should take input from the user, analyze the frequency of each character, build a Huffman tree, and generate the corresponding Huffman codes. These codes can then be used to compress the input data efficiently.

Requirements and Specifications

Source Code


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SYMBOLS 128
typedef struct treeNode {
 char c;
 int freq;
 struct treeNode* left;
 struct treeNode* right;
} treeNode;
typedef struct heap {
 treeNode* array[SYMBOLS];
 int size;
} heap;
heap* createHeap() {
 heap* h = (heap*)malloc(sizeof(heap));
 h->size = 0;
 return h;
}
treeNode* createNode(char c, int freq, treeNode* l, treeNode* r) {
 treeNode* node = (treeNode*)malloc(sizeof(treeNode));
 node->c = c;
 node->freq = freq;
 node->left = l;
 node->right = r;
 return node;
}
void downSift(heap* h, int i) {
 int child1 = 2*i + 1;
 int child2 = 2*i + 2;
 if (child1 >= h->size) {
  return;
 }
 int nextChild = child1;
 if (child2 < h->size && h->array[child2]->freq < h->array[child1]->freq) {
  nextChild = child2;
 }
 if (h->array[i]->freq > h->array[nextChild]->freq) {
  treeNode* sw = h->array[i];
  h->array[i] = h->array[nextChild];
  h->array[nextChild] = sw;
  downSift(h, nextChild);
 }	
}
void upSift(heap* h, int i) {
 if (i == 0) {
  return;
 }
 int parent = (i-1)/2;
 if (h->array[parent]->freq > h->array[i]->freq) {
  treeNode* sw = h->array[i];
  h->array[i] = h->array[parent];
  h->array[parent] = sw;
  upSift(h, parent);
 }
}
treeNode* removeMin(heap* h) {
 if (h->size == 0) {
  return NULL;
 }
 treeNode* res = h->array[0];
 h->array[0] = h->array[h->size-1];
 h->size--;
 downSift(h, 0);
 return res;
}
void add(heap* h, treeNode* node) {
 h->array[h->size] = node;
 h->size++;
 upSift(h, h->size-1);
}
void freeTree(treeNode* n) {
 if (n == NULL) {
  return;
 }
 freeTree(n->left);
 freeTree(n->right);
 free(n);
}
void buildCodes(treeNode* node, char* curr, int len, char codes[SYMBOLS][SYMBOLS]) {
 if (node->c >= 0) {
  curr[len] = 0;
  strcpy(codes[node->c], curr);
 }
 else {
  curr[len] = '0';
  buildCodes(node->left, curr, len + 1, codes);
  curr[len] = '1';
  buildCodes(node->right, curr, len + 1, codes);
 }
}
int fillFreqs(char* filename, int freqs[SYMBOLS]) {
 int i;
 FILE* f = fopen(filename, "r");
 int total = 0;
 char line[256];
 while (fgets(line, sizeof(line), f)) {
    for(i = 0; i   freqs[line[i]]++;
   total++;
  }
  }
 fclose(f);
 return total;
}
int main(int argc, char** argv) {
 treeNode* treeRoot;
 char codes[SYMBOLS][SYMBOLS];
 int freqs[SYMBOLS];
 int i, total;
 char temp[SYMBOLS];
 heap* h;
 for (i = 0; i  codes[i][0] = 0;
  freqs[i] = 0;
 }
 total = fillFreqs(argv[1], freqs);
 h = createHeap();
 for (i = 0; i  if (freqs[i] > 0) {
   treeNode* n = createNode(i, freqs[i], NULL, NULL);
   add(h, n);
  }
 }
 while(h->size > 1) {
  treeNode* l = removeMin(h);
  treeNode* r = removeMin(h);
  treeNode* next = createNode(-1, l->freq + r->freq, l, r);
  add(h, next);
 }
 treeRoot = removeMin(h);
 free(h);
 buildCodes(treeRoot, temp, 0, codes);
 freeTree(treeRoot);
 printf("| ASCII | Percent | Code\n");
 for (i = 0; i  if(freqs[i] > 0) {
   printf("| %5d | %.5f | %s\n", i, (1.0 * freqs[i])/ total, codes[i]);
  }
 }
  return 0;
}

Related Samples

Discover our C Assignment Samples for expert solutions to programming tasks. Covering essential topics such as pointers, arrays, and file handling, these examples offer clear explanations and step-by-step implementations. Perfect for students looking to strengthen their C programming skills and excel academically with practical, educational resources.

See All Samples

Linux File Descriptor Viewer Tool - C Assignment Solution

Word Count

24995 Words

Writer Name:Philip Dudley

Total Orders:2435

Satisfaction rate:

Exploring Multithreaded Learning: A C Assignment Assistance Simulation

Word Count

4788 Words

Writer Name:James Trafford

Total Orders:567