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