Home All posts

Friday, April 15, 2011

Link-List with Stack

  Author : Unknown     No comments
April 15, 2011


import java.util.Scanner;
public class StackLL
{
    Node start=new Node();
    Node top=new Node();
    Node curr=new Node();
    int ch,num;

    StackLL()
    {
        num=0;
        start=null;
        top=null;
    }

    void Push(int val)
    {
        Node t=new Node();
        t.info=val;
        t.next=null;
        if(num++==0)
            start=t;
        else
            top.next=t;
        top=t;

    }

    void Pop()
    {
        curr=start;
        if(num==0)
            System.out.println("Stack is Empty");
        else
        {
            if(top==start)
            {
                start=null;
                top=null;
                num=0;
            }
            else
            {
                while(curr.next!=top)
                    curr=curr.next;
                top=curr;
            }
        }
    }

    void Display()
    {
        curr=start;
        System.out.print("Bottom -> ");
        while(curr!=null)
        {
            System.out.print(curr.info + " -> ");
            curr=curr.next;
        }
        System.out.println("Top");
    }

    public static void main(String args[])
    {
        int ch,val;
        StackLL s=new StackLL();
        Scanner in = new Scanner(System.in);
        while(true)
        {
            System.out.println("\n-----------------------------------");
            System.out.println("Enter your Choice");
            System.out.println("1 : Push\t2 : Pop\t3 : Display\t4 : Exit");
            ch=in.nextInt();
            switch(ch)
            {
                case 1:
                {
                    System.out.print("Enter a Number = ");
                    val=in.nextInt();
                    s.Push(val);
                    break;
                }
                case 2:
                {
                    s.Pop();
                    break;
                }
                case 3:
                {
                    s.Display();
                    break;
                }
                case 4:
                    System.exit(0);
                    break;
                default : continue;
            }
        }
    }
}


By
Read More

Depth First Search with Stack

  Author : Unknown     No comments
April 15, 2011


import java.util.Scanner;
class Stack
{
    int stk[]=new int[10];
    int top;
    Stack()
    {
        top=-1;
    }
    void Push (int item)
    {
        if (top==9)
            System.out.println("Stack overflow");
        else
        stk[++top]=item;
    }
    boolean isEmpty()
    {
    if (top<0)
        return true;
    else
        return false;
    }
    int Pop()
    {
        if (isEmpty())
        {

            System.out.println("Stack underflow");
            return 0;
        }
        else
            return (stk[top--]);
    }
    void stackTop()
    {
        if(isEmpty())
            System.out.println("Stack underflow ");
        else
            System.out.println("Stack top is "+(stk[top]));
    }
    void Display()
    {
        System.out.println("Stack-->");
        for(int i=0;i<=top;i++)
            System.out.println(stk[i]);
    }
}
class Graph
{
    int MAXSIZE=51;
    int adj[][]=new int[MAXSIZE][MAXSIZE];
    int visited[]=new int [MAXSIZE];
    Stack s=new Stack();
    void createGraph()
    {
        int n,i,j,parent,adj_parent,initial_node;
        int ans=0,ans1=0;
        System.out.print("\nEnter total number elements in a Undirected Graph :");
        n=getNumber();
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                adj[i][j]=0;
        for (int c=1;c<=50;c++)
            visited[c]=0;
        System.out.println("\nEnter graph structure for BFS  ");
        do
        {
            System.out.print("\nEnter parent node :");
            parent=getNumber();
            do
            {
                System.out.print("\nEnter adjacent node for node "+parent+ " : ");
                adj_parent=getNumber();
                adj[parent][adj_parent]=1;
                adj[adj_parent][parent]=1;
                System.out.print("\nContinue to add adjacent node for "+parent+"(1/0)?");
                ans1= getNumber();
            } while (ans1==1);
        System.out.print("\nContinue to add graph node?");
        ans= getNumber();
        }while (ans ==1);
        System.out.print("\nAdjacency matrix for your graph is :\n");
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++)
            System.out.print(" "+adj[i][j]);
            System.out.print("\n");
        }
        System.out.println("\nYour Undirected Graph is :");
        for(i=1;i<=n;i++)
        {
            System.out.print("\nVertex "+i+"is connected to : ");
            for (j=1;j<=n;j++)
            {
                if (adj[i][j]==1)
                    System.out.print(" "+j);
            }
        }
        System.out.println("\nEnter the initial node for BFS traversal:");
        initial_node=getNumber();
        DFS (initial_node, n);
    }
    void DFS (int initial_node,int n)
    {
        int u,i;
        s.top = -1;
        s.Push(initial_node);
        System.out.println("\nDFS traversal for given graph is : ");
        while(!s.isEmpty())
        {
            u=s.Pop();
            if(visited[u]==0)
            {
                System.out.print("\n"+u);
                visited[u]=1;
            }
            for (i=1;i<=n;i++)
            {
                if((adj[u][i]==1) && (visited[i]==0))
                {
                    s.Push(u);
                    visited[i]=1;
                    System.out.print(" "+i);
                    u = i;
                }
            }
        }
    }
    int getNumber()
    {
        Scanner in = new Scanner(System.in);
        int ne=0;
        ne=in.nextInt();
        return ne;
    }
}
class DFS
{
    public static void main(String args[])
    {
        Graph g=new Graph();
        g.createGraph();
    }
}

By
Read More

Breadth First Search with Queue

  Author : Unknown     No comments
April 15, 2011


import java.io.*;
import java.util.Scanner;
class Queue
{
    int items[]=new int[10];
    int front,rear;
    Queue()
    {
        front=0;
        rear=-1;
    }

    void Insert(int e)
    {
        if(rear==9)
            System.out.println("Queue overflow");
        else
            items[++rear]=e;
    }

    int Empty()
    {
        return(rear<front? 1:0);
    }


    int Remove()
    {
        int x=0;
        if(Empty()==1)
        {
            System.out.println("Queue Underflow");
            return 0;
        }
        else
        {
            x=items[front++];
            return x;
        }
    }
}

class Graph
{
    int MAXSIZE=10;
    int adj[][]=new int[MAXSIZE][MAXSIZE];
    int visited[]=new int [MAXSIZE];

    Queue q=new Queue();

    void createGraph()
    {
        int n,i,j,parent,adj_parent,initial_node;
        int  ans=0,ans1=0;
        System.out.print("\nEnter total number elements in a Undirected Graph :");
        n=getNumber();
        for (i=1;i<=n;i++)
            for( j=1;j<=n;j++)
                adj[i][j]=0;
        for (int c=1;c<=50;c++)
            visited[c]=0;
        System.out.println("\nEnter graph structure for BFS  ");
        do
        {
            System.out.print("\nEnter parent node :");
            parent=getNumber();
            do
            {
                System.out.print("\nEnter adjacent node for node "+parent+ " : ");
                adj_parent=getNumber();
                adj[parent][adj_parent]=1;
                adj[adj_parent][parent]=1;
                System.out.print("\nContinue to add adjacent node for "+parent+"(1/0)?");
                ans1= getNumber();
            } while (ans1==1);
            System.out.print("\nContinue to add graph node?");
            ans= getNumber();
        }while (ans ==1);
        System.out.print("\nAdjacency matrix for your graph is :\n");
        for (i=1;i<=n;i++)
        {
            for (j=1;j<=n;j++)
            System.out.print(" "+adj[i][j]);
            System.out.print("\n");
        }
        System.out.println("\nYour Undirected Graph is :");
        for (i=1;i<=n;i++)
        {
            System.out.print("\nVertex "+i+"is connected to : ");
            for (j=1;j<=n;j++)
            {
                if (adj[i][j]==1)
                    System.out.print(" "+j);
            }
        }
        System.out.println("\nEnter the initial node for BFS traversal:");
        initial_node=getNumber();
        BFS (initial_node, n);
    }

    void BFS (int initial_node,int n)
    {
        int u,i;
        u = initial_node;
        visited[initial_node]=1;
        System.out.println("\nBFS traversal for given graph is : ");
        System.out.print(initial_node);
        q.Insert(initial_node);
        while(q.Empty()==0)
        {
            u = q.Remove();
            for (i=1;i<=n;i++)
            {
                if((adj[u][i]==1) && (visited[i]==0))
                {
                    q.Insert(i);
                    visited[i]=1;
                    System.out.print(" "+i);
                }
            }
        }
    }

    int getNumber()
    {
        int ne=0;
        Scanner in = new Scanner(System.in);
        ne=in.nextInt();
        return ne;
    }
}

public class BFS
{
    public static void main(String args[])
    {
        Graph g=new Graph();
        g.createGraph();
    }
}

By
Read More

Sequential Search 2

  Author : Unknown     No comments
April 15, 2011


import java.io.*;
class seqsearch
{
  public static void main(String args[]) throws IOException
  { searching x=new searching();
                DataInputStream in=new DataInputStream(System.in);
                int n=10,key=0;
                int a[]=new int[n];
                System.out.print("Enter number of elements ");
                n=Integer.parseInt(in.readLine());
               
                System.out.print("Enter elements");
               
                for(int i=0;i<n;i++)
                {
      a[i]=Integer.parseInt(in.readLine());
    }
   
    System.out.print("Enter number to be searched-");
   
    key=Integer.parseInt(in.readLine());
     
    int z=x.search(a,n,key);
    
     System.out.println("Element present at "+(z+1)+"location");
                 
   }  
  }
 
  class searching
  {           
                int search(int a[],int n,int key)
                {
                                for(int i=0;i<n;i++)
                                {
                                                if(a[i]==key)
                                                                return (i);
                 }
                 return 0;
                      
                }
                }             

By
Read More

Sequential Search 1

  Author : Unknown     No comments
April 15, 2011


import java.io.*;
import java.util.*;
class seqsearch
{
public static void main(String arg[])
{    
      int a[]=new int[50];
      boolean flag=false;
                  DataInputStream in=new DataInputStream(System.in);
try{
                               
                    System.out.println("Enter the no of elements in d array");
                    int n=Integer.parseInt(in.readLine());
                    for(int i=0;i<n;i++)
                    {
                                  System.out.println("Enter the "+(i+1)+" element of d array");
                                  a[i]=Integer.parseInt(in.readLine());
                    }
                    System.out.println("Enter the element to be searched");
                    int num=Integer.parseInt(in.readLine());
                    for(int i=0;i<n;i++)
                    {
                                  if(a[i]==num)

                                  {
                                    flag=true;
                                    System.out.println("Element found at pos"+(i+1));
                                    break;
                      }
                      else
                      flag=false;
                    }
                    if(flag==false)
                                System.out.println("Element not found");
 }
 catch(Exception e){}
}
}

By
Read More

Binary Search – Recursive

  Author : Unknown     No comments
April 15, 2011


import java.util.Scanner;
public class BinSearchRecur
{
    static void BinSearch(int x[],int low,int high,int key)
    {
        int mid;
        if(low<=high)
        {
            mid=(low+high)/2;
            if(x[mid]==key)
                System.out.println("Element found at "+mid);
            if(x[mid]<key)
                BinSearch(x,mid+1,high,key);
            else
                BinSearch(x,low,mid-1,key);

        }
    }
    public static void main(String[] args)
    {
        Scanner in=new Scanner(System.in);
        int x[]=new int[10];
        int KEY,n=10;

        System.out.println("Enter 10 number in ascending order");
        for(int i=1;i<10;i++)
            x[i] = in.nextInt();
        System.out.print("Enter the number to be searched  : ");
        KEY = in.nextInt();
        BinSearch(x,0,n-1,KEY);
    }
}

By
Read More

Binary Search – Simple

  Author : Unknown     No comments
April 15, 2011


import java.util.Scanner;
class BinarySearch
{
    static int Binary_Search(int K[ ],int n,int KEY)
    {
        int low=1,high=n,mid;
        mid=(low+high)/2;
        while (high>=low)
        {
            if (K[mid]==KEY)
                return(mid);
            else
            {
                if(KEY>K[mid])
                    low=mid+1;
                else
                    high=mid-1;
                mid=(low+high)/2;
            }
        }
        return(-1);
    }
    public static void main(String args[ ])
    {
        int i,KEY,flag=0;
        int x[] = new int[25];

        Scanner in = new Scanner(System.in);
        System.out.println("Enter 10 number in ascending order");
        for(i=1;i<10;i++)
            x[i] = in.nextInt();
        System.out.print("Enter the number to be searched  : ");
        KEY = in.nextInt();
        flag = Binary_Search(x,10,KEY);
        if (flag == -1)
            System.out.println(" Number Not present in the given array");
        else
            System.out.println(" Number "+KEY+" found at "+flag+" location in the array");
    }
}

By
Read More
Subscribe to: Posts ( Atom )