1. C ++

Characteristics of C++
C++ is not a purely object-oriented language but a hybrid that contains the functionality
of the C programming language.
C
-universal
-efficient
-close to the machine
-portable

OOP

1. data abstraction, that is, the creation of classes to describe objects
2. data encapsulation for controlled access to object data
3. inheritance by creating derived classes (including multiple derived classes)
4. polymorphism (Greek for multiform), that is, the implementation of instructions that can have varying effects during program execution.

Extensions
-exception handling
-templates
Various language elements were added to C++, such as references, templates, and exception
handling. Even though these elements of the language are not strictly object-oriented
programming features, they are important for efficient program implementation

Objects
Object-oriented programming shifts the focus of attention to the objects, that is, to the
aspects on which the problem is centered. A program designed to maintain bank
accounts would work with data such as balances, credit limits, transfers, interest calculations,
and so on. An object representing an account in a program will have properties
and capacities that are important for account management.

OOP objects combine data (properties) and functions (capacities). A class defines a
certain object type by defining both the properties and the capacities of the objects of
that type. Objects communicate by sending each other “messages,” which in turn activate
another object’s capacities.
Advantages of OOP
Object-oriented programming offers several major advantages to software development:
■ reduced susceptibility to errors: an object controls access to its own data. More
specifically, an object can reject erroneous access attempts
■ easy re-use: objects maintain themselves and can therefore be used as building
blocks for other programs
■ low maintenance requirement: an object type can modify its own internal data
representation without requiring changes to the application.

Tree implementation using Linked List

Main Terms

•Path − Path refers to sequence of nodes along the edges of a tree.

•Root − Node at the top of the tree is called root. There is only one root per tree and one path from root node to any node.

•Parent − Any node except root node has one edge upward to a node called parent.

•Child − Node below a given node connected by its edge downward is called its child node.

•Leaf − Node which does not have any child node is called leaf node.

•Subtree − Subtree represents descendents of a node.

•Visiting − Visiting refers to checking value of a node when control is on the node.

•Traversing − Traversing means passing through nodes in a specific order.

•Levels − Level of a node represents the generation of a node. If root node is at level 0, then its next child node is at level 1, its grandchild is at level 2 and so on.

•keys − Key represents a value of a node based on which a search operation is to be carried out for a node.

Binary Tree Representation:

C code for Tree Implementation using Linked List:
 #include<stdio.h>

typedef struct node
{
    int data;
    struct node *left;
    struct node *right;
} node;
node *create();
void preorder(node *t);       
void inorder(node *t);       
void postorder(node *t);       


int main()
{   
    node *root;
    root=create();
    printf("\nThe preorder traversal of tree is:\n");
    preorder(root);
    printf("\nThe inorder traversal of tree is:\n");
    inorder(root);
    printf("\nThe postorder traversal of tree is:\n");
    postorder(root);
   
    return 0;
}
node *create()
{
    node *p;
    int x;
    printf("Enter data(99 for no data):"); // End of Recursion
    scanf("%d",&x);
   
    if(x==99)
        return NULL; // Assign Null for no data to left or right
   
    p=(node*)malloc(sizeof(node));
    p->data=x;
   
    printf("Enter left child of %d:\n",x);
    p->left=create();

    printf("Enter right child of %d:\n",x);
    p->right=create();
   
    return p;
}

void preorder(node *t)       
{
    if(t!=NULL)
    {

        printf("\n%d",t->data);        //visit the root
preorder(t->left);        //preorder traversal on left subtree
        preorder(t->right);        //preorder traversal on right subtree
    }
}

void inorder(node *t)        //address of root node is passed in t
{
    if(t!=NULL)
    {
    inorder(t->left);        //inorder traversal on left subtree
        printf("\n%d",t->data);        //visit the root
        inorder(t->right);        //inorder traversal on right subtree
    }
}

void postorder(node *t)        //address of root node is passed in t
{
    if(t!=NULL)
    {
    postorder(t->left);        //postorder traversal on left subtree
        postorder(t->right);        //postorder traversal on right subtree
        printf("\n%d",t->data);        //visit the root

    }
}
  /*output
 
  Enter data(99 for no data):50
Enter left child of 50:
Enter data(99 for no data):15
Enter left child of 15:
Enter data(99 for no data):10
Enter left child of 10:
Enter data(99 for no data):99
Enter right child of 10:
Enter data(99 for no data):99
Enter right child of 15:
Enter data(99 for no data):25
Enter left child of 25:
Enter data(99 for no data):99
Enter right child of 25:
Enter data(99 for no data):99
Enter right child of 50:
Enter data(99 for no data):75
Enter left child of 75:
Enter data(99 for no data):65
Enter left child of 65:
Enter data(99 for no data):99
Enter right child of 65:
Enter data(99 for no data):99
Enter right child of 75:
Enter data(99 for no data):85
Enter left child of 85:
Enter data(99 for no data):99
Enter right child of 85:
Enter data(99 for no data):99

The preorder traversal of tree is:

50
15
10
25
75
65
85
The inorder traversal of tree is:

10
15
25
50
65
75
85
The postorder traversal of tree is:

10
25
15
65
85
75
50
--------------------------------
Process exited after 48.53 seconds with return value 0
Press any key to continue . . .

*/ 

Postfix Expression evaluation using stack

1. Enter postfix expression
2. Differentiate operand and operator
3. Push operand onto stack till we get operator
4.Whenever we get operator from expression then pop two operand which are already pushed onto stack in  variable A And B respectively.
5.Apply operator onto operand A and B and again push result onto stack.
6. Repeat whole procedure till we get end of expression (here we use '.' for end of expression)

 #include<stdio.h>
#include<ctype.h>

 # define MAX 50       
 # define Expsize 50   

void push(int item);
int pop();
void EvalPostfix(char postfix[]);
 int stack[MAX];
 int top = -1 ;         

 int main()
 {
int i ;

char postfix[Expsize];
printf("Assume: four operators(*, /, +, -) in an expression and operand is single digit only.\n");
printf( " \nEnter postfix expression,\npress full stop '.' for end expression : ");
//Scan Expression
  for (i = 0 ; i <= Expsize - 1 ; i++)
{
scanf("%c", &postfix[i]);

if ( postfix[i] == '.' )
{ break; }
}

  EvalPostfix(postfix);
return 0;
 }

 void push(int item)
 {
if(top >= MAX -1)
{
printf("stack over flow");
return;
}
else
{
top = top + 1 ;
stack[top]= item;
}
 }

 /* define pop operation */
 int pop()
 {
int item;
if(top <0)
{
printf("stack under flow");
}
else
{
item = stack[top];
top = top - 1;
return item;
}
 }

 /* define function that is used to input postfix expression and to evaluate it */
 void EvalPostfix(char postfix[])
 {

int i ;
char ch;
int val;
int A, B ;


/* evaluate postfix expression */
for (i = 0 ; postfix[i] != '.'; i++)
{
ch = postfix[i];
if (isdigit(ch))
{
/* Push operand i.e. the digit onto stack
ch - '0' is used for getting digit rather than ASCII code of digit */
push(ch - '0');
}
else if (ch == '+' || ch == '-' || ch == '*' || ch == '/')
{
/* Ch is an operator
* pop top element A and next-to-top elemnet B
* from stack and compute B operator A
*/
A = pop();
B = pop();

switch (ch)
{
case '*':
val = B * A;
break;

case '/':
val = B / A;
break;

case '+':
val = B + A;
break;

case '-':
val = B - A;
break;
}

/* push the result get from above onto the stack */
push(val);
}
}
printf( " \n Result of expression evaluation : %d \n", pop()) ;
 }

/*Output
Assume: four operators(*, /, +, -) in an expression and operand is single digit only.

Enter postfix expression,

press full stop '.' for end expression : 359*+.

 Result of expression evaluation : 48

*/

Stack Implementation using array

Stack:
Consider a real life example of chair placed one on another first chair can be removed at last
First in Last Out data structure.
Operation on stack:
Top:
Top is a pointer used to locate top most data on stack.
Push: Push/Add data on to stack. Increment top and add data onto position of top
Pop:Pop/remove data from stack. take data in variable then decrement top
Isfull: Check if stack is full or not. check condition Top=>(Size-1)
Isempty: Check if stack is empty or not. check condition Top<=(-1)

  #include<stdio.h>

int stack[50],choice,n,top,x,i;
void push(void);
void pop(void);
void display(void);
int main()
{
top=-1;
printf("\n Enter the size of STACK[MAX=100]:");
scanf("%d",&n);
printf("\n\t STACK OPERATIONS USING ARRAY");
printf("\n\t 1.PUSH\n\t 2.POP\n\t 3.DISPLAY\n\t 4.EXIT");
do
  {
    printf("\n Enter the Choice:");
    scanf("%d",&choice);
   switch(choice)
    {
      case 1:
       {
         push();
         break;
       }
      case 2:
       {
         pop();
         break;
       }
      case 3:
       {
         display();
          break;
       }
       case 4:
       {
         printf("\n\t EXIT POINT ");
         break;
        }
       default:
        {
           printf ("\n\t Please Enter a Valid Choice(1/2/3/4)");
         }

    }
  }while(choice!=4);
return 0;
}

//Check first stack is overflow or not .
//Else scan data to be pushed ,increment top and then add data in stack at top pointer lacation
void push()
{
   if(top>=n-1)
     {
      printf("\n\tSTACK is over flow");
     }
   else
     {
       printf(" Enter a value to be pushed:");
       scanf("%d",&x);
       top++;
       stack[top]=x;
     }
}

//First check stack is underflow or not
// Else first take data of pointer top then decrement top pointer. 
void pop()
{
   if(top<=-1)
    {
     printf("\n\t Stack is under flow");
    }
   else
    {
     printf("\n\t The popped elements is %d",stack[top]);
     top--;
    }
}

// For display first check either stack is Empty or not .
// then print data from array pointer starts from top to 0 location.
void display()
{
   if(top>=0)
    {
      printf("\n The elements in STACK \n");
      for(i=top; i>=0; i--)
      printf("\n%d",stack[i]);
      printf("\n Press Next Choice");
    }
   else
    {
      printf("\n The STACK is empty");
    }
 }

 /*
 Output


 Enter the size of STACK[MAX=100]:10

STACK OPERATIONS USING ARRAY
--------------------------------
1.PUSH
2.POP
3.DISPLAY
4.EXIT
 Enter the Choice:1
 Enter a value to be pushed:56

 Enter the Choice:1
 Enter a value to be pushed:47

 Enter the Choice:1
 Enter a value to be pushed:40

 Enter the Choice:3

 The elements in STACK

40
47
56
 Press Next Choice
 Enter the Choice:2

The popped elements is 40
 Enter the Choice:2

The popped elements is 47
 Enter the Choice:2

The popped elements is 56
 Enter the Choice:2

Stack is under flow
 Enter the Choice:
 */

Merge Sort

Merge Sort- based On Divide and Conquer algorithm

 In Merge sort algorithm the given array is divided  into two parts and again merge with proper order.
1.Given array is divided into left and right half till we get two element in left half recursively.
2.After getting two element in left half call merge function it will first split array into single element namely left array and right array.
3.Then merge these two array using ascending order of left and right array.
4.Now move to right part of previous array,here also same procedure split array into left and right then merge.

Recursive Function:
Function call within same function is called recursive function.

Whenever function call occur within program the current value of the variables are push onto stack and pop again while returning the function call.
Hence here the index of array change according to function call and recursively left-right-merge is done.



Library files

#include<stdlib.h>
#include<stdio.h>
//Function Prototypes:
void merge(int arr[], int l, int m, int r,int arr_size);
void mergeSort(int arr[], int l, int r,int arr_size);
void printArray(int A[],int arr_size);
int y=0;//Counter for counting merge operation

int main()
{
    int arr[] = {35,25,48,4,8,72,13,100};
    int arr_size = sizeof(arr)/sizeof(arr[0]);
    printf("Given array is \n");
    printArray(arr,arr_size);
    mergeSort(arr, 0, arr_size - 1,arr_size);
    printf("\nSorted array is \n");
    printArray(arr,arr_size);
    return 0;
}

// l is for left index and r is right index of the sub-array of arr to be sorted
void mergeSort(int arr[], int l, int r,int arr_size)
{
    if (l < r)
    {
        int m = l+(r-l)/2;
        mergeSort(arr, l, m,arr_size);// Recursive function call will execute till we get atleast two element in array
        mergeSort(arr, m+1, r,arr_size);// Recursive function call will execute till we get atleast two element in array

        merge(arr, l, m, r,arr_size);//this function will split array into two part and again merge with ascending order
    }
 }

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r,int arr_size)
{
y++;
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;
    //create temp arrays
    int L[n1], R[n2];
    //Copy data to temp arrays L[] and R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];
    // Merge the temp arrays back into arr[l..r]
    i = 0; // Initial index of first subarray
    j = 0; // Initial index of second subarray
    k = l; // Initial index of merged subarray

    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy the remaining elements of L[], if there are any
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy the remaining elements of R[], if there are any
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }

    printf("\n array after %d times merge (merge function)\n",y);
    printArray(arr,arr_size);
}

void printArray(int A[], int arr_size)
{
    int i;
    for (i=0; i <= arr_size-1; i++)
    printf("\'%d\'\t ", A[i]);
    printf("\n");
}


/*
Output
Given array is
'35' '25' '48' '4' '8' '72' '13' '100'

 array after 1 times merge (merge function)
'25' '35' '48' '4' '8' '72' '13' '100'

 array after 2 times merge (merge function)
'25' '35' '4' '48' '8' '72' '13' '100'

 array after 3 times merge (merge function)
'4' '25' '35' '48' '8' '72' '13' '100'

 array after 4 times merge (merge function)
'4' '25' '35' '48' '8' '72' '13' '100'

 array after 5 times merge (merge function)
'4' '25' '35' '48' '8' '72' '13' '100'

 array after 6 times merge (merge function)
'4' '25' '35' '48' '8' '13' '72' '100'

 array after 7 times merge (merge function)
'4' '8' '13' '25' '35' '48' '72' '100'

Sorted array is
'4' '8' '13' '25' '35' '48' '72' '100'




*/

Insertion Sort

Best case complexity of insertion sort is O(n), average and the worst case complexity is O(n²).

Working of Insertion Sort:
Insertion sort work same as player of playing card places upcoming card at its proper sequence.

• Start from pointing first and second element in an array.
• If second element of array is lesser than first element then swap position of those two element.
• Increment the pointer and check for all element sequentially and place each upcoming element to proper sequence in an array till last element of array.

Entered Array is :'111' '12'    '45'    '13'    '78'    '80'
 Sorted Array after 1 pass:'12' '111'   '45'    '13'    '78'    '80'
 Sorted Array after 2 pass:'12' '45'    '111'   '13'    '78'    '80'
 Sorted Array after 3 pass:'12' '13'    '45'    '111'   '78'    '80'
 Sorted Array after 4 pass:'12' '13'    '45'    '78'    '111'   '80'

 Sorted Array after 5 pass:'12' '13'    '45'    '78'    '80'    '111'    

library declaration:
 #include<stdio.h>
#include<stdlib.h>

Prototype Declaration:
int insertionsort(int*,int);
void display(int* ,int);

Main Program:
int main()
{
    int *arr,i,n;
    printf("Enter the no. of elements\n");
    scanf("%d",&n);
    arr=(int*)malloc(n*sizeof(int));
    printf("Enter elements\n");
    for(i=0;i<n;i++)
        scanf("%d \t",(arr+i));
printf("\nEntered Array is :");
display(arr,n);
insertionsort(arr,n);
printf("\nFinally sorted Array is :");
display(arr,n);
return 0;
}

C Function For Insertion Sort:
int insertionsort(int *arr,int n)
{
    int i,j,temp;
for(i=1;i<n;i++)
    {
        temp=*(arr+i);
        j=i-1;
        while(temp<*(arr+j)&&j>=0)
        {
            *(arr+(j+1))=*(arr+j);
            j--;
        }
        *(arr+(j+1))=temp;
        printf("\n Sorted Array after %d pass:",i);
        display(arr,n);
     }
    return 0;
}

C Function For Display Array:
void display(int *arr,int n)
{ int i=0;
  for(i=0;i<n;i++)
printf("\'%d\'\t",*(arr+i));
}

Implementation of Queue using Link List Functions

Implementation of Queue using Link List Functions

Function to Create an empty queue

create only pointer pointing to NULL

void create()

{

    front = rear = NULL;

}

Function for getting queue size 

Take a global variable count and display here.

At every time of enqueue increment count.

and in  dequeue function decrement count.

void queuesize()

{

    printf("\n Queue size : \'%d\'", count);

}

Function for Enqueing the queue

Add a node with Null pointer at rear side and update rear to new node.

void enq(int data)

{

    if (rear == NULL)

    {

        rear = (struct node *)malloc(1*sizeof(struct node));

        rear->ptr = NULL;

        rear->info = data;

        front = rear;

    }

    else

    {

        temp=(struct node *)malloc(1*sizeof(struct node));

        rear->ptr = temp;

        temp->info = data;

        temp->ptr = NULL;

        rear = temp;

    }

    count++; //count for counting number of nodes

}

Function for Displaying the queue elements

void display()

{

    front1 = front;

    if ((front1 == NULL) && (rear == NULL))

    {

        printf("Queue is empty");

        return;

    }

    while (front1 != rear)

    {

        printf("\'%d\' ", front1->info);

        front1 = front1->ptr;

    }

    if (front1 == rear)

        printf("\'%d\'", front1->info);

}

Function for Dequeing the queue

Update front pointer to next location and Remove old front element using dummy pointer as front1. 

void deq()

{

    front1 = front;

    if (front1 == NULL)

    {

        printf("\n Error: Trying to display elements from empty queue");

        return;

    }

    else

        if (front1->ptr != NULL)

        {

            front1 = front1->ptr;

            printf("\n Dequed value : %d", front->info);

            free(front);

            front = front1;

        }

        else

        {

            printf("\n Dequed value : %d", front->info);

            free(front);

            front = NULL;

            rear = NULL;

        }

        count--; // decrement count of total nodes

}

Function to display front element of queue

int frontelement()

{

    if ((front != NULL) && (rear != NULL))

        return(front->info);

    else

        return 0;

}

Function for Display if queue is empty or not

If front and rear both are pointing to Null then queue is empty.

void empty()

{

     if ((front == NULL) && (rear == NULL))

        printf("\n Queue empty");

    else

       printf("Queue not empty");

}

/*

Output

1-Enque                                                                                                                       

 2 - Deque                                                                                                                      

 3 - Front element                                                                                                               

 4 - Empty                                                                                                                      

 5 - Display                                                                                                                     

 6 - Queuesize                                                                                                                  

 7 - Exit                                                                                                                        

 Enter choice : 1                                                                                                               

Enter data for Enque: 10                                                                                                         

                                                                                                                                

 Element of Queue after Enqueque operation:'10'                                                                                  

 Enter choice : 1                                                                                                               

Enter data for Enque: 20                                                                                                         

                                                                                                                                

 Element of Queue after Enqueque operation:'10' '20'                                                                             

 Enter choice : 1                                                                                                               

Enter data for Enque:                                                                                                            

30                                                                                                                              

                                                                                                                                 

 Element of Queue after Enqueque operation:'10' '20' '30'                                                                       

 Enter choice : 2

 Dequed value : 10                                                                                                              

 Element of Queue after deque operation:'20' '30'                                                                                

 Enter choice : 3                                                                                                               

Front element : 20                                                                                                               

 Enter choice : 4                                                                                                               

Queue not empty                                                                                                                  

 Enter choice : 5                                                                                                               

'20' '30'                                                                                                                        

 Enter choice : 6                                                                                                               

                                                                                                                                 

 Queue size : '2'                                                                                                               

 Enter choice : 7                                                                                                                

                                                                                                                                

                                                                                                                                 

...Program finished with exit code 0                                                                                            

Press ENTER to exit console. 

           

*/