# Huffman Algorithm

Page 1 of 1

## 3 Replies - 21046 Views - Last Post: 21 April 2010 - 09:13 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=169363&amp;s=26f8e27ffabc859ab73227f0da8002fa&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 srikant.siki

Reputation: 0
• Posts: 1
• Joined: 21-April 10

# Huffman Algorithm

Posted 21 April 2010 - 06:18 AM

plz help me.....
i need the c code for Huffman Algorithm
Is This A Good Question/Topic? 0

## Replies To: Huffman Algorithm

### #2 spintronic

Reputation: -32
• Posts: 94
• Joined: 25-December 09

## Re: Huffman Algorithm

Posted 21 April 2010 - 06:34 AM

srikant.siki, on 21 April 2010 - 05:18 AM, said:

plz help me.....
i need the c code for Huffman Algorithm

```#include <stdio.h>

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 <stdio.h>

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

```

### #3 sarmanu

• D.I.C Lover

Reputation: 967
• Posts: 2,362
• Joined: 04-December 09

## Re: Huffman Algorithm

Posted 21 April 2010 - 07:07 AM

Good work for posting the entire code for him, spintronic. Oh, wait a moment, you have actually copy-pasted it from here. Great!

### #4 spintronic

Reputation: -32
• Posts: 94
• Joined: 25-December 09

## Re: Huffman Algorithm

Posted 21 April 2010 - 09:13 AM

sarmanu, on 21 April 2010 - 06:07 AM, said:

Good work for posting the entire code for him, spintronic. Oh, wait a moment, you have actually copy-pasted it from here. Great!

I fail to see your point. (Both of them).