Dynamic Huffman Coding

 

Implementation of dynamic Huffman coding.

 More programs at http://www.harishnair.we.bs

Source Code:

#include<stdio.h>

#include<conio.h>

#include<malloc.h>

 

struct doubly //Declaring Doubly Linked List

{

int val1,val2,val3;

struct doubly *prev,*next;

}*start,*node,*temp,*temp2,*temp30,*temp31;

 

struct slink //Declaring Singly Linked List

{

int val;

struct slink *next1;

}*start1,*node1,*temp1;

 

int flag=0;

void create() //Creating Doubly Linked List

{

start=(struct doubly *)malloc(sizeof(struct doubly));

start->next=NULL;

start->prev=NULL;

temp=start;

printf("\nHuffmann Encoding!!\n");

}

 

void create1() //Creating Singly Linked List

{

start1=(struct slink *)malloc(sizeof(struct slink));

start1->next1=NULL;

temp1=start1;

}

void insert1() //Inserting Elements Into The Singly Linked List

{

node1=(struct slink *)malloc(sizeof(struct slink));

node1->val=flag;

node1->next1=start1->next1;

start1->next1=node1;

}

void insert(int n1,int n2,int n3) //Inserting Elements Into The Doubly Linked List

{

node=(struct doubly *)malloc(sizeof(struct doubly));

node->val1=n1;

node->val2=n2;

node->val3=n3;

if(start->next==NULL)

{

node->prev=start;

node->next=NULL;

start->next=node;

}

else

{

node->next=start->next;

start->next->prev=node;

node->prev=start;

start->next=node;

}

}

int n,b[30];

float a[30],z[30];

void reorder() //Function To Arrange The Probabilities In Decreasing Order

{

int i,j,temp5;

float temp6;

for(i=0;i<n;i++)

{

for(j=0;j<n-1;j++)

{

if(a[j+1]>a[j])

{

temp6=a[j];

a[j]=a[j+1];

a[j+1]=temp6;

temp5=b[j];

b[j]=b[j+1];

b[j+1]=temp5;

}

else if(a[j+1]==a[j])

{

if(b[j+1]>b[j]&&b[j+1]>=n)

{

temp6=a[j];

a[j]=a[j+1];

a[j+1]=temp6;

temp5=b[j];

b[j]=b[j+1];

b[j+1]=temp5;

 

}

}

}

}

}

 

void traverse(int var,int valu,struct doubly *temp2) //Traversing And Printing The Huffman Tree

{

create1();

insert1();

while(temp2->prev!=start)

{

if(temp2->prev->val1==var)

{

flag=1;

insert1();

var=temp2->prev->val3;

}

else if(temp2->prev->val2==var)

{

flag=0;

insert1();

var=temp2->prev->val3;

}

temp2=temp2->prev;

}

printf("\nS%d=",valu);

for(temp1=start1;temp1->next1!=NULL;temp1=temp1->next1)

printf("%d",temp1->next1->val);

}

 

int main()

{

int i,t,x,var1=0,var2=0,valu1=0,valu2=0;

float sum=0.0,x1=0.0,y1=0.0,check=0.0;

create();

printf("Enter The Limit\n");

scanf("%d",&n);

printf("Enter the values:\n");

for(i=0;i<n;i++)

{

printf("\nNumber%d",i+1);

printf("\nNumerator:");

scanf("%f",&x1);

printf("Denominator:");

scanf("%f",&y1);

a[i]=x1/y1;

b[i]=i;

check+=a[i];

}

 

if(check>1)

printf("\nInputting Error!!\nSum Of Probabilities Not Equal To 1\n");

else

{

clrscr;

printf("\nSYMBOL\tPROBABILITY\n");

for(i=0;i<n;i++)

printf("S%d\t%f\n",b[i],a[i]);

printf("\nHuffmann Encoding For Symbols:");

reorder();

t=n;

x=t=n;

for(i=0;i<n-1;i++)

{

insert(b[t-2],b[t-1],x); //Creating The Huffmann Tree

sum=a[t-1]+a[t-2];

a[t-1]=0;

a[t-2]=sum;

b[t-2]=x;

reorder();

x++;

t--;

}

for(temp=start->next;temp!=NULL;temp=temp->next)//Traversing Huffmann Tree

{

var1=temp->val3;

var2=temp->val3;

valu1=temp->val1;

valu2=temp->val2;

if(valu1<n)

{

flag=1;

traverse(var1,valu1,temp);

}

if(valu2<n)

{

flag=0;

traverse(var2,valu2,temp);

}

}

}

return 0;

}

 

Output:

Huffman Encoding!!

Enter The Limit

6

 

Number1

Numerator: 1

Denominator: 3

 

Number2

Numerator: 1

Denominator: 4

 

Number3

Numerator: 1

Denominator: 8

 

Number4

Numerator: 1

Denominator: 8

 

Number5

Numerator: 1

Denominator: 12

 

Number6

Numerator: 1

Denominator: 12

 

Symbol Probability

S0 0.333333

S1 0.250000

S2 0.125000

S3 0.125000

S4 0.083333

S5 0.083333

 

Huffman Encoding For Symbols:

S0=11

S1=01

S2=101

S3=100

S4=001

S5=000