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.
0 comments

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.
0 comments

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.
0 comments

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.
0 comments

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.
0 comments