Program to Implement Huffman Encoding in C Assignment Solutions
July 02, 2024
Sarah Williams
🇨🇦 Canada
C
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.
Key Topics
- Instructions
- Requirements and Specifications
Tip of the day
News
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.
C
Word Count
24995 Words
Writer Name:Philip Dudley
Total Orders:2435
Satisfaction rate:
C
Word Count
4788 Words
Writer Name:James Trafford
Total Orders:567
Satisfaction rate:
C
Word Count
4564 Words
Writer Name:John Smith
Total Orders:590
Satisfaction rate:
C
Word Count
7928 Words
Writer Name:John Smith
Total Orders:590
Satisfaction rate:
C
Word Count
4428 Words
Writer Name:Emma Clarke
Total Orders:700
Satisfaction rate:
C
Word Count
4264 Words
Writer Name:Dr. Miriam Goldbridge
Total Orders:812
Satisfaction rate:
C
Word Count
6407 Words
Writer Name:Dr. Miriam Goldbridge
Total Orders:812
Satisfaction rate:
C
Word Count
7276 Words
Writer Name:Prof. Benjamin Mitchell
Total Orders:582
Satisfaction rate:
C
Word Count
5057 Words
Writer Name:Dr. Sophia Reynolds
Total Orders:458
Satisfaction rate:
C
Word Count
4612 Words
Writer Name:Dr. Jonathan Wright
Total Orders:812
Satisfaction rate:
C
Word Count
4457 Words
Writer Name:Dr. Nathan Nguyen
Total Orders:526
Satisfaction rate:
C
Word Count
3950 Words
Writer Name:Mark Davis
Total Orders:429
Satisfaction rate:
C
Word Count
3990 Words
Writer Name:Prof. Elizabeth Taylor
Total Orders:745
Satisfaction rate:
C
Word Count
3319 Words
Writer Name:Mark Davis
Total Orders:429
Satisfaction rate:
C
Word Count
3127 Words
Writer Name:Emma Clarke
Total Orders:700
Satisfaction rate:
C
Word Count
6063 Words
Writer Name:Dr. Jonathan Wright
Total Orders:812
Satisfaction rate:
C
Word Count
4724 Words
Writer Name:Dr. Jonathan Wright
Total Orders:812
Satisfaction rate:
C
Word Count
3095 Words
Writer Name:Dr. Deborah R. Craft
Total Orders:700
Satisfaction rate:
C
Word Count
5089 Words
Writer Name:Dr. Sophia Reynolds
Total Orders:458
Satisfaction rate:
C
Word Count
5780 Words
Writer Name:Emily Johnson
Total Orders:412
Satisfaction rate: