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....
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; | |
| } |