Tree traversal (preorder,inorder,postorder) using linklist (c++)

#include<iostream>
using namespace std;

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

/**********Element insertion*****************/

node* insert(node *root,int data)
{
    if(root==NULL)
    {
        root=new node();
        root->data=data;
        root->left=root->right=NULL;
    }
    else if(data<=root->data)
    {
        root->left=insert(root->left,data);
    }
    else
    {
        root->right=insert(root->right,data);
    }
    return root;
}

/*************Printing in preorder*************/

void preorder(node *root)
{
    if(root==NULL)
    return;

    cout<<" "<<root->data;
    preorder(root->left);
    preorder(root->right);
}

/**************printing in inorder************/

void inorder(node *root)
{
    if(root==NULL)
    return;

    inorder(root->left);
    cout<<" "<<root->data;
    inorder(root->right);
}

/**********printing in postorder************/

void postorder(node *root)
{
    if(root==NULL)
    return;
    postorder(root->left);
    postorder(root->right);
    cout<<" "<<root->data;

}

/**************Driver Function***********/
int main()
{
    node *root=NULL;

    root=insert(root,10);
    root=insert(root,20);
    root=insert(root,30);
    root=insert(root,15);
    root=insert(root,9);
    root=insert(root,25);


    cout<<"\n preorder"<<endl;
    preorder(root);
    cout<<"\n Inorder"<<endl;
    inorder(root);
    cout<<"\n Postorder"<<endl;
    postorder(root);
    cout<<endl;


    return 0;
}

output:

Read More

Implementation of queue using linklist (C++)

#include<iostream>
using namespace std;

struct queue
{
    int data;
    struct queue *next;
};

 queue *front=NULL;
 queue *rear=NULL;
    int count=0;
/**********Inserting Element in Queue******************/
void enqueue(int x)
{
  queue *temp;
  temp=new queue();
  temp->data=x;
  temp->next=NULL;
  if(front==NULL && rear==NULL)
  {
      front=rear=temp;
      count++;
  }
  else
  {
      rear->next=temp;
      rear=temp;
      count++;
  }
}
/*********displaying elements in Queue********************/

void display(int count)
{
    queue *temp;
    temp=front;
    for(int i=0;i<count;i++)
    {
        cout<<temp->data<<" ";
        temp=temp->next;
    }
}
/*******Removing element from Queue*********************/

void dequeue()
{
    if(front==NULL)
    {
        cout<<"Queue is empty"<<endl;
    }
    else
    {
        queue *temp;
        temp=front;
        front=front->next;
        delete temp;
        count--;

        cout<<" \n Item Dequeued Successfully"<<endl;
    }
}

/****************Driver Function************************/

int main()
{
    int choice;
    int x;
    do
    {
        cout<<"Enter element is Queue :"<<endl;
        cin>>x;
        enqueue(x);


    cout<<"Do you want to enQueue again?"<<endl;
    cin>>choice;
    }while(choice==1);

    cout<<"After Enqueue"<<endl;
    display(count);

    do
    {
    dequeue();
    cout<<"Do you want to DeQueue again?"<<endl;
    cin>>choice;
    }while(choice==1);

    cout<<"After dequeue"<<endl;
    display(count);

    return 0;

}

Read More

Circular queue using array(insertion, deletion)

#include <iostream>

using namespace std;

int Q[10];

int size=10;

int count=0;

int rear=0;

int front=0;

void enQ(int element)

{

   if(count==size)

   {

       cout<<"Queue Overflow"<<endl;

   }

   else

   {

       Q[rear]=element;

       rear=(rear+1)%size;

       count++;

   }

}

void DeQ()

{

    if(count==0)

    {

        cout<<"Under Flow"<<endl;

    }

    else

    {

        Q[front]=0;

        front=(front+1)%size;

        count--;

    }

}

bool isempty()

{

    if(count==0)

    {

        return true;

    }

}

int main()

{

    int element;

    int e;

    if(isempty()==true)

    {

        cout<<"Queue is empty"<<endl;

    }

    /*************Enqueue*************/

    do

    {

    cout<<"Enter element in queue:"<<endl;

    cin>>element;

    enQ(element);

    cout<<"Do you want enqueue again?" <<endl;

    cin>>e;

    }while(e==1);

    /************display*************/

    cout<<"After inserting value in circular queue"<<endl;

    for(int i=front;i<=count;i++)

    {

        cout<<Q[i]<<" ";

    }

    /***************deletion***************/

    int d;

    cout<<"Do you want to delete from the queue(1=y): "<<endl;

    cin>>d;

    if(d==1)

    {

        int c;

        do

        {

        DeQ();

        cout<<"DO you want to enqueue again?(1=y)"<<endl;

        cin>>c;

        }while(c==1);

    }

    /************display*************/

    cout<<"After Dequeuing"<<endl;

    for(int i=front;i<=count;i++)

    {

        cout<<Q[i]<<" ";

    }

    return 0;

}

Read More

Doubly Linklist (insertion,deletion of a node)

#include <iostream>
using namespace std;
struct node2
{
    int data2;
    struct node2 *previous;
    struct node2 *next2;
};
int main()
{
    node2 *head2;
    node2 *last2;
    node2 *temp2;
    last2=0;
    int choice;
    do
    {
    cout<<"Enter data in Doubly node:"<<endl;
    temp2=new node2();
    cin>>temp2->data2;
    if(last2==0)
    {
        temp2->next2=0;
        temp2->previous=0;
        last2=head2=temp2;
    }
    else
    {
        temp2->next2=0;
        temp2->previous=last2;
        last2->next2=temp2;
        last2=temp2;
    }
    cout<<"\nDo you want to create a new node (1=yes,0=NO): ";
    cin>>choice;
    }while(choice==1);
    cout<<"Printing from start"<<endl;
    temp2=head2;
    while(temp2!=0)
    {
      cout<<temp2->data2<<" ";
     temp2=temp2->next2;
    }
    cout<<"\n Printing from end"<<endl;
    temp2=last2;
    while(temp2!=0)
    {
      cout<<temp2->data2<<" ";
     temp2=temp2->previous;
    }
   /******************************************/
       do
    {
    cout<<"Enter data"<<endl;
    temp2=new node2();
    cin>>temp2->data2;
    if(last2==0)
    {
        temp2->next2=0;
        temp2->previous=0;
        last2=head2=temp2;
    }
    else
    {
        temp2->next2=head2;
        temp2->previous=0;
        head2->previous=temp2;
        head2=temp2;
    }
    cout<<"\nDo you want to create a new node (1=yes,0=NO): ";
    cin>>choice;
    }while(choice==1);
    cout<<"\n Printing from start"<<endl;
    temp2=head2;
    while(temp2!=0)
    {
      cout<<temp2->data2<<" ";
     temp2=temp2->next2;
    }
    return 0;
}

Read More

Singly Linklist in C++ (insertion at satart,middle and end. Searching in linklist. Deletion of any node)

#include <iostream>

using namespace std;
struct node
{
    int data;
    struct node *next;
};

int main()
{
    node *head;
    node *temp;
    node *last;

    last=0;
    int choice;

   do
    {
        temp=new node();
        cout<<"Enter values in a node:"<<endl;
        cin>>temp->data;
        if(last==0)
        {
            head=last=temp;

        }
        else
        {
            last->next=temp;
            last=temp;
        }
        cout<<"Enter your choice:"<<endl;
        cin>>choice;
    }while(choice==1);

        last->next=0;
        temp=head;

        while(temp!=0)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
        /************insertion at the start of the node***************************/
        do{
        temp=new node();
        cout<<"Enter value at the start of the node: "<<endl;
        cin>>temp->data;

        temp->next=head;
        head=temp;

        cout<<"Enter your choice: "<<endl;
        cin>>choice;
        }while(choice==1);

        temp=head;
        while(temp!=0)
        {
            cout<<temp->data<<" ";
            temp=temp->next;

        }

        /************** iNSERTION AT MIDDLE OF THE LINKLIST***********/
        node *temp2;
        int location=0;

        cout<<"\n Enter your location"<<endl;
        cin>>location;

        temp=new node();
        cout<<"\n Enter data in node: "<<endl;
        cin>>temp->data;

        temp2=head;

        while(location-1>0)
        {
            location--;
            temp2=temp2->next;
        }
        temp->next=temp2->next;
        temp2->next=temp;

        temp=head;
        while(temp!=0)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }

    /**************************Search traverse*************/
    int value;
    int count=1;
    int flag=0;
    cout<<"\n Enter value you want to search in LinkList: "<<endl;
    cin>>value;
    temp=head;
    while(temp!=0)
    {
        if(temp->data==value)
        {
            cout<<"Data found successfully at index "<<count<<endl;
            flag=1;
            break;
        }
        else
        {
            temp=temp->next;
            count++;
        }
    }

    if(flag==0)
    {
        cout<<"Data not found"<<endl;
    }
    /**************************deleting node******************/
    int b=0;
    int item;
    node *temp3;
    cout<<"which data do you want to delete?"<<endl;
    cin>>item;
    temp=head;
    while(temp->next->next!=0)
    {
        if(temp->next->data==item)
        {
            cout<<"Data found successfully"<<endl;
            b=1;
            break;
        }
        else
        {
            temp=temp->next;
            temp3=temp->next;
        }
    }

    if(b==0)
    {
        cout<<"Data not found"<<endl;
    }
    else
    {
        temp->next=temp->next->next;
        delete temp3;
    }

    temp=head;
        while(temp!=0)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }


    return 0;
}

Read More

Binary Search in C++

#include <iostream>
using namespace std;

void binarysearch(int arr[],int s,int size);
void binarysearch(int arr[],int s,int size)
{
    int lower=0,higher=size-1,m;
    while(lower<=higher)
    {
        m=(lower+higher)/2;
        if(s==arr[m])
        {
        cout<<"Search found at index"<<m<<endl;
        return;
        }
        else if(s>arr[m])
            lower=m+1;
        else
            higher=m-1;
    }
    cout<<"Search not found"<<endl;
}

/******************************************/

int main()
{
    int n[5],s,size;
    cout<<"Enter value in array of type int:"<<endl;
    for(int i=0;i<5;i++)
    {
     cin>>n[i];
    }
    cout<<"Enter number in Search: ";
    cin>>s;
    size=sizeof(n)/sizeof(n[0]);
    binarysearch(n,s,size);
    return 0;
}

Read More

Selection sorting Dynamically

Worst-Complexity: n ^ 2

Average-Complexity: n ^ 2

Best-Complexity: n ^ 2

Space-Complexity:  1

#include<iostream>
using namespace std;

/*********************sorting function********************/

void selection_Sort(int arr[], int n)
{
    int i, j, min;

    for (i = 0; i < n-1; i++)
    {
        min = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min])
            min = j;

          swap(arr[min],arr[i]);
    }
} 

 /****************** Printing values*****************************/

void print_Array(int arr[], int size) 

{ 

    int i; 

    for (i=0; i < size; i++) 

        cout<<arr[i];

cout<<endl; 

} 

/**********************Driver function*************************/

int main() 

{ 

int *arr;

int n;

cout<<"How many numbers your want to sort:"<<endl;

    cin>>n;

    arr=new int[n];

    cout<<"Enter the numbers:"<<endl;

for(int i=0;i<n;i++)

{

cin>>arr[i];

}    

selection_Sort(arr, n); 

    cout<<"After sorting array: \n"<<endl; 

    print_Array(arr, n); 

    return 0; 

} 

Read More

"Infix to Post-fix" conversion and "parenthesis check using "User define" stacks C++

#include<iostream>

using namespace std;

char stack[100]; //

char postfix[100];

char exp[100]; // mathematical expression entered by the user

int top=-1;

/**********************************************/

void push1(char newitem)

{

                if(top=='\0')

                {

                                cout<<"Stack overflow"<<endl;

                }

                else

                {

                                exp[++top]=newitem;

                }

}

/**********************************************/

bool ArePair(char opening,char closing)

{

                if(opening == '(' && closing == ')') return true;

                else if(opening == '{' && closing == '}') return true;

                else if(opening == '[' && closing == ']') return true;

                return false;

}

/**********************************************/

void pop1()

{

                if(top==-1)

                {

                cout<<"Cannot pop. The stack does not exist"<<endl;

                }

                else

                {

                                top--;

                }

}

/**********************************************/

int rtop()

{

    if(top!=-1)

    {

        return exp[top];

    }

    else

    return false;

}

/**********************************************/

bool isempty()

{

    if(top==-1)

    {

        return true;

    }

    else

    {

        return false;

    }

}

/**********************************************/

bool AreParanthesesBalanced(char exp[])       // This function will check that parantheses are balanaced or not. If it if balance it will return true.

{

                for(int i =0;exp[i]!= '\0';i++)

                {

                                if(exp[i] == '(' || exp[i] == '{' || exp[i] == '[')

                                {

                                    push1(exp[i]);

                                }

                                else if(exp[i] == ')' || exp[i] == '}' || exp[i] == ']')

                                {

                                                if(isempty() || !ArePair(rtop(),exp[i]))

                                                {

                                                   return false;

                                                }

                                                else

                                                {

                                                    pop1();

                                                }

                                }

                }

                return isempty();

}

/**********************************************/

int precedence(int ch)

{

 if(ch=='(')

        return 0;

 else if(ch=='+'||ch=='-')

    return 1;

 else if(ch=='*'||ch=='/'||ch=='%')

    return 2;

   return -1;

}

/**********************************************/

char pop()

{

  if(top==-1)

  {

   cout<<"\n stack is Empty";

  }

  else

  {

    char ch=stack[top];

    top--;

    return (ch);

  }

}

/**********************************************/

void push(int ch)

{

  if(top!=sizeof(stack)-1)

  {

    top++;

   stack[top]=ch;

  }

  else

    cout<<"Stack Overflow"<<endl;

}

/************************************************/

bool IsOperator(char C)

{

                if(C == '+' || C == '-' || C == '*' || C == '/' || C== '$')

                                return true;

                return false;

}

/************************************************/

bool IsOperand(char C)

{

                if(C >= '0' && C <= '9') return true;

                if(C >= 'a' && C <= 'z') return true;

                if(C >= 'A' && C <= 'Z') return true;

                return false;

}

/**********************************************/

void postfixfun(char exp[])

{

    int k=0;

    int j=0;

       int p=0;

    while(exp[k]!='\0')

    {

/*------------------------------------------------------------*/

        if(IsOperand(exp[k])==true)

        {

         postfix[j]=exp[k];

            j++;

        }

/*----------------------------------------------------------------*/

       else if(exp[k]=='(')

        {

          push(exp[k]);

        }

/*-------------------------------------------------------------------*/

       else if(IsOperator(exp[k])==true)

        {

            while(precedence(stack[top])>=precedence(exp[k]))

            {

                postfix[j]=pop();

            j++;

            }

            push(exp[k]);

        }

/*-------------------------------------------------------------------*/

        else if(exp[k]=')')

        {

            while(stack[top]!='(')

            {

                postfix[j]=stack[top];

                j++;

                pop();

            }

            pop();

        }

        k++;

    }

   

    while(top!=-1)

    {

    postfix[j]=pop();

    j++;

    }

}

/************************************************/

int main()

{

    cout<<"Enter your mathematic expression:"<<endl;

    cin>>exp;

    int size;

    size=sizeof(exp);

    if(AreParanthesesBalanced(exp))

    {

        cout<<"Expression is balanced \n" <<endl;

            cout<<"Postfix Expression="<<endl;

            postfixfun(exp);

            for(int i=0;i<size;i++)

            {

                cout<<postfix[i];

            }

    }

    else

    {

        cout<<"Not balanced"<<endl;

    }

    return 0;

}

New Website Design? Contact Us at Quatro Link

Read More

A Program which uses linear searching? C++

Starts from the base index and compare it with the rest of the element of an array. If the serached index found, it returns 1 else it returns -1.

#include<iostream>
using namespace std;
/********************************************/

int linearSearch(int n[],int s,int size)

    {

        for(int i=0;i<size;i++)

        {

            if(n[i]==s)

            {

            return i;

            }

        }

        return -1;

    }

/*********************************************/

int main()

{

   int n[10];

   int s;

   int result;

   cout<<"Enter values in 'int' array"<<endl;

    for(int j=0;j<10;j++)

    {

    cin>>n[j];

    }

   cout<<"Enter number to search in array"<<endl;

   cin>>s;

   int size=sizeof(n)/sizeof(n[0]);

   result=linearSearch(n,s,size);

   if(result==-1)

   {

       cout<<"Value not found!"<<endl;

    }

    else

    {

    cout<<"value is on index"<<result<<endl;

    }

       return 0;

}

Read More

Implementation of "STACKS" using arrrays (Data structure)

#include <iostream>
#include <cstdlib>
using namespace std;

int stackarr[5];
int size=5;
int top=-1;
/***************************************************/
void push(int item)
{
    if(top==size-1)
    {
        cout<<"\n Stack is Overflow:"<<endl;
    }
    else
    {
        top++;
        stackarr[top]=item;
       cout<<item<<" \n Item is insorted"<<endl;
    }
}
/********************************************************/
int isFull()
{
    if(top=size-1)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
/*************************************************************/
int pop()
{
    if(top==-1)
    {
        return 0;
    }
    else
    {
        return stackarr[top--];
    }
}
/***************************************************************/
void disply()
{
    if(top==-1)
    {
        cout<<"\n Stack is Empty"<<endl;
    }
    else
    {
        for(int i=0;i<size;i++)
        {
            cout<<stackarr[i]<<" ";
        }
    }
}

/***************************************************************/
int isEmpty()
{
    if(top==-1)
    {
        return 1;
    }
    else
    {
        return 0;
    }

}
/*************************************************************/
void topfun()
{
    if(isEmpty())
    {
        cout<<" \n Stack is Empty"<<endl;
    }
    else
    {
        cout<<"\n Top element= "<<stackarr[top]<<endl;
    }
}

/*************************************************************/
int main()
{
    int choice,item,r;
   while(1)
   {
    cout << "Enter 1 for push: " << endl;
    cout << "Enter 2 for pop: " << endl;
    cout << "Enter 3 for Top: " << endl;
    cout << "Enter 4 for display: " << endl;
    cout << "Enter 5 for exit: " << endl;
    cout<<"Enter your choice:"<<endl;
    cin>>choice;
        switch(choice)
        {
            case 1: cout<<"\n Enter items in stack: "<<endl;
                    cin>>item;
                    push(item);
                    break;

            case 2:     r=pop();
                        if(r==0)
                        {
                            cout<<"\n Stack is underflow"<<endl;
                        }
                        else
                        {
                            cout<<"\n ITem is popped "<<endl;
                        }
                        break;

            case 3: topfun();
            break;

            case 4: disply();
            break;

           case 5: exit(0);;
               break;

            default :
                cout<<"\n invalid input"<<endl;
        }
   }

    return 0;
}

Read More

Quick sorting program

Worse case performance: O(n^2)
Best case performance: O(nlogn)
Average performance: O(nlogn)


#include <iostream>
void quicksort(int arr[],int low,int high);
int partition(int arr[],int low,int high);
using namespace std;
/***********************************/
int partition(int arr[],int low,int high)
{
    int pivot,i;
    pivot=arr[high];
    i=low-1;

    for(int j=low; j<high; j++)
    {
        if(arr[j]<=pivot)
        {
            i++;
            swap(arr[i],arr[j]);
        }
    }
    swap(arr[i+1],arr[high]);
    return(i+1);
}
/*********************************/
void quicksort(int arr[],int low, int high)
{
    if(low<high)
    {
    int pivot;
    pivot=partition(arr,low,high);

    quicksort(arr,low,pivot-1);
    quicksort(arr,pivot+1,high);
    }
}
/*********************************/
int main()
{
    int arr[5]={5,4,3,2,1};
    int n=5;
    cout << "Before sorting values is: ";
    for(int i=0;i<n;i++)
    {
    cout<<arr[i]<<" ";
    }
    quicksort(arr,0,n-1);
    cout<<"\n After sorting: ";
    for(int i=0;i<n;i++)
    {
    cout<<arr[i]<<" ";
    }
    cout<<endl;
    return 0;
}

Read More

Merge sorting program in C++

#include <iostream>

using namespace std;
/****************************************************************************************************/
void merg(int *arr,int first,int last)
{
    int mid=(first+last)/2;
 int i=first;
 int j=mid+1;
 int k=first;
 int temp[100];

    while(i<=mid && j<=last)
    {
        if(arr[i]<arr[j])
            {
            temp[k++]=arr[i++];
            }
        else
            {
                temp[k++]=arr[j++];
            }
    }
        while(i<=mid)
        {
            temp[k++]=arr[i++];
        }
            while(j<=mid)
            {
                temp[k++]=arr[j++];
            }
    for(int i=first;i<=last;i++)
    {
        arr[i]=temp[i];
    }
}
/*********************************************************************************************************/
void mergesort(int arr[],int first,int last)
{
    if(first>=last)
    {
        return;
    }

    int mid=(first+last)/2;

    mergesort(arr,first,mid);
    mergesort(arr,mid+1,last);

    merg(arr,first,last);
}
/**************************************************************************************************************/

int main()
{
    int arr[100];
    int n;
    cout<<"Enter number of elements in array:"<<endl;
    cin>>n;
    cout<<"Enter numbers to be sort:"<<endl;
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    mergesort(arr,0,n-1);
    for(int i=0;i<n;i++)
    {
        cout<<arr[i]<<" ";
    }
    return 0;
}

Read More

Insertion sorting using pointers and function

Write a program for insertion sorting. 

 

#include <iostream>

using namespace std;

void insertionSort(int *p,int size);

void insertionSort(int *p,int size)

{

    int i,j,temp;

    for(i=1;i<size;i++)

    {

        temp=p[i];

        j=i-1;

        while(j>=0 && p[j]>temp)

        {

            p[j+1]=p[j];

        j--;

        }

        p[j+1]=temp;

    }

    for(i=0;i<size;i++)

    {

        cout<<p[i]<<" ";

    }

}

int main()

{

    int n;

    int *p;

    cout<<"Enter number of element you want to store in an a array:"<<endl;

    cin>>n;

    p=new int[n];

    cout<<"Now enter the values"<<endl;

    for(int i=0;i<n;i++)

    {

        cin>>p[i];

    }

    insertionSort(p,n);

}

Insertion sorting using pointers and function

Checkout more java programs on Zamacodes.com

         

Read More