In the Name of Allah the Most

Beneficent the Most Merciful

Subject : Data Structures & Algorithms

Lecture : 03

Monday, January 18, 2021 1

 Pointers to pointers
 C++ allows the use of pointers that point to pointers, that
these, in its turn, point to data (or even to other pointers).
The syntax simply requires an asterisk (*) for each level
of indirection in the declaration of the pointer:
 char a;
 char * b;

 char ** c;

 a = 'z';

 b = &a;

 c = &b;

This, assuming the randomly chosen memory locations for each

variable of 7230, 8092, and 10502, could be represented as:

Monday, January 18, 2021 2

 Pointers to pointers
 The new thing in this example is variable c, which is a
pointer to a pointer, and can be used in three different
levels of indirection, each one of them would correspond
to a different value:

 c is of type char** and a value of 8092

 *c is of type char* and a value of 7230
 **c is of type char and a value of 'z'

Monday, January 18, 2021 3

 void pointers
 The void type of pointer is a special type of pointer. In C+
+, void represents the absence of type. Therefore, void
pointers are pointers that point to a value that has no type.

 This gives void pointers a great flexibility, by being able to

point to any data type, from an integer value or a float to a
string of characters. In exchange, they have a great limitation:
the data pointed by them cannot be directly dereferenced
(which is logical, since we have no type to dereference to),
and for that reason, any address in avoid pointer needs to be
transformed into some other pointer type that points to a
concrete data type before being dereferenced. 
 void pointers
 One of its possible uses may be to pass generic
parameters to a function. For example:  // increaser

 #include <iostream>
 using namespace std;
int main ()
  void increase (void* data, int psize) { char a = 'x';
 { if ( psize == sizeof(char) ) int b = 1602;
increase (&a,sizeof(a));
 { char* pchar; increase (&b,sizeof(b));
 pchar=(char*)data; cout << a << ", " << b
<< '\n';
 ++(*pchar); } return 0;
 else if (psize == sizeof(int) ) }
 { int* pint; y, 1603
 pint=(int*)data; ++(*pint); } }
 Memory leak
Suppose you have the following declaration:
int *p; // this statement declares p to be a pointer variable of type int.
p = new int; // line 1
*p = 54; // line 2
p = new int; // line 3
*p = 73; // line 4
The statement in line 1 allocates memory space of type int and stores the
address of the allocated memory space into p. suppose that the address of
allocated memory space is 1500. then the value of p after execution of this
statement is 1500.

Next the statement in line 3 executes, which allocates a memory space of

type int and stores the address of the allocated memory space into p.
suppose the address of this allocated memory space is 1800. the value of p
is now 1800.

Line 4 stores 73 into the memory space to which p points, which is 1800
 Memory leak..
 Now the obvious question is, what happened to the memory space
1500. to which p was pointing, before the execution of the statement
in line 3? After execution of the statement in line 3, p points to the
new memory space at location 1800. the previous memory space at
location 1500 is now inaccessible.
 In addition, the memory space 1500 remains marked as allocated. In
other words, it cannot be reallocated. This is called memory leak
there is an unused memory space that cannot be allocated.
 How to avoid memory leak. When dynamic variable is no longer
needed, it can be destroyed, its memory can be deallocated. The C++
operator delete is used to destroy dynamic variables. delete p;
 Dangling pointers
 Depending on a particular system, after the delete p;
statement executes, the pointer variable might still contain
the addresses of the deallocated memory space. In this
case we sat that these pointers are dangling.
 One way to avoid this pitfall is to set these pointers to
NULL after the delete operation.
 int *p;
 p = new int;
 *p = 34;
 delete p;
 p = NULL;
 p = new int;
 *p = 60;
 Dynamic Two-Dimensional Arrays
 There are various ways you can create dynamic two-
dimensional arrays. One way is:
 int *board[4];
 This statement declares board to be an array of four
pointers where each pointer is of type int. because
board[0], board[1], board[2], board[3] are pointers, you
can now use these pointers to create the rows of board.
Suppose that each row of board has six columns. Then
the following for loop creates the rows of board.
 for (int row =0; row<4; row++)
 board[row] = new int [6];
 Note that expression new int[6] creates an array of six
components of type int and returns the base address of the
array.
 Dynamic Two-Dimensional Arrays
 After the execution of for loop, board is a two-dimensional
array of 4 rows and six columns.
 The number of columns of board can be specified during
execution. However the way board is declared, the number of
rows is fixed. So in reality, board is not a true dynamic two-
dimensional array.
 Next consider the following statement:
 int **board;
 This statement declares board to be a pointer to a pointer. In
other words, board and *board are pointers. Now board can
store the address of a pointer or an array of pointers of type
int, and *board can store the address of an int memory space
or an array of int values.
 Dynamic Two-Dimensional Arrays
 Suppose that you want board to be an array of 10 rows
and 15 columns. To accomplish this, first we create an
array of 10 pointers of type int and assign the address of
that array to board.
 board = new int*[10];
 Next we create the columns of board. The following for
loop accomplish this:
 for(int row = 0; row < 10; row++)
 Board[row] = new int[15];
 Number of rows and number of columns of board can
be specified during program execution.
 Dynamic Arrays example
 #include <iostream>
 using namespace std;
 void fill (int **p, int rowSize, int columnSize);
 void print (int **p, int rowSize, int columnSize);
  int main () {
 int **board;
 int rows, columns;
 cout<<“ Enter the number of rows and columns: ”;
 cin>>rows>> columns;
 board = new int* [rows]; //create the rows of board
 for( int row = 0; row < rows; row++)
 board[row] = new int [columns]; //create the columns of board
 fill ( board, rows, columns); //insert elements into board
 print ( board, rows, columns); //output the elements of board
 return 0;}
 Dynamic Arrays example
 void fill ( int **p, int rowSize, int columnSize)
 { for ( int row = 0; row< rowSize; row++)
 { cout<<“Enter ”<<columnSize<<“number(s) for row”<<“number
”<<row<< “ : ”;
 for( int col = 0; col < columnSize; col++ )
 cin>>p[row][col]; cout<<endl;
 }}
 void print( int **p, int rowSize, int columnSize)
 { for (int row = 0; row < rowSize; row++)
 { for ( int col = 0; col < columnSize; col++)
 cout<<setw(5)<<p[row][col];
 cout<<endl;
 }}
 Shallow Vs. Deep Copy and Pointers
 Suppose that you have the following declaration:
 int *first;
 int *second;
 Further suppose that first points to an int array.
 Next, consider the following statement:
 second = first; //this statement copies the value of first into
second. After this statement executes, both first and second point to
the same array.
 The statement first[4] = 10; not only changes the value of first [4], it
also changes the value of second[4] because they point to the same
array.
 Let us execute the following statement:
 delete [ ]second;
 After this statement executes, the array to which second points is deleted.
 Shallow Vs. Deep Copy and Pointers
 First and second pointed to the same array after the statement
 delete [ ] second; executes, first becomes invalid, that is, first ( as
well as second ) are now dangling pointers.

 Therefore, if the program later tries to access the memory to which

first pointed, either the program will access the wrong memory or it
will terminate in an error. This case is an example of a shallow copy.

 More formally, in a shallow copy, two or more pointers of the same

type point to the same memory; that is, they point to the same data.
 On the other hand, suppose that instead of earlier statement, we have
the following statements:
 second = new int [10];
 for (int j = 0; j < 10; j++)
 second [ j ] = first [ j ];
 Shallow Vs. Deep Copy and Pointers

 On the other hand, suppose that instead of earlier statement, we

have the following statements:
 second = new int [10];
 for (int j = 0; j < 10; j++)
 second [ j ] = first [ j ];

Both first and second now point to their own data. If second deletes its
memory, there is no effect on first. This case is an example of Deep
Copy. More formally, in a deep copy, two or more pointers have their
own data.
 Recursion
 The process of solving a problem by reducing it to smaller versions of
itself is called recursion. Recursion is a very powerful way to solve
certain problems for which the solution would otherwise be very
complicated.

 Let us consider a problem that is familiar to most everyone. You

probably learned how to find the factorial of a nonnegative integer. .
 For example, the factorial of 5, written 5!, is 5 * 4 * 3 * 2 * 1 = 120.
1. Every recursive definition must have one (or more) base cases
2. The general case must eventually be reduced to a base case
3. The base case stops the recursion

Here we talk about recursive algorithms and recursive functions. An

algorithm that finds the solution to a given problem by reducing the
problem to smaller versions of itself is called a recursive algorithm.
 Recursion
 A function that calls itself is called a recursive function. The body
of the recursive function contains a statement that causes the same
function to execute again before completing the current call.
Recursive algorithms are implemented using recursive functions.

 A recursive function that implements the factorial function.

 int fact ( int num )

 { if ( num == 0)
 return 1;
 else
 return num * fact (num - 1);
 }
 cout<< fact (3) << endl;
 Recursion
fact (3)
num==3
Because sum != 0
 Execution of factorial function return 3 * fact (2);
 Output is 6.
fact (2)
num==2
Because sum != 0
return 2 * fact (1);

fact (1)
num==1
Because sum != 0
return 1 * fact (0);

fact (0)
num==0
Because sum is 0
return 1;
 Recursion

Monday, January 18, 2021 20

 Direct and Indirect Recursion

 A function is called directly recursive if it calls itself.

 When function calls itself, it is called direct recursion, the example
we have seen above is a direct recursion example.

 A function that calls another function and eventually results in the

original function call is said to be indirectly recursive.

 When function calls another function and that function calls the
calling function, then this is called indirect recursion. For example:
function A calls function B and Function B calls function A.
 Indirect Recursion Example
#include <iostream>
using namespace std;
int fa(int);
int fb(int);
int fa(int n)
{
if(n<=1)
return 1;
else return n*fb(n-1);
}

int fb(int n)
{
if(n<=1)
return 1;
else
return n*fa(n-1);
}

int main()
{
int num=5;    
cout<<fa(num);
return 0;
} January 18, 2021
Monday, 22
 Advantages and Disadvantages of Recursion
 Advantages
 It makes our code shorter and cleaner.
 Recursion is required in problems concerning data structures
and advanced algorithms, such as Graph and Tree Traversal.

 Disadvantages
 It takes a lot of stack space compared to an iterative program.
 It uses more processor time.
 It can be more difficult to debug compared to an equivalent
iterative program.

23
 Composition
 An object may be composed of other smaller
objects

 The relationship between the “part” objects and the

“whole” object is known as Composition

 Composition is represented by a line with a filled-

diamond head towards the composer object
Example – Composition of Ali
Head
1

Arm Ali Leg

2 2

1
Body
Example – Composition of Chair
Back
1

Chair

2 1 4
Arm Seat Leg
 Example – Composition is
Stronger

 Ali is made up of different body parts

 They can’t exist independent of Ali

 Example – Composition is
Stronger

 Chair’s body is made up of different parts

 They can’t exist independently

 Composition Example
 #include<conio.h> void show()
 #include<iostream.h> {
 #include<stdio.h> if(u==120 && l==80)
{
 class B_P
cout<<"normal";
 { }
 int u; else
 int l; {
 public: cout<<"not normal";
} } };
 void getB_P()
 { cout<<"\nenter value for upper blood p: ";
 cin>>u;
 cout<<"\n enetr value for lower blood p: ";
 cin>>l; }
 Composition Example
 class patient
 {
 char name[20];
 B_P b_p; void main()
 public:
{
 void display()
 {
clrscr();
 cout<<"\n Enter name :" ; patient p1;
 gets(name); p1.display();
 b_p.getB_P(); getch();
 b_p.show();
}
 }
 };
 The END

Question and Answer

Monday, January 18, 2021 31