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 :