Data Structures and Algorithms

Chapter 4 – Pointers

Dr. Georges Badr

1
Data types in C++

The C++ manipulates addresses using variables called pointers

Data types in C++

Simple Composed
Address

Integer Real array struct union class

int, char, Float, double,

bool, etc etc

pointer reference
enum

2
 Pointer
▪ Object whose value represents the location of another object

 In C++ there are pointer types for each type of object

▪ Pointers to int objects
▪ Pointers to char objects
▪ Pointers to Car, Student, Circle … objects
▪ …
▪ Even pointers to pointers
- Pointers to pointers to int objects

3
Pointers variables
 Declaration: DataType* var;
 Multiple declarations: DataType *var1, *var2, …;
 Examples
int * ad ;
int n ;
n = 20 ;
ad = &n ; //assign the address of n to ad
*ad = 30 ;// assign *ad the value 30, n becomes 30
 The variable ad
▪ is a pointer to integers, pointer of type int*
▪ Contains the address of an integer

 * is a unary operator that designates the content of an address

 * indicates that a variable is a pointer (in the declaration)
 *ad is an object with address ad, we say that we dereference the pointer
4
Pointers variables

 Representation of pointers

Address Variable
ad n 5000 5008 ad
20

30 5008 30 n

ad = &n ; //assign the address of n to ad

*ad = 30 ;//assign *ad the value 30

5
Motivation

 Why do we need address types:

▪ They can make a program more efficient
- in terms of execution time and memory usage
- e.g., dynamic memory allocation and removal of this memory during running time
 this can replace static arrays and structures
- e.g., passing arguments to functions by pointer avoid copying variables and give direct access to original data

▪ They are used to create more complex data structure

- e.g., linked list, stacks and queues etc.

6
Some examples

int * ad1, * ad2, *ad ;

int n = 10, p = 20 ;
ad1 = &n ;
ad2 = &p ;
*ad1 = *ad2 + 2 ; //n = p + 2 ;
*ad1 += 3; //n = n + 3
(*ad1)++; //n++
*(ad1++);
ad1++ = next address;
*(ad1++): the value referenced by ad1++ if it exists

7
Some examples (cont.)
 Remarks:
1. ad et *ad are lvalues, but &ad is not

2. int * ad ; reserves a memory place for a pointer pointing to an integer, but it does not
reserve the integer.

3. int &x = y; //reference not address (call by reference in fct)

4. int x =5;
&x=10; //error

5. int x=10;
int y = &x; //y will contain the integer value of address of x

5. int y=10; int *x = &y; //x is a pointer to y. it contains the address of y

6. int *x; x=&y; //declaration then initialization

8
Pointer incrementation

int * ad ;
ad++;
 ad contains the address of the next integer (element) (i.e. the integer that is
after *ad)
 In fact, the address is increased by sizeof(dataType) bytes.
 In this case, it’s sizeof(int)

9
Reference type

int& j = i;
▪ j is a reference (of type reference) to an integer (type int&) which is now equivalent to i.

 All that we do to j is now done to i (and inversely)

int i = 18;
int& j = i;
i++;
j++;
▪ i and j will be both equal to 20

10
Reference type

 Remarks:
1. int &j = i; //same as: int& j = i;
▪ &j, means that the memory place referenced by j, is of type integer, and is the same as i

2. There is no operation done with references

▪ but operations are performed to the referenced variable
▪ e.g. j++ is applied to i

3. int &i; int& j;

▪ this is incorrect and it is refused by the compiler
▪ the initialization is required

11
Example
Suppose:
Adr x = 3000 int x = 5;
Adr y = 4000 int &y = x;
Adr p = 2000 int *p;
int *p = &x; Address Variable
p = &x;
cout << *p; → 5 2000 3000 p
cout << p; → 3000 (&x)
cout << &p; → 2000
cout << x; → 5 3000 67
8
5 x
cout << &x; → 3000
cout << y; → 5
cout << x++; → 5 //postincrementation 85
67
4000 y
cout << *p; → 6
cout << y; → 6
cout << ++y; → 7
cout << x; → 7
*p++;
cout << x; → 8
12
Pointer on a pointer - Example
Suppose
&n = 0x22ff40 Address Variable
&pn = 0x22ff44
&ppn = 0x22ff5c 0x22ff40 44 n
int n = 44;
cout << "n = " << n << endl; → n = 44

cout << "&n = " << &n << endl; → &n = 0x22ff40 0x22ff44 0x22ff40 pn
int* pn = &n;
cout << "pn = " << pn << endl; → pn = 0x22ff40
0x22ff5c 0x22ff44 ppn
cout << "&pn = " << &pn << endl; → &pn = 0x22ff44
cout << "*pn = " << *pn << endl; → *pn = 44

int** ppn = &pn;

cout << "ppn = " << ppn << endl; → ppn = 0x22ff44
cout << "&ppn = " << &ppn << endl; → &ppn = 0x22ff5c
cout << "*ppn = " << *ppn << endl; → *ppn = 0x22ff40
cout << "**ppn = " << **ppn << endl; → **ppn = 44

13
Passing argument to a function

 We have three modes of passing arguments

1. Passing arguments by value
2. Passing arguments by reference
3. Passing argument by address with pointers

14
Passing arguments by value
#include <iostream.h>
Address Variable
void swap (int, int );
3000 10 n
int main(){
int n = 10, p = 20 ;
cout << "before call: " << n << " " << p << "\n"; 3004 20
5 p
swap (n, p) ;
cout << "after call: " << n << " " << p << "\n";
return 0;
}
Address Variable
void swap (int a, int b){
int tmp ; 5000 10
20 a
cout << "start swap: " << a << " " << b << "\n";
tmp = a ;
a = b ;
5004 10
20 b
b = tmp ;
cout << "end swap: " << a << " " << b << "\n"; 5008 10 tmp
}
before call: 10 20
Output start swap: 10 20
end swap: 20 10
15
after call: 10 20
Passing arguments by reference
#include <iostream.h>
Address Variable
void swap (int&, int& );
3000 20
10 n a
int main(){
int n = 10, p = 20 ;
cout << "before call: " << n << " " << p << "\n"; 3004 10
20 p b
swap (n, p); // attention, here there is no &n, &p
cout << "after call: " << n << " " << p << "\n";
return 0;
} int& a = n;
int& b = p; Address Variable
void swap (int& a, int& b){
int tmp ;
cout << "start swap: " << a << " " << b << "\n"; 5008 10 tmp
tmp = a ;
a = b ;
b = tmp ;
cout << "end swap: " << a << " " << b << "\n";
}
before call: 10 20
Output start swap: 10 20
end swap: 20 10
16
after call: 20 10
Passing arguments by address with pointers
#include <iostream.h>
Address Variable
void swap (int*, int* );
3000 20
10 n
int main(){
int n = 10, p = 20 ;
cout << "before call: " << n << " " << p << "\n"; 3004 10
20 p
swap (&n, &p);// attention, here we have &n, &p
cout << "after call: " << n << " " << p << "\n";
return 0;
} int* a = &n;
int* b = &p; Address Variable
void swap (int* a, int* b){
int tmp ; 5000 3000 a
cout << "start swap: " << *a << " " <<* b << "\n";
tmp = *a ;
*a = *b ;
5004 3004 b
*b = tmp ;
cout << "end swap: " << *a << " " << *b << "\n"; 5008 10 tmp
}
before call: 10 20
Output start swap: 10 20
end swap: 20 10
17
after call: 20 10
Remark

 The prototype of the swap function can be written as follows:

void swap (int * const ad1, int * const ad2)
▪ * const ad1 is of type int,
▪ ad1 is then a constant address pointing to an integer, i.e. a constant pointer.
- i.e. the address or pointer cannot be changed
Error: ad1++
 If we had: const int * ad1
▪ int * ad1 is a constant, and then:
▪ ad1 is a pointer to a constant integer
- i.e. we cannot change the integer value pointed by ad1

18
int * a; // a is a pointer to integer
int x = 10;
a = &x;
*a = 20;

const int *a ; // a is a pointer to a constant integer

int x = 10;
a = &x;
*a = 20; //error

19
TYU
Write a function that asks the user to input an integer value

int input(){ void input(int &x){ void input(int *x){

int x; cin >> x; cin >> *x;
cin >> x; } }
return x;
} int main(){ int main()
int a; {
int main(){
input(a); int a;
int a;
return 0; input(&a);
a = input();
} return 0;
return 0;
}
}

20