C Program for Enter the string and sort the character in different string

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char string[30];
int n;
char c;
char alphabets[20];
int num[20];
char symbol[10];
char operators[10];
int i,j;
int p=0,q=0,r=0,s=0;
clrscr();
printf("Developed By: Nandan Kr. Kushwaha\n\n");
printf("Enter the size of string\n");
scanf("%d",&n);
printf("Enter the string\n");
for(i=0;i<n;i++)
{
c=getchar();
string[i]=c;
}
printf("String is:");
for(i=0;i<n;i++)
{
putchar (string[i]);
}
for(i=0;i<n;i++)
{
c=string[i];
if((c>='a'&&c<='z')||(c>='A'&&c<='Z'))
{
alphabets[p]=c;
p++;
}
else if(c>='0'&&c<='9')
{
num[q]=c;
q++;
}
else if(c=='+'||c=='-'||c=='*'||c=='/')
{
operators[r]=c;
r++;
}
else
{
symbol[s]=c;
s++;
}}
printf("\n Alphabets are:");
for(j=0;j<p;j++)
{
putchar(alphabets[j]);
}
printf("\n Numbers are:");
for(j=0;j<q;j++)
{
putchar(num[j]);
}
printf("\n Operators are:");
for(j=0;j<r;j++)
{
putchar(operators[j]);
}
printf("\n Symbols are:");
for(j=0;j<s;j++)
{
putchar(symbol[j]);
}
getch();
}

OUTPUT:-

C program for Enter and display string using getchar and putchar

#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
char nandan[20];
char c;
int i,n;
clrscr();
printf("Developed By: Nandan Kr. Kushwaha\n\n");
printf("Enter the size of the string\n");
scanf("%d",&n);
printf("Enter the string\n");
for(i=0;i<=n;i++);
{
c=getchar();
nandan[i]=c;
}
printf("\n String is:");
for(i=0;i<=n;i++)
{
putchar(nandan[i]);
}
getch();
}

OUTPUT:-

C Program for Lexical Analyzer

#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<string.h>
void main()
{
char fname[20],ch,ch1[2],arr[60];
int i,j,flag=0,k;
FILE *f1;
char keyw[32][10]={"auto","break","case","const","continue",
"default","do","double","else","enum","extern","float","goto","if",
"long","register","return","short","sizeof","static","struct",
"switch","typedef","union","volatile","while","getch","void","int",
"char","signed","unsigned"};
clrscr();
printf("\n\tENTER THE FILE NAME:");
scanf("%s",fname);
f1=fopen(fname,"r");
if(f1==NULL)
{
printf("\n\tFILE NOT FOUND");
getch();
exit(0);
}
else
{
ch=fgetc(f1);
while(ch!=EOF)
{
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='='||
ch=='('||ch==')'||ch=='.'||ch=='['||ch==']'||ch=='{'||
ch=='}'||ch=='|'||ch=='&'||ch=='^'||ch=='%'||ch=='$'||
ch==':'||ch=='?'||ch=='('||ch==')'||ch=='.'||ch=='<'||
ch=='>'||ch=='!'||ch=='?'||ch=='~')
{
i=0;
ch1[i]=ch;
i++;
ch=fgetc(f1);
if(ch=='+'||ch=='-'||ch=='*'||ch=='/'||
ch=='='||ch=='('||ch==')'||ch=='.'||ch=='['||
ch==']'||ch=='{'||ch=='}'||ch=='|'||ch=='&'||
ch=='^'||ch=='%'||ch=='$'||ch==':'||ch=='?'||
ch=='('||ch==')'||ch=='.'||ch=='<'||ch=='>'||
ch=='!'||ch=='?'||ch=='~')
{
ch1[i]=ch;
printf("\n\t%c%c IS AN OPERATOR",ch1[i-1],ch1[i]);
}
else
{
printf("\n\t%c IS AN OPERATOR",ch1[i-1]);
continue;
}
}
else if(ch>='a'&&ch<='z')
{
flag=0;
j=0;
while(ch>='a'&&ch<='z'||ch>='0'&&ch<='9')
{
arr[j]=ch;
j++;
ch=fgetc(f1);
}
arr[j]='\0';
for(k=0;k<32;k++)
{
if((strcmp(keyw[k],arr))==0)
{
printf("\n\t%s IS A KEYWORD",arr);
flag=1;
break;
}
}
if(flag==0)
{
printf("\n\t%s IS A IDENTIFIER",arr);
}
continue;
}
else if(ch>='0'&&ch<='9')
{
j=0;
while(ch>='0'&&ch<='9')
{
arr[j]=ch;
j++;
ch=fgetc(f1);
}
arr[j]='\0';
printf("\n\t%s IS A VALUE",arr);
continue;
}
else if(ch==' '||ch=='\n'||ch=='\t')
{
ch=fgetc(f1);
continue;
}
else
{
printf("\n\t%c IS A SPECIAL CHARACTER",ch);
}
ch=fgetc(f1);
}
}
getch();
}

C++ Program for friend function

#include<iostream.h>
#include<conio.h>

class complex
{
float x,y;
public:
void input(float real,float imag)
{
x=real;
y=imag;
}
friend complex sum(complex,complex);
void show(complex);
};
complex sum(complex c1,complex c2)
{
complex c3;
c3.x=c1.x+c2.x;
c3.y=c1.y+c2.y;
return(c3);
}
void complex::show(complex c)
{
cout<<"\n"<<c.x<<"+ j"<<c.y;
}
void main()
{
complex a,b,c;
clrscr();
a.input(3.1,5.65);
b.input(27.5,1.2);
c=sum(a,b);
cout<<"\nA =";
a.show(a);
cout<<"\nB = ";
b.show(b);
cout<<"\nC =";
c.show(c);
getch();

}


OUTPUT:-

C Program for constructing a minimum cost spanning tree using 1)Prims and 2)Kruskal algorithm

#define infinity 9999
#define MAX 20
#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
int G[MAX][MAX],spanning[MAX][MAX],n;
void prims();
void kruskal();
void main()
{
int i,j,op;
clrscr();
do {
   printf("\n\n1)Create\n2)Prim's\n3)Kruskal\n4)Quit");
   printf("\nEnter Your Choice : ");
   scanf("%d",&op);
   switch(op)
    { case 1:
     printf("\nEnter No. of vertices : ");
     scanf("%d",&n);
     printf("\nEnter the adjacency matrix :");
     for(i=0;i<n;i++)
for(j=0;j<n;j++)
 scanf("%d",&G[i][j]);
      break;
case 2: prims();break;
case 3: kruskal();break;

     }
}while(op!=4);
}
void prims()
{
int cost[MAX][MAX];
int u,v,min_distance,distance[MAX],from[MAX];
int visited[MAX],no_of_edges,i,min_cost,j;
// create cost[][] matrix ,spanning[][]
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
if(G[i][j]==0)
cost[i][j]=infinity;
else
cost[i][j]=G[i][j];
      spanning[i][j]=0;
}
// initialise visited[],distance[] and from[]
distance[0]=0;visited[0]=1;
for(i=1;i<n;i++)
{
distance[i]=cost[0][i];
from[i]=0;
visited[i]=0;
}
min_cost=0;            //cost of spanning tree
no_of_edges=n-1;       //no.of edges to be added
while(no_of_edges>0)
{
//find the vertex at minimum distance from the tree
min_distance=infinity;
for(i=1;i<n;i++)
if(visited[i]==0 && distance[i] < min_distance)
{
v=i;
min_distance=distance[i];
}
u=from[v];
// insert the edge in spanning tree
spanning[u][v]=distance[v];
spanning[v][u]=distance[v];
no_of_edges--;
visited[v]=1;
// update the distance[] array
for(i=1;i<n;i++)
if(visited[i]==0 && cost[i][v] < distance[i])
{
distance[i]=cost[i][v];
from[i]=v;
}
min_cost=min_cost+cost[u][v];
}

printf("spanning tree Edges(Prims) : \n");
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
   if(spanning[i][j] != 0)
      printf("\n%d - %d cost= %d",i,j,spanning[i][j]);
printf("\nTotal cost of spanning tree=%d",min_cost);
}

/**** Functions and structures used for Kruskal's Algorithm */
typedef struct edge
{ int u,v,w;
}edge;

typedef struct edgelist
 { edge data[30];
   int n;
 }edgelist;
edgelist elist,spanlist;
int find(int belongs[],int vertexno);
void sort();
void union1(int belongs[],int c1,int c2);
void print();
void kruskal()
{  int belongs[MAX],i,j,cno1,cno2;
   /*create a list of edges */
   elist.n=0;
   for(i=0;i<n;i++)
     for(j=0;j<n;j++)
       if(G[i][j]!=0)
{ elist.data[elist.n].u=i;
  elist.data[elist.n].v=j;
  elist.data[elist.n].w=G[i][j];
  elist.n++;
}
   sort();
 // create the spanning tree with n components
 for(i=0;i<n;i++)
  belongs[i]=i;
 spanlist.n=0;
 // add edges one by one to spanning tree
 for(i=0;i<elist.n;i++)
  { cno1=find(belongs,elist.data[i].u);
    cno2=find(belongs,elist.data[i].v);
    if(cno1 != cno2) // if the edge does not cause a cycle
      { spanlist.data[spanlist.n++]=elist.data[i];
union1(belongs,cno1,cno2);
      }
   }
 //print the spanning tree
  print();
}

int find(int belongs[] ,int vertexno)
 { return(belongs[vertexno]);
 }

void union1(int belongs[], int c1 , int c2)
 { int i;
   for(i=0;i<n;i++)
    if(belongs[i]==c2) // merge two components
      belongs[i]=c1;
 }
void sort()
 { int i,j;
   edge temp;
   for(i=1;i<elist.n;i++)
     for(j=0;j<elist.n-i;j++)
       if(elist.data[j].w > elist.data[j+1].w)
 { temp=elist.data[j];
   elist.data[j]=elist.data[j+1];
   elist.data[j+1]=temp;
 }
  }

void print()
 { int i,cost=0;
   for(i=0;i<spanlist.n;i++)
     { printf("\n%d - %d cost= %d",spanlist.data[i].u,spanlist.data[i].v,
  spanlist.data[i].w);
       cost=cost+spanlist.data[i].w;
     }
   printf("\nCost of the spanning tree : %d",cost);
}




OUTPUT:-



1)Create
2)Prim's
3)Kruskal
4)Quit
Enter Your Choice : 1

Enter No. of vertices : 4

Enter the adjacency matrix :
 0 2 3 1
 2 0 4 0
 3 4 0 7
 1 0 7 0


1)Create
2)Prim's
3)Kruskal
4)Quit
Enter Your Choice : 2
spanning tree Edges(Prims) :

0 - 1 cost= 2
0 - 2 cost= 3
0 - 3 cost= 1
Total cost of spanning tree=6

1)Create
2)Prim's
3)Kruskal
4)Quit
Enter Your Choice : 3

0 - 3 cost= 1
0 - 1 cost= 2
0 - 2 cost= 3
Cost of the spanning tree : 6

1)Create
2)Prim's
3)Kruskal
4)Quit
Enter Your Choice : 4

C program for Shortest path using Dijkstra's Algorithm

#define INFINITY 9999
#include <stdio.h>
#include <conio.h>
#define MAX 10

void dijikstra(int G[MAX][MAX],int n, int startnode);
void main()
{ int G[MAX][MAX],i,j,n,u;
  clrscr();
  printf("\nEnter no. of vertices : ");
  scanf("%d",&n);
  printf("\nEnter adjacency matrix : ");
  for(i=0;i<n;i++)
   for(j=0;j<n;j++)
    scanf("%d",&G[i][j]);
  printf("\nEnter the starting node : ");
  scanf("%d",&u);
  dijikstra(G,n,u);
  getch();
}

void dijikstra(int G[MAX][MAX],int n, int startnode)
{ int cost[MAX][MAX],distance[MAX],pred[MAX];
  int visited[MAX],count,mindistance,nextnode,i,j;
  /*pred[] stores the predecessor of each node
  count gives the number of nodes seen so far*/

  //create the cost matrix
  for(i=0;i<n;i++)
    for(j=0;j<n;j++)
     if(G[i][j]==0)
       cost[i][j]=INFINITY;
     else
       cost[i][j]=G[i][j];
  //initialize
  for(i=0;i<n;i++)
   { distance[i]=cost[startnode][i];
     pred[i]=startnode;visited[i]=0;
   }
  distance[startnode]=0;visited[startnode]=1;
  count=1;
  while(count<n-1)
   { mindistance=INFINITY ;
// nextnode is the node at minimum distance
     for(i=0;i<n;i++)
       if(distance[i] < mindistance && !visited[i])
{ mindistance=distance[i];
  nextnode=i;
}
//check if a better path exist through nextnode
   visited[nextnode]=1;
   for(i=0;i<n;i++)
    if(!visited[i])
      if(mindistance+cost[nextnode][i]<distance[i])
{ distance[i]=mindistance+cost[nextnode][i];
  pred[i]=nextnode;
}
   count++;
 }

 //print the path and distance of each node
 for(i=0;i<n;i++)
    if(i!=startnode)
      { printf("\n Distance of %d = %d ",i,distance[i]);
printf("\nPath = %d ",i);
j=i;
do {
    j=pred[j];
    printf("<- %d ",j);
  }while(j!=startnode);
     }
}


OUTPUT:-



Enter no. of vertices : 4

Enter adjacency matrix :
0 1 1 1
1 0 1 0
1 1 0 1
1 0 1 0

Enter the starting node : 1

 Distance of 0 = 1
Path = 0 <- 1
 Distance of 2 = 1
Path = 2 <- 1
 Distance of 3 = 2
Path = 3 <- 0 <- 1

BFS and DFS on a graph represented using adjacency list C program

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
#define MAX 20

typedef struct Q
{
 int data[MAX];
 int R,F;
}Q;

typedef struct node
{
 struct node *next;
 int vertex;
}node;

void enqueue(Q *,int);
int dequque(Q *);
int empty(Q *);
int full(Q *);
void BFS(int);
void readgraph();      //create an adjecency list
void insert(int vi,int vj);     //insert an edge (vi,vj)in adj.list
void DFS(int i);
int visited[MAX];
node *G[20];          //heads of the linked list
int n;                 // no of nodes

void main()
{
 int i,op;
 clrscr();
 do
   { printf("\n\n1)Create\n2)BFS\n3)DFS\n4)Quit");
     printf("\nEnter Your Choice: ");
     scanf("%d",&op);
     switch(op)
      { case 1: readgraph();break;
        case 2: printf("\nStarting Node No. : ");
         scanf("%d",&i);
         BFS(i);break;
        case 3:  for(i=0;i<n;i++)
    visited[i]=0;
         printf("\nStarting Node No. : ");
         scanf("%d",&i);
         DFS(i);break;
       }
    }while(op!=4);
}


void BFS(int v)
{
 int w,i,visited[MAX];
 Q q;

 node *p;
 q.R=q.F=-1;              //initialise
 for(i=0;i<n;i++)
  visited[i]=0;
 enqueue(&q,v);
 printf("\nVisit\t%d",v);
 visited[v]=1;
 while(!empty(&q))
 {
  v=dequeue(&q);
  //insert all unvisited,adjacent vertices of v into queue
  for(p=G[v];p!=NULL;p=p->next)
  {
   w=p->vertex;
   if(visited[w]==0)
   {
    enqueue(&q,w);
    visited[w]=1;
    printf("\nvisit\t%d",w);
   }
  }
 }
}

void DFS(int i)
{
 node *p;
 printf("\n%d",i);
 p=G[i];
 visited[i]=1;
 while(p!=NULL)
 {
  i=p->vertex;
  if(!visited[i])
   DFS(i);
  p=p->next;
 }
}


int empty(Q *P)
{
 if(P->R==-1)
  return(1);
 return(0);
}

int full(Q *P)
{
 if(P->R==MAX-1)
  return(1);
 return(0);
}

void enqueue(Q *P,int x)
{
 if(P->R==-1)
 {
  P->R=P->F=0;
  P->data[P->R]=x;
 }
 else
 {
  P->R=P->R+1;
  P->data[P->R]=x;
 }
}

int dequeue(Q *P)
{
 int x;
 x=P->data[P->F];
 if(P->R==P->F)
 {
  P->R=-1;
  P->F=-1;
 }
 else
  P->F=P->F+1;
 return(x);
}

void readgraph()
{  int i,vi,vj,no_of_edges;
 printf("\nEnter no. of vertices :");
 scanf("%d",&n);
 //initialise G[] with NULL
 for(i=0;i<n;i++)
  G[i]=NULL;
 //read edges and insert them in G[]
 printf("\nEnter no of edges :");
 scanf("%d",&no_of_edges);
 for(i=0;i<no_of_edges;i++)
 {
  printf("\nEnter an edge (u,v)  :");
  scanf("%d%d",&vi,&vj);
  insert(vi,vj);
  insert(vj,vi);
 }
}

void insert(int vi,int vj)
{
 node *p,*q;
 //acquire memory for the new node
 q=(node *)malloc(sizeof(node));
 q->vertex=vj;
 q->next=NULL;
 //insert the node in the linked list for the vertex no. vi
 if(G[vi]==NULL)
  G[vi]=q;
 else
 {
  // go to the end of linked list
  p=G[vi];
  while(p->next!=NULL)
   p=p->next;
  p->next=q;
 }
}

OUTPUT:-

1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 1

Enter no. of vertices :4

Enter no of edges :5

Enter an edge (u,v)  :1 2

Enter an edge (u,v)  :2 3

Enter an edge (u,v)  :3 4

Enter an edge (u,v)  :4 1

Enter an edge (u,v)  :1 3


1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 2

Starting Node No. : 1

Visit   1
visit   2
visit   3
visit   4


1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 3

Starting Node No. :2


2
1
4
3
1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 2

Starting Node No. : 4

Visit   4
visit   3
visit   1
visit   2

1)Create
2)BFS
3)DFS
4)Quit
Enter Your Choice: 4

C program for Sorting methods Quick sort and Merge sort using recursion

#include<conio.h>
#include<stdio.h>
void quick_sort(int [],int,int);
int partition(int [],int,int);
void mergesort(int a[] ,int i , int j);
void merge(int a[],int i1, int j1, int i2, int j2);
void main()
{
int a[30],n,i,op;
clrscr();
do
  {
    printf("\n1)Quick Sort\n2)Merge Sort \n3)Quit");
    printf("\nEnter your choice : ");
    scanf("%d",&op);
    switch(op)
     {
case 1: printf("\nEnter no of elements :");
scanf("%d",&n);
printf("\nEnter array elements :");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
quick_sort(a,0,n-1);
printf("\nSorted array is :");
for(i=0;i<n;i++)
printf("%d  ",a[i]);
break;

case 2: printf("\nEnter no of elements :");
scanf("%d",&n);
printf("\nEnter array elements :");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("\nSorted array is :");
for(i=0;i<n;i++)
printf("%d   ",a[i]);
break;

  }
     }while(op!=3);
}
void quick_sort(int a[],int l,int u){
int j;
if(l<u)
{
j=partition(a,l,u);
quick_sort(a,l,j-1);
quick_sort(a,j+1,u);
}
}
int partition(int a[],int l,int u)
{
    int v,i,j,temp;
    v=a[l];
    i=l;
    j=u+1;
    do
    {
do
{ i++;
}while(a[i]<v && i<=u);

do
{ j--;
}while(a[j]>v);

if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
    }while(i<j);
    a[l]=a[j];
    a[j]=v;
    return(j);
}

 void mergesort(int a[] ,int i , int j)
   {
int mid;
if(i<j)
{ mid=(i+j)/2;
  mergesort(a,i,mid);    //left recursion
  mergesort(a,mid+1,j);  //right recursion
  merge(a,i,mid,mid+1,j); //meging of two sorted sub-arrays
}
    }


void merge(int a[],int i1, int j1, int i2, int j2)
  {
     int temp[50];//array used for merging
     int i,j,k;
     i=i1;//beginning of the first list
     j=i2;//beginning of the second list
     k=0;
     while(i<=j1 && j <=j2) //while elemnts in both lists
      {
if(a[i]<a[j])
  temp[k++]=a[i++];
else
  temp[k++]=a[j++];
      }
    while(i<=j1)//copy remaining elements of the first list
       temp[k++]=a[i++];
    while(j<=j2)//copy remaining elements of the second list
       temp[k++]=a[j++];
  //Transfer elemnts from temp[] back to a[]
    for(i=i1,j=0;i<=j2;i++,j++)
       a[i]=temp[j];
  }


OUTPUT:-



1)Quick Sort
2)Merge Sort
3)Quit
Enter your choice : 1

Enter no of elements :4

Enter array elements :23 6 89 5

Sorted array is :5  6  23  89
1)Quick Sort
2)Merge Sort
3)Quit
Enter your choice : 2

Enter no of elements :4

Enter array elements :15 7 34 0

Sorted array is :0   7   15   34
1)Quick Sort
2)Merge Sort
3)Quit
Enter your choice : 3

Implement sorting methods using functions - bubble sort, selection sort insertion sort and shell sort C program

void insertion_sort(int [],int);
void selection_sort(int a[],int n);
void bubble_sort(int a[],int n);
void shell_sort(int a[],int n);
void main()
{
int a[50],n,i,op;
clrscr();
do
 {
   printf("\n1)insertion\n2)Selection\n3)Bubble\n4)Shell\n5)Quit");
   printf("\nEnter your choice : ");
   scanf("%d",&op);
   switch(op)
    {
case 1: printf("\nEnter no of elements :");
scanf("%d",&n);
printf("\nEnter array elements :");
for(i=0;i<n;i++)
   scanf("%d",&a[i]);
insertion_sort(a,n);
break;
case 2: printf("\nEnter no of elements :");
scanf("%d",&n);
printf("\nEnter array elements :");
for(i=0;i<n;i++)
   scanf("%d",&a[i]);
selection_sort(a,n);
break;
case 3: printf("\nEnter no of elements :");
scanf("%d",&n);
printf("\nEnter array elements :");
for(i=0;i<n;i++)
   scanf("%d",&a[i]);
bubble_sort(a,n);
break;
case 4: printf("\nEnter no of elements :");
scanf("%d",&n);
printf("\nEnter array elements :");
for(i=0;i<n;i++)
   scanf("%d",&a[i]);
shell_sort(a,n);
break;
    }
} while(op!=5);

}

void insertion_sort(int a[],int n)
{
int i,j,temp,k;
printf("\nUnsorted Data:");
for(k=0;k<n;k++)
 printf("%5d",a[k]);

for(i=1;i<n;i++)
{
temp=a[i];
for(j=i-1;j>=0 && a[j]>temp;j--)
a[j+1]=a[j];
a[j+1]=temp;
 printf("\nAfter pass   %d",i);
     for(k=0;k<n;k++)
      printf("%5d",a[k]);

}
}
void selection_sort(int a[],int n)
{
int i,j,temp,k;
printf("\nUnsorted Data:");
for(k=0;k<n;k++)
 printf("%5d",a[k]);

for(i=0;i<n-1;i++)
{       k=i;
for(j=i+1;j<n;j++)
 if(a[j]<a[k])
   k=j;
temp=a[i];
a[i]=a[k];
a[k]=temp;
 printf("\nAfter pass   %d",i+1);
     for(k=0;k<n;k++)
      printf("%5d",a[k]);

}
}
void bubble_sort(int a[],int n)
{
int i,j,k,temp;
printf("\nUnsorted Data:");
for(k=0;k<n;k++)
 printf("%5d",a[k]);
for(i=1;i<n;i++)
 {
   for(j=0;j<n-1;j++)
if(a[j]>a[j+1])
  {
     temp=a[j];
     a[j]=a[j+1];
     a[j+1]=temp;
 }
     printf("\nAfter pass   %d",i);
     for(k=0;k<n;k++)
      printf("%5d",a[k]);
  }
}

void shell_sort(int a[],int n)
  {
     int i,j,step,pass=1,temp;
printf("\nUnsorted Data:");
for(i=0;i<n;i++)
 printf("%5d",a[i]);

     for(step=n/2; step>0 ; step=step/2)
{
  for(i=step; i< n ; i++)
     {
temp=a[i];
for(j=i; j>=step ; j=j-step)
  {
    if(temp < a[j-step])
 a[j]=a[j-step];
    else
 break;
  }
a[j]=temp;
    }
  printf("\nAfter pass   %d",pass);
  for(i=0;i<n;i++)
      printf("%5d",a[i]);
  pass++;
}
  }


OUTPUT:-

1)insertion
2)Selection
3)Bubble
4)Shell
5)Quit
Enter your choice : 1

Enter no of elements :4

Enter array elements :45 67 90 2

Unsorted Data:   45   67   90    2
After pass   1   45   67   90    2
After pass   2   45   67   90    2
After pass   3    2   45   67   90
1)insertion
2)Selection
3)Bubble
4)Shell
5)Quit
Enter your choice : 2

Enter no of elements :4

Enter array elements :34 78 5 12

Unsorted Data:   34   78    5   12
After pass   1    5   78   34   12
After pass   2    5   12   34   78
After pass   3    5   12   34   78
1)insertion
2)Selection
3)Bubble
4)Shell
5)Quit
Enter your choice : 3

Enter no of elements :4

Enter array elements :56 7 23 19

Unsorted Data:   56    7   23   19
After pass   1    7   23   19   56
After pass   2    7   19   23   56
After pass   3    7   19   23   56
1)insertion
2)Selection
3)Bubble
4)Shell
5)Quit
Enter your choice : 4

Enter no of elements :4

Enter array elements :2 67 4 8

Unsorted Data:    2   67    4    8
After pass   1    2    8    4   67
After pass   2    2    4    8   67
1)insertion
2)Selection
3)Bubble
4)Shell
5)Quit
Enter your choice : 5

C Program for various searching methods

#include <stdio.h>
#include <conio.h>
int fib(int n); // return a Fibonacci Number
int fibsearch(int a[],int key,int mid ,int p ,int q); //Fibonacci search function
int binsearch(int a[],int i ,int j,int key);/*Recursive binary search*/
int linsearch(int a[],int n , int key);
void main()
 {
   int a[30],key,mid,p,q,k,n,i,result,op;
   clrscr();
   do
      {
printf("\n1)Linear Search\n2)Binary Search\n3)Fibonacci Search");
printf("\n4)Quit");
printf("\nEnter Your Choice : ");
scanf("%d",&op);
switch(op)
    {
case 1: printf("\n Enter No. of elements : ");
scanf("%d" ,&n);
printf("\n Enter a  list of %d elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the the element to be searched : ");
scanf("%d",&key);
result=linsearch(a,n,key);
if(result==-1)
      printf("\n Not found : ");
else
      printf("\n Found at location= %d",result);
break;

case 2: printf("\n Enter No. of elements : ");
scanf("%d" ,&n);
printf("\n Enter a sorted list of %d elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the the element to be searched : ");
scanf("%d",&key);
result=binsearch(a,0,n-1,key);
if(result==-1)
      printf("\n Not found : ");
else
      printf("\n Found at location= %d",result);
break;

case 3: printf("\n Enter No. of elements : ");
scanf("%d" ,&n);
printf("\n Enter a sorted list of %d elements : ",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("\n Enter the the element to be searched : ");
scanf("%d",&key);
//locate the kth term of Fibonacci series , such that fib(k) > n
for(k=1 ; fib(k) <= n ; k++)
;
p=fib(k-2);
q=fib(k-3);
mid=n-p+1;
result=fibsearch(a,key,mid,p,q);
if(result==-1)
      printf("\n Not found : ");
else
      printf("\n Found at location= %d",result);
break;

     }
      }while(op!=4);
 }

 int fib(int n)
  { if(n==0) return(0);
    if(n==1)    return(1);
    return(fib(n-1)+fib(n-2));
  }

int fibsearch(int a[],int key,int mid ,int p ,int q)
   {
       int temp;

       if(key==a[mid])
 return(mid);
       if(key> a[mid])
 {
    if(p==1)
return(-1);

    mid=mid+q;  // new mid
    p=p-q;      //p=fib(k-4)
    q=q-p;      //q=fib(k-5)
    return(fibsearch(a,key,mid,p,q));
 }
       else    //key < a[mid]
 {
    if(q==0)
return(-1);
    mid=mid-q;    // new mid
    temp=p-q;
    p=q;         //p=fib(k-3)
    q=temp;      //q=fib(k-4)
    return(fibsearch(a,key,mid,p,q));
 }
    }

int binsearch(int a[],int i, int j,int key)
{
   int c;
   if(i>j)
    return(-1);
   c=(i+j)/2;
   if(key==a[c])
       return(c);
   if(key>a[c])
       return(binsearch(a,c+1,j,key));
   return(binsearch(a,i,c-1,key));
 }
int linsearch(int a[],int n , int key)
{
    int i;
    for(i=0;i<n;i++)
      {
if(a[i]==key)
    return(i);
      }

   return(-1);
}


OUTPUT:-

1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 1

 Enter No. of elements : 4

 Enter a  list of 4 elements : 23 34 8 96

 Enter the the element to be searched : 8

 Found at location= 2
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 1

 Enter No. of elements : 3

 Enter a  list of 3 elements : 12 34 3

 Enter the the element to be searched : 12

 Found at location= 0
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 2
 Enter No. of elements : 4

 Enter a sorted list of 4 elements : 4 8 27 90

 Enter the the element to be searched : 5

 Not found :
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 2

 Enter No. of elements : 3

 Enter a sorted list of 3 elements : 5 6 89

 Enter the the element to be searched : 5

 Found at location= 0
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 3

 Enter No. of elements : 4

 Enter a sorted list of 4 elements : 2 13 34 78

 Enter the the element to be searched : 13

 Found at location= 1
1)Linear Search
2)Binary Search
3)Fibonacci Search
4)Quit
Enter Your Choice : 4

program showing various operations on binary search tree in C

#include<conio.h>
#include<stdio.h>
#include<stdlib.h>
typedef struct BSTnode
{
int data;
struct BSTnode *left,*right;
}BSTnode;

BSTnode *find(BSTnode *,int);
BSTnode *insert(BSTnode *,int);
BSTnode *delet(BSTnode *,int);
BSTnode *create();
void inorder(BSTnode *T);
void preorder(BSTnode *T);
void postorder(BSTnode *T);
void main()
{
BSTnode *root=NULL,*p;
int x,op;
clrscr();
do
 { printf("\n\n1)Create\n2)Delete\n3)Search\n4)Preorder");
   printf("\n5)Inorder\n6)Posorder\n7)Insert\n8)Quit");
   printf("\nEnter Your Choice :");
   scanf("%d",&op);
    switch(op)
     {
case 1:root=create();break;
case 2: printf("\nEnter the key to be deleted :");
scanf("%d",&x);
root=delet(root,x);
break;
case 3: printf("\nEnter the key to be searched :");
scanf("%d",&x);
p=find(root,x);
if(p==NULL)
 printf("\n ***** Not Found****");
else
 printf("\n ***** Found*****");
break;
case 4: preorder(root);break;
case 5: inorder(root);break;
case 6: postorder(root);break;
case 7: printf("\nEnter a Data : ");
scanf("%d",&x);
root=insert(root,x);
break;
    }
}while(op!=8);
}


void inorder(BSTnode *T)
{
if(T!=NULL)
{
inorder(T->left);
printf("%d\t",T->data);
inorder(T->right);
}
}

void preorder(BSTnode *T)
 {     if(T!=NULL)
 { printf("%d\t",T->data);
   preorder(T->left);
   preorder(T->right);
 }
 }
void postorder(BSTnode *T)
 {     if(T!=NULL)
 {
   postorder(T->left);
   postorder(T->right);
   printf("%d\t",T->data);
 }
 }
BSTnode *find(BSTnode *root,int x)
{
while(root!=NULL)
{
if(x==root->data)
return(root);
if(x>root->data)
root=root->right;
else
root=root->left;
}
return(NULL);
}

BSTnode *insert(BSTnode *T,int x)
{
BSTnode *p,*q,*r;
// acquire memory for the new node
r=(BSTnode*)malloc(sizeof(BSTnode));
r->data=x;
r->left=NULL;
r->right=NULL;
if(T==NULL)
return(r);
// find the leaf node for insertion
p=T;
while(p!=NULL)
{
q=p;
if(x==p->data)
 {
    printf("\nDuplicate Data : ");
    return(T);
 }
if(x>p->data)
p=p->right;
else
p=p->left;
}
if(x>q->data)
q->right=r;  // x as right child of q
else
q->left=r;   //x as left child of q
return(T);
}

BSTnode *delet(BSTnode *T,int x)
{
BSTnode *temp;
if(T==NULL)
{
printf("\nElement not found :");
return(T);
}
if(x < T->data)                // delete in left subtree
{
T->left=delet(T->left,x);
return(T);
}
if(x > T->data)                // delete in right subtree
{
T->right=delet(T->right,x);
return(T);
}

// element is found
if(T->left==NULL && T->right==NULL)   // a leaf node
{
temp=T;
free(temp);
return(NULL);
}
if(T->left==NULL)
{
temp=T;
T=T->right;
free(temp);
return(T);
}
if(T->right==NULL)
{
temp=T;
T=T->left;
free(temp);
return(T);
}
// node with two children
//go to the inorder successor of the node
temp=T->right;
while(temp->left !=NULL)
 temp=temp->left;
T->data=temp->data;
T->right=delet(T->right,temp->data);
return(T);
}

BSTnode *create()
{
int n,x,i;
BSTnode *root;
root=NULL;
printf("\nEnter no. of nodes :");
scanf("%d",&n);
printf("\nEnter tree values :");
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=insert(root,x);
}
return(root);
}



OUTPUT:-

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :1

Enter no. of nodes :4

Enter tree values :12 34 87 56


1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :4
12      34      87      56

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :5
12      34      56      87

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :6
56      87      34      12

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :7

Enter a Data : 33


1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :4
12      34      33      87      56

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :3
Enter the key to be searched :33

 ***** Found*****

1)Create
2)Delete
3)Search
4)Preorder
5)Inorder
6)Posorder
7)Insert
8)Quit
Enter Your Choice :8