Thursday, 8 December 2016

Huffman Encoding

Here's a program to find the Huffman codes for the following given data:
1. Character names
2. Frequencies

I can't believe I did this....

#include <stdio.h>
#include <stdlib.h>
//We arrange the elements in a ascending order using a ascending priority queue
//No need to write display, inorder functions they are just for debugging
struct node {
char data;
int priority;
struct node *next, *left, *right;
};
struct node *start = NULL;
int c = 0; // Count
struct node *insert(struct node *start, char d, int pr) {
struct node *nn, *p;
c++;
nn = (struct node *) malloc (sizeof(struct node));
nn -> data = d;
nn -> priority = pr;
nn -> left = nn -> right = NULL;
if(start == NULL || pr <= start -> priority) {
nn -> next = start;
start = nn;
} else {
p = start;
while(p -> next != NULL && p -> next -> priority < pr) {
p = p -> next;
}
// Insert nn in between p and next node
nn -> next = p -> next;
p -> next = nn;
}
return start;
}
struct node *dequeue() {
struct node *temp;
if(start == NULL) {
printf("Queue Underflow\n");
return;
} else {
c--;
temp = start;
start = start -> next;
temp -> next = NULL;
// We dont free temp we return it instead
}
return temp;
}
//No need to study this function
void display(struct node *start) {
struct node *p;
if(start == NULL) {
printf("Empty Queue\n");
} else {
p = start;
while(p != NULL) {
printf("(%c,%d) -> ", p -> data, p -> priority);
p = p -> next;
}
printf("NULL\n");
}
}
void magic() {
struct node *nn, *l, *r, *p;
r = dequeue();
l = dequeue();
// Note that c is decremented by 2 in the above functions
// So we increment c by 1 as we are adding back one node
c++;
nn = (struct node *)malloc(sizeof(struct node));
nn -> data = 'T';
nn -> priority = l -> priority + r -> priority;
nn -> right = r;
nn -> left = l;
// Same logic as insert function above
if(start == NULL || nn -> priority <= start -> priority) {
nn -> next = start;
start = nn;
} else {
p = start;
while(p -> next != NULL && p -> next -> priority < nn -> priority) {
p = p -> next;
}
// Insert nn in between p and next node
nn -> next = p -> next;
p -> next = nn;
}
}
//This function too is just for debugging
void inorder(struct node *root) {
if(root != NULL) {
inorder(root -> left);
printf("(%c, %d) ", root -> data, root -> priority);
inorder(root -> right);
}
}
void PrintCode(struct node *root, int a[], int top) {
int i;
// We traverse the tree and everytime we go left we add 0 to the array and everytime
// we go right we add 1 to the array and we print the array when we get a leaf node
if(root -> left != NULL) {
a[top] = 0;
PrintCode(root -> left, a, top + 1);
}
if(root -> right != NULL) {
a[top] = 1;
PrintCode(root -> right, a, top + 1);
}
if(root -> left == NULL && root -> right == NULL) {
//Leaf Node
printf("%c: ", root -> data);
for(i = 0; i < top; i++) {
printf("%d", a[i]);
}
printf("\n");
}
}
int main() {
int n, i, pr, a[100], top = 0;
char d;
struct node *nn;
printf("Enter number of characters: ");
scanf("%d", &n);
for(i = 0; i < n; i++) {
printf("Character: %d\n", i+1);
printf("Enter name of letter: ");
scanf(" %c", &d);
printf("Enter frequency: ");
scanf("%d", &pr);
start = insert(start, d, pr);
}
display(start);
// Now the priority queue is full with nodes which have only letters in them
// Now we will keep removing two nodes and forming new nodes until
// we have only one node left i.e. c = 1
while(c > 1) {
magic();
printf("The new list:\n");
display(start);
}
printf("Inorder: \n");
inorder(start);
printf("\n");
printf("The codes are:\n")
PrintCode(start, a, top);
return 0;
}