To Implement Huffman Encoding in C Assignment Solutions.

Instructions

Objective
Write a program to implement huffman encoding in C language.
Requirements and Specifications

program implement huffman encoding in C language
program implement huffman encoding in C language 1
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<strlen(line); 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<SYMBOLS; i++) {
  codes[i][0] = 0;
  freqs[i] = 0;
 }
 total = fillFreqs(argv[1], freqs);
 h = createHeap();
 for (i = 0; i<SYMBOLS; 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<SYMBOLS; i++) {
  if(freqs[i] > 0) {
   printf("| %5d | %.5f | %s\n", i, (1.0 * freqs[i])/ total, codes[i]);
  }
 }
  return 0;
}
Program to Implement Huffman Encoding in C Assignment Solutions.

Instructions

Requirements and Specifications
