Hoffmans algorithm in C
Implement Huffmans algorithm in C Language.
Hoffmans algorithm in C Language Code
|
1 2 |
<br/>/*Hoffmans algorithm in C Language*/<br/> #include <br/> #include <br/> #include <br/> #define MAX 26 <br/> typedef struct str <br/> { <br/> int freq; <br/> char alpha; <br/> }str; <br/> typedef struct huff <br/> { <br/> struct str info; <br/> struct huff *lc,*rc; <br/> }huff; <br/> typedef struct sll <br/> { <br/> int flag; <br/> union data <br/> { <br/> struct huff * addr; <br/> struct str info; <br/> }data; <br/> struct sll *link; <br/> }sll; <br/> sll *insert(sll *,huff*,sll *); <br/> void insertsort(str *,int ); <br/> sll * createsll(str *); <br/> sll * input(str*); <br/> huff * huffman(sll *,huff *); <br/> void itpost(huff *); <br/> huff *freepa(huff *); <br/> void leveldis(huff *f); <br/> void prefix(huff *,int [],int ); <br/> void main() <br/> { <br/> int ch,a[25],i; <br/> str *s; <br/> sll *f=NULL; <br/> huff *pa=NULL; <br/> s=(str *)calloc(1,26*sizeof(str)); <br/> do <br/> { <br/> clrscr(); <br/> printf("\n\t\tHUFFMAN TREE CREATION\n\t\t1.INPUT\n\t\t2.HUFFMAN TREE\n\t\t3.DISPLAY\n\t\t4.PREFIX CODE\n\t\t5.LEVEL VISE DISPLAY\n\t\t6.EXIT"); <br/> printf("\n\t\tENTER UR CHOICE"); <br/> scanf("%d",&ch); <br/> switch(ch) <br/> { <br/> case 1: <br/> printf("INPUT"); <br/> f=input(s); <br/> break; <br/> case 2: <br/> if(pa!=NULL) <br/> pa=freepa(pa); <br/> printf("HUFFMAN TREE"); <br/> pa=huffman(f,pa); <br/> printf("HUFFMAN TREE IS CREATED"); <br/> break; <br/> case 3: <br/> if(pa==NULL) <br/> printf("MAKE HUFFMAN TREE FIRST"); <br/> else <br/> { <br/> printf("DISPLAY"); <br/> itpost(pa); <br/> } <br/> break; <br/> case 4: <br/> if(pa==NULL) <br/> printf("MAKE HUFFMAN TREE FIRST"); <br/> else <br/> { <br/> printf("PREFIX CODE"); <br/> i=-1; <br/> prefix(pa,a,i); <br/> getch(); <br/> } <br/> break; <br/> case 5: <br/> if(pa==NULL) <br/> printf("MAKE HUFFMAN TREE FIRST"); <br/> else <br/> { <br/> printf("LEVEL VISE DISPLAY"); <br/> leveldis(pa); <br/> } <br/> break; <br/> } <br/> getch(); <br/> }while(ch!=6); <br/> } <br/> sll* input(str *s) <br/> { <br/> sll *f=NULL; <br/> char st[100]; <br/> int k=0,j,i; <br/> for(i=0;i<max;i++) <br=""> (s+i)->freq=0; <br/> flushall(); <br/> gets(st); <br/> for(i=0;st[i]!=NULL;i++) <br/> { <br/> if((64<st[i]&&st[i]<91)||(96<st[i]&&st[i]<123)) <br=""> { <br/> for(j=0;j<k;j++) <br=""> { <br/> if(st[i]==(s+j)->alpha) <br/> break; <br/> } <br/> if(j==k||i==0) <br/> { <br/> (s+k)->alpha=st[i]; <br/> (s+k)->freq++; <br/> k++; <br/> } <br/> else <br/> { <br/> (s+j)->freq++; <br/> } <br/> } <br/> } <br/> insertsort(s,k); <br/> f=createsll(s); <br/> return f; <br/> } <br/> sll * createsll(str *s) <br/> { <br/> sll *nw,*t,*f=NULL; <br/> int i; <br/> for(i=0;(s+i)->freq!=0;i++) <br/> { <br/> nw=(sll *)malloc(sizeof(sll)); <br/> nw->flag=0; <br/> nw->link=NULL; <br/> nw->data.info.freq=(s+i)->freq; <br/> nw->data.info.alpha=(s+i)->alpha; <br/> nw->link=NULL; <br/> if(f==NULL) <br/> f=nw; <br/> else <br/> { <br/> t=f; <br/> while(t->link!=NULL) <br/> t=t->link; <br/> t->link=nw; <br/> } <br/> } <br/> return f; <br/> } <br/> void insertsort(str *a,int n) <br/> { <br/> int i,j; <br/> str temp; <br/> for(i=1;i<n;i++) <br=""> { <br/> temp.freq=(a+i)->freq; <br/> temp.alpha=(a+i)->alpha; <br/> for(j=i-1;j>=0&&(a+j)->freq>temp.freq;j--) <br/> { <br/> (a+j+1)->freq=(a+j)->freq; <br/> (a+j+1)->alpha=(a+j)->alpha; <br/> } <br/> (a+j+1)->freq=temp.freq; <br/> (a+j+1)->alpha=temp.alpha; <br/> } <br/> } <br/> huff * huffman(sll *f,huff *pa) <br/> { <br/> huff *q=NULL,*nw,*lch,*rch,*p; <br/> sll *t,*s; <br/> while(f!=NULL) <br/> { <br/> if(f->flag==0) <br/> { <br/> nw=(huff *)malloc(sizeof(huff)); <br/> nw->info=f->data.info; <br/> nw->lc=nw->rc=NULL; <br/> lch=nw; <br/> } <br/> else <br/> lch=f->data.addr; <br/> t=f; <br/> f=f->link; <br/> free(t); <br/> if(f!=NULL) <br/> { <br/> if(f->flag==0) <br/> { <br/> nw=(huff *)malloc(sizeof(huff)); <br/> nw->info=f->data.info; <br/> nw->lc=nw->rc=NULL; <br/> rch=nw; <br/> } <br/> else <br/> rch=f->data.addr; <br/> t=f; <br/> f=f->link; <br/> nw=(huff *)malloc(sizeof(huff)); <br/> nw->info.freq=lch->info.freq+rch->info.freq; <br/> nw->lc=lch; <br/> nw->rc=rch; <br/> p=nw; <br/> p->info.alpha='\0'; <br/> t->flag=1; <br/> t->data.addr=p; <br/> t->link=NULL; <br/> f=insert(f,p,t); <br/> } <br/> else <br/> p=lch; <br/> } <br/> q=p; <br/> free(t); <br/> return(q); <br/> } <br/> sll *insert(sll *f,huff*p,sll *t) <br/> { <br/> sll *s; <br/> s=f; <br/> if(f!=NULL) <br/> { <br/> if(((p->info.freqdata.info.freq)&&f->flag==0)||((p->info.freqdata.addr->info.freq)&&f->flag==1)) <br/> { <br/> t->link=f; <br/> f=t; <br/> } <br/> else <br/> { <br/> while(s->link!=NULL) <br/> { <br/> if(s->link->data.info.freq>t->data.addr->info.freq&&s->link->flag==0) <br/> { <br/> t->link=s->link; <br/> break; <br/> } <br/> else if(s->link->data.addr->info.freq>t->data.addr->info.freq&&s->link->flag==1) <br/> { <br/> t->link=s->link; <br/> break; <br/> } <br/> s=s->link; <br/> } <br/> } <br/> } <br/> s->link=t; <br/> if(s->link==NULL) <br/> t->link=NULL; <br/> return f; <br/> } <br/> /*void itpost(huff *root) <br/> { <br/> huff *t; <br/> stack *top,*nw; <br/> top=NULL; <br/> t=root; <br/> while(t!=NULL||top!=NULL) <br/> { <br/> if(t!=NULL) <br/> { <br/> nw=(stack*)malloc(sizeof(stack)); <br/> nw->ad=t; <br/> nw->next=top; <br/> nw->flag=0; <br/> top=nw; <br/> t=t->lc; <br/> } <br/> else <br/> { <br/> t=top->ad; <br/> if(top->flag==0) <br/> { <br/> top->flag=1; <br/> t=t->rc; <br/> } <br/> else <br/> { <br/> if(t->lc==NULL&&t->rc==NULL) <br/> printf("%c",t->info.alpha); <br/> else <br/> printf("%d",t->info.freq); <br/> nw=top; <br/> top=top->next; <br/> free(nw); <br/> t=NULL; <br/> } <br/> } <br/> } <br/> getch(); <br/> } */ <br/> huff *freepa(huff *t) <br/> { <br/> huff *q,*n; <br/> if(t!=NULL) <br/> { <br/> q=t->lc; <br/> n=t->rc; <br/> if(q->lc==NULL&&q->rc==NULL) <br/> q=freepa(q); <br/> if(n->lc==NULL&&n->rc==NULL) <br/> n=freepa(n); <br/> } <br/> return q; <br/> } <br/> void leveldis(huff *f) <br/> { <br/> huff *queue[MAX],*t; <br/> int front=-1,rear=-1,i=-1,pl=0,cl=1; <br/> t=f; <br/> if(front==-1) <br/> front++; <br/> rear=(rear+1)%MAX; <br/> queue[rear]=t; <br/> while(cl!=0||pl!=0) <br/> { <br/> if(pl==0) <br/> { <br/> i++; <br/> printf("\nELEMENT IN %d LEVEL:",i); <br/> pl=cl; <br/> cl=0; <br/> } <br/> t=queue[front]; <br/> if(front==rear) <br/> front=rear=-1; <br/> else <br/> front=(front+1)%MAX; <br/> if(t->info.alpha!='\0') <br/> printf("\t%c",t->info.alpha); <br/> else <br/> printf("\t%d",t->info.freq); <br/> if(t->lc!=NULL) <br/> { <br/> if(front==-1) <br/> front++; <br/> rear=(rear+1)%MAX; <br/> queue[rear]=t->lc; <br/> cl++; <br/> } <br/> if(t->rc!=NULL) <br/> { <br/> if(front==-1) <br/> front++; <br/> rear=(rear+1)%MAX; <br/> queue[rear]=t->rc; <br/> cl++; <br/> } <br/> pl--; <br/> } <br/> getch(); <br/> } <br/> void prefix(huff *f,int a[],int i) <br/> { <br/> huff *t; <br/> int m; <br/> t=f; <br/> i++; <br/> if(t!=NULL) <br/> { <br/> if(t->lc==NULL&&t->rc==NULL) <br/> { <br/> printf("\nPREFIX OF %c:",t->info.alpha); <br/> for(m=0;m<i;m++) <br=""> printf("\t%d",a[m]) ; <br/> printf("\tFREQUENCY:%d",t->info.freq); <br/> } <br/> if(t->lc!=NULL) <br/> { <br/> a[i]=0; <br/> prefix(t->lc,a,i); <br/> } <br/> if(t->rc!=NULL) <br/> { <br/> a[i]=1; <br/> prefix(t->rc,a,i); <br/> } <br/> } <br/> } |
Source projectgeek.com
