Google Ads

Thursday, December 3, 2009

WARSHALL’S ALGORITHM

WARSHALL’S ALGORITHM


SOURCE CODE:


#include “ stdio.h “
#include “ conio.h “
void main()
{
int n,i,j,k,p[10][10],a[10][10];
clrscr();
printf("Enter The Number Of Nodes: ");
scanf("%d",&n);

for(i=0;i < n;i++)
{
printf("\n");
for(j=0;j < n;j++)
{
scanf("%d",&a[i][j]);
}
}
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
if(a[i][j]==0)
p[i][j]=0;
else
p[i][j]=1;
}
}
for(k=0;k < n;k++)
{
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
p[i][j]=p[i][j]||(p[i][k]&&p[k][j]);
}
}
}
printf("\n");
for(i=0;i < n;i++)
{
for(j=0;j < n;j++)
{
printf("%d ",p[i][j]);
}
printf("\n");
}
getch();
}



OUTPUT:


Enter The Number Of Nodes: 4

0
1
0
0

0
0
0
1

0
0
0
0

1
0
1
0

1 1 1 1
1 1 1 1
0 0 0 0

HUFFMAN ALGORTHAM

HUFFMAN ALGORTHAM


CODING:

#include ” stdio.h “
#include “ conio.h “
#define true 1
#define false 0
#define MAXBITS 50
#define MAXSYMBS MAXBITS
#define MAXNODES 2*MAXSYMBS-1
struct codetype
{
int bits[MAXBITS];
int startpos;
};
struct nodetype
{
int frequency;
int parent;
int isleft;
};
void pqinsert(int);
int pqmindelete();
struct nodetype node[MAXNODES];
void main()
{
struct codetype cd,code[MAXSYMBS];
int i;
int no_of_symbols;
int nextavilnode;
int bitcounter;
int leftnode,rightnode;
int root;
int thisnode;
char symbol,alphabet[MAXSYMBS];
clrscr();
for(i=0;i < MAXSYMBS;i++)
{
alphabet[i]=' ';
}
printf("Enter the no-of-symbols:");
scanf("\n%d",&no_of_symbols);
printf("\nEnter the symbol and frequency:");
for(i=0;i < no_of_symbols;i++)
{
scanf("%s%d",&symbol,&node[i].frequency);
pqinsert(i);
alphabet[i]=symbol;
}



for(nextavilnode=no_of_symbols;nextavilnode < 2*no_of_symbols-
1;nextavilnode++)
{
leftnode=pqmindelete();
rightnode=pqmindelete();
node[leftnode].parent=nextavilnode;
node[rightnode].parent=nextavilnode;
node[leftnode].isleft=true;
node[rightnode].isleft=false;
node[nextavilnode].frequency=node[leftnode].frequency+node[rightnode].
frequency;
pqinsert(nextavilnode);
}
root=pqmindelete();
for(i=0;i < no_of_symbols;i++)
{
cd.startpos=MAXBITS;
thisnode=i;
while(thisnode!=root)
{
--cd.startpos;
cd.bits[cd.startpos]=node[thisnode].isleft?0:1;
thisnode=node[thisnode].parent;
}
for(bitcounter=cd.startpos;bitcounter < MAXBITS;bitcounter++)
{
code[i].bits[bitcounter]=cd.bits[bitcounter];
}
code[i].startpos=cd.startpos;
}
printf("\nSymbols Frequency AssignBits");
for(i=0;i < no_of_symbols;i++)
{
printf("\n%c\t%d\t\t",alphabet[i],node[i].frequency);
for(bitcounter=code[i].startpos;bitcounter < MAXBITS;bitcounter++)
{
printf("%d",code[i].bits[bitcounter]);
}
Printf("\n");
}
getch();
}
int rootnodes=-1;
void pqinsert(int which)
{
int thisnode,previous;
if(rootnodes==-1)
{
node[which].parent=-1;
rootnodes=which;
}
else
{
thisnode=rootnodes;
previous=-1;

while(thisnode!=-1&&node[thisnode].frequency < node[which].frequency)
{
previous=thisnode;
thisnode=node[thisnode].parent;
}
node[which].parent=thisnode;
if(previous!=-1)
{
node[previous].parent=which;
}
else
{
rootnodes=which;
}
}
}
int pqmindelete()
{
int thisnode=rootnodes;
rootnodes=node[thisnode].parent;
return thisnode;
}








OUTPUT:

Enter the no-of-symbols:4

Enter the symbol and frequency:
S 21
H 28
A 11
M 7

Symbols Frequency AssignBits
S 21 11

H 28 0

A 11 101

M 7 100