Programming in C

Queue Using Two Stack In C

PROGRAM :

#include<stdio.h>

int top1=-1;
int last1=-1;
int top2=-1;
void push(int s1[], int f);
void display(int s1[]);
void enque(int s1[],int x);
void deque(int s1[],int s2[]);
void pop(int s2[]);
void pore(int s2[],int s1[],int x);
int main()
{

int a,b,s1[100],s2[100];
while(1)
{
printf(" \n\n 1--enque \n 2--deque \n 3--display \n 4--exit \n");
scanf("%d",&a);
switch(a)
{

case 1:
printf(" \n enter the vlue to be insert ");
scanf("%d",&b);
enque(s1,b);
break;

case 2: deque(s1,s2);
break;

case 3: display(s1);
break;

case 4: exit(0);

default : printf(" \n wrong choice ");

}
}
}

void deque(int s1[],int s2[])
{
int flag;
if(top1!=-1)
{
flag=12;
pore(s2,s1,flag);
pop(s2);
flag=21;
pore(s2,s1,flag);
return ;
}
else
{
printf("\n queue is empty ");
}
}
void pore(int s2[],int s1[],int x)
{
if(x==21)
{
while(top2!=-1)
{
top1=top1+1;
s1[top1]=s2[top2];
top2=top2-1;
}
}
else if(x==12)
{
while(top1!=-1)
{
top2=top2+1;
s2[top2]=s1[top1];
top1=top1-1;
}
}

}
void pop(int s2[])
{
printf("\n deleted item is %d",s2[top2]);
top2=top2-1;
}

void enque(int s1[], int x)
{
push(s1,x);
}
void push(int s1[], int x)
{
if(top1!=100)
{
top1=top1+1;
s1[top1]=x;
}
else
{
printf("\n queue is full ");
}

}

void display(int s1[])
{
if(top1!=-1)
{
last1=0;
printf("\n");
while(top1+1!=last1)
{
printf(" %d",s1[last1]);
last1++;

}

}
else
printf(" \n queue is empty ");

}

Comparison Between Quick sort And bubble sort In C

PROGRAM :

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
void bubble_sort(int *ar,int length);
void quick_sort(int *ar,int l,int u);
int partition(int *ar, int l,int u);
void swap(int a[],int i,int j);

int main()
{
int i,j,k,*ab,*aq,size;
int n[]={40,60,100,200,5000,10000,20000,50000,80000,100000};
int l=10;
clock_t begin, end;
double time_bubble, time_quick;
srand(time(NULL));
printf("\n Input size Time For Quick Sort Time For Bubble Sort \n\n");
for(j=0;j<l;j++)
{
size=n[j];
ab=(int *)malloc(sizeof(int)*n[j]);
aq=(int *)malloc(sizeof(int)*n[j]);
for(i=0;i<size;i++)
{
k = rand()%(size + 1);
ab[i]=k;
aq[i]=k;
}
begin=clock();
bubble_sort(ab,size);
end=clock();
time_bubble=((double)(end-begin)/CLOCKS_PER_SEC);

begin=clock();
quick_sort(aq,0,size-1);
end=clock();
time_quick=((double)(end-begin)/CLOCKS_PER_SEC);

printf(" %d\t\t\t%0.10f\t\t\t%0.10f\n", size, time_quick, time_bubble);

}
return 0;
}

void bubble_sort(int *ar, int n)
{
int i,j,flag=0,tmp;
for(i=0;i<n-1;i++)
{
flag=0;
for(j=0;j<n-i-1;j++)
{
if(ar[j]>ar[j+1])
{
flag=1;
tmp=ar[j];
ar[j]=ar[j+1];
ar[j+1]=tmp;
}
}
if( flag==0)
break;
}
}

void quick_sort(int *arr,int l,int u)
{
int p;
if(l<u)
{
p=partition(arr,l,u);
quick_sort(arr,l,p-1);
quick_sort(arr,p+1,u);
}
}
void swap(int *arr,int i,int j)
{
int tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
int partition(int *arr,int l,int u)
{
int i;
int p=l;
int pivot=arr[p];
for(i=l+1;i<=u;i++)
{
if(arr[i]<pivot)
swap(arr,i,++p);
}
swap(arr,l,p);
return p;

}

OUTPUT :

Brute-force search in C

PROGRAM :

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void brute_force(char a[],int l)
{
char n[l];
int p;
int q = 0 , i = 0 , j = 0 , k=0 , c=0 , z ;
printf("\n\n enter the patern ");
scanf("%s",&n);
p=strlen(n);
printf("\n\n enter the number of error you egnore ");
scanf("%d",&z);
printf("\n\n text is \n\n");
printf("%s",a);
printf("\n\n pattern is \n\n");
printf("%s",n);
printf("\n\n length of petern is %d",p);
printf("\n\n");
for( i=0 ; i <= (l-p) ; i++ )
{
j=0;
c=0;
while( (j < p) && (( a[i+j] == n[j] ) || ( c < z )))
{
if( a[i+j] != n[j] )
{
c=c+1;
}
j=j+1;
}
if( j == p )
{
printf("\n\n pattern found from position %d",i+1);
q=1;
k++;
}
}

if(q==0)
{
printf("\n string not found ");
}

printf("\n\n pattern found in the text %d times \n\n",k);

}

int main()
{
FILE *fopen(),*fp;
char c,n[100],temp,*a;
int l=0,i;
printf("\n enter the file name ");
scanf("%s",&n);
fp=fopen(n,"r");
c=getc(fp);
while(c!=EOF)
{
l++;
c=getc(fp);
}
fclose(fp);

a = (char *)malloc(l*sizeof(char));
fp=fopen(n,"r");
c=getc(fp);
a[0]=c;
for(i=1;c!=EOF;i++)
{
c=getc(fp);
a[i]=c;
}
fclose(fp);

brute_force(a,l);

}

OUTPUT :

Travelling Salesman Problem in C

PROGRAM :

#include<stdio.h>
#include<math.h>
#define INF 9999
#define min(a,b) ((a<b)?a:b)

int k, dist[10][10], v[20][2048], pt[20][2048], s;

int TSP(int i, int bit)
{
int ans=INF, j, temp, j1;
if(bit == 0)
return dist[i][s];
if(v[i][bit] != -1)
return v[i][bit];
else
{
for(j=0; j<k; j++)
{
if((j!=i) && ((bit & (1<<(k-j-1)))!=0))
{
temp = ans;
ans = min(ans,(dist[i][j] + TSP(j, (bit ^ (1<<(k-j-1))))));
if(temp!=ans)
j1 = j;
}
}
pt[i][bit] = j1;
v[i][bit] = ans;
return ans;
}
}

int main()
{
int i, j, value, p, q, t;
printf("\n\n Enter number of vertices : ");
scanf("%d", &k);
printf("Enter cost matrix : \n");
for(i=0; i<k; i++)
{

for(j=0; j<k; j++)
{
scanf("%d", &dist[i][j]);
if(dist[i][j] == 0)
dist[i][j] = INF;
}
for(j=0; j<((int)pow(2,k))-1; j++)
{
v[i][j] = -1;
pt[i][j] = -1;
}
}

printf("Enter source vertex : ");
scanf("%d", &s);
s=s-1;
value = TSP(s, ((int)(pow(2,k)-1) ^ (1<<(k-s-1))));
if(value>=INF)
{
printf("No path exists!");
return;
}
printf("The optimal value is : %d", value);
printf("\nThe optimal path is : \n");
t = k;
p = s;
q = (int)(pow(2,k)-1) ^ (1<<(k-s-1));
printf("%d -> ", s+1);
while(t>1)
{
printf("%d -> ", pt[p][q] + 1);
p = pt[p][q];
q = q ^ (1<<(k-p-1));
t--;
}
printf("%d", s+1);
}

OUTPUT :

C Program to implement Breadth First Search (BFS) Using Adjacency List (linked list)

PROGRAM :

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<process.h>
#include<math.h>
typedef struct adja
{
int data;
struct adja * link;
char ch;
int h;

} adja;

void graph_display(adja arr[],int n);

int front=0;
int rear=-1;

adja *head=NULL,*ptr=NULL;

void graph_bfs_dis(adja arr[],int queue[])
{
int i,height,level,j;
level=0;
for(i=0;i<=rear;i++)
{
printf(" -> v(%d)", queue[i] );
}
printf("\n\n");

/* height = (int)(log(rear+1)/log(2));
printf("\n");
rear=rear+1;
for(i=0; i<rear; i++)
{
if(level!=(int)(log(i+1)/log(2)))
{
printf("\n\n");
level = (int)(log(i+1)/log(2));
}
for(j=(int)pow(2,height-level); j>0; j--)
printf("\t");
printf("%d", queue[i]);

for(j=(int)pow(2,height-level);j>0;j--)
printf("\t");
}
rear=rear-1;*/

}

void set_colour(adja arr[],int queue[],int n)
{
int i,k,j=rear,d;
for(i=0;i<n;i++)
{
for(k=0;k<=j;k++)
{
if(arr[i].data==queue[k])
{
arr[i].ch='b';
}
}
ptr=arr[i].link;
while(ptr!=NULL)
{
for(k=0;k<=j;k++)
{
if(ptr->data==queue[k])
{
ptr->ch='b';
}
}
ptr=ptr->link;
}

}

}

void graph_bfs(adja arr[],int n)
{
int queue[n],j,p=0,i=0;
for(j=0;j<n;j++)
{
queue[j]='0';
}
do
{
head=NULL;
ptr=NULL;
if(arr[i].ch=='r')
{
rear++;
queue[rear]=arr[i].data;

}
ptr=arr[i].link;
while(ptr!=NULL)
{
if(ptr->ch=='r')
{
queue[++rear]=ptr->data;
}
ptr=ptr->link;
}
set_colour(arr,queue,n);
printf("\n after update ");
graph_display(arr,n);
printf("\n visited node ");
graph_bfs_dis(arr,queue);
j=queue[++front];
for(p=0;p<n;p++)
{
if(arr[p].data==j)
{
i=p;
}
}

}while((rear+1)<n);
printf("\n---- after BFS the ordered values and hight are --- ");
graph_bfs_dis(arr,queue);
}

void graph_display(adja arr[],int n)
{
int i;
printf("the adjacency list is \n\n ");
for(i=0;i<n;i++)
{
head=NULL;
ptr=NULL;
printf(" %d(%c)",(arr[i].data),(arr[i].ch));
ptr=arr[i].link;

while(ptr!=NULL)
{
printf("->%d(%c)",ptr->data,ptr->ch);
ptr=ptr->link;
}

printf("\n \n ");
}

}

void graph_input(int n,adja arr[])
{

int i,j,m,p;
for(i=0;i<n;i++)
{
head=NULL;
ptr=NULL;

printf("\n enter the value of number %d vertex ",(i+1));
scanf("%d",&(arr[i].data));
arr[i].ch='r';
arr[i].h=-99;
arr[i].link=NULL;
if(n>1)
{
printf("\n enter the number of vertices connected with %d ",(arr[i].data));
scanf("%d",&p);

if(p!=0)
{
printf("\n enter the value of vertices connected with %d ",(arr[i].data));

for(j=0;j<p;j++)
{
scanf("%d",&m);
ptr=(adja *)malloc(sizeof(adja));
ptr->data=m;
ptr->ch='r';
ptr->link=NULL;
ptr->h=-99;

if(j==0)
{
arr[i].link=ptr;
//printf(" %d ",arr[i].data);
}
else
{
head->link=ptr;
}
head=ptr;

}
}

}

}

}

int main()
{
int n,i,j,m,p;

printf("\n enter the number of vertex ");
scanf("%d",&n);
if(n!=0)
{
adja *arr=(adja *)malloc(n*sizeof(adja));

graph_input(n,arr);

arr[0].h=0;

printf("\n======================================================================================\n");

printf("\n initial situation of ");

graph_display(arr,n);

printf("\n root node of tree is [%d] \n",arr[0].data);

graph_bfs(arr,n);
}
else
{
printf("\n graph is empty \n");
}

}

OUTPUT :