Introduction to Data Structures
and Algorithm
21COMP04C
2023
Lecture2
1
Lab1 submission
• Labs are ungraded
• Lab 1 submission is next Sunday.
2
Lecture 2
Pointers
Object Oriented Programming
Lecture Resources
Data-Structure Using C++ by D.S. Malik (ch 1)
Data Structures Using C by Reema Thareja (ch2)
These slides are adapted for the text book's slides 3
Contents
• OO principles
• Classes
• Pointers
• Address of Operator (&)
• * operator
• Dynamic Arrays
• References
4
OOP has the following basic principles:
• Encapsulation:
• The ability to combine data and operations in a single unit and to
hide the information within an object so that it cannot be
accessed directly from outside the object.
• In C++, encapsulation is accomplished via the use of data types
called classes
• Abstraction
• Abstraction is the process of hiding the implementation details of
an object so that it can be used without understanding how it
works. This allows you to create code that is easy to use and
maintain. In C++, Abstraction is accomplished via the use of data
types called classes
• Inheritance:
• The ability to create new (data) types from existing (data) types
• In C++, Inheritance accomplished via the use of class inheritance.
• Polymorphism:
• The ability to use the same expression to denote different
operations or the ability of an object to take on multiple forms.
This is useful because it allows you to create code that is more
flexible and adaptable
• In C++, Polymorphism is accomplish via the use of functions and
operators overloading Source: https://technocation.pk/object-oriented-programming-course-in-rawalpindi/
5
Classes
• OOD first step: identify components (objects)
• Encapsulation: object combines data and data operations in a single unit
• Class: collection of a fixed number of components
• Components → Class members
• With each member (or component) has a type or category called access specifiers
• Category specifies how to access (or use) the class member
• Component’s Categories : Private, public, protected
Class definition
6
Class member
• Variables
• Functions
• Constructor(s) (special type of functions)
• Destructors (special type of functions)
7
clockType
8
class clockType
{
Example private:
int hr; //variable to store the hours Constructor
Functions overloading
int min; //variable to store the minutes Const
int sec; //variable to store the seconds Private and public order
Function definition is not here
public:
void setTime(int hours, int minutes, int seconds);
void printTime() const;
void incrementSeconds();
void incrementMinutes();
void incrementHours();
bool equalTime(const clockType otherClock) const;
clockType(int hours, int minutes, int seconds); //constructor not return type and no void
clockType(); // default constructor
};
9
Object Declaration and class member access
class clockType
{
……………………
}
void main()
{
clockType Clock1; // create all the variable members of the class
clockType Clock2; // create another group of all the variable members of the class
Clock1.setTime(5,6,8);
Clock2.setTime(10,11,3);
Clock1.printTime();
Clock2.printTime();
int hour=Clock1.hr //not accepted hr is a private member
} 10
Constructors
class clockType
{
……………………
}
main()
{
clockType Clock1; // create all the variable members of the class + call default constructor (no need to put())
clockType Clock2(10,11,3); // create another group of all the variable members of the class+ call instructor)
Clock1.setTime(5,6,8);
Clock2.setTime(10,11,3);
Clock1.printTime();
Clock2.printTime();
Clock1.ClockType(); //not valid because constructors can’t be called by objects of the class
11
Implementation of Member Functions
1-inside class definition
class clockType {
…………………..
void setTime(int hours, int minutes, int seconds);
void printTime() const
{
if (hr < 10)
cout << "0"; Access hr,min,sec without access operator
cout << hr << ":";
if (min < 10)
cout << "0";
cout << min << ":";
if (sec < 10)
cout << "0";
cout << sec; } ………………..};
12
Implementation of Member Functions
2-outsideclass definition
class clockType
{
…………………..
void printTime() const;
………………….
};
void clockType:: printTime() const
{
if (hr < 10)
cout << "0";
cout << hr << ":";
if (min < 10)
cout << "0";
cout << min << ":";
if (sec < 10)
cout << "0";
cout << sec;
} 13
Constructors definition
clockType::clockType() //default constructor {
hr = 0; main()
min = 0;
{
sec = 0; }
clockType::clockType(int hours, int minutes, int seconds) clockType Clock1; //default constructor
{ clockType Clock2(10,11,3) //second constructor)
if (0 <= hours && hours < 24) Clock1.setTime(5,6,8);
hr = hours;
Clock1.printTime();
else
hr = 0; Clock2.printTime();
if (0 <= minutes && minutes < 60) }
min = minutes;
else
min = 0;
if (0 <= seconds && seconds < 60)
sec = seconds;
else
sec = 0; } 14
Using objects as function parameters
bool clockType::equalTime(const clockType otherClock) const
{
return (hr == otherClock.hr
&& min == otherClock.min
&& sec == otherClock.sec); }
main()
{
clockType Clock1;
clockType Clock2(10,11,3)
Clock1.setTime(5,6,8);
if( Clock1.equalTime(Clock2)):
cout<<“both clocks are equal”;
} 15
Call class function from inside another class function
clockType::clockType() //default constructor
clockType::setTime(int hours, int minutes, int
{ hr = 0;
seconds)
min = 0;
{
sec = 0; }
if (0 <= hours && hours < 24)
clockType::clockType(int hours, int minutes, int
hr = hours;
seconds)
else
{
hr = 0;
if (0 <= hours && hours < 24)
if (0 <= minutes && minutes < 60)
hr = hours;
min = minutes;
else
else
hr = 0;
min = 0;
if (0 <= minutes && minutes < 60)
if (0 <= seconds && seconds < 60)
min = minutes;
sec = seconds;
else
else
min = 0;
sec = 0;
if (0 <= seconds && seconds < 60)
}
sec = seconds;
else
clockType::clockType(int hours, int minutes, int seconds)
sec = 0; }
{ setTime(hours, minutes,seconds) ; } 16
BUILT-IN OPERATIONS ON CLASSES
• Assignment Operator =
Clock1 = Clock2;
17
Constructors and Default Parameters
If constructor porotype is as follow:
clockType:: clockType(int = 0, int = 0, int = 0);
clockType clock1;
clockType clock2(5);
clockType clock3(12, 30);
clockType clock4(7, 34, 18);
18
Classes (cont’d.)
• Destructors
• Functions
• No type
• Neither value-returning nor void function
• One destructor per class
• No parameters
• Name
• Tilde character (~) followed by class name
• Automatically executes
• When class object goes out of scope
19
Unified Modeling Language diagrams
• Graphical notation describing a class and its members
• Private and public members
FIGURE 1-5 UML class diagram of the class clockType
20
Pointer Data types
• The data types in C++ are classified into three categories: simple,
structured, and pointers.
• pointer variable is a variable whose content is a memory address.
1. Declaring Pointer Variables
• When declaring a Pointer Variables we use the datatype of the data that will be
stored in the location pointed by the pointed variable stored address
• you declare a pointer variable by using the asterisk symbol ( *) between the data
type and the variable name
dataType *identifier;
int *ptr;
int Var1=100;
ptr=&Var1 21
Examples
• For example:
• int *p; //spaces after * or before is also valid
• char *ch;
• int* p, q; //only p is a pointer
• int *p, *q; //p and q is pointers
22
How to make a pointer variable point to a
memory address
• Use Address of Operator (&)
• Example :
23
How to use pointers: use * operator
• int x; p x
• int *p;
• p = &x; // p and x are pointing to the same data
• x=25
• cout<<x<<endl //print 25
• cout<<*p<<endl // print 25
• *p=30
• cout<<x<<endl //print 30
24
int *p;
Example int num;
num = 78; //statement 1
p = # //statement 2
*p = 24; //statement 3
Another Example 3.2 in Page 135 25
cout<<p //print 1800
Initializing Pointer Variables
• int *p;
• p = NULL; // All capital letters
• p = 0;
26
Operations on Pointer Variables
• int *p,*q;
• p = q;
• p == q
• p != q
• p++ //increments the value of p by 4 bytes because p is a pointer of type int
27
Arrays
Array name is a constant pointer
• Array name value: constant
• Increment, decrement operations cannot be applied
int list[5] FIGURE 3-14 list and array list
list[0] = 25;
list[2] = 78;
FIGURE 3-15 Array list after the execution
of the statements list[0] = 25; and list[2] = 78;
28
Using pointers to handle Dynamic Variables
• Variables that are created during program execution
• Created using operator new
• Deleted using operator delete
• We use pointers to create and access Dynamic variables.
• The new operator initializes the memory and returns the address of the
newly allocated and initialized memory to the pointer variable.
• To create a dynamic variable
• new dataType; /// instead of datatype variable-identifier
• int *ptr;
• ptr = new int; //instead of int x;
29
Example new operator
• int *p;
• int x;
• p = &x; //no new memory location is allocated
• p = new int; // a new memory location is created
• *p = 28; // store 28 in the new allocated memory location
30
Example delete operator
• int *p;
• p = new int; //Line 1 //after Line 1
• *p = 54; //Line 2 //after Line 2
delete p
• p = new int; //Line 3 //after Line 3
• *p = 73; //Line 4
• delete p deallocate the memory spaces to which the //after Line 4
pointers p point.
• If you are not to use p right after that make sure to
re-initialise p with p=Null Location 1500 is inaccessible
(memory leak)
More in Example 3.3 page 142 31
Why we use Dynamic variable
• The main use of the concept of dynamic memory allocation is for
allocating arrays when we have to declare an array by specifying its
size but are not sure about the size..
• The most important use is flexibility provided to programmers. We
are free to allocate and deallocate memory whenever we need and
whenever we don’t need anymore. There are many cases where this
flexibility helps. Examples of such cases are Linked List, Tree, etc.
32
Dynamic Arrays
*intList=25 //stor 25 in the first element ofarray
intList++; //inList points to the next array component
*intList = 35; // store 35 into the second memory location
intList[0]=25 //inList[0] refers to the first array component
intList[1] = 35; // store 35 into the second memory location
33
Traverse Dynamic arrays using loops
• int *p= new int[10]
• for (int j = 0; j < 10; j++)
p[j] = 0;
• When the array notation is used to process the array to which p
points, p stays fixed at the first memory location. Note that p is a
dynamic array, created during program execution
To delete dynamical allocated array use the delete operator
delete [] p;
34
Pointers and classes objects
member access operator arrow: ->
• ClockType Clock1;
• ClockType *Clock2;
• Clock2=& Clock1;
• Clock1.setTime(10,5,55);
• (*Clock2).setTime(10,5,55);
• Clock2-> setTime(10,5,55);
35
References
• The “pointer” and “reference” both are used to point or refer an
another variable
pointers reference
int a = 5,b=6; int a = 5,b=6; A reference must be initialized
int *p = &a; int &ref = a; when it is declared.
int *p = &a; int &ref = a; reference can’t be reassigned
p=&b &ref = b; //invalid
A pointer can be assigned to a References cannot be NULL NULL
NULL value.
int a = 5; int a=5; Reference are easy to use
int *p = &a; int &ref = a;
*p=6 ref=6;
cout<<a; //print 6 cout<<a //print 6
Use -> opertor use . operator To access member of object of
class
36
Shallow Vs. Deep Copy and Pointers
1-Shallow copy (want to copy array then delete original)
• int *first= new int[10]
• int *second;
• second = first; Copy statement
Changing any element in second will change the same element in first
• delete [] first;
37
2-Deep copy
• Two or more pointers have their own data
• Manually create a new array and copy all elements
int *first= new int[10]
………..
int *second;
//Deep copy operation
second = new int[10];
for (int i=0;i<10;i++)
{
second[i]=first FIGURE 3-19 first and second both pointing to their own data
}
delete [] first;
38
