Selection Sort Data Structure Array C Program

This Program is for Selection Sort on Array. This is part of Mumbai University MCA Colleges Data Structures C program


#include<stdio.h>
#include<conio.h>

void selection(int elements[], int maxsize);
void display(int elements[],int maxsize);
int elements[]={100,25,88,13,76,31,45,68,94,53};
int maxsize=10;

void main()
{
          int i;
          clrscr();
          printf("\nArray before sorting:\n\n");
          for (i = 0; i < maxsize; i++)
                   printf("%d ",elements[i]);
          printf ("\n");

          selection(elements, maxsize);

          printf("\nArray after sorting:\n\n");
          for (i = 0; i < maxsize; i++)
                   printf("%d ", elements[i]);
          getch();
}

void selection(int elements[], int maxsize)
{
          int i, j, k;
          int min, temp,cnt=0;
          for (i = 0; i < maxsize-1; i++)
          {
                   min = i;
                   for (j = i+1; j < maxsize; j++)
                   {
                             if (elements[j] < elements[min])
                             min = j;
                   }
                   temp = elements[i];
                   elements[i] = elements[min];
                   elements[min] = temp;
                   cnt++;
                   if(cnt<=3)
                   {
                             printf("\nElement after pass %d:",cnt);
                             display(elements,maxsize);
                   }


          }
}

void display(int elements[],int maxsize)
{
          int i;

          for(i=0;i<maxsize;i++)
                   printf("  %d ",elements[i]);
          printf("\n");
}

Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.

Binary Search Traversal C Program Data Structure

This Program is for Binary Search Tree and Traversal in C, and is part of Mumbai University MCA Colleges Data Structures in C program MCA Sem 2

# include <stdio.h>
#include<conio.h>
# include <malloc.h>

struct node
{
          int info;
          struct node *lchild;
          struct node *rchild;
}*root,*t;
struct node* search(struct node* ptr,int info);
void find(int item,struct node **par,struct node **loc);
void insert(int item);
void del(int item);
void case_a(struct node *par,struct node *loc );
void case_b(struct node *par,struct node *loc);
void case_c(struct node *par,struct node *loc);
void preorder(struct node *ptr);
void inorder(struct node *ptr);
void postorder(struct node *ptr);
void display(struct node *ptr,int level);
int item,n;

void main()
{
struct node *ptr;
int info;
          int choice,num;
          clrscr();
          root=NULL;
printf("\n\n============== BINARY SEARCH TREE ============\n\n");
          while(1)
          {
                   printf("\n\n------------- MAIN MENU --------------------\n\n");
                   printf("\n1.Insert\n\n");
                   printf("\n2.Delete\n\n");
                   printf("\n3.Inorder Traversal\n\n");
                   printf("\n4.Preorder Traversal\n\n");
                   printf("\n5.Postorder Traversal\n\n");
                   printf("\n6.Search\n\n");
                   printf("\n7.Display\n\n");
                   printf("\n8.Exit\n\n");
                   printf("\nEnter your choice : ");
                   scanf("%d",&choice);

                   switch(choice)
                   {
                    case 1:
printf("\n\n~~~~~~~~~~~~~~~ INSERTION ~~~~~~~~~~~~~~~~\n\n");
                             printf("\nEnter the number to be inserted : ");
                             scanf("%d",&num);
                             insert(num);
                             break;
                    case 2:
printf("\n\n~~~~~~~~~~~~~~~ DELETION ~~~~~~~~~~~~~~~~\n\n");
                             printf("\nEnter the number to be deleted : ");
                             scanf("%d",&num);
                             del(num);
                             break;
                    case 3:
printf("\n\n~~~~~~~~~~~~~~~ INORDER TRAVERSAL ~~~~~~~~~~~~~~~~\n\n");
                             inorder(root);
                             break;
                    case 4:
printf("\n\n~~~~~~~~~~~~~~~ PREORDER TRAVERSAL ~~~~~~~~~~~~~~~~\n\n");
                             preorder(root);
                             break;
                    case 5:
printf("\n\n~~~~~~~~~~~~~~~ POSTORDER TRAVERSAL ~~~~~~~~~~~~~~~~\n\n");
                             postorder(root);
                             break;

                    case 6:
printf("\n\n~~~~~~~~~~~~~~~ SEARCHING ~~~~~~~~~~~~~~~~\n\n");
                             printf("\nEnter the node to be searched :");
                             scanf("%d",&info);
                             ptr=search(ptr,info);
                             if(ptr==NULL)
                             {
                             printf("\n\n------------------------\n\n");
                             printf("\nSEARCH ELEMENT NOT FOUND");
                             printf("\n\n------------------------\n\n");
                             }
                             else
                             {
                             printf("\n\n------------------------\n\n");
                             printf("\nSEARCHED ELEMENT IS %d",ptr->info);
                             printf("\n\n------------------------\n\n");
                             }
                             break;
                    case 7:
printf("\n\n~~~~~~~~~~~~~~~ DISPLAYING ~~~~~~~~~~~~~~~~\n\n");
                             display(root,1);
                             break;
                    case 8:
                             exit();
                    default:
                             printf("\n\nINVALID ENTRY !!!!! TRY AGAIN\n\n");
                   }
          }
          getch();
}

void find(int item,struct node **par,struct node **loc)
{
          struct node *ptr,*ptrsave;

          if(root==NULL)
          {
                   *loc=NULL;
                   *par=NULL;
                   return;
          }
          if(item==root->info)
          {
                   *loc=root;
                   *par=NULL;
                   return;
          }
          if(item<root->info)
                   ptr=root->lchild;
          else
                   ptr=root->rchild;
          ptrsave=root;

          while(ptr!=NULL)
          {
                   if(item==ptr->info)
                   {       *loc=ptr;
                             *par=ptrsave;
                             return;
                   }
                   ptrsave=ptr;
                   if(item<ptr->info)
                             ptr=ptr->lchild;
                   else
                             ptr=ptr->rchild;
           }
           *loc=NULL;
           *par=ptrsave;
}

void insert(int item)
{       struct node *tmp,*parent,*location;
          find(item,&parent,&location);
          if(location!=NULL)
          {
                   printf("\n\n------------------------------\n\n");
                   printf("\nITEM ALREADY PRESENT");
                   printf("\n\n------------------------------\n\n");
                   return;
          }

          tmp=(struct node *)malloc(sizeof(struct node));
          tmp->info=item;
          tmp->lchild=NULL;
          tmp->rchild=NULL;

          if(parent==NULL)
                   root=tmp;
          else
                   if(item<parent->info)
                             parent->lchild=tmp;
                   else
                             parent->rchild=tmp;
}

void del(int item)
{
          struct node *parent,*location;
          if(root==NULL)
          {
                   printf("\n\n------------------------------\n\n");
                   printf("\nTREE IS EMPTY");
                   printf("\n\n------------------------------\n\n");
                   return;
          }

          find(item,&parent,&location);
          if(location==NULL)
          {
                   printf("\n\n------------------------------\n\n");
                   printf("\nITEM NOT PRESENT IN TREE");
                   printf("\n\n------------------------------\n\n");
                   return;
          }

          if(location->lchild==NULL && location->rchild==NULL)
                   case_a(parent,location);
          if(location->lchild!=NULL && location->rchild==NULL)
                   case_b(parent,location);
          if(location->lchild==NULL && location->rchild!=NULL)
                   case_b(parent,location);
          if(location->lchild!=NULL && location->rchild!=NULL)
                   case_c(parent,location);
          free(location);
}

void case_a(struct node *par,struct node *loc )
{
          if(par==NULL)
                   root=NULL;
          else
                   if(loc==par->lchild)
                             par->lchild=NULL;
                   else
                             par->rchild=NULL;
}

void case_b(struct node *par,struct node *loc)
{
          struct node *child;


          if(loc->lchild!=NULL)
                   child=loc->lchild;
          else
                   child=loc->rchild;

          if(par==NULL )
                   root=child;
          else
                   if( loc==par->lchild)
                             par->lchild=child;
                   else
                             par->rchild=child;
}

void case_c(struct node *par,struct node *loc)
{
          struct node *ptr,*ptrsave,*suc,*parsuc;

          ptrsave=loc;
          ptr=loc->rchild;
          while(ptr->lchild!=NULL)
          {
                   ptrsave=ptr;
                   ptr=ptr->lchild;
          }
          suc=ptr;
          parsuc=ptrsave;

          if(suc->lchild==NULL && suc->rchild==NULL)
                   case_a(parsuc,suc);
          else
                   case_b(parsuc,suc);

          if(par==NULL)
                   root=suc;
          else
                   if(loc==par->lchild)
                             par->lchild=suc;
                   else
                             par->rchild=suc;

          suc->lchild=loc->lchild;
          suc->rchild=loc->rchild;
}

void preorder(struct node *ptr)
{
          if(root==NULL)
          {
                   printf("\n\n----------------------------\n\n");
                   printf("\nTREE IS EMPTY");
                   printf("\n\n----------------------------\n\n");
                   return;
          }
          if(ptr!=NULL)
          {
                   printf("%d  ",ptr->info);
                   preorder(ptr->lchild);
                   preorder(ptr->rchild);
          }
}

void inorder(struct node *ptr)
{
          if(root==NULL)
          {
                   printf("\n\n----------------------------\n\n");
                   printf("\nTREE IS EMPTY");
                   printf("\n\n----------------------------\n\n");
                   return;
          }
          if(ptr!=NULL)
          {
                   inorder(ptr->lchild);
                   printf("%d  ",ptr->info);
                   inorder(ptr->rchild);
          }
}

void postorder(struct node *ptr)
{
          if(root==NULL)
          {
                   printf("\n\n----------------------------\n\n");
                   printf("\nTREE IS EMPTY");
                   printf("\n\n----------------------------\n\n");
                   return;
          }
          if(ptr!=NULL)
          {
                   postorder(ptr->lchild);
                   postorder(ptr->rchild);
                   printf("%d  ",ptr->info);
          }
}

void display(struct node *ptr,int level)
{
          int i;
          if ( ptr!=NULL )
          {
                   display(ptr->rchild, level+1);
                   printf("\n");
                   for (i = 0; i < level; i++)
                             printf("    ");
                   printf("%d", ptr->info);
                   display(ptr->lchild, level+1);
          }

}

struct node* search(struct node *ptr,int info)
{
if(ptr!=NULL)
          if(info< ptr->info)
                   ptr=search(ptr->lchild,info);
          else if(info > ptr->info)
                   ptr=search(ptr->rchild,info);
          return(ptr);

}




Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.

Data Structures Warshall's Algorithm C Program

This program is for Warshall's Algorithm in C, and is a part of Mumbai University MCA Colleges Data Structures in C program MCA Sem 2

#include<stdio.h>
#include<conio.h>
#define MAX 20
main()
{
          int i,j,k,n;
          int w_adj[MAX][MAX],adj[MAX][MAX],path[MAX][MAX];
          clrscr();
printf("==================== WARSHALL'S ALGORITHM ===================\n");
          printf("\nEnter number of vertices : ");
          scanf("%d",&n);
          printf("\nEnter weighted adjacency matrix :\n");
          for(i=0;i<n;i++)
             for(j=0;j<n;j++)
                   scanf("%d",&w_adj[i][j]);

          printf("\nThe weighted adjacency matrix is :\n");
          display(w_adj,n);
          for(i=0;i<n;i++)
             for(j=0;j<n;j++)
                   if(w_adj[i][j]==0)
                             adj[i][j]=0;
                   else
                             adj[i][j]=1;

          printf("\nThe adjacency matrix is :\n");
          display(adj,n);

          for(i=0;i<n;i++)
             for(j=0;j<n;j++)
                   path[i][j]=adj[i][j];

          for(k=0;k<n;k++)
          {
                    printf("\nP%d is :\n",k);
                   display(path,n);
                   for(i=0;i<n;i++)
                     for(j=0;j<n;j++)
                         path[i][j]=( path[i][j] || ( path[i][k] && path[k][j] ) );
          }
          printf("Path matrix P%d of the given graph is :\n",k);
          display(path,n);
          getch();
}

display(int matrix[MAX][MAX],int n)
{
          int i,j;
          for(i=0;i<n;i++)
          {
                   for(j=0;j<n;j++)
                             printf("%3d",matrix[i][j]);
                   printf("\n");
          }

}


Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.

Data Structures Depth,Breath search C Program

This Program is for Depth First, Breath First Search in C program, and is a part of Mumbai University MCA Colleges Data Structures in C program MCA Sem 2

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

typedef enum boolean{false,true} bool;
int adj[MAX][MAX];
bool visited[MAX];
int n;
main()
{
          int i,v,choice;
          clrscr();
printf("====================== TRAVERSAL IN GRAPH =====================\n");
          create_graph();
          while(1)
          {
                   printf("\n");
                   printf("\n1. Adjacency matrix\n");
                   printf("\n2. Depth First Search using stack\n");
                   printf("\n3. Depth First Search through recursion\n");
                   printf("\n4. Breadth First Search\n");
                   printf("\n5. Adjacent vertices\n");
                   printf("\n6. Components\n");
                   printf("\n7. Exit\n");
                   printf("\nEnter your choice : ");
                   scanf("%d",&choice);

                   switch(choice)
                   {
                    case 1:
                             printf("\nAdjacency Matrix\n");
                             display();
                             break;
                    case 2:
                             printf("\nEnter starting node for Depth First Search : ");
                             scanf("%d",&v);
                             for(i=1;i<=n;i++)
                                      visited[i]=false;
                             dfs(v);
                             break;
                    case 3:
                             printf("\nEnter starting node for Depth First Search : ");
                             scanf("%d",&v);
                             for(i=1;i<=n;i++)
                                      visited[i]=false;
                             dfs_rec(v);
                             break;
                    case 4:
                             printf("\nEnter starting node for Breadth First Search : ");
                             scanf("%d", &v);
                             for(i=1;i<=n;i++)
                                      visited[i]=false;
                             bfs(v);
                             break;
                    case 5:
                             printf("\nEnter node to find adjacent vertices : ");
                             scanf("%d", &v);
                             printf("Adjacent Vertices are : ");
                             adj_nodes(v);
                             break;
                    case 6:
                             components();
                             break;
                    case 7:
                             exit(1);
                    default:
                             printf("Wrong choice\n");
                             break;
                    }
          }
          getch();
}

create_graph()
{
          int i,max_edges,origin,destin;

          printf("\nEnter number of nodes : ");
          scanf("%d",&n);
          max_edges=n*(n-1);

          for(i=1;i<=max_edges;i++)
          {
                   printf("\nEnter edge %d( 0 0 to quit ) : ",i);
                   scanf("%d %d",&origin,&destin);

                   if((origin==0) && (destin==0))
                             break;

                   if( origin > n || destin > n || origin<=0 || destin<=0)
                   {
                             printf("Invalid edge!\n");
                             i--;
                   }
                   else
                   {
                             adj[origin][destin]=1;
                   }
          }
}

display()
{
          int i,j;
          for(i=1;i<=n;i++)
          {
                   for(j=1;j<=n;j++)
                             printf("%4d",adj[i][j]);
                   printf("\n");
          }
}

dfs_rec(int v)
{
          int i;
          visited[v]=true;
          printf("%d ",v);
          for(i=1;i<=n;i++)
                   if(adj[v][i]==1 && visited[i]==false)
                             dfs_rec(i);
}

dfs(int v)
{
          int i,stack[MAX],top=-1,pop_v,j,t;
          int  ch;

          top++;
          stack[top]=v;
          while (top>=0)
          {
                   pop_v=stack[top];
                   top--;
                   if( visited[pop_v]==false)
                   {
                             printf("%d ",pop_v);
                             visited[pop_v]=true;
                   }
                   else
                             continue;

                   for(i=n;i>=1;i--)
                   {
                             if( adj[pop_v][i]==1 && visited[i]==false)
                             {
                                      top++;
                                      stack[top]=i;
                             }
                   }
          }
}

bfs(int v)
{
          int i,front,rear;
          int que[20];
          front=rear= -1;

          printf("%d ",v);
          visited[v]=true;
          rear++;
          front++;
          que[rear]=v;

          while(front<=rear)
          {
                   v=que[front];
                   front++;
                   for(i=1;i<=n;i++)
                   {

                             if( adj[v][i]==1 && visited[i]==false)
                             {
                                      printf("%d ",i);
                                      visited[i]=true;
                                      rear++;
                                      que[rear]=i;
                              }
                   }
          }
}

adj_nodes(int v)
{
          int i;
          for(i=1;i<=n;i++)
          if(adj[v][i]==1)
                   printf("%d ",i);
          printf("\n");
}

components()
{
          int i;
          for(i=1;i<=n;i++)
                   visited[i]=false;
          for(i=1;i<=n;i++)
          {
                   if(visited[i]==false)
                             dfs_rec(i);
          }
          printf("\n");
}

Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.

Shaker Sort Data Structure C Program

This Program is for Shaker Sort. This is part of Mumbai University MCA Colleges Data Structures C program.

#include<stdio.h>
#include<conio.h>
void main()
{
          int arr[10]={100,25,88,13,76,31,45,68,94,53};
          int current,sorted,walker1,walker2,temp,i;
          clrscr();
          current=0;
          sorted=0;
          printf("The original array is:\n----------------------\n");
          for(i=0;i<10;i++)
          printf("%d ",arr[i]);
          while(current<3 && sorted==0)
          {
                   walker1=9;
                   walker2=current;
                   sorted=1;

                   while(walker1>current)
                   {
                             if(arr[walker1]<arr[walker1-1])
                             //Least value bubbles to the beginning of the array
                             {
                                      sorted=0;
                                      temp=arr[walker1];
                                      arr[walker1]=arr[walker1-1];
                                      arr[walker1-1]=temp;
                             }
                             if(arr[walker2]>arr[walker2+1])
                             //Greatest value bubble to the end of the array
                             {
                                      sorted=0;
                                      temp=arr[walker2];
                                      arr[walker2]=arr[walker2+1];
                                      arr[walker2+1]=temp;
                             }
                             walker2++;
                             walker1--;
                   }
                   current++;
                   printf("\n\n\n\nAfter %d pass of Shaker Sort:\n\n",current);
                   for(i=0;i<10;i++)
                             printf("%d ",arr[i]);
          }
          getch();
}



Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.