Huffman Coding in C

#include 

typedef struct qnode qnode;
typedef tree qtype;
typedef struct 
{
    qnode *front;
    qnode *rear;
} queue;

struct qnode 
{
    qtype op;
    qnode *next;
};

bool qEmpty( queue *q ) 
{
    return (q->front == NULL);
}

void qPushBack( queue *q, qtype op ) 
{
    /*
     * pushes op at q.rear.
     */
    qnode *ptr = (qnode *)malloc( sizeof(qnode) );
    ptr->op = op;
    ptr->next = NULL;
    if( qEmpty(q) )    // first element in q.
        q->front = ptr;
    else
        q->rear->next = ptr;
    q->rear = ptr;
}

void qInsertSorted(queue *q, qtype op) 
{
   /*
    * inserts val in sorted q and keeps new q sorted.
    */
   qnode *ptr = (qnode *)malloc(sizeof(qnode));
   qnode *curr, *prev;
   ptr->op = op;

   for(prev=NULL, curr=q->front; curr && curr->op->w < op->w; prev=curr, curr=curr->next)
       ;
   if(!curr && !prev)    // q empty.
       ptr->next = NULL, q->rear = q->front = ptr;
   else if(!curr)       // op is the max value.
       ptr->next = NULL, prev->next = q->rear = ptr;
   else if(!prev)       // op is the min value.
       ptr->next = curr, q->front = ptr;
   else { // if prev and ptr both exist.
      ptr->next = curr;
      prev->next = ptr;
   }
}

qtype qPopFront( queue *q ) {
    /*
     * pops op from q->front.
     */
    qnode *ptr = q->front;
    qtype op;

    if( qEmpty(q) )
        return (qtype)NULL;
    q->front = q->front->next;
    if( qEmpty(q) ) q->rear = NULL;

    op = ptr->op;
    free(ptr);
    return op;
}

/********************* huffman.c *************************/
#include 

#define MAXLEN 80

typedef struct node node;
typedef char type;
typedef node *tree;
typedef enum {FALSE, TRUE} bool;

struct node {
    int w;
    type val;
    node *left, *right;
};

#include "huffman.q.h"

int compare(const void *e1, const void *e2) {
    /*
     * compare the two elements in e1 and e2.
     * each element is a vector of two elements.
     */
     return ((int *)e1)[1] > ((int *)e2)[1];
}

void printTree(tree t, char *outputstr) {
    /*
     * print the huffman codes for each element of t.
     * outputstr contains huffman code for t (NOT parent of t).
     * assumes t!=NULL.
     */
   char str[2] = "1";

   if(t->right) {
      strcat(outputstr, str);
      printTree(t->right, outputstr);
      outputstr[strlen(outputstr)-1] = 0; // restore.
   }
    if(t->left) {
       str[0] = '0';
       strcat(outputstr, str);
       printTree(t->left, outputstr);
       outputstr[strlen(outputstr)-1] = 0; // restore.
    }
    else if(!t->right)
       printf("%c=%d=%s.\n", t->val, t->w, outputstr);
}

tree buildTree(int a[][2], int n) {
    /*
     * build a huffman tree using frequency in a[i][1] where a[0][j] indicates
     * the character
     * for that sort a on frequency.
     * n is the size of a.
     */
    int i;
    tree t = NULL;
    queue sortedq = {NULL};

    // sort a on frequency.
    qsort(a, n, sizeof(a[0]), compare);

    // insert each element in tree.
    for(i=0; iw = a[i][1];
       temp->val = (type)a[i][0];
       qPushBack(&sortedq, temp);
    }
    // assume n>0.
    while(TRUE) {
       tree t2 = NULL,
               t1 = qPopFront(&sortedq);
       if(!qEmpty(&sortedq))
              t2 = qPopFront(&sortedq);
       else {
             t = t1;
             break;
       }

          t = (tree)malloc(sizeof(node));
          t->w = t1->w + t2->w;
          t->left = t1;
          t->right = t2;
           {
                   qnode *ptr;
                   for(ptr=sortedq.front; ptr; ptr=ptr->next)
                          printf("%d ", ptr->op->w);
                   printf("\n");
          }
          printf("insertsorted=%d.\n", t->w);
          qInsertSorted(&sortedq, t);
     }
     return t;
}

int main() {
    int a[][2] = { {'a', 20},
                          {'b', 23},
                          {'c', 14},
                          {'d', 56},
                          {'e', 35},
                          {'f', 29},
                          {'g', 5 }
                   };
   char outputstr[MAXLEN] = "";
   tree t = buildTree(a, sizeof(a)/2/sizeof(int));

   if(t)
      printTree(t, outputstr);

   return 0;
}

Related Links :