queue using circular linked list

queue using circular linked list

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int info;
    struct node *link;
}*rear=NULL;

void insert(int item);
int del();
void display();
int isEmpty();
int peek();

main()
{
    int choice,item;
    while(1)
    {
        printf("1.Insert\n");
        printf("2.Delete\n");
        printf("3.Peek\n");
        printf("4.Display\n");
        printf("5.Quit\n");
        printf("Enter your choice : ");
        scanf("%d",&choice);

        switch(choice)
        {
         case 1:
            printf("Enter the element for insertion : ");
            scanf("%d",&item);
            insert(item);
            break;
         case 2:
            printf("Deleted element is %d\n",del());   
            break;
         case 3:
            printf("Item at the front of queue is %d\n",peek());
            break;
         case 4:
            display();
            break;
         case 5:
            exit(1);
         default:
            printf("Wrong choice\n");
        }/*End of switch*/
    }/*End of while*/
}/*End of main()*/

void insert(int item)
{
    struct node *tmp;
    tmp=(struct node *)malloc(sizeof(struct node));
    tmp->info=item;
    if(tmp==NULL)
    {
        printf("Memory not available\n");
        return;
    }
   
    if( isEmpty() ) /*If queue is empty */
    {
        rear=tmp;
        tmp->link=rear;
    }
    else
    {
        tmp->link=rear->link;
        rear->link=tmp;
        rear=tmp;
    }
}/*End of insert()*/

del()
{
    int item;
    struct node *tmp;
    if( isEmpty() )
    {
        printf("Queue underflow\n");
        exit(1);
    }
    if(rear->link==rear)  /*If only one element*/
    {
        tmp=rear;
        rear=NULL;
    }
    else
    {
        tmp=rear->link;
        rear->link=rear->link->link;
    }
    item=tmp->info;
    free(tmp);
    return item;
}/*End of del()*/

int peek()
{
    if( isEmpty() )
    {
        printf("Queue underflow\n");
        exit(1);
    }
    return rear->link->info;
}/* End of peek() */

int isEmpty()
{
    if( rear == NULL )
        return 1;
    else
        return 0;
}/*End of isEmpty()*/


void display()
{
    struct node *p;
    if(isEmpty())
    {
        printf("Queue is empty\n");
        return;
    }
    printf("Queue is :\n");
    p=rear->link;
    do
    {
        printf("%d ",p->info);
        p=p->link;
    }while(p!=rear->link);
    printf("\n");
}

Circular Queue

A circular queue is a Queue but a particular implementation of a queue. It is very efficient. It is also quite useful in low level code, because insertion and deletion are totally independant, which means that you don't have to worry about an interrupt handler trying to do an insertion at the same time as your main code is doing a deletion.

Algorithm for Insertion:-Step-1: If "rear" of the queue is pointing to the last position then go to step-2 or else step-3
Step-2: make the "rear" value as 0
Step-3: increment the "rear" value by one
Step-4:

1. if the "front" points where "rear" is pointing and the queue holds a not NULL value for it, then its a "queue overflow" state, so quit; else go to step-4.2
2. insert the new value for the queue position pointed by the "rear"

Algorithm for deletion:-
Step-1: If the queue is empty then say "empty queue" and quit; else continue
Step-2: Delete the "front" element
Step-3: If the "front" is pointing to the last position of the queue then step-4 else step-5
Step-4: Make the "front" point to the first position in the queue and quit
Step-5: Increment the "front" position by one

c program for tower of hanoic problem

TOWER OF HANOIC PROBLEM> (RECURSION)
#include<stdio.h>
void tofh(int ndisk, char source, char temp, char dest);

main( )
{
    char  source = 'A', temp = 'B', dest = 'C';
    int ndisk;
    printf("Enter the number of disks : ");
    scanf("%d", &ndisk );
    printf("Sequence is :\n");
    tofh(ndisk, source, temp, dest);
}/*End of main()*/

void tofh(int ndisk, char source, char temp, char dest)
{
    if(ndisk==1)
    {
        printf("Move Disk %d from %c-->%c\n", ndisk, source, dest);
        return;
    }
    tofh(ndisk-1, source, dest, temp);
    printf("Move Disk %d from %c-->%c\n", ndisk, source, dest);
    tofh(ndisk-1, temp, source, dest);

}

reference....

Recursive solution

Let call the three pegs Src (Source), Aux (Auxiliary) and Dst (Destination). To better understand and appreciate the following solution you should try solving the puzzle for small number of disks, say, 2,3, and, perhaps, 4. However one solves the problem, sooner or later the bottom disk will have to be moved from Src to Dst. At this point in time all the remaining disks will have to be stacked in decreasing size order on Aux. After moving the bottom disk from Src to Dst these disks will have to be moved from Aux to Dst. Therefore, for a given number N of disks, the problem appears to be solved if we know how to accomplish the following tasks:

1. Move the top N - 1 disks from Src to Aux (using Dst as an intermediary peg)
2. Move the bottom disk from Src to Dst
3. Move N - 1 disks from Aux to Dst (using Src as an intermediary peg)

Assume there is a function Solve with four arguments - number of disks and three pegs (source, intermediary and destination - in this order). Then the body of the function might look like

Solve(N, Src, Aux, Dst)
    if N is 0 
      exit
    else
      Solve(N - 1, Src, Dst, Aux)
      Move from Src to Dst
      Solve(N - 1, Aux, Src, Dst)

This actually serves as the definition of the function Solve. The function is recursive in that it calls itself repeatedly with decreasing values of N until a terminating condition (in our case N = 0) has been met. To me the sheer simplicity of the solution is breathtaking. For N = 3 it translates into

1. Move from Src to Dst.
2. Move from Src to Aux.
3. Move from Dst to Aux.
4. Move from Src to Dst.
5. Move from Aux to Src.
6. Move from Aux to Dst.
7. Move from Src to Dst.

Of course "Move" means moving the topmost disk. For N = 4 we get the following sequence

1. Move from Src to Aux.
2. Move from Src to Dst.
3. Move from Aux to Dst.
4. Move from Src to Aux.
5. Move from Dst to Src.
6. Move from Dst to Aux.
7. Move from Src to Aux.
8. Move from Src to Dst.
9. Move from Aux to Dst.
10. Move from Aux to Src.
11. Move from Dst to Src.
12. Move from Aux to Dst.
13. Move from Src to Aux.
14. Move from Src to Dst.
15. Move from Aux to Dst.

c program to perform polynomial addition

polynomial addition using linked list

    #include<stdio.h>
    #include<malloc.h>
    #include<conio.h>
    struct link{
    int coeff;
    int pow;
    struct link *next;
    };
    struct link *poly1=NULL,*poly2=NULL,*poly=NULL;
    void create(struct link *node)
    {
    char ch;
    do
    {
    printf("\n enter coeff:");
    scanf("%d",&node->coeff);
    printf("\n enter power:");
    scanf("%d",&node->pow);
    node->next=(struct link*)malloc(sizeof(struct link));
    node=node->next;
    node->next=NULL;
    printf("\n continue(y/n):");
    ch=getch();
    }
    while(ch=='y' || ch=='Y');
    }
    void show(struct link *node)
    {
    while(node->next!=NULL)
    {
    printf("%dx^%d",node->coeff,node->pow);
    node=node->next;
    if(node->next!=NULL)
    printf("+");
    }
    }
    void polyadd(struct link *poly1,struct link *poly2,struct link *poly)
    {
    while(poly1->next && poly2->next)
    {
    if(poly1->pow>poly2->pow)
    {
    poly->pow=poly1->pow;
    poly->coeff=poly1->coeff;
    poly1=poly1->next;
    }
    else if(poly1->pow<poly2->pow)
    {
    poly->pow=poly2->pow;
    poly->coeff=poly2->coeff;
    poly2=poly2->next;
    }
    else
    {
    poly->pow=poly1->pow;
    poly->coeff=poly1->coeff+poly2->coeff;
    poly1=poly1->next;
    poly2=poly2->next;
    }
    poly->next=(struct link *)malloc(sizeof(struct link));
    poly=poly->next;
    poly->next=NULL;
    }
    while(poly1->next || poly2->next)
    {
    if(poly1->next)
    {
    poly->pow=poly1->pow;
    poly->coeff=poly1->coeff;
    poly1=poly1->next;
    }
    if(poly2->next)
    {
    poly->pow=poly2->pow;
    poly->coeff=poly2->coeff;
    poly2=poly2->next;
    }
    poly->next=(struct link *)malloc(sizeof(struct link));
    poly=poly->next;
    poly->next=NULL;
    }
    }
    main()
    {
    char ch;
    do{
    poly1=(struct link *)malloc(sizeof(struct link));
    poly2=(struct link *)malloc(sizeof(struct link));
    poly=(struct link *)malloc(sizeof(struct link));
    printf("\nenter 1st number:");
    create(poly1);
    printf("\nenter 2nd number:");
    create(poly2);
    printf("\n1st Number:");
    show(poly1);
    printf("\n2nd Number:");
    show(poly2);
    polyadd(poly1,poly2,poly);
    printf("\nAdded polynomial:");
    show(poly);
    printf("\n add two more numbers:");
    ch=getch();
    }
    while(ch=='y' || ch=='Y');
    }
coefficients Like-power terms are added in polynomial addition.
i.e.;
First Polynomial Second Polynomial
coeffcient of x + coeffcient of x
coeffcient of x^2 + coeffcient of x^2
coeffcient of x^3 + coeffcient of x^3
--------------------------------------…
and so on. If first polynomial is of 5th degree and second is of 3rd degree.
Then u add terms of both polynomial upto 3rd term and u put remaining 2 terms (4th and 5th) of first polynomial as it is in the final polynomial.

So ur logic goes like this.
u will have three linked lists
first linked list for first polynomial
second linked list for second polynomial
third linked list for addition of polynomials


u traverse linked list of higher-degree polynomial and keep on adding coefficients of both polynomials in a third polynomial.
after adding each coefficient u move to next node in both the linked lists.
during traversal lower degree polynomial will end then u simply copy remaining terms in third linked list.

how to calculate the address of the 2D array

Address of a[ i ][ j ]th element (row major)
*********************************************
 BA + [ n * ( i - LBR) + ( j - LBC) ] * w

                                                         Where BA = Base address
                                                               W = Number of bytes occupied by each element
                                                                 N = Number of columns


Address of a[ i ][ j ]th element (colum major)
*********************************************
     BA + [ ( i - LBR) + m * ( j - LBC) ] * w

                                                           Where BA = Base address
                                                                        W = Number of bytes occupied by each element
                                                                         N = Number of rows

 WHAT IS A 2D ARRAY?

 A matrix (two dimensional array) is a group of lists, or arrays that are organized into one data set. To understand them, first look an example of the standard one dimensional array:

Array "A":
16
8
99
0
5

You can reference any point in the "array" by naming the array and following it with a number representing the position of a piece of data on the list. The first data on the array is represented with a "0", the second with a "1", and so on. For example, A[2] (in bold) represents 99 because it is the third figure of array A. You could imagine the references of the above table as the following:

Array "A":
[0]
[1]
[2]
[3]
[4]

A matrix is a set of arrays. Visualize the following table:

Matrix "B":
16 17 9
8 88 74
99 12 21
0 6 40
5 19 18

There are 3 different arrays in a single data set, "B". In Array A, you could reference any data by naming the point on the list, such as "1" or "3". However, with a matrix, you must give both a row and a column. You can reference data on a matrix in the following format:

MatrixName[row][column]

For example, B[3][2] would represent 40 because it is the it is on the fourth row down and the third column. Remember, matrix references also start at zero, not one! You can reference any of the data on this table with this chart:

Matrix "B":
[0][0] [0][1] [0][2]
[1][0] [1][1] [1][2]
[2][0] [2][1] [2][2]
[3][0] [3][1] [3][2]
[4][0] [4][1] [4][2]

Two-dimensional arrays are used everywhere, but are especially prevalent in computer programming and accounting

infix to postfix conversion

Infix to Postfix conversion using stack

Introduction:
         In the last post I have explained about the infix,prefix,postfix expression. In this post we are going to know about the conversion of infix to postfix expression.

Infix to Postfix Conversion:

• Consider an infix string x+y*c.Each character of the string is called tokens.
• The algorithm for converting an infix expression to postfix expression is given below.
• We need a stack to solve this problem

Algorithm for converting infix expression to postfix expression:

• Initialize an empty stack and a Postfix String S.
• Read the tokens from the infix string one at a time from left to right
• If the token is an operand, add it to the Postfix string S.
• If the token is a left parentheses, Push it on to the stack
• If the token is a right parentheses
  1. Repeatedly Pop the stack and add the poped out element in to the string S until a left parenthesis is encountered;
  2. Remove the left parenthesis from the stack and ignore it
• If the token is an operator
  1. If the stack is empty push the operator in to the stack       
  2. If the stack is not empty compare the precedence of the operator with the element on top of the stack
     • If the operator in the stack has higher precedence than the token Pop the stack and add the poped out element in to the string S. else Push the operator in to the stack                   
     • Repeat this step until the stack is not empty or the operator in the stack has higher precedence than the token         
• Repeat this step till all the characters are read.
• After all the characters are read and the stack is not empty then Pop the stack and add the tokens to the string S
• Return the Postfix string S

Example for Converting infix to Postfix Expression:

Example 1:
Infix String----->A*B+C/D
Solution:

1. Initially the stack is empty and the Postfix String S has no characters
2. Read the token A.A is a operand so it is added to the string S.now Stack->empty and S->A
3. Read the token *.* is an operator.stack is empty so push * in to the stack. now Stack->* and S->A
4. Read the token B.B is an operand so it is added to the string S. now Stack->* and S->AB
5. Read the token +.+is an operator.compare +and *.* has higher precedence than +. so pop * from the stack and add it to the string S. now Stack->empty and S->AB*.now the stack is empty so push the + in to the stack.now Stack->+ and S->AB*
6. Read the token C.C is a operand so it is added to the string S.now Stack->+ and S->AB*C
7. Read the token /./ is an operator.compare /and +./ has higher precedence than +. so push / in to the stack . now Stack->+/ and S->AB*C
8. Read the token D.D is a operand so it is added to the string S.now Stack->+/ and S->AB*CD
9. All the characters are read but the stack is not empty so pop the stack and add the characters to the String. now S->AB*CD/+

     So the Postfix String is AB*CD/+


Example 2:
Infix String----->A*(B+C)/D
Solution:

1. Initially the stack is empty and the Postfix String S has no character.
2. Read the token A.A is a operand so it is added to the string S.now Stack->empty and S->A
3. Read the token *.* is an operator.stack is empty so push * in to the stack. now Stack->* and S->A
4. Read the token (.push the left parentheses in to the stack.
5. Read the token B.B is an operand so it is added to the string S. now Stack->* and S->AB
6. Read the token +.+is an operator.compare +and *.+ has lower precedence than *.So push + in to the stack. now Stack->*+ and S->AB
7. Read the token C.C is an operand so it is added to the string S.now Stack->*+ and S->ABC
8. Read the token ). ) is a right parentheses ,Pop the stack and add the + in to the string S. now Stack->* and S->ABC+
9. Read the token /./ is an operator.compare /and *./ and * have equal precedence but * comes before /so pop the stack and add * in to the string S.now stack is empty so push / in to the stack . now Stack->/ and S->ABC+*
10. Read the token D.D is an operand so it is added to the string S.now Stack->/ and S->ABC+*D 
11. Now the input string is empty but the stack is not empty so pop the stack and add the characters to the String.now Stack->Empty and S->ABC+*D/

         So the Postfix String is ABC+*D/

program to perform sparse matrix addition

program to add sparse matrix

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define MAX1 3
#define MAX2 3
#define MAXSIZE 9
#define BIGNUM 100
struct sparse
{
int *sp ;
int row ;
int *result ;
} ;
void initsparse ( struct sparse * ) ;
void create_array ( struct sparse * ) ;
int count ( struct sparse ) ;
void display ( struct sparse ) ;
void create_tuple ( struct sparse *, struct sparse ) ;
void display_tuple ( struct sparse ) ;
void addmat ( struct sparse *, struct sparse, struct sparse ) ;
void display_result ( struct sparse ) ;
void delsparse ( struct sparse * ) ;
void main( )
{
struct sparse s[5] ;
int i ;
clrscr( ) ;
for ( i = 0 ; i <= 4 ; i++ )
initsparse ( &s[i] ) ;
create_array ( &s[0] ) ;
create_tuple ( &s[1], s[0] ) ;
display_tuple ( s[1] ) ;
create_array ( &s[2] ) ;
create_tuple ( &s[3], s[2] ) ;
display_tuple ( s[3] ) ;
addmat ( &s[4], s[1], s[3] ) ;
printf ( "\nResult of addition of two matrices: " ) ;
display_result ( s[4] ) ;
for ( i = 0 ; i <= 4 ; i++ )
delsparse ( &s[i] ) ;
getch( ) ;
}
/* initialises structure elements */
void initsparse ( struct sparse *p )
{
p -> sp = NULL ;
p -> result = NULL ;
}
/* dynamically creates the matrix */
void create_array ( struct sparse *p )
{
int n, i ;
/* allocate memory */
p -> sp = ( int * ) malloc ( MAX1 * MAX2 * sizeof ( int ) ) ;
/* add elements to the array */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
printf ( "Enter element no. %d:", i ) ;
scanf ( "%d", &n ) ;
* ( p -> sp + i ) = n ;
}
}
/* displays the contents of the matrix */
void display ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % MAX2 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
}
/* counts the number of non-zero elements */
int count ( struct sparse s )
{
int cnt = 0, i ;
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
if ( * ( s.sp + i ) != 0 )
cnt++ ;
}
return cnt ;
}
/* creates an array that stores information about non-zero elements */
void create_tuple ( struct sparse *p, struct sparse s )
{
int r = 0 , c = -1, l = -1, i ;
/* get the total number of non-zero elements
and add 1 to store total no. of rows, cols, and non-zero values */
p -> row = count ( s ) + 1 ;
/* allocate memory */
p -> sp = ( int * ) malloc ( p -> row * 3 * sizeof ( int ) ) ;
/* store information about
total no. of rows, cols, and non-zero values */
* ( p -> sp + 0 ) = MAX1 ;
* ( p -> sp + 1 ) = MAX2 ;
* ( p -> sp + 2 ) = p -> row - 1 ;
l = 2 ;
/* scan the array and store info. about non-zero values in the 3-tuple */
for ( i = 0 ; i < MAX1 * MAX2 ; i++ )
{
c++ ;
/* sets the row and column values */
if ( ( ( i % MAX2 ) == 0 ) && ( i != 0 ) )
{
r++ ;
c = 0 ;
}
/* checks for non-zero element row, column and non-zero element value is assigned to the matrix */
if ( * ( s.sp + i ) != 0 )
{
l++ ;
* ( p -> sp + l ) = r ;
l++ ;
* ( p -> sp + l ) = c ;
l++ ;
* ( p -> sp + l ) = * ( s.sp + i ) ;
}
}
}
/* displays the contents of the matrix */
void display_tuple ( struct sparse s )
{
int i, j ;
/* traverses the entire matrix */
printf ( "\nElements in a 3-tuple: \n" ) ;
j = ( * ( s.sp + 2 ) * 3 ) + 3 ;
for ( i = 0 ; i < j ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.sp + i ) ) ;
}
printf ( "\n" ) ;
}
/* carries out addition of two matrices */
void addmat ( struct sparse *p, struct sparse s1, struct sparse s2 )
{
int i = 1, j = 1, k = 1 ;
int elem = 1 ;
int max, amax, bmax ;
int rowa, rowb, cola, colb, vala, valb ;
/* get the total number of non-zero values from both the matrices */
amax = * ( s1.sp + 2 ) ;
bmax = * ( s2.sp + 2 ) ;
max = amax + bmax ;
/* allocate memory for result */
p -> result = ( int * ) malloc ( MAXSIZE * 3 * sizeof ( int ) ) ;
while ( elem <= max )
{
/* check if i < max. non-zero values
in first 3-tuple and get the values */
if ( i <= amax )
{
rowa = * ( s1.sp + i * 3 + 0 ) ;
cola = * ( s1.sp + i * 3 + 1 ) ;
vala = * ( s1.sp + i * 3 + 2 ) ;
}
else
rowa = cola = BIGNUM ;
/* check if j < max. non-zero values in secon 3-tuple and get the values */
if ( j <= bmax )
{
rowb = * ( s2.sp + j * 3 + 0 ) ;
colb = * ( s2.sp + j * 3 + 1 ) ;
valb = * ( s2.sp + j * 3 + 2 ) ;
}
else
rowb = colb = BIGNUM ;
/* if row no. of both 3-tuple are same */
if ( rowa == rowb )
{
/* if col no. of both 3-tuple are same */
if ( cola == colb )
{
/* add tow non-zero values
store in result */
* ( p -> result + k * 3 + 0 ) = rowa ;
* ( p -> result + k * 3 + 1 ) = cola ;
* ( p -> result + k * 3 + 2 ) = vala + valb ;
i++ ;
j++ ;
max-- ;
}
/* if col no. of first 3-tuple is < col no. of second 3-tuple, then add info. as it is to result */
if ( cola < colb )
{
* ( p -> result + k * 3 + 0 ) = rowa ;
* ( p -> result + k * 3 + 1 ) = cola ;
* ( p -> result + k * 3 + 2 ) = vala ;
i++ ;
}
/* if col no. of first 3-tuple is > col no. of second 3-tuple, then add info. as it is to result */
if ( cola > colb )
{
* ( p -> result + k * 3 + 0 ) = rowb ;
* ( p -> result + k * 3 + 1 ) = colb ;
* ( p -> result + k * 3 + 2 ) = valb ;
j++ ;
}
k++ ;
}
/* if row no. of first 3-tuple is < row no. of second 3-tuple, then add info. as it is to result */
if ( rowa < rowb )
{
* ( p -> result + k * 3 + 0 ) = rowa ;
* ( p -> result + k * 3 + 1 ) = cola ;
* ( p -> result + k * 3 + 2 ) = vala ;
i++ ;
k++ ;
}
/* if row no. of first 3-tuple is > row no. of second 3-tuple, then add info. as it is to result */
if ( rowa > rowb )
{
* ( p -> result + k * 3 + 0 ) = rowb ;
* ( p -> result + k * 3 + 1 ) = colb ;
* ( p -> result + k * 3 + 2 ) = valb ;
j++ ;
k++ ;
}
elem++ ;
}
/* add info about the total no. of rows, cols, and non-zero values that the resultant array contains to the result */
* ( p -> result + 0 ) = MAX1 ;
* ( p -> result + 1 ) = MAX2 ;
* ( p -> result + 2 ) = max ;
}
/* displays the contents of the matrix */
void display_result ( struct sparse s )
{
int i ;
/* traverses the entire matrix */
for ( i = 0 ; i < ( * ( s.result + 0 + 2 ) + 1 ) * 3 ; i++ )
{
/* positions the cursor to the new line for every new row */
if ( i % 3 == 0 )
printf ( "\n" ) ;
printf ( "%d\t", * ( s.result + i ) ) ;
}
}
/* deallocates memory */
void delsparse ( struct sparse *p )
{
if ( p -> sp != NULL )
free ( p -> sp ) ;
if ( p -> result != NULL )
free ( p -> result ) ;
}

Sparse matrices, which are common in scientific applications, are matrices in which most elements are zero. To save space and running time it is critical to only store the nonzero elements. A standard representation of sparse matrices in sequential languages is to use an array with one element per row each of which contains a linked-list of the nonzero values in that row along with their column number. A similar representation can be used in parallel. In NESL a sparse matrix can be represented as a sequence of rows, each of which is a sequence of (column-number, value) pairs of the nonzero values in the row

operator overloading using friend function

operator overloading both unary and binary operator using friend function.

What is a friend function c plus plus?

A friend function in C++ is a function that is not part of the implementation of a class, i.e. not a method of the class, but that is allowed to manipulate the private parts of a class.

#include <iostream>
using namespace std;
class loc {
int longitude, latitude;
public:
loc() {} // needed to construct temporaries
loc(int lg, int lt) {
longitude = lg;
latitude = lt;
}
void show() {
cout << longitude << " ";
cout << latitude << "\n";
}
friend loc operator+(loc , loc ); // now a friend
loc operator-(loc op2);
loc operator=(loc op2);
loc operator++();
};
// Now, + is overloaded using friend function.
loc operator+(loc op1, loc op2)
{
loc temp;
temp.longitude = op1.longitude + op2.longitude;
temp.latitude = op1.latitude + op2.latitude;
return *this;
}
// Overload - for loc.
loc loc::operator-(loc op2)
{
loc temp;
// notice order of operands
temp.longitude = longitude - op2.longitude;
temp.latitude = latitude - op2.latitude;
return temp;
}
// Overload assignment for loc
loc loc::operator=(loc op2)
{
longitude = op2.longitude;
latitude = op2.latitude;
return *this; // i.e., return object that generated call
}
// Overload ++ for loc.
loc loc::operator++()
{
longitude++;
latitude++;
return *this;
}
int main()
{
loc ob1(10, 20), ob2( 5, 30);
ob1 = ob1 + ob2;
ob1.show();
return 0;
}

C++ Operator Overloading Guidelines

One of the nice features of C++ is that you can give special meanings to operators, when they are used with user-defined classes. This is called operator overloading. You can implement C++ operator overloads by providing special member-functions on your classes that follow a particular naming convention. For example, to overload the + operator for your class, you would provide a member-function named operator+ on your class.
The following set of operators is commonly overloaded for user-defined classes:

• = (assignment operator)
• + - * (binary arithmetic operators)
• += -= *= (compound assignment operators)
• == != (comparison operators)

operator overloading

operator overloading using unary and binary operator
#include <iostream>
using namespace std;
class loc
{
int longitude, latitude;
public:
loc() {} // needed to construct temporaries
loc(int lg, int lt)
{
longitude = lg;
latitude = lt;
}
void show()
{
cout << longitude << " ";
cout << latitude << "\n";
}
loc operator+(loc op2);
loc operator-(loc op2);
loc operator=(loc op2);
loc operator++();
};
// Overload + for loc.
loc loc::operator+(loc op2)
{
loc temp;
temp.longitude = op2.longitude + longitude;
temp.latitude = op2.latitude + latitude;
return *this;
}
// Overload - for loc.
loc loc::operator-(loc op2)
{
loc temp;
// notice order of operands
temp.longitude = longitude - op2.longitude;
temp.latitude = latitude - op2.latitude;
return *this;
}
// Overload asignment for loc.
loc loc::operator=(loc op2)
{
longitude = op2.longitude;
latitude = op2.latitude;
return *this; // i.e., return object that generated call
}
// Overload prefix ++ for loc.
loc loc::operator++()
{
longitude++;
latitude++;
return *this;
}
int main()
{
loc ob1(10, 20), ob2( 5, 30), ob3(90, 90);
ob1.show();
ob2.show();
++ob1;
ob1.show(); // displays 11 21
ob2 = ++ob1;
ob1.show(); // displays 12 22
ob2.show(); // displays 12 22
ob1 = ob2 = ob3; // multiple assignment
ob1.show(); // displays 90 90
ob2.show(); // displays 90 90
return 0;
}

*what is operator overloading?
Operators are functions. Specifically, operators are special functions that are used to perform operations on data without directly calling methods each time. Common operators that you should be familiar with include +, -, *, /, <<, >>, and so on. All such operators can be used on primative data types in C++ to achieve certain results. For example, we can use the + operator to add together two numeric values, such as ints, floats, and doubles:
* What are the benefits of operator overloading?

By overloading standard operators on a class, you can exploit the intuition of the users of that class. This lets users program in the language of the problem domain rather than in the language of the machine.
The ultimate goal is to reduce both the learning curve and the defect rate.

program for queue Implementation using Linked List in C++

Queue Implementation using Linked List in C++

#include<iostream.h>
#include<conio.h>
struct node
{
 int data;
 struct node *link;
};
class queue
{
 struct node *front,*rear,*ptr;
 public:
 queue(){
 rear=NULL;
 front=NULL;
 }
 void enqueue(int);          
 void dqueue();
 void display();
};
  void queue::enqueue(int data)
{
  ptr=new node;
  if(rear==NULL)
   { front=ptr;
   }
   else
   {
    rear->link=ptr;
    ptr->link=NULL;
    }
    rear=ptr;
  rear->data=data;               
  cout<<"\n>>";
      }
  void queue::dqueue()
{
int item;
 if(front==NULL)
 cout<<"\nQueue is empty:\n";
 else
 {
   item=front->data;
if(front==rear)
   {
   front=NULL;
   rear=NULL;
   }
else
{
   ptr=front;
   front=front->link;
   delete ptr;
   }
   cout<<"deleted elmnt : "<<item;
 }
}

  void queue::display()
{
ptr=front;
 if(front==NULL)
    cout<<"\nQueue is empty";
 else
    {
cout<<"\nElements in queue are: ";
     while(ptr!=NULL)
{
  cout<<ptr->data<<"|";
  ptr=ptr->link;
}
    }         
}
  void main()
{
queue q;
int ch,data;
clrscr();
cout<<"\n........MENU..........\n";
cout<<"1 . enqueue\n";
cout<<"2 . dqueue\n";
cout<<"3 . display\n";
cout<<"4 . exit\n";
while(1)
{
cout<<"\n Enter your choice: ";
cin>>ch;
switch(ch)
   {
    case 1:
    cout<<"\n Enter the element: ";
    cin>>data;
    q.enqueue(data);break;

    case 2:
    q.dqueue();break;

    case 3:
    q.display();break;

    case 4:
    ch=5;break;
    default:
    cout<<"\nInvalid selection\n";break;
    }
    if(ch==5)
    break;
}
       getch();
}

What are queues in C plus plus?

A queue in any language is a singly-linked list structure that permits new data to be inserted only at the end of a list while existing data can only be extracted from the beginning of the list. Queues are also known as a first in, first out (FIFO) structure. Unlike a standard singly-linked list, the list maintains a pointer to the last node as well as the first, in order to insert new data and extract existing data in constant time.
Variations on the queue include the priority queue which permit data to be weighted, such that data with the greatest priority is promoted to the front of the queue, behind any existing data with the same or higher priority, using an insertion sort technique. Insertion is therefore achieved in linear time rather than constant time, however extraction is always in constant time.

Linked Lists

The linked list is used in many libraries/applications and for a good reason. The following are advantages it has over other containers, indirectly from the reference page on cplusplus.com:

• Efficient insertion and erasure of elements anywhere in the container (constant time).
• Iterating over the elements in forward order (linear time).
• Efficient moving elements and block of elements within the container or even between different containers (constant time).

The following only applies to a doubly linked list which I will explain later on:

• Iterating over the elements in forward or reverse order (linear time).

Something the reference doesn't explain is how it's implemented. Why would you *want* to know about that? For me, simply curiosity. For others, perhaps they may create their own type of linked list container. Either way, it's knowledge that *someone* will eventually use hopefully. 

Design

The linked list is generally pictured as a list of linear nodes that are tethered together somehow. In C/++, you generally have a structure which contains data and a pointer to the next structure container which contains data and a pointer to the next structure container... and so on. The linked list's main advantage is that it doesn't contain data in a contiguous way and rather, a flexible way. This allows for fast insertion and better overall iteration. The linked list is often even used as the basis for other containers (such as queue or stack containers).

There are several variations of the linked-list. Actually, the term "linked list" doesn't really refer to the implementation (thus, an abstract term), just the nature of how the data of the container is held (linked via references). The most common implementation of the linked list is probably the doubly linked list. The doubly linked list is a list that contains nodes that contains references to the previous *and* next link in the list. This allows for fast node erasure, faster fetching of end nodes, and more flexible iteration.

At the cost of flexibility of the doubly-linked list, it generally costs more memory to use. In large lists, consider the idea of a node being twice the size as normal. This can affect the application quite a bit. In the case that you have no reason to iterate backwards, the doubly-linked list can be considered inefficient, simply by design. std::list is a doubly linked list. As a result, if I ever come about the need for a singly-linked list, I implement my own. A singly-linked list can only iterate forward simply because the node it holds only holds a reference to the next node in the list and not the previous but comes with the merit of one less reference.

Another type of linked-list that's not used quite as often is the circular linked-list. All this is a singly/doubly-linked list where the end node iterates forward to the beginning node (and possibly vice versa). There aren't many uses for this as it generally has problems with iterating through the list but take, for instance, a list that iterates through the nodes until a given signal is received. Also, it's really a technique used with linked lists... not always in implementation although special list implementations can handle circular linked lists better than others.

In embedded systems, the use of linked lists can be expensive. The holding of each reference can be so heavy that it's undesirable to use a linked-list with nodes that only hold one location of data. Instead, they generally used what's called unrolled linked lists. In an unrolled linked list, the node holds a reference to the next and previous, like normal, but each node holds arrays of data. When you iterate through each node, you iterate through the data in the array linearly, then move on to the next node. This way we can have three or four nodes of data in one while reducing the amount of nodes altogether (therefor saving memory). However, this generally uses contiguous memory to hold nodes so it becomes difficult to move nodes that are in the array.

c program to generate 1 12 123 pattern

program to generate 1 12 123 pattern

#include<stdio.h>

void main()
{
int i,j,n;
clrscr();
printf("how many lines you need to print :");
scanf("%d",&n);
for(i=0;i<n;i++)
   {
   for(j=0;j<=i;j++)
      {
      printf("%d",j+1);
      }
    printf("\n");
   }
getch();
}

program to generate 333 22 1 series

program to generate 333 22 1 series

#include<stdio.h>

void main()
{
int i,j,n;
clrscr();
printf("how many lines you need to print :");        //program to generate 333 22 1 series
scanf("%d",&n);
for(i=n;i>0;i--)
   {
   for(j=0;j<i;j++)
      {
      printf("%d",i);                                         //  program to generate 333 22 1 series
      }
    printf("\n");
   }
getch();
}

// program to generate 333 22 1 series

C program to display perfect,abudent,and deficiant numbers

C program to display perfect,abudent,and deficiant numbers 

what is an abundant number?
An abundant number is a number with its proper factors equalling a higher number than itself

what is a perfect number?
 A perfect number is one whose positive integer factors, other than itself, add up to the number itself. For example, the factors of 6, other than itself, are 1, 2, 3, and 1 + 2 + 3 = 6. Therefore, 6 is a perfect number.
The first eight perfect numbers are:

• 6
• 28
• 496
• 8128
• 33550336
• 8589869056
• 137438691328
• 2305843008139952128

what is a deficient number?
 A deficient number is a number with its proper factors equalling a lower number than itself.

#include<conio.h>

#include<stdio.h>

#include<iostream.h>

#include<math.h>

int test(int n);

void main()

{

int i,lower,upper,temp;

clrscr();

printf("Enter the range\n");

printf("\tLower Bound?");

scanf("%d",&lower);

printf("\tUpper Bound?");

scanf("%d",&upper);

if(lower>upper)

{  

temp=lower;

lower=upper;

upper=temp;

}

    printf("Number\tType\n");

    for(++lower;lower<upper;lower++)

    switch(test(lower))

          {   

           case 0:printf("%d\tperfect\n",lower);break;

           case 1:printf("%d\tAbudant\n",lower);break;

           case 2:printf("%d\tdeficiant\n",lower);break;

          }

     getch();     

}

int test(int n)

{

 int i,sum=0;

 for( i=2;i<n;++i)

   if(n%i==0)

     sum+=i;

     printf("%d",sum);

     getch();

   if(sum==n)

     return 0;

  else

    if(sum>n)

      return 1;

    else 

      return 2;

}

program to illustrate pass by reference method

#include<iostream.h>
#include<conio.h>
class sample
{
int x;
public:
void read()
{
cout<<"Enter the value\n";
cin>>x;
}
void display()
{
cout<<"The sum is\n";
cout<<x;
}
void add(sample &s1,sample &s2)
{
x=s1.x+s2.x;
}
};
void main()
{
sample s1,s2,s3;
clrscr();
s1.read();
s2.read();
s3.add(s1,s2);
s3.display();
getch();
}

Pass by value

When you use pass-by-value, the compiler copies the value of an argument in a calling function to a corresponding non-pointer or non-reference parameter in the called function definition. The parameter in the called function is initialized with the value of the passed argument. As long as the parameter has not been declared as constant, the value of the parameter can be changed, but the changes are only performed within the scope of the called function only; they have no effect on the value of the argument in the calling function.

Pass by reference

Passing by by reference refers to a method of passing the address of an argument in the calling function to a corresponding parameter in the called function.In C, the corresponding parameter in the called function must be declared as a pointer type. In C++, the corresponding parameter can be declared as any reference type, not just a pointer type.

In this way, the value of the argument in the calling function can be modified by the called function.

Difference between pass by value and pass by reference  

In pass by value approach, the called function creates another copies of the variables passes as arguments. In this approach, the values of the original variables remain unchanged. However, we come across situations where we need to change the values of the original variables. Then the values may b passed by reference

program to represent pass by value concept

c++program code for representing  pass by value concept,also connected with class object concept
#include<iostream.h>
#include<conio.h>
class sample
{
int x;
public:
void read()
{
cout<<"Enter the value\n";
cin>>x;
}
void display()
{
cout<<"The sum is\n";
cout<<x;
}
void add(sample s1,sample s2)
{
x=s1.x+s2.x;
}
};
void main()
{
sample s1,s2,s3;
clrscr();
s1.read();
s2.read();
s3.add(s1,s2);
s3.display();
getch();
}

program to swap the values of 2 different object

c++ program code for swapping the values of different object (uses freind function concept)

c++ program code for swaping the values of different object

#include<iostream.h>
#include<conio.h>
class sample
{
int x;
public:
void read();
friend void display(sample,sample);
friend void swap(sample,sample);
};
void sample::read()
{
cout<<"Enter the value\n";
cin>>x;
}
void display(sample s1,sample s2)
{
cout<<"Before swaping\n";
cout<<"s1  "<<s1.x;
cout<<"\ns2  " <<s2.x;
}

void swap( sample s1,sample s2)
{
int t;
t=s1.x;
s1.x=s2.x;
s2.x=t;
cout<<"\nAfter swaping\n";
cout<<"s1  "<<s1.x;
cout<<"\ns2  " <<s2.x;
}
void main()
{
clrscr();
sample s1,s2;
s1.read();
s2.read();

display(s1,s2);
swap(s1,s2);
getch();
}

 what is an object?

A region of storage with associated semantics.

After the declaration int i; we say that "i is an object of type int." In OO/C++, "object" usually means "an instance of a class." Thus a class defines the behavior of possibly many objects (instances).

program to add n time in hh\mm\ss format(using class)

program to add n time using  class and object concept

program to add n numbers using class and object concept

#include<iostream.h>
#include<conio.h>
 class time
 {
 public:
 int h,m,s,oh,om,os,i,j,n,p,q;
 void read();
 void display();

 }ob;
 void time:: read()
 {
 cout<<"Enter the limit\n";
 cin>>n;
  h=0;
 m=0;
 s=0;

 for(i=0;i<n;i++)
 {
 cout<<"Enter the "<<i+1<<" time in hh/mm/ss format \n";
 cin>>oh;
 h=h+oh;
 cin>>om;
 m=m+om;
 cin>>os;
 s=s+os;
 }
 }
 void time::display( )
 {

  p=ob.s/60;
  ob.s=ob.s%60;
  q= (ob.m+p)/60;
  ob.m=(ob.m+p)%60;
  ob.h=ob.h+q;
  cout<<" time in hh/mm/ss format \n";
  cout<<ob.h<<":"<<ob.m<<":"<<ob.s;
  }
  void main()
  {
  clrscr();
  ob.read();
  ob.display();
  getch();
  }

program for queue operation

Program for queue operation ,using   class object concept.

#include<iostream.h>
#include<conio.h>
class queue
{
public:
int q[50],n,limit,front, rear;
queue()
{
cout<<"\nEnter the limit\n";
cin>>limit;
front=0;
rear=0;
}
void push();
void pop();
void peep();
};
void queue::push()
{
if(rear<limit)
{
cout<<"Enter the data\n";
cin>>q[rear];
rear++;
cout<<"Element inserted\n";
}
else
{
cout<<"\nqueue is full\n";
}

}
void queue::pop()
{
if(front<rear)
{
front++;

push operation in a queue

cout<<"\nElement is deleted\n";
}
else
{
cout<<"Queue is empty\n";
}
}


 void queue::peep()
 {
 int i;
 if(front<rear)
 {
 cout<<"The queue elements are:";
 for(i=front;i<rear;i++)
 {
 cout<<"\n"<<q[i];
 }
 }
 else
 {
 cout<<"Queue is empty\n";
 }
 }
 void main()
 {
 clrscr();
 queue ob;
 int n,limit;
 do
 {
 cout<<"\nMENU\n\n1.PUSH\n2.POP\n3.PEEP\n4.EXIT\n";
 cout<<"\nENTER YOUR CHOICE:";
 cin>>n;
 switch(n)
 {
 case 1:ob.push();
       break;
case 2:ob.pop();
break;
case 3: ob.peep();
break;
}

}while(n!=4);
getch();
}

what is a queue i?

A queue is a singly linked list that models a first in first out model (just as a queue of diners are dealt with on a first come first served basis). Insertions always occur at the tail of the queue and extractions always at the head.
A variation of the queue is a priority queue where nodes are weighted such that those with higher priority are moved in front of those with lower priority. This is akin to diners who have a reservation being moved to the head of the queue. In this case, insertions always occur at the head but the head node will pass the data onto the next node if the data has lower priority. The process continues until the data has higher priority than the current node at which point is it is placed in front of the current node. If the current node has no next node to pass the data onto, the data becomes the tail node. This is known as an insertion sort.

Difference between Stack and Queue  

Stack is a collection of objects that works in LIFO (Last in First out) mechanism while Queue is FIFO (First in First out). This means that the object that is inserted first is removed last in a stack while an object that is inserted first is removed first in a queue

program for all stack operation

c++ program for stack operations..(operation include pop,peep,push)
#include<iostream.h>
#include<conio.h>
class stack
{
public:
int s[50],n,item,top;
void read();
void push();                // for stck insertion
void pop();                //for stack deletion
void display();          // displaying stack element
};
void stack:: read()
{
cout<<"Enter the limit of the stack\n";
cin>>n;
}
void stack::push()
{
top++;
if(top==n)
{
cout<<"Stack full\n";
getch();
}
else
{
cout<<"Enter the item\n";
cin>>item;
s[top]=item;
cout<<"Element inseted into the stack\n";
}
}
void stack::pop()
{
if(top==-1)
{
cout<<"Stack empty\n";
}
else
{
top--;
cout<<"Element deleted\n";
}
}
 void stack::display()
 {
 int i;
 if(top==-1)
 {
 cout<<"Stack is empty\n";
 getch();
 }
 else
 {
 cout<<"The stack elements are:";
 for(i=top;i>=0;i--)
 {
 cout<<"\n"<<s[i];
 getch();
 }
 }
 }
 void main()
 {
 clrscr();
 stack a;
 a.top=-1;
 int n,c,k;
 a.read();
 do
 {
 cout<<"\nMENU\n\n1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT\n";
 cout<<"\nENTER YOUR CHOICE:";
 cin>>n;
 switch(n)
 {
 case 1:
 cout<<"\nenter number of insertion:";
 cin>>c;
 for(k=0;k<c;k++)
 {
 a.push();
 }
 break;
case 2:
 cout<<"\nenter number of deletion:";
 cin>>c;
 for(k=0;k<c;k++)
 {
 a.pop();
 }
 break;
case 3:
 a.display();
 break;

}
}while(n!=4);
getch();
}
what is stack operation?
Stack is an ordered group of homogeneous items. —Items are added to and removed from the top of the stack (the most recently added items are at the top of the stack). —The last item to be added is the first to be removed (LIFO: Last In, First Out). A stack is an ordered collection of items into which new items may be inserted and from which items may be deleted at one end called the TOP of the stack.
—The implementation of stack provides for the insertion and deletion of items (at run time), so that a stack is a dynamic, constantly changing object.—

Difference between Stack and Queue  

Stack is a collection of objects that works in LIFO (Last in First out) mechanism while Queue is FIFO (First in First out). This means that the object that is inserted first is removed last in a stack while an object that is inserted first is removed first in a queue

Recursive program for finding tha greatest common divisor.

greatest common divisor(GCD) or HCF highest common factor....

#include<iostream.h>
#include<conio.h>
#include<process.h>
void hcf(int,int);
void main()
{
int a,b,c;
clrscr();
cout<<"Enter two numbers\n";
cin>>a>>b;
hcf(a,b);
getch();
}
void hcf(int a,int b)
{
int rem;
if(b>0)
{
rem=a%b;
a=b;
b=rem;
hcf(a,b);  //recursive function call for greatest common factor
}
cout<<" The GCD is\t"<<a;
getch();
exit(0);
}

method 2
#include<iostream.h>
#include<conio.h>
int gcd(int,int);
void main()
{
int a,b,c;
clrscr();
cout<<"Enter two numbers\n";
cin>>a>>b;
c=gcd(a,b);
cout<<"The Greatest Common Divisor is \t"<<c;
getch();
}
int gcd(int n,int m)
{
if(n%m== 0)
{
 return m;
 }
 else
 return gcd(m,n%m);
 }

what is recursion in c++?

Recursion, in any programming language, refers to, most commonly, a call to a function inside that function, (i.e a function calling itself) .