Programs for Computer Engineering,Mumbai Univrsity: Data Structure

Showing posts with label Data Structure. Show all posts

Sunday, September 26, 2010

Graph : BFS and DFS

import java.io.*;
import java.util.*;
class Graph
{
  int v[][],q[];
  boolean flag[];
  int rear=-1,front=-1,size,v1,v2;

  Graph(int siz)
  {
   size=siz;
   v=new int[size][size];
   q=new int[size];
   flag=new boolean[size];
   for(int i=0;i<size;i++)
   {
for(int j=0;j<size;j++)
   {
v[i][j]=0;
}
q[i]=0;
flag[i]=false;
}
  }

  void create()throws Exception
  {
   DataInputStream di=new DataInputStream(System.in);
   char ch='y';
do
   {
System.out.println("\nEnter the edges of graph : ");
v1=Integer.parseInt(di.readLine());
v2=Integer.parseInt(di.readLine());
v[v1][v2]=1;
v[v2][v1]=1;
System.out.println("\nDo you want to enter more edges(y/n):");
String s=di.readLine();
   ch=s.charAt(0);
}while(ch!='n');
  }
  void mat()throws Exception
  {
   System.out.println("\nMatrix for the Graph is:\n");
   for(int i=0;i<size;i++)
   {
for(int j=0;j<size;j++)
   {
System.out.print(v[i][j]+" ");
}
System.out.println();
}
  }

  void bfs(int x)throws Exception
  {
   rear++;
q[rear]=x;
flag[rear]=true;
for(int i=0;i<size;i++)
   {
x=q[++front];
System.out.println(x);
for(int j=0;j<size;j++)
   {
   if(v[x][j]==1 && flag[j]==false)
{
flag[j]=true;
q[++rear]=j;
   }
}
   }
for(int i=0;i<size;i++)
   {
flag[i]=false;
}
  }

  void dfs(int i)throws Exception
  {
   System.out.println(i);
flag[i]=true;
for(int j=0;j<size;j++)
   {
   if(v[i][j]==1&&flag[j]==false)
{
dfs(j);
   }
}
  }

  public static void main(String args[ ])throws Exception
  {
   int siz,x;
DataInputStream dis=new DataInputStream(System.in);
System.out.print("\nEnter total no of vertices: ");
siz=Integer.parseInt(dis.readLine());
Graph g=new Graph(siz);
try
{
g.create();
g.mat();
System.out.println("\nBreadth First Search Traversal");
System.out.print("\nEnter vertex from which you want to traverse:");
x=Integer.parseInt(dis.readLine());
g.bfs(x);
System.out.println("\nDepth First search Traversal");
   System.out.print("\nEnter vertex from which you want to traverse:");
x=Integer.parseInt(dis.readLine());
g.dfs(x);

}
catch(Exception e)
{}
  }
}

/*
OUTPUT

C:\java\bin>javac Graph.java

C:\java\bin>java Graph

Enter total no of vertices: 4

Enter the edges of graph :
0
1

Do you want to enter more edges(y/n):
y

Enter the edges of graph :
0
2

Do you want to enter more edges(y/n):
y

Enter the edges of graph :
1
3

Do you want to enter more edges(y/n):
y

Enter the edges of graph :
2
3

Do you want to enter more edges(y/n):
n

Matrix for the Graph is:

0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

Breadth First Search Traversal

Enter vertex from which you want to traverse:0
0
1
2
3

Depth First search Traversal

Enter vertex from which you want to traverse:0
0
1
3
2
*/

Binary Tree :Preorder,Inorder,Postorder

import java.io.*;
class Node
{
   int info;
Node l,r;
Node(int data)
{
   info=data;
   l=null;
   r=null;
}
}
class Binary
{
   Node root;
   Binary()
   {
   root=null;
   }

   void insert(Node nnode)throws Exception
   {
   Node q,p;
q=null;
p=root;
   while(p!=null)
{
q=p;
if(p.info>nnode.info)
p=p.l;
else
p=p.r;
}
p=nnode;
if(q.info>p.info)
q.l=p;
else
q.r=p;

   System.out.println("value inserted....");
  }

  void search(int data)throws Exception
   {
   Node p;
p=root;
int x=0;
   while(p!=null)
{
if(p.info==data)
{
x=1;
   System.out.println("value found.....");
   break;
}
else
{
if(p.info>data)
p=p.l;
else
p=p.r;
}
   }
if(x==0)
System.out.println("value does not found.....");
  }

   void preorder(Node roo)
{
if(roo!=null)
{
System.out.println(roo.info+" ");
preorder(roo.l);
preorder(roo.r);
}
}

void inorder(Node roo)
{
if(roo!=null)
{
inorder(roo.l);
System.out.println(roo.info+" ");
inorder(roo.r);
}
}

   void postorder(Node roo)
{
if(roo!=null)
{
postorder(roo.l);
postorder(roo.r);
System.out.println(roo.info+" ");
}
}

void del(int data)throws Exception
   {
   Node q,p;
q=null;
p=root;
   while(p!=null)
{
if(p.info==data)
break;
if(p.info>data)
{
q=p;
p=p.l;
}
else
{
q=p;
p=p.r;
}
}
if(p!=null)
{
if(p.l==null&&p.r==null)
{
if(q.info>p.info)
q.l=null;
else
q.r=null;
}
if(p.l==null&&p.r!=null)
{
if(q.info>p.info)
q.l=p.r;
else
q.r=p.r;
}
if(p.l!=null&&p.r==null)
{
if(q.info>p.info)
q.l=p.l;
else
q.r=p.l;
}
if(p.l!=null&&p.r!=null)
{
Node x=p,z=null;
while(x.l!=null)
   {
z=x;
   x=x.l;
}
p.info=x.info;
z.l=null;
}
System.out.print("value Deleted : "+data);
}
else
System.out.println("value does not found.....");
}
   public static void main(String args[ ])throws IOException
   {
   Binary ob=new Binary();
   int c,a=1,x;
DataInputStream dis=new DataInputStream(System.in);
   while(a==1)
   {
   System.out.println("\n Main Menu");
   System.out.println("\n1:Insert value\n2:Display");
   System.out.println("3:Search value\n4:Delete");
   System.out.println("5:EXIT");
   System.out.println();
   System.out.print("Enter your choice:");

   c=Integer.parseInt(dis.readLine());

   switch(c)
   {
   case 1: try
{
   System.out.print("Enter your value:");
   x=Integer.parseInt(dis.readLine());
   Node nnode=new Node(x);
   if(ob.root==null)
   ob.root=nnode;
else
ob.insert(nnode);

}
   catch( Exception e)
   {}
   break;

   case 2: System.out.println("1:preorder");
   System.out.println("1:inorder");
System.out.println("1:postorder");
   System.out.print("Enter your choice:");
int z=Integer.parseInt(dis.readLine());
switch(z)
{
case 1:ob.preorder(ob.root);
break;
case 2:ob.inorder(ob.root);
break;
case 3:ob.postorder(ob.root);
break;
}
break;

   case 3: try
{
   System.out.print("Enter value for search:");
   x=Integer.parseInt(dis.readLine());
ob.search(x);
   }
catch(Exception e)
{}
   break;

case 4: try
{
   System.out.print("Enter value for Delete : ");
   x=Integer.parseInt(dis.readLine());
ob.del(x);
   }
catch(Exception e)
{}
   break;

   case 5: System.out.println("....EXIT....");
System.exit(1);
   break;
   }
   }
   }
}

/*
OUTPUT
C:\java\bin>javac Binary.java

C:\java\bin>java Binary

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:1
Enter your value:56

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:1
Enter your value:67
value inserted....

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:1
Enter your value:45
value inserted....

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:1
Enter your value:12
value inserted....

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:1
Enter your value:78
value inserted....

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:80

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:2
1:preorder
1:inorder
1:postorder
Enter your choice:2
12
45
56
67
78

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:3
Enter value for search:78
value found.....

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:4
Enter value for Delete : 67
value Deleted : 67
  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:2
1:preorder
1:inorder
1:postorder
Enter your choice:2
12
45
56
78

  Main Menu

1:Insert value
2:Display
3:Search value
4:Delete
5:EXIT

Enter your choice:5
....EXIT....

*/

Doubly Linked List

import java.io.*;
class Node
{
   Object info;
   Node next,pre;
   Node(Object data)
   {
   info=data;
   next=null;
   pre=null;
   }
}
class DLinkedList
{
   Node start;
   DLinkedList()
   {
   start=null;
   }
   void first(Node nnode)
   {
   nnode.next=start;
   start.pre=nnode;
   start=nnode;
   }
   void mid(Node nnode,int v)
   {
   Node p=start;
   for(int i=1;i<v-1;i++)
   {
   p=p.next;
   }
   (p.next).pre=nnode;
   nnode.next=p.next;
   nnode.pre=p;
   p.next=nnode;
   System.out.println("value inserted at "+v+" position.");
  }
   void end(Node nnode)
   {
   Node p=start;
   while(p.next!=null)
   {
   p=p.next;
   }
   p.next=nnode;
   nnode.pre=p;
   System.out.println("value inserted at end");
  }
   void display()
   {
   Node p=start;
   if(p==null)
   {
   System.out.println("\n The LinkedList is empty.");
   }
   else
   {
   System.out.print("your values are : ");
   while(p!=null)
   {
   System.out.print(p.info+" ");
   p=p.next;
   }
   }
   }
   Node search(Object data)throws Exception
   {
   Node p;
   int co=1,f=0;
   p=start;
   if(p==null)
   {
   System.out.println(" The LinkedList is empty.");
   }
   else
   {
   while((p!=null)&&(f==0))
   {
   if((p.info).equals(data)==true)
   {
   f=1;
   }
   else
   {
   p=p.next;
   co++;
   }
   }
   if((p.info).equals(data)==true)
   {
   System.out.println(p.info+" found at "+co+" place " );
   return(p);
   }
   else
   {
   System.out.println(data+" does not found");
   return(null);
   }
   }
   return(p);
  }
  void del(Object data)throws Exception
  {
   Node p=null;
   int f=0;
   if(start==null)
   {
   System.out.println(" The linked list is empty.");
   }
   try
   {
   p=search(data);
   }
   catch(Exception e){}
   if(p!=null)
   {
   if(p.pre!=null)
   {
   if(p.next==null)
   {
p.pre.next=p.next;
p=null;
   }
   else
   {
p.pre.next=p.next;
p.next.pre=p.pre;
p=null;
   }
   }
   else
   {
   if(p.pre!=null && p.next==null)
   start=null;
   else
   {
start=start.next;
   start.pre=null;
   }
   }
   }
  }

   public static void main(String args[ ])throws Exception
   {
   DLinkedList ob=new DLinkedList();
   int c,a=1,x;
   DataInputStream dis=new DataInputStream(System.in);
   while(a==1)
   {
   System.out.println("\n Main Menu \n");
   System.out.println("1:Insert value\n2:To Delete value");
   System.out.println("3:Display\n4:Search value");
   System.out.println("5:Exit");
   System.out.print("\nEnter your choice:");
   c=Integer.parseInt(dis.readLine());
   switch(c)
   {
   case 1: System.out.println("\n....INSERTION.... \n");
   System.out.print("Enter your value:");
   x=Integer.parseInt(dis.readLine());
   Node nnode=new Node(new Integer(x));
   if(ob.start==null)
   ob.start=nnode;
   else
   {
   System.out.println("\n1:Insert value at first place");
   System.out.println("2:Midle");
   System.out.println("3:Insert value at end");
   System.out.print("Enter your choice:");
   int pos=Integer.parseInt(dis.readLine());
   if(pos==1)
   ob.first(nnode);
   if(pos==2)
   {
   System.out.print("Enter position:");
   int v=Integer.parseInt(dis.readLine());
   ob.mid(nnode,v);
   }
if(pos==3)
   ob.end(nnode);
}
break;

   case 2: try
{
   System.out.print("Enter value to delete:");
   x=Integer.parseInt(dis.readLine());
ob.del(new Integer(x));
System.out.print(" value is to deleted");
}
catch(Exception e)
{}
   break;

   case 3:
   System.out.println();
   ob.display();
   break;

   case 4: try
{
   System.out.print("Enter value for search:");
   x=Integer.parseInt(dis.readLine());
Node p=null;
p=ob.search(new Integer(x));
   }
catch(Exception e)
{}
   break;

   case 5: System.out.println("\n....EXIT....");
   System.exit(1);
   break;
   default: System.out.println("\n....Wrong Choice....");
   }
   }
   }
}

/*
OUTPUT:

C:\java\bin>javac DLinkedList.java
Note: DLinkedList.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.

C:\java\bin>java DLinkedList

   Main Menu

1:Insert value
2:To Delete value
3:Display
4:Search value
5:Exit

Enter your choice:1

....INSERTION....

Enter your value:54

   Main Menu

1:Insert value
2:To Delete value
3:Display
4:Search value
5:Exit

Enter your choice:1

....INSERTION....

Enter your value:34

1:Insert value at first place
2:Midle
3:Insert value at end
Enter your choice:3
value inserted at end

   Main Menu

1:Insert value
2:To Delete value
3:Display
4:Search value
5:Exit

Enter your choice:1

....INSERTION....

Enter your value:778

1:Insert value at first place
2:Midle
3:Insert value at end
Enter your choice:1

   Main Menu

1:Insert value
2:To Delete value
3:Display
4:Search value
5:Exit

Enter your choice:1

....INSERTION....

Enter your value:898

1:Insert value at first place
2:Midle
3:Insert value at end
Enter your choice:2
Enter position:2
value inserted at 2 position.

   Main Menu

1:Insert value
2:To Delete value
3:Display
4:Search value
5:Exit

Enter your choice:3

your values are : 778 898 54 34
   Main Menu

1:Insert value
2:To Delete value
3:Display
4:Search value
5:Exit

Enter your choice:2
Enter value to delete:778
778 found at 1 place
value is to deleted
   Main Menu

1:Insert value
2:To Delete value
3:Display
4:Search value
5:Exit

Enter your choice:5

....EXIT....

*/

Queue

import java.io.*;
class Queue
{
   int size=5;
   Object item[]=new Object[size];
   int rare=0,front=0;

   boolean empty()
   {
   if((front==size)||(front==rare))
   {
   System.out.println("Queue is empty....");
   front=0;
   return(true);
   }
   else
   {
   return(false);
   }
   }
   boolean full()
   {
   if(rare==size)
   {
   System.out.println("Queue is Full..cannot insert element ");
   return(true);
   }
   else
   {
   return(false);
   }
   }

   void inQueue(Object o,Queue z)
   { if(z.full())
   {
   }
   else
   {
   item[rare++]=o;
   System.out.println(" value is inserted.");
   }
   }

   Object deQueue(Queue z)
   {
   if(z.empty())
   {
   return(null);
   }
   else
   {
   return(item[front++]);
   }
   }

   void display(Queue z)
   {
   if(z.empty())
   {
   }
   else
   {
   System.out.println("values in Queue are:");
   for(int i=front;i<rare;i++)
   {
   System.out.print(" "+item[i]);
   }
   System.out.println();
   }
   }

}
class Queues
{
   public static void main(String args[ ])throws IOException
   {
   Queue ob=new Queue();
   int c,a=1;

   DataInputStream dis=new DataInputStream(System.in);
   while(a==1)
   {
   System.out.println();
   System.out.println("1:to enter value into Queue:");
   System.out.println("2:to delete the value from Queue:");
   System.out.println("3:display Queue:");
   System.out.println("4:to check Queue is full :");
   System.out.println("5:exit");
   System.out.println();
   System.out.print("Enter your choice:");
   System.out.println();

   c=Integer.parseInt(dis.readLine());

   switch(c)
   {
   case 1:
   System.out.println("Enter your value:");
   int x=Integer.parseInt(dis.readLine());
   ob.inQueue(new Integer(x),ob);

   break;

   case 2: Object z=ob.deQueue(ob);
   if(z!=null)
   {
   System.out.println();
   System.out.println("value deleted:"+z);
   }
   break;

   case 3:
   System.out.println();
   ob.display(ob);
   break;

   case 4:
   if(ob.full())
   {
   System.out.println();
   }
   else
   {
   System.out.println("Queue is not Full.... ");
   }
   break;

   case 5:
   x=0;
   System.exit(1);
   break;

   }
   }

   }

}

LINKED LIST

import java.io.*;

class Node
{
   Object info;
Node next;

Node(Object data)
{
   info=data;
   next=null;
}
}
class LinkedList
{
   Node start;
   LinkedList()
   {
   start=null;
   }
   void first(Node nnode)//for first node
   {
   nnode.next=start;
   start=nnode;
   }
   void mid(Node nnode,int v)//for middle node
   {
   Node p=start;
   for(int i=1;i<(v-1);i++)
   {
  p=p.next;
   }
nnode.next=p.next;
p.next=nnode;
   System.out.println("value inserted at "+v+" position.");
  }
   void end(Node nnode)//for last node
   {
   Node p=start;
while(p.next!=null)
{
p=p.next;
}
p.next=nnode;
   System.out.println("value inserted at end");
   }
   void display()//dsplay link list
   {
   Node p=start;
if(p==null)
{
System.out.println("\n The LinkedList is empty.");
}
else
{
   System.out.print("your values : ");
   while(p!=null)
   {
   System.out.print(" "+p.info);
   p=p.next;
   }
   System.out.println();
}
   }
   void search(Object data)throws IOException//search value in link list
   {
   Node p;
int co=1,f=0;
p=start;
if(p==null)
{
System.out.println(" The LinkedList is empty.");
   }
else
   {
while((p!=null)&&(f==0))
{
if((p.info).equals(data)==true)
{
   f=1;
}
else
{
   p=p.next;
   co++;
}
}
if((p.info).equals(data)==true)
{
System.out.println(p.info+" found at "+co+" place " );
}
else
{
System.out.println(data+" does not found");
}
   }
  }
   void del(Object data)throws Exception//delete perticular value in link list
   {
   Node p=start;
Node q=start.next;
int f=0;
   if(start==null)
{
  System.out.println(" The linked list is empty.");
   }
if((p.info).equals(data)==true)
   {
  System.out.println(data+" deleted" );
  start=p.next;
   }
   else
{
   while((f==0)&&(p!=null))
{
   if((p.info).equals(data)!=true)
   {
   q=p;
   p=p.next;
   }
   else
   {
   f=1;
   }
  }
}
   if(f==1)
{
  q.next=p.next;
  System.out.println(data+" deleted");
}
else
{
System.out.println("value does not match");
   }
}

   public static void main(String args[ ])throws IOException
   {
   LinkedList ob=new LinkedList();
   int c,a=1,x;

   DataInputStream dis=new DataInputStream(System.in);
   while(a==1)
   {
   System.out.println("\nMain menu");
   System.out.println("\n1:insert value");
   System.out.println("2:to delete value");
   System.out.println("3:display");
   System.out.println("4:search value");
   System.out.println("5:exit");
   System.out.print("\nEnter your choice:");

   c=Integer.parseInt(dis.readLine());

   switch(c)
   {
   case 1: System.out.print("\nEnter your value:");
   x=Integer.parseInt(dis.readLine());
   Node nnode=new Node(new Integer(x));
   if(ob.start==null)
   {
   ob.start=nnode;
   }
   else
   {
   System.out.println("\n1:to insert value at first place");
   System.out.println("2:midle");
   System.out.println("3:to insert value at end");
   System.out.print("\nEnter your choice:");
   int pos=Integer.parseInt(dis.readLine());
   if(pos==1)
   {
   ob.first(nnode);
   }
   if(pos==2)
   {
   System.out.println("Enter position:");
   int v=Integer.parseInt(dis.readLine());
   ob.mid(nnode,v);
   }
   if(pos==3)
   {
   ob.end(nnode);
   }
   }
   break;

   case 2: try
   {
   System.out.print("Enter value to delete:");
   x=Integer.parseInt(dis.readLine());
   ob.del(new Integer(x));
   }
   catch(Exception e)
   {}
   break;

   case 3:
   System.out.println();
   ob.display();
   break;

   case 4: try
   {
   System.out.print("Enter value for search:");
   x=Integer.parseInt(dis.readLine());
   ob.search(new Integer(x));
   }
   catch(Exception e)
   {}
   break;

   case 5:
   System.exit(1);
   break;
   }
   }
   }
}

/*OutPut:

E:\java\bin>javac LinkedList.java

E:\java\bin>java LinkedList

Main menu

1:insert value
2:to delete value
3:display
4:search value
5:exit

Enter your choice:1

Enter your value:112

Stack

import java.io.*;
class Stack
{
Object ob[]=new Object[5];
int top=-1;
void push(Object x)
{
   if(top==4)
   {
   System.out.println("Stack is full");
   }
   else
   {
   ob[++top]=x;
   }
}
void pop()
{
  if(top==-1)
  {
   System.out.println("stack is empty");
   }
   else
   System.out.println("pop item:-"+ob[top--]);
  }
  void dis()
  {
   for(int i=top;i<=0;--i)
   System.out.println(ob[i]);
  }
  public static void main(String ar[])
  {
   DataInputStream p=new DataInputStream(System.in);
   Stack s=new Stack();
   int ch;
   Object x;
   try
   {
   while(true)
   {
   System.out.println("1.push \n 2.pop\n 3.dis\n 4.exit");
   System.out.println("Select:-");
   ch=System.in.read();
   switch(ch)
   {
   case 1:
   x=p.readLine();
   s.push(x);
   break;
   case 2:s.pop();
   break;
   case 3: s.dis();
   break;
// case 4: exit();
   }
   }
   }
   catch(Exception e)
   {}

  }

}

Program for Factorial using Recursion

import java.io.DataInputStream;
class Fact
{
int fac(int n)
{
if(n==1)
{
return(1);
}
else
{
return(n*fac(n-1));
}
}
public static void main(String args[])throws Exception
{
Fact b=new Fact();
int f,n;
DataInputStream o=new DataInputStream(System.in);
System.out.println("Enter the value:");
n=Integer.parseInt(o.readLine());
f= b.fac(n);
System.out.println(" ");
System.out.println("Factorial of "+n+" = "+f);
}
}

/*
Enter the value:
5

Factorial of 5 = 120

Process completed.

*/

Labels

Sunday, September 26, 2010

import java.io.*;