HUFFMAN CODING

[compgeek]

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define MAX 100
#define N 9
using namespace std;
typedef struct node
{
int info;
struct node *left;
struct node *right;
struct node *father;
}NODE;
typedef struct
{
NODE *item[MAX];
int front;
int rear;
}PQ;
typedef struct
{
int bits[MAX];
int spos;
}CSTRUCT;
int empty(PQ *a)
{
if((a->rear)<(a->front))
return 1;
else
return 0;
}
void fix(PQ *a,NODE *x,int put)
{
if((x->info) >= (a->item[(put-1)])->info)
a->item[put]=x;
else
{
a->item[put]=a->item[(put-1)];
if((put-1)==0)
a->item[(put-1)]=x;
else
fix(a,x,(put-1));
}
}
void insert(PQ *a,NODE *x)
{
int c;
if((a->front==0) && (a->rear==MAX-1))
{
printf("Queue Overflow\n");
exit (1);
}
if((a->rear==MAX-1) && (a->front!=0))
{
while(a->front!=0)
{
c=a->front;
while(c!=a->rear)
{
a->item[(c-1)]=a->item[c];
c++;
}
a->item[(c-1)]=a->item[c];
a->front--;
a->rear--;
}
}
if(empty(a))
{
a->item[++(a->rear)]=x;
}
else
{
if((x->info) > (a->item[a->rear])->info)
a->item[++(a->rear)]=x;
else
fix(a,x,++(a->rear));
}
}
NODE* deleteq(PQ *a)
{
if(empty(a))
{
printf("PQ is empty\n");
exit (1);
}
else
{
return(a->item[(a->front)++]);
}
}
NODE* make(int n)
{
NODE *p;
p=(NODE *)malloc((unsigned)sizeof(NODE));
p->info=n;
p->right=NULL;
p->left=NULL;
p->father=NULL;
return p;
}
void setleft(NODE **a,NODE **b)
{
if((*a)==NULL)
{
printf("VOID INSERTION\n");
exit (1);
}
if((*a)->left!=NULL)
{
printf("INVALID INSERTION\n");
exit (1);
}
else
{
(*a)->left=(*b);
(*b)->father=(*a);
}
}
void setright(NODE **a,NODE **b)
{
if((*a)==NULL)
{
printf("VOID INSERTION\n");
exit (1);
}
if((*a)->right!=NULL)
{
printf("INVALID INSERTION\n");
exit (1);
}
else
{
(*a)->right=(*b);
(*b)->father=(*a);
}
}
int isleft(NODE *a)
{
NODE *p;
p=a->father;
if(p->left == a)
return 1;
else
return 0;
}
void inorder(NODE *a)
{
NODE *p,*q;
q=NULL;
p=a;
do
{
while(p != NULL)
{
q=p;
p=p->left;
}
if(q!=NULL)
{
printf("%d\n",q->info);
p=q->right;
}
while((q != NULL) && (p == NULL))
{
do
{
p=q;
q=p->father;
}while((q != NULL) && (!isleft(p)));
if(q != NULL)
{
printf("%d\n",q->info);
p=q->right;
}
}
}while(q != NULL);
}
void preorder(NODE *a)
{
if(a!=NULL)
{
printf("%d\n",a->info);
preorder(a->left);
preorder(a->right);
}
}
void postorder(NODE *a)
{
if(a!=NULL)
{
postorder(a->left);
postorder(a->right);
printf("%d\n",a->info);
}
}
int main()
{
int i,j;
NODE *p,*p1,*p2,*root;
PQ pq;
//char symbol[]={'A','B','C','D'};
char symbol[]={'A','B','C','D','E','F','G','H','I'};
CSTRUCT code[N];
int frequency[]={15,6,7,12,25,4,6,1,15};
// int frequency[]={3,1,2,1};
NODE *position[N];
pq.front=0;
pq.rear=-1;
for(i=0;i<N;i++)
{
p=make(frequency[i]);
position[i]=p;
insert(&pq,p);
}
while(pq.rear-pq.front > 0)
{
p1=deleteq(&pq);
p2=deleteq(&pq);
p=make((p1->info) + (p2->info));
setleft(&p,&p1);
setright(&p,&p2);
insert(&pq,p);
}
/*tree is now constructed ; use it to find codes*/
root=deleteq(&pq);
for(i=0;i<N;i++)
code[i].spos=0;
for(i=0;i<N;i++)
{
p=position[i];
while(p != root)
{
if(isleft(p))
{

code[i].bits[(code[i].spos)]=0;
code[i].spos++;
}
else
{
code[i].bits[(code[i].spos)]=1;
(code[i].spos)++;
}
p=p->father;
}
}
for(i=0;i<N;i++)
{
printf("\ncode for %c is : ",symbol[i]);
for(j=code[i].spos-1;j>=0;j--)
printf("%d",code[i].bits[j]);
printf("\n");
}
getch();
}