In this article you will learn about dynamic memory allocation. Dynamic memory allocation is made using dynamic variables. The variables that we have created so far are static variables. Static variables are created during compile time. On the other hand, dynamic variables, which can be of any basic data type or structured data type, can be created or destroyed during runtime of a program. A dynamic variable is not referenced by a name, rather it is referenced through a pointer that contains the address in memory of the dynamic variable referenced. Thus every dynamic variable created has an associated pointer by which it is referenced.

Static Memory Allocation

Though arrays can be used for implementing a list of data items, they are of static structure. A static structure is one whose size is fixed at compile time. In other words, the programmer must know the size of the array or data while writing the programs. A static structure exists as long as the part of the program or block in which it is declared is executing.

But there are so many instances where we work with lists and we have no idea of the number of data items in such lists. The usual approach in this situation us to declare an array large enough to hold the maximum amount of data we could logically expect. For example, consider the following declaration:
int a[500];

In this you can store 500 integer values in memory. The moment you declare this, 1000 bytes are reserved for storing 500 integers in it. However it may so happen that when we actually run the program we might be wanted to storing only 100 integer values. Even in this case 1000 bytes would be reserved in memory and unfortunately you are using only 200 bytes and thus it would result in wastage of memory of 800 bytes.

Another possibility is that when you run the program you need to store more than 500 integer values, say 600. In this case, the array would fall short in size of 200 bytes. The ultimate conclusion is that when we use arrays static memory allocation takes place because there is no way to decrease or increase the array size during the program’s execution. This problem is overcome by dynamic memory allocation.

Dynamic Memory Allocation

When memory is allocated during runtime, it is called as dynamic memory allocation. C provides many built-in library functions, such as malloc(), calloc(), and realloc() that allocates memory dynamically. Since these functions allocate memory during the execution time, they are often known as “dynamic memory allocation functions” and the dynamic memory allocation is the process of allocating memory at the run time instead of allocation at the compilation time. Additionally C provides free() function for efficient dynamic memory deallocation. These functions are defined and declared in header files. Let us discuss these functions one by one.

malloc()

The declaration of malloc() function is:
(void *) malloc (size);

The malloc() function allocates a memory block of at least size bytes from the free memory space. If the size is 0, malloc() allocates a zero-length item. This function returns a pointer to the newly allocated memory block, of course if it successfully allocates a memory block; otherwise it returns a NULL value. The default return type of malloc() function is void *. In earlier article we have already studied that the NULL is defined in header file. Let us see a simple program that illustrates the use of malloc() function.

main()
{
int num, i;
int *ptr;

printf("\nHow many integer numbers you want to store? ");
scanf("%d", &num);

ptr = (int *)malloc(num*sizeof(int));    /* creating memory dynamically */

if (ptr==NULL)
{
printf("\nInsufficient memory space for dynamic memory allocation.");
exit(0);
}
printf("\nPlease enter %d integer values : \n", num);

for(i=0; i scanf("%d", ptr+i);

printf("\nYou have entered these integer values.\n");
for(i=0; i printf("\n%d", *(ptr+i));
free(ptr);
}

The output of this program is as….

How many integer numbers you want to store? 7

Please enter 7 integer values:
11
22
33
44
55
66
77

You have entered these integer values.

11
22
33
44
55
66
77

In this program, we must ask for the number of integers to be created during run time and then allocate only as much as memory is really needed to store these numbers. If there is sufficient memory space then the malloc() function returns the starting address of the memory block in an integer pointer ptr. Since we are creating memory space for integer values dynamically therefore it is necessary to typecast the address being returned, which is (int *) in this case. We know that the storage space pointed to by the return value is guaranteed to be suitably aligned for storage of any type of object. That’s why to get a pointer to a type other than void, use a typecast on the return value.

calloc()

The C library provides another function calloc() to allocate memory space at runtime. The declaration of calloc() function is:
(void *) calloc (num, size);

Here num specifies the number of data items to allocate and size specifies the size of each data item. The calloc() function works exactly similar to malloc() function except for the fact that it needs two arguments rather than one as in malloc() function. But like malloc() function, calloc() function returns a pointer to the newly created block if there is sufficient amount of free memory and on failure it returns a NULL. Since it also returns a void pointer, therefore it should be typecast to an appropriate pointer type before dereferencing, like malloc(). The following program illustrates this fact.

main()
{
int num, i;
int *ptr;

printf("\nHow many integer numbers you want to store? ");
scanf("%d", &num);

ptr = (int *)calloc(num, sizeof(int));

if (ptr==NULL)
{
printf("\nInsufficient memory space for dynamic memory allocation.");
exit(0);
}
printf("\nPlease enter %d integer values : \n", num);

for(i=0; i scanf("%d", ptr+i);

printf("\nYou have entered these integer values.\n");
for(i=0; i printf("\n%d", *(ptr+i));
free(ptr);
}

The output of this program is similar to previous one.

Another main difference between malloc() and calloc() functions lies in the fact that where calloc() initializes the allocated space to zeros, malloc() does not provide any initialization. Therefore the space allocated by malloc() contains garbage initially. This program illustrates this difference.

main()
{
int num, i;
int *ptr1, *ptr2;

printf("\nHow many integer numbers you want to store? ");
scanf("%d", &num);

ptr1 = (int *)malloc(num*sizeof(int));

if (ptr1==NULL)
{
printf("\nInsufficient memory space for dynamic memory allocation.");
exit(0);
}
ptr2 = (int *)calloc(num, sizeof(int));
if (ptr2==NULL)
{
printf("\nInsufficient memory space for dynamic memory allocation.");
free(ptr1);
exit(0);
}

printf("\nDefault initial values in malloc() function are as....\n");
for(i=0; i printf("\n%d", *(ptr1+i));

printf("\n\nDefault initial values in calloc() function are as....\n");
for(i=0; i printf("\n%d", *(ptr2+i));
free(ptr1);
free(ptr2);
}

Here is the output of this program….

How many integer numbers you want to store? 5

Default initial values in malloc() function are as....

18
0
35
0
5036

Default initial values in calloc() function are as....

0
0
0
0
0

realloc()

For whatever reason, the memory that was previously dynamically allocated is increased or reduced by the function realloc(). The declaration of realloc() function is as:
(void *) realloc (ptr, size);

This function changes the size of an allocated block of memory pointed to by the pointer variable ptr to the block to size, copying the contents to a new location, if necessary. Here the ptr is the return value from the last call to malloc() or calloc() or realloc(). If pointer-variable is a null pointer, realloc() works just like malloc(). If there is sufficient free memory then the realloc() function returns the address of the reallocated block, which might be different from the address of the original block. Unfortunately it realloc() fails, it returns a NULL value. This program illustrates the use of realloc() function.

main()
{
int num1, num2, i;
int *ptr;

printf("\nHow many integer numbers you want to store? ");
scanf("%d", &num1);

ptr = (int *)malloc(num1*sizeof(int));

if (ptr==NULL)
{
printf("\nInsufficient memory space for dynamic memory allocation.");
exit(0);
}

printf("\nPlease enter %d integer values.\n", num1);
for(i=0; i scanf("\n%d", (ptr+i));
printf("\nYou have entered these values....\n");
for(i=0; i printf("\n%d", *(ptr+i));

printf("\nHow many integers you want more? ");
scanf("%d", &num2);
ptr = (int *)realloc(ptr, sizeof(num2));

if (ptr==NULL)
{
printf("\nInsufficient memory space for dynamic memory allocation.");
exit(0);
}

printf("\nPlease enter %d more integer values.\n", num2);
for(i=0; i scanf("\n%d", (ptr+num1+i));
printf("\nYou have entered these integer values....\n");
for(i=0; i printf("\n%d", *(ptr+i));
free(ptr);
}

The output of this program is as….

How many integer numbers you want to store? 4

Please enter 4 integer values.
11
33
55
77

You have entered these values....

11
33
55
77
How many integers you want more? 2

Please enter 2 more integer values.
99
111

You have entered these integer values....

11
33
55
77
99
111

free()

The free() function is used to deallocate a memory block previously allocated by malloc(), calloc() and realloc() functions. The declaration of free() function is as:
void free (void *ptr);

Once the memory has been released, it can not be reused. It can be reused as a subsequent call to malloc(). The ptr is the starting address of the previously allocated memory that has to be released. One main point to note is that you should never pass an uninitialized pointer or a pointer to a variable not allocated by malloc() or calloc() or realloc() functions. if you try to attempt so it would be very dangerous and disastrous. Now let us see some examples that illustrate the use of these functions:

Example-1: Write a program that arranges a set of numbers in ascending order using pointer notations.

main()
{
int *ptr;
int i, j, n, temp;

printf("\nHow many integer numbers you want to sort? ");
scanf("%d", &n);
printf("\nPlease enter any %d integer numbers.\n", n);
ptr = (int *)malloc(n*sizeof(int));
for(i=0; i scanf("%d", ptr+i);
printf("\nUnsorted array is : \n");
for(i=0; i printf("%d\n", *(ptr+i));
for(i=0; i {
for(j=i; j {
if (*(ptr+i) > *(ptr+j))
{
temp = *(ptr+i);
*(ptr+i) = *(ptr+j);
*(ptr+j) = temp;
}
}
}

printf("\nSorted array is : \n");
for(i=0; i printf("%d\n", *(ptr+i));
free(ptr);
}

Here is the output of this program….

How many integer numbers you want to sort? 5

Please enter any 5 integer numbers.
14
11
15
13
12

Unsorted array is :
14
11
15
13
12

Sorted array is :
11
12
13
14
15

Creating Strings Dynamically

You can also create strings of any length dynamically. However the syntax of creating a dynamic string is similar to creating a number of integers dynamically. For example, if you want to create a string of 40 characters then you will use the following statements:

char *cptr;
cptr = (char *) mallloc (40);
or
cptr = (char *) callloc (40, 1);

Similarly you can create a string of ‘n’ number of character. Let us see a simple program that illustrates this fact.

main()
{
char *str;
char name[20];
int len;
printf("\nEnter the string : ");
scanf("%s", name);

len = strlen(name);
str = (char *)malloc(sizeof(len));
strcpy(str, name);
printf("Duplicate string : %s", str);
free(str);
}

The output of this program is as….

Enter the string : Tendulkar
Duplicate string : Tendulkar

Creating Multi-Dimensional Arrays Dynamically

In earlier section, you have studied how to create a number of items dynamically at run time. In this section you will study how to create a two-dimensional array when the size is not known during the writing of a program. This can be achieved by allocating a single-dimensional array of pointers, where each pointer representing a row, and then allocating each row as a normal single dimensional array. For example, a matrix ‘num’ of size m*n of int variables is created dynamically as:

int **num;

num = (int **) malloc (m*sizeof(int *));

for (i=0; i num[i] = (int *) malloc (n*sizeof(int));

Accessing a data item in row ‘i’ and column ‘j’ is done as usual, using the expression mat[i][j]. This program illustrates dynamic allocation of a two-dimensional array.

main()
{
int i, j, row, col;
int **num;
printf("\nEnter the row numbers : ");
scanf("%d", &row);
printf("\nEnter the column numbers : ");
scanf("%d", &col);

num = (int **)malloc(row*sizeof(int *));
if (num==NULL)
{
printf("\nInsufficient memory space for dynamic memory allocation.");
exit(0);
}
for(i=0; i num[i] = (int *)malloc(col*sizeof(int));

printf("\nEnter the elements of a matrix (%d*%d) : \n", row, col);

for(i=0; i for(j=0; j scanf("%d", &num[i][j]);
printf("\nEnter the elements of a matrix (%d*%d) : \n", row, col);

for(i=0; i {
printf("\n");
for(j=0; j printf("%d\t", num[i][j]);
}
}

Here is the output of this program….

Enter the row numbers : 3

Enter the column numbers : 4

Enter the elements of a matrix (3*4) :
1 2 3 4
5 6 7 8
9 10 11 12

Elements of a matrix (3*4) :

1 2 3 4
5 6 7 8
9 10 11 12

Creating Structures Dynamically

Like arrays, you can also create structures dynamically. When you create a structure dynamically you have to use the structure data type in malloc() function. For example, let us have a following structure type:

struct Employee
{
char name[20];
int age;
char section;
};

Then you can create a structure of this type dynamically as:

struct Employee *eptr;
eptr = (struct Employee *) malloc (sizeof(struct Employee));

Now let us see a simple program that illustrates the use of creating a structure dynamically.

main()
{
struct Employee
{
char name[20];
int age;
float salary;
};

struct Employee *eptr;
float a=10, *b=&a;

eptr = (struct Employee *)malloc(sizeof(struct Employee));

printf("\nEnter Employee name, age and salary : ");
scanf("%s %d %f", eptr->name, &eptr->age, &eptr->salary);
printf("Employee name, age and salary : %s %d %f", eptr->name,
eptr->age, eptr->salary);
free(eptr);
}

Here is the output of this program….

Enter Employee name, age and sex : Aditya 35 10000.50
Employee name, age and salary : Aditya 35 10000.500000

Similarly you can create an array of ‘n’ structures as:

eptr = (struct Employee ) malloc (n * sizeof(struct Employee));

The following program creates array of structures dynamically.

main()
{
struct Employee
{
char name[20];
int age;
float salary;
};
struct Employee *eptr;

int i, n;
float a=10, *b=&a;

printf("\nHow many structures you want to create? ");
scanf("%d", &n);
eptr = (struct Employee *)malloc(sizeof(struct Employee)*n);
printf("\n");
for(i=0; i {
printf("Enter Employee #%d name, age and salary : ", i+1);
scanf("%s %d %f", (eptr+i)->name, &(eptr+i)->age, &(eptr+i)->salary);
}
for(i=0; i {
printf("\nEmployee #%d name, age and salary : %s %d %f", i+1,
(eptr+i)->name, (eptr+i)->age, (eptr+i)->salary);
}
free(eptr);
}

Here is the output of this program….

How many structures you want to create? 4

Enter Employee #1 name, age and salary : Mohit 20 4500.75
Enter Employee #2 name, age and salary : Rahul 24 5000.50
Enter Employee #3 name, age and salary : Aditya 30 8775.25
Enter Employee #4 name, age and salary : Amit 25 7500.00

Employee #1 name, age and salary : Mohit 20 4500.750000
Employee #2 name, age and salary : Rahul 24 5000.500000
Employee #3 name, age and salary : Aditya 30 8775.250000
Employee #4 name, age and salary : Amit 25 7500.000000

This property of creating dynamic structure variables is most used in dynamic data structures, such as singly linked lists, doubly linked lists, linked stacks and linked queues, trees and graphs.

Memory can be allocated either statically or dynamically. C uses runtime library functions, such as malloc(), calloc() and realloc(), for allocation of memory dynamically and free() function for releasing the memory dynamically. You can create memory space dynamically for one-dimensional arrays, two-dimensional arrays, strings and structures.

 

In this article I am going to write about virtual function – another type of polymorphism. Polymorphism is another essential feature of an Object – Oriented Programming language. It is the polymorphism that enables us to deal with different types of object as if they are all of the same type. We have already seen two types of polymorphism – function overloading and operator overloading. The third type of polymorphism simplifies the syntax of performing the same operation with different classes through virtual functions.

This type of polymorphism simplifies the syntax of performing the same operation with a hierarchy of classes. With the help of polymorphism we can easily keep the interface to the classes clearly. And in this case we do not need to have unique function names for similar operation on each derived classes. This type of polymorphism is supported by virtual keyword. For the new C++ programmer the concept of virtual function may be difficult to understand. But it would be harmful if you skip this topic because there is no analog to virtual function in procedural languages. Thus just read on, the concept of virtual function would soon become clearer.


Virtual Functions

Let us understand this concept by taking a simple program – v1.cpp that has normal member functions in base class as:

// Program – v1.cpp: Without virtual function

#include
 class father 
 {
 public:
 void display()
 {
 cout<< “\nI am your father”;
 }
 };
 class baby1 : public father
 {
 public:
 void display()
 {
 cout << “\nI am your first baby”;
 }
 };
 
 class baby2 : public father
 {
 public:
 void display()
 {
 cout << “\nI am your second baby”;
 }
 };
 
 void main()
 {
 baby1 b1;
 baby2 b2;
 father *fptr;
 fptr=&b1;
 fptr-> display();
 fptr=&b2;
 fptr -> display;
 }

In this program we have derived two classes baby1 and baby2 from the base class father. Each of these three classes has a number functions display (). In main () we have created two objects b1 and b2 from two derived classes baby1 and baby2 respectively and a pointer fptr to base class father.

In first assignment statement we have

fptr =&b1;

Should this not give us an error, since we are assigning an address of one type to a pointer of another? No, because unlike normal pointers, the compiler does not flash an error message. In inheritance a pointer or a reference to a base class type can refer to an object of a derived class type. In this case the pointers to object of a derived class are type compatible with pointer to objects of the base class. Such type of casting is called a upcasting. Similarly a reference to base is compatible with any object of a derived class.

When we execute next statement

fptr-> display()

One may ask - Which function gets called – display() of derived class baby1 or display () of base class, father.

The same question arises in the last statement

fptr-> display()

In these cases the function in the base class gets called. Thus when we execute this program we get the following output….

I am your father
I am your father

It happens so because the compiler ignores the contents of the pointer and selects the member function that matches the type of the pointer. It is good sometimes but it is does not like that what we have discussed at the beginning of this article that is accessing functions of different classes using the same statement. Here we are going to discuss the concept of polymorphism, in which we manipulate more than one derived type with a base class pointer or reference. 

If we make a small change in this program by using the keyword virtual in front of the function display() in the base class, we can get the desired output.

Program v2.cpp illustrates this concept.

// Program – v2.cpp : With virtual function

#include 
 class father
 {
 public:
 virtual void display()
 {
 cout << “\nI am your father”;
 }
 };
 class baby1 : public father
 {
 public:
 void display()
 {
 cout << “\nI am your first baby”;
 }
 };
 
 class baby2 : public father
 {
 public:
 void display()
 {
 cout << “\nI am your second baby”;
 }
 };
 
 void main()
 {
 baby1 b1;
 baby2 b2;
 father *fptr;
 fptr=&b1;
 fptr-> display();
 fptr=&b2;
 fptr ->display();
 }

Now if we execute this program, the out put will be as:

I am your first baby
I am your second baby

Using a base class pointer, when we refer to any member function it retrieves the actual derived type of an object. From the output of this program, it is clear that the same function call

fptr->display ();

executes different functions, depending on the contents of fptr.

Thus a non virtual pointer sets up in any derived class always points to the member function in the base class only. Whereas when virtual functions are defined, the virtual pointer points to member function of the derived class. That’s why in this program the compiler has selected the function based on the contents of the pointer fptr, not on the type of the pointer.

When the compiler compiles this program, it does not know which object’s address fptr may contain. It could be the address of an object of the baby1 class or of the baby2 class. So it does not know which version of display() would get called. In this case the compiler leaves the decision until the program is running. At run  time after receiving  the address of an  appropriate object, it calls the appropriate function. This is called late binding or dynamic binding. On the other hand if the functions are chosen during compile time, the binding is called as early or static binding. 

We can also achieve the same by using references instead of pointer as:

// Program – v3.cpp : With virtual function

#include 
 class father
 {
 public:
 virtual void display()
 {
 cout << “ I am your father”;
 }
 };
 class baby1 : public father
 {
 public:
 void display()
 {
 cout << “I am your first baby”;
 }
 };
 
 class baby2 : public father
 {
 public:
 void display()
 {
 cout << “I am your second baby”;
 }
 };
 void main()
 {
 baby1 b1;
 baby2 b2;
 
 father &f1ref=b1;
 f1ref.display();
 father &f2ref=b2;
 f2ref.display();
 }

When we execute this program, we get the same output as previous one.

Pure Virtual Function

A pure virtual function is a virtual function with no body. In a situation, where the function of the base class are not used we use the notation=0 in the function declaration.
For example the statement

virtual void display()=0;

declare the function display() to be a pure virtual function. Here the value 0 is not assigned to anything. It is used to simply tell the compiler that function will be pure that is have no body.

Here any intelligent person may think that if we remove the body of the virtual function then  can we not remove the function of together? But unfortunately it would be wrong. Because without a function display() in base class, the statement like

fptr-> display()

would be invalid. Since fptr is a pointer to a base class. And we know that a base class does not have any knowledge of its derived class’s members.

Program v4.cpp illustrates this concept of pure virtual function.

// Program – v4.cpp : Pure virtual function

#include
class father
{
 public:
virtual void display()=0;
};
class baby1 : public father
 {
 public:
 void display()
 {
 cout << “I am your first baby”;
 }
};

class baby2 : public father
{
 public:
 void display()
 {
 cout << “I am your second baby”;
 }
};
void main()
{
 baby1 b1;
 baby2 b2;
 father &f1ref=b1;
 father &f2ref=b2;
 f1ref.display();
 f2ref.display();
}

A More Practical Example

We have already seen that an upcasting can convert a pointer that referes to an object of class type to a pointer to a class in the same class hierarchy. It is achieved by using virtual functions. A virtual function appears to exits but does not exist in reality. A virtual function is defined and declared in the base class as being virtual. It is then used by several derived functions by setting up pointers.

Let us assume that our program defines a class library to represent the different areas of shape. Let we have two different classes called Triangle and Rectangle. Each of these two classes has a member function area_display() to display the are of relevant shape on the screen. If we want to display the are of numerous triangles and rectangles, we can create an array that holds pointers to all the different objects in the class hierarchy.

The array might be defined as:

Shape * sptr[5];

And if we want to display the areas of different shapes, we will use the following loop:

for(i=0; i<20; i++)
sptr[i]->area_display();

Earlier we have seen that how the same function call is responsible for the execution of completely different function. It means that when sptr[i] contains address of the Triangle object, it would call

Triangle :: area_display()

function. When it contains the address of the Rectangle object it would call the

Rectangle :: area_display() 

function. It happens so because the array sptr[] has been defined to contain shape pointer and not triangle or rectangle pointers. This concept is called the polymorphism. Here the functions have the same name, area_display(), but different functions from different classes are executed. And it depends upon the contents of sptr [i]

To achieve this, following conditions must be met:

1. All the different classes Triangle and Rectangle must be derived from a single base class, Shape.
2. The area_display() function must be declared to be virtual in the base class, Shape. Once a function is declared virtual in a base class, its definition remains virtual in all derived classes; even when the keyword virtual is not repeated in the definition of the derived class.

For this we define a base class Shape and from this base class we derive two classes Triangle and Rectangle as:

class Shape
 {
 // ….
 };
 class Triangle : public Shape
 {
 // ….
 };
 class Rriangle : public Shape
 {
 // ….
 };

Now let us see how to implement this in practical use.

Let we create a base class Shape which stores two double type data members that could be used to compute the area of figure. From this base class, we derive two classes Triangle and Rectangle. In base class we define a member function getdata() to initialize base class data members and another member function area_display() to compute and display the area of figure. Make the function area_display() as a virtual function and redefine these functions in the derived classes to match their requirements.

In case of Triangle class, these two values of base class will treated as base and height whereas in Rectangle these two values of base class will treated as length and breadth of rectangle. The area is computed as:

Area of triangle = (x0 * y0) / 2;
 Area of rectangle = x0 * y0;

Following program does this.

// Program – v5.cpp

#include
class Shape
{
 protected :
 double x0, y0;
 public :
 void getdata(double x, double y)
 {
 x0 = x;
 y0 = y;
 }
 virtual void area_display() = 0;
};
class Triangle : public Shape
{
 public :
 void getdata(double x, double y)
 {
 Shape :: getdata(x,y);
 }
 void area_display()
 {
 double area = (x0 * y0)/2.0;
 cout << "\n Area of triangle = " << area;
 }
};
class Rectangle : public Shape
{
 public :
 void getdata(double x, double y)
 {
 Shape :: getdata(x,y);
 }
 void area_display()
 {
 double area = (x0 * y0);
 cout << "\n Area of rectangle = " << area;
 }
};
void main()
{
 Triangle *tptr;
 Rectangle *rptr;
 Shape *sptr[2];
 int i;
 tptr = new Triangle;
 rptr = new Rectangle;
 tptr->getdata(20.0,30.0);
 rptr->getdata(20.0,20.0);
 sptr[0] = tptr;
 sptr[1] = rptr;
 for(i=0; i<2; i++)
 sptr[i]->area_display();
}

The output of this program is

Area of triangle =300
Area of rectangle =400

Abstract Classes

In program v5.cpp we have not created any object of class Shape because there is no need to make objects of Shape class. Here Shape class is used just to derive Triangle and Rectangle classes. Such class is known as an abstract class.

Thus an abstract class is a class which is not used to create any objects, rather than it is used to derive the classes. An abstract classes one that contain at least one pure virtual function and it defines properties common to other classes derived from it. We can also create a pointer or a reference to an abstract class. This allows an abstract class to be used as a base class, pointers to which can be used to select the proper virtual function.

Here one should remember that it is necessary to override a pure virtual function in all the derived classes from this abstract class. If you do not override then the derived class is also treated as an abstract class. However if you try to create an object of the abstract class then the compiler will certainly flag an error message.

For example, if you try to execute the following program

// Program - v6.cpp

#include 
class Father
{
 public :
 virtual void display() = 0;
};
class Baby1 : public Father
{

};
class Baby2 : public Father
{

};
void main()
{
 Father *fptr;
 Baby1 b1;
 Baby2 b2;
 fptr = &b1;
 fptr->display();
 fptr = &b2;
 fptr->display();
}

then the compiler reports the following error messages:

Cannot create instance of abstract class 'Baby1'
Cannot create instance of abstract class 'Baby2'

Here one should remember that an object of a derived class can be assigned to a base class object. When you do this, the compiler copies only the base portion of the derived object. It means that it has no knowledge of data members or member functions which are defined in derived classes only.

For example let we have a base class First, which has two data members a and b and a derived class Second also has two data members c and d. It means that the derived class Second now has total four data members whereas the base class First has only two. Now if you assign the object of a derived class Second to an object of base class First then it simply copies a and b of Second class object and truncates the derived portion of the derived object, which is c and d. It happens so because there is no way to find in advance that a derived class can have how many number of data members in advance.

Following program illustrates this concept.

// Program - v7.cpp

#include 
class First
{
 protected :
 int a, b;
 public :
 First(int aa=0, int bb=0)
 {
 a=aa;
 b=bb;
 }
 virtual void display()
 {
 cout << "\n" << a << "\t" << b;
 }
};
class Second : public First
{
 private :
 int c, d;
 public :
 Second(int aa=0, int bb=0, int cc=0, int dd=0) : First(aa,bb)
 {
 c=cc;
 d=dd;
 }
 virtual void display()
 {
 cout<<"\n"<<<"\t"<<<"\t"<<<"\t"<
 }
};
void main()
{
 First f(10,20);
 Second s(100,200,300,400);
 f.display();
 s.display();
 f=s;
 f.display();
}

When you execute this program you get the following output....

10    20
100    200    300    400   
100    200

From this output it is clear that the base class object removes only the derived portion of the derived class object rather that simply changing the meaning of an address as when using a pointer or a reference.

Like this we know that a pointer of base class can contain the address of a derived class object. Similarly a pointer to a base class object has no knowledge of member functions that exist only in derived classes. It has knowledge of member functions, which are declared as virtual in base class. Following program illustrates this concept. 

// Program - v8.cpp

#include 
class Father
{
 public :
 virtual void display() = 0;
};
class Baby1 : public Father
{
 public :
 void display()
 {
 cout << "\nI am derived from Father.";
 }
 void child1()
 {
 cout << "\nI am pure baby 1.";
 }

};
class Baby2 : public Father
{
 public :
 void display()
 {
 cout << "\nI am derived from Father.";
 }
 void child2()
 {
 cout << "\nI am pure baby 2.";
 }

};
void main()
{
 Father *fptr;
 Baby1 b1;
 Baby2 b2;
 fptr = &b1;
 fptr->display();
 fptr->child1();
 fptr = &b2;
 fptr->display();
 fptr->child2();
}

When you execute this program you get the following output....

'child1' is not a member of 'Father1;
'child2' is not a member of 'Father1;

If you want to call a function at any level in a class hierarchy through a base class pointer then that function must be declared as virtual in the base class, such as shown in following program

// Program - v9.cpp

#include 
class Father
{
 public :
 virtual void display() = 0;
 virtual void child() = 0;
};
class Baby : public Father
{
 public :
 void display()
 {
 cout << "\nI am derived from Father.";
 }
 void child1()
 {
 cout << "\nI am pure baby.";
 }

};
void main()
{
 Father *fptr;
 Baby b;
 fptr = &b;
 fptr->display();
 fptr->child();
 
}

Now when we execute this program, we will get the following output….

I am derived from Father.
I am pure baby.

Virtual Destructors

We already know that when an object of a derived class is created then the compiler calls the base class constructor first and then derived class constructor. And the process of calling destructors is just reverse. The destructor of a derived class is called before the base class destructor. For a multi level inheritance, the constructor of the base class is called first and then the more derived constructor and so on. The destructor starts at the most derived class and works its way down to the base class. This process of calling constructor  and destructors is handled by the compiler automatically.

It is good as well as safe. Since the derived class can access the class members of the base class while the reverse is not true. Therefore it is good and safe to set up the class data members of a base class constructor before the derived class constructor. Similarly in order to destroy an object safely the derived class destructor is called before the base class destructor.

But thing are different when we create a derived class object using a new operator and then assigns the address of this object to a pointer to a base class object, as illustrated in program v10.cpp

// Program - v10.cpp

#include 
#include 
class Father
{
 public :
 Father()
 {
 cout << "\nFather Constructor.";
 }
 ~Father()
 {
 cout << "\nFather Destructor.";
 }
};
class Baby : public Father
{
public :
 Baby()
 {
 cout << "\nBaby Constructor.";
 }
 ~Baby()
 {
 cout << "\nBaby Destructor.";
 }

};
void main()
{
 Father *fptr;
 Baby *bptr = new Baby;
 fptr = bptr;
 delete fptr;
}

When you execute this program, you get the following output….

Father Constructor
Baby Constructor
Father Constructor

This program does not call the derived class destructor, because the statement

delete fptr;

calls the base class destructor only even though it points to the object of Baby class. The delete operator does not know at run time the type of the object pointed by fptr. Therefore if you the execution of the derived class destructor prior to the base class destructor then declare it a virtual destructor as:

virtual ~Father()
 {
 cout << "\nFather Destructor.";
 }

Program – v11.cpp illustrates the use of virtual destructor.

// Program - v11.cpp

#include 
#include 
class Father
{
 public :
 Father()
 {
 cout << "\nFather Constructor.";
 }
 virtual ~Father()
 {
 cout << "\nFather Destructor.";
 }
};
class Baby : public Father
{
public :
 Baby()
 {
 cout << "\nBaby Constructor.";
 }
 ~Baby()
 {
 cout << "\nBaby Destructor.";
 }

};
void main()
{
 Father *fptr;
 Baby *bptr = new Baby;
 fptr = bptr;
 delete fptr;
}

When you execute this program, you get the following output….

Father Constructor
Baby Constructor
Baby Destructor
Father Constructor

Thus if we delete an object identified by a pointer or reference then the destructor for a base class object should be virtual functions. After using virtual destructors, it is guaranteed that the program will first call the object destructor instead of the destructor associated with the pointer or a reference.

After declaring a base class destructor, the compiler calls the correct type of destructor functions irrespective of the type of the pointer. Now when we compile this program, the delete operator executes the Baby destructor first and then Father destructor.

However, in this program the base class needs no special destruction, but still you must provide a virtual destructor (with an empty statement block) to permit appropriate destruction calls for dynamically allocated object. Here one main point to note is that although destructor functions can be virtual, constructor functions can not be virtual.

Virtual Functions Without Derived Overrides

Can you guess the output of a program in which the derived class has no function to override the base class’s virtual function? For example, consider the following program….  

// Program - v12.cpp

#include 
class Father
{
 public :
 virtual void display()
 {
 cout << "\nBase class virtual function.";
 }
};
class Baby1 : public Father
{

};
class Baby2 : public Father
{

};
void main()
{
 Father *fptr;
 Baby1 b1;
 Baby2 b2;
 fptr = &b1;
 fptr->display();
 fptr = &b2;
 fptr->display();
}

Here when this program is executed, the compiler executes the base class’s function display() regardless of the pointer or reference type. Thus the output of this program is as:

Base class virtual function.
Base class virtual function.

Friends

The primary objective of C++ classes is that it supports the great OOPs goal of data hiding. A class encapsulates data and member functions into a single entity and allows us to change the private data only by working through member functions. So nonmember functions are not allowed to access an object’s private or protected data. However, sometimes we have to make an exception to this rule to avoid programming inconvenience. Sometime some specific outside functions need to read and write private data members directly. For such type of situation C++ provides a keyword called friend. A friend function is a nonmember function that is granted access to a class’s private members. Similarly a friend class is a class whose member functions can access another class’s private members.

Friend Functions

One of the most common reasons for using a friend function is when we want a function to operate on objects of two different classes. Logically, such a function should be a member of both classes. But it is impossible. The only way to achieve this goal is by using a friend function that acts as a bridge between two different classes. A friend function belongs to neither, and able to access both.

Following program illustrates this concept.

// Program – v13.cpp : Friend function

#include 
class Second;
class First
{
 private :
 int i;
 public :
 First ()
 {
 i=10;
 }
 
 friend int funny(const First &ff, const Second &ss);
};
class Second
{
 private :
 int j;
 public :
 Second ()
 {
 j=15;
 }
 friend int funny(const First &ff, const Second &ss);
};

int funny(const First &ff, const Second &ss)
{
int temp;
 temp = ff.i+ss.j;
 return temp;
}
void main()
{
 First f;
 Second s;
 int data;
 data = funny (f, s);
 cout << data;
}

When we run this program, we get the following output….

25

In this program we have used to classes First and Second. The constructor in these classes initialize their private data member i and j to 10 and 15 respectively. In both class we have declared a function funny() to access their private data member as:

friend int funny(const first &ff, const second &ss);

This declaration can be placed any where in the class, either in private section or in the public section. An object of each class has been passed as an argument to the function funny(). And it accesses the private the data member of both classes through these arguments.

Note that the friend declaration is necessary in both classes. Another notable point is the declaration class second; at the beginning of the program.

This forward declaration is necessary because we can not refer a class until it has been declared. The class second is being referred to in the declaration of the function funny() in class First. So Second must be declared before First. This declaration tells the compiler that the class Second is defined later.

However, If we omit this forward declaration then the compiler can not understand the Second type when it encounters the First friend declaration and therefore the compiler will report an error message. If you place the entire class Second definition before class First then the compiler would not know what the first type is when it encounters the friend declaration in the Second class type. That’s why it is necessary to use the forward declaration.

Now see the definition of this friend function. Here the definition for funny() does not use the keyword friend. The keyword friend is used only for the prototype appearing in a class using the function. Another point to note is that this function definition does not use the scope resolution operator (::). It is so because this friend function belongs to no class. It means that the friend function has file scope, rather than class scope. Thus there will only one friend function with a specific name and signature per file.

Friend Classes

Like a friend function, we can also have an entire class as a friend. If we declare an entire class as a friend then all the member functions of this class become friend functions. Following program illustrates the use of friend classes.

// Program – v14.cpp

#include 
class Second;
class First
{
 private :
 int i;
 public :
 First()
 {
 i = 10;
 }
 friend Second;
};
class Second
{
 private :
 int j;
 public :
 Second()
 {
 j = 20;
 }
 void putdata(First ff)
 {
 cout << "\n" << ff.i << "\t" << j;
 }
 void display(First ff)
 {
 cout << "\n" << ff.i << "\t" << j;
 }
};
void main()
{
 First f;
 Second s;
 s.putdata(f);
 s.display(f);
}

In this program, we have declared an entire class Second as friend in class First:

class Second;

It means that all the member functions of Second class can access the private data members of First. When we execute this program we get the following output….

10    20
10    20

Operator Overloading and Friends

Another useful situation of using a friend function is to increase the versatility of overloading operators. Now watch the following program carefully.

// Program - v15.cpp

#include 
class Distance
{
 private :
 int meter;
 float cm;
 public :
 Distance ()
 {
 meter = 0;
 cm = 0;
 }
 Distance (float mm)
 {
 meter = int (mm);
 cm = (mm - meter) * 100;
 }
 Distance (int mm, float cc)
 {
 meter = mm;
 cm = cc;
 }
 void display()
 {
 cout <<"\nMeter = "<<<"\nCentimeter = "<< cm;
 }
 Distance operator + (const Distance &);
};
Distance Distance :: operator + (const Distance &dd)
{
 Distance temp;
 temp.meter = meter + dd.meter;
 temp.cm = cm + dd.cm;
 if (temp.cm >= 100)
 {
 temp.meter++;
 temp.cm -= 100;
 }
 return temp;
}

void main ()
{
 Distance d1(20, 45.85), d2, d3, d4;
 d2 = 70.65;                // one argument constructor
 d1.display();
 d2.display();
 d3 = d1 + 70.55;            // Distance + float : O.K.
 d3.display();
 d4 = 50.25 + d2;            // float + Distance : ERROR
 d4.display();
}

When you run this program, you get the following output….

Illegal structure operation

In this program there are three constructors: zero argument, one argument and two argument constructors. There also exists an overload + operator to add two objects of type Distance.

When we use a statement like

d3 = d1 + 70.55;

This translate to the following function call,

d3 = d1.operator + (70.55);

Here it requires to define the member function operator + () in the class Distance.

The overloaded operator + is looking for objects of type Distance both on its left and right. In this case the second argument is of type float, so the compiler will use the one argument constructor to convert this float to a Distance and then carry out the addition.

But what about the following statement:

d4 = 50.25 + d2;

internally this would become

d4 = 50.25 . operator + ();

and the overloaded + operator must have a Distance variable to the left of the dot operator because it is a member of Distance class, otherwise this operator +() function must be a member of the float class (which does not exist) and that takes a type Distance argument. Therefore when we place a variable of a different type, other than a Distance variable, the compiler reports an error. Here a friend can help us out in this situation.

To overcome this problem we can use a friend function with the float number as the first argument and the Distance as the second argument:

friend Distance operator + (float dist, const Distance &dd);

And in this friend function we reverse the order of its arguments and then calls the original function as:

Distance operator + (float dist, const Distance &dd)
{
 return dd+dist;
}

Now when compiler encounters the statement

d4 = 50.25 + d2;

the friend function translates this statement into the following statement

d4 = d2 + 50.25;

Thus a friend function helps in reversing the order of its arguments for overloading an operator that takes two different types of arguments.

However C++ also provides another way to achieve the same using friend. Incidentally C++ provides the facility of defining all the operator functions as friend functions. Here we would define an operator function that requires two Distance arguments, such as

friend Distance operator + (const Distance &dd1, const Distance &dd2);

This friend function is defined as:

Distance Distance :: operator + (const Distance &dd1, const Distance &dd2)
{
 Distance temp;
 temp.meter = dd1.meter + dd2.meter;
 temp.cm = dd1.cm + dd2.cm;
 if (temp.cm >= 100)
 {
 temp.meter++;
 temp.cm -= 100;
 }
 return temp;
}

From this definition it is clear that a friend function always requires one more argument than equivalent normal member function. Thus the statement

d3 = d1 + d2;

is interpreted as:

d3 = d2 . operator + (d1); 
// if the operator function is defined as a normal member function
and        d3 = operator + (d1, d2); 
// if the operator function is defined as a friend function

Thus in friend function the extra argument represents the object that a normal member function uses implicitly.

Following program shows how this can be achieved.

// Program – v16.cpp

#include 
class Distance
{
 private :
 int meter;
 float cm;
 public :
 Distance()
 {
 meter = 0;
 cm = 0;
 }
 Distance(float mm)
 {
 meter = int (mm);
 cm = (mm - meter) * 100;
 }
 Distance(int mm, float cc)
 {
 meter = mm;
 cm = cc;
 }
 void display()
 {
 cout <<"\nMeter = "<<<"\nCentimeter = "<< cm;
 }
 friend Distance operator + (const Distance &dd1, const Distance&dd2);
};

Distance operator + (const Distance &dd1, const Distance &dd2)
{
 Distance temp;
 temp.meter = dd1.meter + dd2.meter;
 temp.cm = dd1.cm + dd2.cm;
 if (temp.cm >= 100)
 {
 temp.meter++;
 temp.cm -= 100;
 }
 return temp;
}

void main ()
{
 Distance d1 (20, 45.85), d2, d3, d4;
 d2 = 70.65;                // one argument constructor
 d1.display();
 d2.display();
 d3 = d1 + 70.55;            // Distance + float : O.K.
 d3.display();
 d4 = 50.25 + d2;            // float + Distance : O.K.
 d4.display();
}

Here is the output of this program….

Meter = 20
Centimeter = 45.85
Meter = 70
Centimeter = 65
Meter = 91
Centimeter = 0.85
Meter = 120
Centimeter = 90

In earlier version of this program the overloaded + operator took only one argument, whereas in this program it takes two arguments. This is because in earlier program, one of the object on which the + operator is the object of which it was a member, and the second is an argument. And in this program the operator function is no longer a member function of the class, rather than it is a friend of the class Distance.

A more Practical Example

Now let us see another example of friend function. Let we create two classes DM and DF which stores the value of Distances. The DM class stores Distance in meters and cm and DF in feet and inches. Here we would write a friend function that adds one object of DM with another object of DF. The object that stores the result may be DM object or DF object. The output should be in the format of meter and cm or feet and inches depending on the objects on the display.
// Program – v17.cpp

#include 
const float MTFT = 3.280833;
class DM;
class DF
{
 private :
 int feet;
 float inches;
 public :
 DF()
 {
 feet = 0;
 inches = 0;
 }
 DF(int ff, float hh)
 {
 feet = ff;
 inches = hh;
 }
 void getdist()
 {

 cout << "\nEnter Feet = ";
 cin >> feet;
 cout << "Enter Inches = ";
 cin >> inches;
 }
 void display()
 {
 cout << "\nFeet = " << feet;
 cout << "\nInches = " << inches;
 }
 friend DM operator + (DM,DF);
};
class DM
{
 private :
 int meter;
 float cm;
 public :
 DM()
 {
 meter = 0;
 cm = 0;
 }
 DM(int mm, float cc)
 {
 meter = mm;
 cm = cc;
 }
 void getdist()
 {

 cout << "\nEnter Meter = ";
 cin >> meter;
 cout << "Enter Centimeter = ";
 cin >> cm;
 }
 void display()
 {
 cout << "\nMeter = " << meter;
 cout << "\nCentimeter = " << cm;
 }
 operator DF()
 {
 int ft;
 float inch, temp;
 temp = (meter+cm/100)*MTFT;
 ft = int(temp);
 inch = (temp-ft)*12;
 return DF(ft,inch);
 }
 friend DM operator + (DM,DF);
};
DM operator + (DM d1, DF d2)
{
 DM temp;
 float t;
 t = d2.feet+(d2.inches)/12;
 t /=  MTFT;
 temp.meter = d1.meter + int (t);
 temp.cm = d1.cm + (t-int(t))*100;
 return temp;
}

void main()
{
 DM d1,d2;
 DF d3,d4;
 cout << “\nEnter first Distance in meter and centimeter.”;
 d1.getdist();

 cout << “\nEnter second Distance in feet and inches.”;
 d3.getdist();

 d2 = d1+d3;
 d4 = d1+d3;

 cout << “\nAddition of two Distance in meter and centimeters.”;
 d2.display();
 
 cout << “\nAddition of two Distance in feet and inches.”;
 d4.display();

}

The output of this program is

Enter first Distance in meter and centimeter.

Enter Meter =10
Enter Centimeter =50

Enter second Distance in feet and inches.
Enter Feet = 20
Enter Inches = 11.75

Addition of two Distance in meter and centimeters.

Meter = 16
Centimeter = 89.446304

Addition of two Distance in feet and inches.

Feet =55
Inches = 5.134964

Overloaded Operators:

Overloading the

In earlier programs we have used getdist() and display() functions to read Distance objects and write Disaply objects on the console. Now one may ask – Can’t we read user-defined objects as cin >> d1; or display user-defined object, such as cout and << operators to perform input/output for user-defined data types.

No doubt, these two operators are heavily overloaded. The standard ostream class overloads the << operator to send its objects whatever arguments the overloaded operator function receives. Remind that cout is a standard ostream object that is smart enough to recognize all the basic C++ data types. The ostream class has following overloaded operator functions:

ostream & operator << (char c);
ostream & operator << (unsigned char c);
ostream & operator << (signed char c);
ostream & operator << (short n);
ostream & operator << (unsigned short n);
ostream & operator << (int n);
ostream & operator << (unsigned int n);
ostream & operator << (float n);
ostream & operator << (double n);
ostream & operator << (long double n);
ostream & operator << (long n);
ostream & operator << (unsigned long n);
ostream & operator << (bool b);
ostream & operator << (const char *s);
ostream & operator << (const unsigned char *s);
ostream & operator << (const signed char *s);

On similar track, the istream overloads >> operator for all the basic C++ data types. If you want to use operators on user-defined data types then it is necessary to overload operators. The << operator is overloaded as:

ostream & operator << (ostream &os, const class_name &cobj)
{
 os << ….        // display object’s contents
 return os;
}

Similarly, the >> operator is overloaded as:

istream & operator >> (istream &is, class_name &cobj)
{
 is >> ….;        // read object’s contents
 return is;
}

Here class_name is the name of the class whose object is to read or display. Both of these functions return a reference to an ostream object and istream object. However it is not mandatory, but generally the overloaded >> operator functions should be made friend functions when they are used to read and write user-defined objects.

For example, if we want to read and display Distance class object then we will overload these operators as:

istream & operator >> (istream &is, Distance &dd)
{
 is >> dd.meter >> dd.cm;
 return is;
}

and

ostream & operator << (ostream &os, const Distance &dd)
{
 os << "\nMeter = " << dd.meter << "\nCentimeter = " << dd.cm;
 return os;
}

Program v18.cpp shows the usage of these two overloaded operator functions.

// Program – v18.cpp

#include 
class Distance
{
 private :
 int meter;
 float cm;
 public :
 Distance(int mm=0, float cc=0.0)
 {
 meter=mm;
 cm=cc;
 }
 friend ostream & operator << (ostream &os, const Distance &dd);
 friend istream & operator >> (istream &os, Distance &dd);
};
ostream & operator << (ostream &os, const Distance &dd)
{
 os << "\nMeter = " << dd.meter << "\tCentimeter = " << dd.cm;
 return os;
}
istream & operator >> (istream &is, Distance &dd)
{
 is >> dd.meter >> dd.cm;
 return is;
}
void main()
{
 Distance d;
 cout << "Enter meters and centimeter = ";
 cin >> d;
 cout << d;
}

Here is the output of this program….

Enter meters and centimeter = 40    30.75
Meter =40    Centimeter = 30.75

In this program we have defined two friend functions operator (). Since these functions access the private members of Distance class only, not the private members of ostream class. Therefore these functions are declared as friends in Distance class only.

Here when the compiler encounters the statements

cin >> d; and 
cout << d; 

they are converted into the following statements:

operator >> (cin, dd);    and
 operator << (cout, dd);

respectively. Another main point to note is that the objects in these operator functions are collected as reference, in order to prevent creation of another copies of these objects. These operator functions returns the istream and ostream object by reference to permit cascading, such as:

cin >> d1 >> d2;    and
 cout << d1 << d2;

Friends or No Friends

Is it always necessary to declare operator () functions as friend functions? Its answer is no. If they access the private members of both classes directly then these functions should be friends to both classes. If these two operator functions access the private data members of either class then it is necessary to define these two functions as a  friend function in that particular class.

If we look at the last program then it is clear that these functions access the private data members of Distance objects directly but only uses the istream and ostream objects as a whole. Therefore it is necessary to define these two functions friend to Distance class only, not in istream and ostream class. However if these two operator functions do not access data member functions directly then there is no need to declare them friends in either class. For example, let we overload these operator functions as:

ostream & operator << (ostream &os, Distance &dd)
{
 os << "\nMeter = " << dd.getmeter() << "\nCentimeter = " << dd.getcm();
 return os;
}
istream & operator >> (istream &is, Distance &dd)
{
 int mm;
 float cc;
 is >> mm >> cc;
 dd.setdist(mm,cc);
 return is;
}

where getmeter(), getcm() and setdist() are member functions which are defined in Distance class as:

void setdist(int mm, float cc)
{
 meter = mm;
 cm = cc;
}
int getmeter()
{
 return meter;
}
float getcm()
{
 return cm;
}

Following program illustrates this concept.

// Program – v19.cpp

#include 
class Distance
{
 private :
 int meter;
 float cm;
 public :
 Distance(int mm=0, float cc=0.0)
 {
 meter=mm;
 cm=cc;
 }
 void setdist(int mm, float cc)
 {
 meter = mm;
 cm = cc;
 }
 int getmeter()
 {
 return meter;
 }
 float getcm()
 {
 return cm;
 }

};
ostream & operator << (ostream &os, Distance &dd)
{
 os << "\nMeter = " << dd.getmeter() << "\nCentimeter = " << dd.getcm();
 return os;
}
istream & operator >> (istream &is, Distance &dd)
{
 int mm;
 float cc;
 is >> mm >> cc;
 dd.setdist(mm,cc);
 return is;
}
void main()
{
 Distance d;
 cout << "Enter meters and centimeter = ";
 cin >> d;
 cout << d;
}

Here is the output of this program….

Enter meters and centimeter = 30     50.75

Meter = 30
Centimeter = 50.75

Reconstruction of a Binary Tree from its Inorder and Preorder Traversal

It is for you kind information that the inorder traversal of two or more different binary tree may produce the same sequence of nodes. Similarly preorder or postorder traversals may produce the same sequence of nodes. Look at all the Figure- l1 Both figures produce the same sequence of nodes if they are traversed in inorder fashion (BADCE).

Figure l1

It means that we can not reconstruct a binary tree if we are provided its inorder or preorder or postorder. However if we are provided with inorder and preorder sequence of nodes then we can construct a unique binary tree.

For example, let we have following inorder and postorder traversal of a binary tree:

Inorder Sequence:    D B G E H A C I F
Preorder Sequence :    A B D E G H C F I

We know that in preorder traversal of a binary tree, the root node is visited first. And since ‘A’ is the first node in the preorder sequence, therefore ‘A’ becomes the root node of the binary tree. And as far as the inorder traversal is concerned, the root node is visited after traversing the left sub-tree. Therefore all the nodes which are on the left side of ‘A’ in the given inorder sequence belong to the left subtree and the nodes to the right of ‘A’ belong to the right subtree of the tree as shown below:

Moreover, the order in which the nodes to the left of ‘A’ occur in the given inorder sequence is the same as the inorder sequence of the left subtree. So we can say that if there are ‘x’ number of nodes after ‘A’ in inorder sequence then the first ‘x’ nodes after ‘A’ in preorder sequence become the preorder sequence of the left subtree. This process is applied to both the left and right subtrees once again. Let we consider the left subtree. The preorder sequence of this subtree suggests that ‘B’ is the root node of this subtree. The position of ‘B’ in the inorder sequence determines the inorder sequence of the left and the right subtree as shown below:

This process continues for each subtree. Figure-l2 continues the step-by-step reconstruction of a binary tree. Here is the ‘C’ function which construct a binary tree given its inorder and preorder traversals.

Reconstruct(TreeNode *inhead, TreeNode *prehead)

/* Here inhead and prehead are pointers to the inorder list and preorder list of a binary tree */

{
 TreeNode *incurr, *precurr;
 precurr = prehead->prev->prev;
 while (precurr != prehead)
 {
 incurr = inhead->next;
 while ((incurr!=inhead)&&(incurr->data != precurr->data))
 incurr = incurr->next;
 if (incurr == inhead)
 {
 printf("\n Error in input");
 exit(0);
 }
 if (precurr->next->data == incurr->prev->data)
 {
 precurr->lchild = precurr->next;
 DelNode(incurr->prev);
 DelNode(precurr->next);
 if (precurr->next == prehead)
 precurr = precurr->prev;
 }
 else
 {
 if (precurr->next->data == incurr->next->data)
 {
 precurr->rchild = precurr->next;
 DelNode(precurr->next);
 DelNode(incurr->next);
 if (precurr->next == prehead)
 precurr = precurr->prev;
 }
 else
 precurr = precurr->prev;
 }
 }
}
DelNode(struct TreeNode *temp)
{
 temp->prev->next = temp->next;
 temp->next->prev = temp->prev;
}

Following code segment illustrates how to use this function Reconstruict()….

 ….
printf("\n Enter inorder traversal = ");
 gets(instr);
 printf("\n Enter preorder traversal = ");
 gets(prestr);
 ….
 ListCreate(&inhead,instr);
 ListCreate(&prehead,prestr);
 Reconstruct(inhead,prehead);
 TreeDisplay(prehead->next,0);
 ….

Here ListCreate() function is used to create a linked list of inorder sequence and preorder sequence of characters of a tree. And once we have such two lists we pass these two lists to Reconstruct() function in order to get a binary tree.

Figure l2

We can reconstruct a binary tree if the inorder and the postorder traversal of a binary tree is provided. But one should remember that a binary tree can not be uniquely reconstructed if its preorder and postorder traversals are provided.

Binary Search Trees

Binary trees that we have studied so far contain unordered elements. However in many applications an order data is required. For such applications, we have binary search trees. In a binary search tree data is maintained in some order. We know that the nodes in a binary tree represent some records and these records are ordered on some key properties in a binary search tree. Therefore we can define a binary search tree as:

(i)    every node has a key and no two keys have the same key value
(ii)    all keys (if any) in the left subtree are smaller than the key in the root
(iii)    all keys (if any) in the right subtree are larger than the key in the root
(iv)    the left and right subtrees of a binary search tree are binary search trees once again

We can say that the definition of a binary search tree is itself recursive. Figure-l3 shows some example of binary search trees.

Figure l3

The tree of figure-l3(e) is not a binary search tree because this tree rooted at the node ‘3’ is not a binary search tree, as its right subtree has a key value ‘2’ that is smaller than ‘3’. So it violates the third properties of the definition of a binary search tree. However all other binary trees of figure-l3 are binary search trees.

Now you can read some basic operations on binary search tree in this article.

Search in a Binary Search Tree

Since the definition of a binary search tree is recursive, therefore it is easier to describe a recursive search method. Let I want to search for an element with key ‘item’. Initially the key is compared with the key at the root. If both are equal then the search terminates successfully. If the given key is less than the key at the root then the search is initiated only at the left subtree of the current root because no element in the right subtree can have key value ‘item’. Similarly if the given key is greater than the key at the root then the search is initiated only at the right subtree of the current root because no element in the left subtree can have key value ‘item’. The search process terminates unsuccessfully when search is done on an empty tree, that is the current root node contains a NULL value.

For the sake of convenience we consider the same data type for a node as we have taken earlier, that each node has three fields – lchild, data and rchild.

Here is the algorithm which searches a given key in a binary search tree.

Algorithm: Search

Search(Root, item)

Here Root contains the address of root node and item be the element to be searched.

Step-1 : If (Root == NULL) then return 0;
Step-2 : If (Root->data == item) return 1
Else if (Root->data > item) Call Search(Root->lchild, item)
Else Call Search(Root->rchild, item)
Step-3 : Exit

Here is the ‘C’ implementation of this function:

Implementation : Search

Search(TreeNode *Root, int item)
{
 if (Root == NULL)
 return 0;
if (Root->data == item)
 return 1;
else if (Root->data > item)
 Search(Root->lchild, item);
else
 Search(Root->rchild, item);
}

This function returns 1 if search terminates successfully; otherwise returns 0. The recursion in this function can be easily converted to an iterative one since it is a tail recursion.

Here is the iterative equivalent of a Search() function.

NonRecSearch(TreeNode *Root, int item)
{
 while (Root != NULL)
 {
 if (Root->data == item)
 return 1;
 else if (Root->data > item)
 Root = Root->lchild;
 else
 Root = Root->lchild;
}
return 0;
}

The Search() function can be used in the following segment as:

….
flag = Search(Root, item);
if (flag==1)
 printf(“\nItem is searched successfully.”);
else
 printf(“\nItem is not found”);
….

Here ‘item’ contains the value to be searched.

Insertion into a Binary Search Tree

When we insert a new element into a binary search tree then there are two possibilities, either tree is empty or not. If tree is empty then we need only make root point to the new node. However if the tree is not empty then we must compare the given key with the key value in the root. If it is less then the new node must be inserted into the left subtree. If it is larger one then the new node must be inserted into the right subtree. If both keys are equal then it must display an error message because our assumption, that no two nodes have the same key, is violated. So while inserting a key into a binary search tree one must preserve the conditions mentioned in the definition of a binary search tree.

For example, let we want to insert an element with key 32 into the tree of Figure-l4(a). Here we first compare ‘32’ with the root’s key 22. Since 32 is greater than 22 so we move towards right subtree of the tree rooted at 22. Now we compare 32 with 37. Since 32 is less than 37 so we move towards left subtree of the tree rooted at 37. Now we compare 32 with 29. Since 32 is greater than 29 so we move towards right subtree of the tree rooted at 29 and since there is no further nodes to be checked, so we insert this new element as the right child of this node. The resulting search tree is shown in Figure-l4(b).

Figure l4

Here is the algorithm which inserts a new node into a binary search tree.

Algorithm : TreeInsert

TreeInsert(&Root, item)

Here Root contains the address of root node. The value of Root is passed by reference (pointer to pointer) in order to allow change in the insertion of a node.

Step-1 : If Root is NULL then create a new node and sets its field and assign it to Root and return back.
Step-2 : If ((Root ->data > item) then
call TreeInsert(&((*Root)->lchild), item)
Else if  ((Root ->data V item) then
call TreeInsert(&((*Root)->rchild), item)
Else print an error message – “No two nodes can have same value.”
Step-3 : Exit.

Here is the ‘C’ implementation of this algorithm.

Implementation : TreeInsert

TreeInsert(TreeNode **Root, int item)
{
 if (*Root == NULL)
 {
 *Root = getnode();
 (*Root)->data = item;
 (*Root)->lchild = NULL;
 (*Root)->rchild = NULL;
 return;
 }
 if ((*Root)->data > item)
 TreeInsert(&((*Root)->lchild), item);
 else if ((*Root)->data < item)
 TreeInsert(&((*Root)->rchild), item);
 else
 {
 printf("\nError : No two nodes have same key value.\n");
 exit(0);
 }
}

As this function is also tail recursive, it is easy to replace recursion with iteration.

Here is the non-recursive insertion algorithm.

NonRecTreeInsert(TreeNode **Root, int item)
{
 TreeNode *temp, *current;

 temp = getnode();
 temp->data = item;
 temp->lchild = NULL;
 temp->rchild = NULL;

 if (*Root == NULL)
 {
 *Root = temp;
 return;
 }
 current = (*Root);
 while (current != NULL)
 {
 if (current->data > item)
 {
 if (current->lchild != NULL)
 current = current->lchild;
 else
 {
 current->lchild = temp;
 return;
 }
 }
 else if (current->data < item)
 {
 if (current->rchild != NULL)
 current = current->rchild;
 else
 {
 current->rchild = temp;
 return;
 }
 }
 else
 {
 printf("\nError : No two nodes have same key value.\n");
 exit(0);
 }
 }

}

Deletion from a Binary Search Tree

Now I am writing how to delete a node from a binary search tree. Deletion of a node from a binary search tree is more complex than searching in a binary search tree or insertion of a node into a binary search tree. When we delete a node we will search it first and then delete it.

There are four possibilities:

1.    The deleted node is a leaf node
2.    The deleted node has only right child
3.    The deleted node has only left child
4.    The deleted node has both children

If the node to be deleted is a leaf node the only task in this case is to be done is to reset the respective pointer of its parent to NULL, as shown in Figure-l5(a). Even the node to be deleted has one child only then the deletion process is very simple. In this case we adjust the link from the parent of the deleted node to point to its non-empty subtree as shown in figure-l5(b) and figure-l5(c). But the situation becomes complex when the node to be deleted has both left and right subtrees non-empty, as shown in Figure-l6.

When the node to be deleted has both left and right subtrees non-empty, we first replace the node to be deleted either the largest element in the left subtree or the smallest element in the right subtree. And then we proceed to delete this replacing node from the subtree from which it was taken.

Figure l5

For example, let we want to delete the element 40 in the tree shown in figure-l6(a). Here we will replace it by either the largest element ‘30’ in its left subtree or the smallest element ‘51’ in its right subtree. Suppose we opt the smallest element in the right subtree as shown in figure-l6(b). For this we will need to find the inorder successor of a node to be deleted. Inorder successor of a node is found out by first going to its right child and then continually going to left as long as an empty subtree is encountered. The inorder successor of element 40 is 51. So now we replace the data of the node to be deleted by the data of the inorder successor node. Once the element is replaced, we must delete the inorder successor. The inorder successor of any node with two children can have at most one child because it can not have a non-empty left subtree. In this case since 51 has no child, the pointer from its parent is set to NULL. Figure-l6(b) shows the resultant tree after deleting element 40.

Figure l6

Here is the algorithm, which deletes the specific node from a binary search tree.

Algorithm : TreeDelete

TreeDelete(&Root, item)

Here Root contains the address of root node. The value of Root is passed by reference (pointer to pointer) in order to allow change after the deletion of a node.

1.    If Root is NULL then print an error message and go to step-12.
2.    Set current to Root node and father to NULL
3.    Repeat through step-6 while ((current != NULL)&&(current->data != item))
4.    Update father = current
5.    If (current->data > item) then current = current->lchild
6.    Else current = current->rchild
7.    Check the value of current. If current is NULL then print an error message and go to step-12; otherwise go to step-8
8.    If the current node has both children then replace the data field of current node with its inorder successor node ‘succ’.
9.    Set current = succ
10.    If the current node has one child only then set the father’s link appropriately
11.    Free the memory space occupied by current node
12.    Exit.

Here is the ‘C’ implementation of this algorithm.

Implementation : TreeDelete

TreeDelete(TreeNode **Root, int item)
{
 TreeNode *current, *father, *succ;
 if (*Root == NULL)
 {
 printf(“\nEmpty Tree.”);
 return;
 }
 current = (*Root);
 father = NULL;
 while ((current != NULL)&&(current->data != item))
 {
 father = current;
 if (current->data > item)
 current = current->lchild;
 else
 current = current->rchild;
 }
 if (current == NULL)
 {
 printf("\nItem does not exit.\n");
 return;
 }
if ((current->lchild != NULL)&&(current->rchild!=NULL))   /* if current has both children */
 {
 father = current;
 succ = current->rchild;
 while (succ->lchild != NULL)
 {
 father = succ;
 succ = succ->lchild;
 }
 current->data = succ->data;
 current = succ;
 }
if (current->lchild == NULL)                /* if current has only right child */
 {
 if (father != NULL)
 {
 if (father ->lchild == current)
 father->lchild = current->rchild;
 else
 father->rchild = current->rchild;
 }
 else
 (*Root) = current->rchild;
 }
else if (current->rchild == NULL)            /* if current has only right child */
 {
 if (father != NULL)
 {
 if (father ->lchild == current)
 father->lchild = current->lchild;
 else
 father->rchild = current->lchild;
 }
 else
 (*Root) = current->lchild;
 }
 freenode(current);
 return;
}

 

 

 

A Object Oriented Intro

Every Software Engineer is familiar with programming. Already  you   know,  programming  is  just automating a  system. Obviously, by automation we mean instead of carrying out tasks of a  system  manually,  we  write certain series of instructions in a sequential manner, which are  functionally  and  logically  related. All  these  instructions  work  independently  but  in perfect synchronization and harmony to produce the desired output.

If  we  believe  in  the  above  definition  of  a  program,  then  we  can  conclude  that  in programming, the main focus is on the  system to be automated. What we aim at, while writing a program, is to determine the tasks carried out in the system, and in the course, what are the inputs it require, and after processing, the outputs it produces.

Let’s understand this with a real life process. All of you surely enjoy a steaming cup of tea after a tough and grueling day. So, let’s automate the process of tea making. While automating this process, the tasks that has to be carried out are as follows:

1.   Taking some water in a container.

2.   Putting it on the oven.

3.   Lighting the oven and letting the water boil.

4.   Once the water has boiled, adding tea leaves to it and waiting for some time.

5.   When the liquor is ready, putting sugar and milk as required. The tea is ready.

You  can  find  that  for  automating  the  process  (of  tea  making),  we  concentrated  on  the process and divided it into certain subtasks. While carrying out the tasks we identify the ingredients (data) and the type of processing (function) required on them.

Now say, one fine evening you aspire for a cup of hot and creamy coffee. Now you have to automate the process of coffee making. But alas! You have to redo it from scratch, even after a tiring day. This is because the process of coffee making is different from that of tea making. The tasks involved in this case are as follows:

1. Putting some milk in a container.

2.   Adding sugar to it.

3.   Boiling it on the oven.

4.   Adding coffee powder to it.

Vao It’s ready.

As you can see that the tasks are different as compared to that of tea making, accordingly some ingredients and processing done on them are also different. Therefore, there is no evasion but to start from scratch, to automate this process.

This  is  what,  is  being  done  in procedural programming. While automating a process in procedural programming, the full concentration is on the process and the associated data required.  Whenever  the  process  changes,  every  thing  has  to  be  redone,  even  if  they resemble in some way or the other.

The major features and disadvantages of the procedural programming are written in this article.

Advantages and limitations of Procedural Programming

Procedural approach:

• The  problem  is  viewed  as  a  sequence  of  actions,  such  as  reading,  calculating, printing. Programming language is used to implement those actions.

• A large program written using procedural language was broken down into smaller and manageable sections. Each of these sections is called procedures.

• The procedures worked upon the data present in the programs.

• More  stress  was  given  on  the  functions,  rather  than  the  data  governed  by  those functions.

• In multi function programs data were made global so that they could be accessed by many functions.

Certain drawbacks of the procedural language:

• As the program became lengthy, the decision structures became more complex.

• Large changes in code had to be made to bring in a minor change in the program.

• Most of the time programs in procedural languages could not be reused.

• Since data were made global, this led to confusion and accidental data corruption as it was difficult to identify what data was used by which function.

• Programs  written  in  procedural  languages  were  difficult  to  design  because  the  data used in the program treated separately from the functions that operated on the data.

As  you  can  understand  from  the  above  discussion  that  procedural  programming  has certain   major   limitation, which hampers the manageability and reusability   of code, therefore new technique of programming evolved,   known   as   Object   Oriented.

Programming (OOP)

Object oriented programming is an approach that attempts to eliminate the disadvantages of the conventional programming approach.

Object Oriented Programming is a simulation of real-life processes. In real life, a process is carried on with several  self contained  and self-sustained objects interacting with each other  via  their  behaviors , which are the integral part of the object. These objects also have certain properties by virtue of which we can easily identify them uniquely.

If we continue with our previous example, of tea making, in Object Oriented approach we will not concentrate on how the process is carried on.  Instead we will try to locate the different objects that participate in the  process. We will create those individual objects along with their properties and behaviors. Then those Objects will be brought together. Consequently  with  the  exhibition  of  their  related  behavior  they  will  interact  with  each other.

In  case  of  the  tea-making  process,  we  will  create  the  objects  like  water,  sugar,  milk, tealeaves, oven etc.

The advantage that we will gain from this approach is that while automating the process of coffee making we don’t have to start from scratch once again. We can reuse certain objects like milk, sugar, and oven, which had been already created. Thus it offers us the extreme reusability of code.

The concept of object oriented programming (OOP) was first implemented in a language called Simula. Some other examples of object oriented languages are:

1.   Smalltalk.

2.   C++.

3.   Objective C.

4.   NeXTstep.

5.   Java

6.   VC++

7.   C#

And most of the recent and up coming languages are likely to support OOPS.

Features of Object Oriented language:

Languages  supporting  this  concept  were  designed  to  develop  programs  that  would combine data and the functions (that operated on the data) into a single entity.

These languages could imitate real-life entities more closely.

Something About Class

The primary idea of the object-oriented approach, in programming was to keep data and functions together.

It is very similar to real life  processes. Different objects interact with each other via their methods with the virtue of its  properties and give birth to a  process.  For example, if we consider the process of tea making then different objects like oven, water, sugar, milk etc. interacts with each other and thereby spawns the process of tea making.

Thus, in object oriented programming our main focus will be in creating an object.  We can  define  an  object  as  anything  which  can  be  identified  easily,  with  the  virtue  of properties it posses and it exhibits certain functionality.

In any real life object the properties and functionality (methods) are bundled into a single whole. For example, consider a Ball Pen.  A ball pen has certain properties like  color, length, diameter  etc. On the other hand it also contains certain functionality like  writing. All the properties and methods are grouped into the object ball pen itself.

In Object oriented programming the main focus is not on the process, which has to be automated, instead, concentration is on the objects that constitutes the process. For object oriented programming we have to create objects.

In a particular process, many similar types of object can participate. In that case creating several  objects  individually  is  a  painful  stake.  Therefore,  instead  of  creating  objects individually  we  create  a  blueprint of  the  object.  From  that  blueprint  we  can  create  as many objects as we require.

We can consider the example of the cake class. In OOP, the ingredients (data) used to bake the cake and the process (functions) of baking are kept in a single entity. Thus a class can be called a blue print or a template that contains both data and functions that work on the data.

We can take the example of a car manufacturing process. Once a template defining the manufacturing process is made any number of cars can be manufactured by following the blueprint.

A class can be defined in the following way:

Here in the car class bodycolor, number_plate, no_of_seats and engine are the attributes of the class. These attributes or properties can determine the body color of the car or how many seats are there in the car etc.

Now a car can move and can stop. These two operations are done with the help of the property (engine), of the car class. But these two operations can be performed by using some methods only. These two methods are function move and function stop in the class car, which is defined earlier.

Objects

Once a template or a blueprint for manufacturing cars is defined any number of cars can be created following the template. So all the cars that are manufactured are instances of the template or the class that defines the manufacturing process.

These manufactured cars are called objects of the car class.

• An object can be defined as an instance of a class.

• Once a class is defined any number of objets can be created from it.

Let’s take the example of the car class. Objects of the maruti_car class can be defined in the following way:

MARUTI_CAR  C1, C2, C3

Therefore, C1, C2, C3 are all objects of the maruti_car class and are independent of each other. The objects will have its own copy of the information that is defined in the class.

We can take the instance C1 and assign values to the data members present inside the instance C1.

C1 -> bodycolor = blue;
C1-> number_plate = ABC789556; C1-> no_of_seats = 4;
C1-> engine = disel;

The above statements use the arrow symbol with the name of the object to work with the data.

Characteristics of Objects

Classes are declared to combine together  data and functions that work on the data. The data  present  inside  in  an  object  are  called  the attributes or the  characteristics of the object. The functions present in the object are called member functions or methods of the object.  The  methods  determine  how  the  object  is  going  to  behave  when  information  is supplied to it. In an object, class attributes are initialized with specific data value.

The main features or characteristics of a class are:

Encapsulation

• It  is  the  mechanism,  of  binding  the  member  functions  and  data  present  in  the  object together so that it is safe from external misuse. Encapsulation implements two things  – data hiding and data abstraction.

• In  Object  Oriented  Programming,  the  user  can  classify  data  as  private  or  public  when defining a class. So when objects are declared of that particular class, the data within the object which are private are not accessible to any other class, objects or methods outside the class. The public data within the object is otherwise accessible to outside the class. Thus the object is created in such a way that the public data of the object is used to provide an interface to the outside world to work with the private data. This separating of data as private and public to protect information from accidental corruption is called data hiding.

• The process of data hiding implements another important feature called data abstraction. In  OOP,  importance  is  given  as  to  how  an  object  behaves  when  some  information  is provided  to  it.  The  user  is  only  concerned  with the  output  and  not  how  the  output  is generated.

• Let us consider the example of riding in a hired cab. The passenger passes the message to the  driver  about  his destination. The  passenger  is  not  concerned  about  the  methods  the driver uses to take the passenger to the destination. Thus the passenger is abstracted from the mechanism of driving the cab to reach his destination.

Characteristics of Objects

Inheritance

It is the process in which one object can acquire the features of another object. Let’s take the example of defining a cake class. The class can be defined as follows

The above class contains the description of baking an ordinary cake. If the user wants to bake a chocolate cake his task becomes much easier. He can incorporate all the features of the ordinary cake and include the extra information, i.e., the chocolate.

This can be explained by the following figure.

Polymorphism

It is the process where the same object behaves in different ways in different situations.

For example a person named Ram is an instance of the class human beings. He interacts with  different  people  at  different  times.  He  behaves  professionally  in  his  office  and personally in his home. So the same person behaves differently under different situations.

Advantages Of Object Orientation

The main advantage of Object Oriented programming (OOP) language is that it simplifies the development of complex systems.

The advantages of object oriented programming are:

Maintainability

It may so happen that a team of software developers was engaged to develop software. But  the  people  responsible  for developing  the  software  are  no  longer  available  to maintain  the  software,  which  was  developed  previously.  Programs written  using  OOP techniques are easily understood and hence can be maintained without much difficulty.

Reusability

Let us consider the example of baking an ordinary cake. The process involved in baking an ordinary cake cannot be much different from the process of baking a chocolate cake. Thus  a  person  trying  to  bake  a  chocolate  cake  can  reuse  most  of  the  process  that  is required to bake  an ordinary cake. As programs written using OOP are more close to real world entities, the concept of reusability can be applied here. Once a standard program is written,  it  can  be  reused  easily  by  incorporating  minimal  changes  and  more  functionality can be added. The same code can be utilized for developing a different project altogether.

Thus reusability implements extensibility of code.

Apart  from  the  above-mentioned  primary  advantages  of  OOP’s  there  are  some  other derived advantages also.

Extensibility:

In the object oriented approach we can easily extend new characteristics and behavior to an existing object. So the unnecessary duplication of the code can be avoided.

Decomposability:

In   this  approach,  we  can  split  a  large  program  into  small  modules.  Then  separate programmers can develop every small part. In this way we can develop and manage a large project easily and on time by distributing the total task.

Understandability:

OOP approach is very much similar to the real life.