Saturday, April 16, 2011

Binary Tree Array


import java.util.Scanner;

class NodeBT
{
    int info;
    boolean used;
}

public class BinaryTreeArray
{

    NodeBT node[]=new NodeBT[20];

    void MakeTree(int val)
    {
        node[0]=new NodeBT();
        node[0].info=val;
        node[0].used=true;
        for(int i=1;i<20;i++)
        {
            node[i]=new NodeBT();
            node[i].info=0;
            node[i].used=false;
        }
    }

    void setLeft(int p,int val)
    {

Binary Tree with Traversels– InOrder, PreOrder, PostOrder – (Recursive& Non-Recursive)


import java.util.Scanner;
import java.util.Stack;

public class Node
{
    int info;
    Node next,prev;
    Node left,right;
}

public class BinaryTree
{
    Node Insert(int val)
    {
        Node t=new Node();
        t.info=val;
        return(t);
    }
    void setLeft(Node p,int val)
    {
        if(p==null || p.left!=null)
            System.out.println("\nInvalid Insertion");
        else
            p.left=Insert(val);
    }
    void setRight(Node p,int val)
    {
        if(p==null || p.right!=null)
            System.out.println("\nInvalid insertion");
        else
            p.right=Insert(val);
    }
    void InRecur(Node Start)
    {

Circular Queue


import java.util.*;
public class CircularQueue
{
    int front,rear,size=5;
    int a[]=new int[size];

    CircularQueue()
    {
        front=rear=size-1;
    }

    void Insert(int n)
    {
        Ins:
        {
        if(rear==size-1)
            rear=0;
        else rear++;
        if(rear==front)
        {
            System.out.println("Overflow");
            break Ins;

Merging two Link List


import java.util.Scanner;
import java.util.Stack;
public class MergeList
{
    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        SingleLL s1=new SingleLL();
        SingleLL s2=new SingleLL();
        int i,j;
        System.out.println("Enter 5 Elements for Link 1");
        for(i=0;i<5;i++)
            s1.AddEnd(in.nextInt());
        System.out.println("Enter 5 Elements for Link 2");
        for(i=0;i<5;i++)
            s2.AddEnd(in.nextInt());
        SingleLL s3=new SingleLL();
        s3=s1;
        s3.end.next=s2.start;
        Stack s=new Stack();
        s3.curr=s3.start;
        while(s3.curr!=null)

Double Link List with Operations - Add in Beginning, Add at End, Del at Beg, Del at End, Del any Element, Display, Search


import java.util.Scanner;

public class Node
{
    int info;
    Node next,prev;
    Node left,right;
}

public class DoubleLL
{
    Node start=new Node();
    Node end=new Node();
    Node curr=new Node();
    int num;
   
    DoubleLL()
    {
        start=null;
        end=null;
        num=0;
    }
    void AddBeg(int val)
    {
        Node t=new Node();
        t.info=val;

Single Link-List with Operations - Add in Beginning, Add at End, Del at Beg, Del at End, Del any Element, Display, Search


import java.util.Scanner;
public class SingleLL
{
    Node start=new Node();
    Node end=new Node();
    Node curr=new Node();
    int num;

    SingleLL()
    {
        start=null;
        end=null;
        num=0;
    }
   
    void AddBeg(int val)
    {
        Node t=new Node();
        t.info=val;
        if(num++==0)
            end=t;
        else
            t.next=start;
        start=t;
    }

    void AddEnd(int val)
    {

Stack Operations – Push, Pop & Display for Characters


import java.io.IOException;
import java.util.Scanner;
public class Stack_Char
{
    char arr[];
    int top;
   
    Stack_Char()
    {
        arr=new char[30];
        top=-1;
    }

    void Push(char val)
    {
        if(top==30)
            System.out.println("Stack OVerflow");
        else
            arr[++top]=val;
    }
   
    char Pop()
    {
        if(top==-1)
        {
            System.out.println("Stack Underflow");
            return 0;
        }

Stack Operations – Push, Pop & Display for Numbers


import java.util.Scanner;
public class Stack_Num
{
    double arr[];
    int top;
   
    void Push(double val)
    {
        if(top==9)
            System.out.println("Stack OVerflow");
        else
            arr[++top]=val;
    }
   
    double Pop()
    {
        if(top==-1)
        {
            System.out.println("Stack Underflow");
            return 0;
        }
        else
        {
            return arr[top--];
        }
    }


    void Display()
    {
        if(top==-1)
               System.out.println("Stack is Empty");
        else
        {
            System.out.println("Stack is");
            for(int i=0;i<=top;i++)
                System.out.print(arr[i] + "-");
        }
        System.out.println(" ");
    }

    boolean isEmpty()
    {
        if (top<0)
            return true;
        else
            return false;
    }

    Stack_Num()
    {
        top=-1;
        arr=new double[10];
    }

    public static void main(String[] args)
    {
        Scanner in = new Scanner(System.in);
        int ch,val;
        Stack_Num s=new Stack_Num();
        while(true)
        {
            System.out.println("Choose");
            System.out.println("1 : Push\t2 : Pop\t3 : Display\t4 : Exit");
            ch=in.nextInt();
            switch(ch)
            {
                case 1:
                {
                    System.out.println("Enter Value");
                    val=in.nextInt();
                    s.Push(val);
                    break;
                }
                case 2:
                {
                    System.out.println("Popped Value is " + s.Pop());
                    break;
                }
                case 3:
                {
                    s.Display();
                    break;
                }
                case 4:
                {
                    System.exit(0);
                }
                default:
                    System.out.println("Wrong Choice");
            }
        }
    }
}

Link List with Queue


import java.util.Scanner;

public class Node
{
    int info;
    Node next,prev;
    Node left,right;
}

public class QueueLL
{
    Node start=new Node();
    Node end=new Node();
    Node curr=new Node();
    int ch,num;
    Object obj=new Object();

    QueueLL()
    {
        start=null;
        end=null;
        num=0;
    }

    void Add(int val)
    {

Link-List with Stack


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;

Depth First Search with Stack


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())
        {

Breadth First Search with Queue


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);
    }

Friday, April 15, 2011

Sequential Search 2


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);

Sequential Search 1


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)

Binary Search – Recursive


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;

Binary Search – Simple


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];

Radix Sort


import java.util.*;
class radixsort
{
                static void sort(int a[],int n)
    {
                   int large, num,l,d=1;
                   int bucket[][]=new int[10][10];
                   int b[]=new int[10];
                   large=a[0];
                   for(int i=1;i<n;i++)
                   {
                                  if(large<a[i])
                                  large=a[i];                        
                }
                   num=0;
       while(large>0)
                {
                                num++;
                                large=large/10;
                    }
                for(int p=0;p<num;p++)
        {
                                   for(int k=0;k<10;k++)
                                    b[k]=0;
                               
                                   for(int i=0;i<n;i++)
                                   {

Bubble Sort 2


import java.util.Scanner;
import java.util.Timer;
class BubbleSort2
{
    static void Bubble(int x[],int n)
    {
        int i,j,t;
        boolean switched=true;
        for(i=0;(i<n-1)&&(switched==true);i++)
        {
            switched=false;
            for(j=0;j<n-i-1;j++)
                if(x[j]>x[j+1])
                {
                    switched=true;
                    t=x[j];
                    x[j]=x[j+1];
                    x[j+1]=t;
                }
        }
    }
   
    public static void main(String args[ ])
    {
        int i,n=10;

Bubble Sort 1


import java.util.Scanner;
class BubbleSort1
{
    static void Bubble(int x[],int n)
    {
                int t,i,j;
                for(i=0;i<n-1;i++)
        for(j=0;j<n-1;j++)
            if(x[j]>x[j+1]) // Change to < for Descending Order
                        {
                            t=x[j];
                x[j]=x[j+1];
                x[j+1]=t;
                }
    }
   
    public static void main(String args[ ])
                {
        int i,n=10;
        Scanner in = new Scanner(System.in);
        System.out.print("Enter how many numbers to be sorted : ");
        n = in.nextInt();
        int x[]=new int[n];

Heap Sort


import java.util.Scanner;
class HeapSort
{
    static void Display(int a[], int n)
    {
        int i;
        for(i=0;i<n;i++)
            System.out.print("   "+a[i]);
        System.out.println("\n---------------------------------");
    }

    static void Heap(int x[],int n)
    {
        int i,elt,s,f,ivalue,pass=1;
        for(i=1;i<n;i++)
        {
            elt=x[i];
            s=i;
            f=(s-1)/2;
            while((s>0)&&(x[f]<elt))
            {
                x[s]=x[f];
                s=f;
                f=(s-1)/2;
            }
            x[s]=elt;

Insertion Sort


import java.util.Scanner;
class InsertsertionSort
{
    static void Insertion(int x[],int n)
    {
        int i,k,y;
        for(k=1;k<n;k++)
        {
            y=x[k];
            for(i=k-1;i>=0&&y<x[i];i--)
                x[i+1]=x[i];
            x[i+1]=y;
        }
    }
   
    public static void main(String args[ ])
    {
                int i,n=6;
        Scanner in = new Scanner(System.in);
        int x[]=new int[n];
        System.out.println("Enter numbers");
        for(i=0;i<n;i++)
            x[i] = in.nextInt();
        Insertion(x,n);

Link Sort - Sorted Link List


import java.util.Scanner;
public class Node
{
    int info;
    Node next,prev;
    Node left,right;
}

public class LinkSort
{
    Node start=new Node();
    Node end=new Node();
    Node curr=new Node();
    int num;

    LinkSort()
    {
        start=null;
        end=null;
        num=0;
    }
               
    void Add(int val)
    {
        Node t=new Node();
        t.info=val;
        if(num++==0)
            start=t;

Link Sort - Sorted Link List


Merge Sort


import java.util.Scanner;
class MergeSort
{
                static void Merge(int x[],int n)
    {
        int sub[] = new int[25];
        int i,j,k,l1,l2,u1,u2,size;
        size=1;    
        while(size<n)
        {
            l1=0;                       
            k=0;                      
            while((l1+size)<n)     
            {
                l2=l1+size;        
                u1=l2-1;
                u2=((l2+size-1)<n)?(l2+size-1):(n-1);
                for(i=l1,j=l2;i<=u1 && j<=u2;k++)
                    if(x[i]<=x[j])
                        sub[k]=x[i++];
                    else
                        sub[k]=x[j++];
                for(;i<=u1;k++)
                    sub[k]=x[i++];

                for(;j<=u2;k++)
                    sub[k]=x[j++];
                l1=u2+1;
            }
            for(i=l1;k<n;i++)
                sub[k++]=x[i];
            for(i=0;i<n;i++)
                x[i]=sub[i];
            size*=2;
        }
    }
   
    public static void main(String args[ ])
                {
                                int i,n=10;
        Scanner in = new Scanner(System.in);
        System.out.print("Enter how many numbers to be sorted : ");
        n = in.nextInt();
        int x[]=new int[n];
        System.out.println("Enter numbers");
        for(i=0;i<n;i++)
            x[i] = in.nextInt();
        Merge(x,n);
        System.out.println("\nSorted Elements are :");
        for(i=0;i<n;i++)
        System.out.print(x[i] + "  ");
    }
}

Non-Recursive Quick Sort

import java.util.*;
import java.util.Stack;
class QuickSortNonRec
{
    static void Display(int x[], int n)
    {
        int i;
        System.out.println(" ");
        for(i=0;i<n;i++)
            System.out.print("\t"+x[i]+ " ");
        System.out.println(" ");
    }

    static int Partition(int x[], int lb, int ub )
    {
        int a, down, temp, up,pj;
        a=x[lb];
        up=ub;
        down=lb;
        while(down<up)
        {
            while(x[down]<=a && down<up)
                down=down+1;       
            while(x[up]>a)
                up=up-1;         

            if(down<up)
            {
                temp=x[down]; 
                x[down]=x[up];
                x[up]=temp;
            }
        }
        x[lb]=x[up];
        x[up]=a;
        pj=up;
        return (pj);
    }

    static void Quick(int[] a, int lb, int ub)
    {
        Stack S = new Stack();
        S.push(lb);
        S.push(ub);
        while (!S.empty())
        {
            ub = (Integer)S.pop();
            lb = (Integer)S.pop();
            if (ub <= lb) continue;
            int i = Partition(a, lb, ub);
            if (i-lb > ub-i)
            {
                S.push(lb);
                S.push(i-1);
            }
            S.push(i+1);
            S.push(ub);
            if (ub-i >= i-lb)
            {
                S.push(lb);
                S.push(i-1);
            }
        }
    }

    public static void main(String args[ ])
    {
        int i,n=10;
        int x[]=new int[10];
        Scanner in = new Scanner(System.in);
        System.out.println("Enter 10 numbers");
        for(i=0;i<n;i++)
            x[i] = in.nextInt();
        Quick(x,0,n-1);
        System.out.println("\nSorted Elements are :");
        for(i=0;i<n;i++)
            System.out.print(x[i] + "  ");
    }
}

Recursive Quick Sort

ava.util.Scanner;
class QuickSortRec
{
    static void Display(int x[], int n)
    {
        int i;
        System.out.println(" ");
        for(i=0;i<n;i++)
            System.out.print("\t"+x[i]+ " ");
        System.out.println(" ");
    }
   
    static int Partition(int x[], int lb, int ub, int pj)
    {
        int a, down, temp, up;
        a=x[lb];
        up=ub;
        down=lb;
        while(down<up)
        {
            while(x[down]<=a && down<up)
                down=down+1;
            while(x[up]>a)

                up=up-1;
            if(down<up)
            {
                temp=x[down];
                x[down]=x[up];
                x[up]=temp;
            }
        }
        x[lb]=x[up];
        x[up]=a;
        pj=up;
        return (pj);
    }

    static void Quicksort(int x[], int lb, int ub, int n)
    {
        int j=0;
        if(lb>=ub)
            return;
        j=Partition(x, lb, ub, j);
        System.out.println("After partitioning array from index "+(lb+1)+" to "+(ub+1)+ " :\n ");
        Display(x,n);
        Quicksort(x, lb, j-1, n);
        Quicksort(x, j+1, ub, n);
    }

    public static void main(String args[ ])
    {
        int i,n=10;
        int x[]=new int[10];
        Scanner in = new Scanner(System.in);
        System.out.println("Enter numbers");
        for(i=0;i<n;i++)
        x[i] = in.nextInt();
        Quicksort(x,0,n-1,n);
        System.out.println("\nSorted Elements are :");
        for(i=0;i<n;i++)
            System.out.print(x[i] + "  ");
    }
}