Data structure and problem solving ch05.ppt

Chapter 5 Pointers and Dynamic Memory

2 Outline • C++ Pointers  Declaring Pointer Variables  Assigning Address Values to Pointers  Accessing Data with Pointers  Arrays and Pointers  Pointers and Class Types • Dynamic Memory  The Memory Allocation Operator new  The Memory Deallocation Operator delete  Class using Dynamic memory  Dynamic Arrays  The Destructor • Assignment and Initialization  Overloading the Assignment Operator =  Copy Constructor  The pointer this

3 Storage of Data in Memory A ddress D ata contents A ddress 0 A ddress n A ddress 2 A ddress 1 A ddr 0 A ddr 1 A ddr 2 Addr n Vertical View of M emory H orizontal View of M emory . . . ... • Memory consists of a sequence of bytes (eight-bit groups). • Each location in the sequence has an associated address.

4 Data Addresses in Memory 50 integer char 5000 S 5004 5005 • The number of bytes to store a data item depends on its type  An integer typically requires four bytes  A character uses a single byte • In the case where a data item occupies more than one byte, we associate with the item the address of its first byte.  Integer 50 is stored at address 5000  Character ‘S’ is stored at address 5004

5 • The pointer ptr is a variable whose value is the address of a data item of the designated type. Declaring Pointer Variables int *intPtr; char *charPtr; type *ptr; • Declare a pointer by stating the type followed by the variable name, but with a "*" added immediately before the name. • C++ uses pointer variables (pointers) to hold the address of (also called point to) an object (or variable) of a specified type.

6 Assigning Address Values to Pointers • The following assignment statement sets intPtr to point at an actual data item.  &m is the address of the integer in memory. intPtr = &m; int m = 50, *intPtr; 50 m ? intPtr ? 50 m & m intPtr (a) A fte r de claration (b) A fte r as s ignme nt • How to obtain an address value?  C++ has the “address-of” operator &, which retrieves the memory address of a variable or object declared within the program.

7 int x = 50, y = 100, *px = &x, *py = &y; 50 x p x 100 y p y • We may declare a pointer and assign it an address value at the same time. • Note x and y are regular integer variables, px and py are pointers. px is set to point at x, and py is set to point at y.  This is equivalent to write Assigning Address Values to Pointers int x = 50, y = 100, *px, *py; px = &x; py = &y;

8 Accessing Data with Pointers double x = 2.98; // declares double variable x double *dPtr; // declares a pointer that can // hold address of a double type data dPtr = &x; // assign the address of x to dPtr cout << *dPtr; // output the data 2.98 *dPtr = -3.6; // assigns -3.6 to the double type // variable x referenced by dPtr • How to access the data pointed to by the pointer?  C++ provides the dereference operator *, which combines with (attached immediately before) the pointer to access to the data referenced by the pointer.  NOTE: We use symbol * when declaring a pointer, and we also use * (the dereference operator) when accessing the data referenced by the pointer. 2.98 ? dPtr x ? &x dPtr 2.98 x &x dPtr -3.6 x

9 Accessing Data with Pointers int x = 50, y = 100, *px = &x, *py = &y; • Expressions combine the pointers and the dereference operator * to update values of x and y *px = *py + 2; // assign to x the value y + 2 = 102 *py = *py * 2; // double the value of y to 200 (*px)++; // Increment x from 102 to 103 50 x p x 100 y p y *px = *py + 2; *py = *py * 2; (*px)++; 102 x px 100 y py 102 x px 200 y py 103 x px 200 y py

10 Accessing Data with Pointers • Pointers are variables and we may assign one pointer to another  The pointer on the left-hand side gets a new address value and references the same data item as the pointer on the right-hand side. py = px; // py points to the same object referenced by px cout << *px << “ “ << *py; // output: 103 103 cout << x << “ “ << y; // output: 103 200 before assignment after assignment 103 x px 200 y py 103 x px 200 y py

11 Arrays and Pointers arr arr[0] arr[6] arr[5] arr[4] arr[3] arr[2] arr[1] arr+7 arr+2 arr+1 6000 6028 6020 6016 6012 6008 6004 6032 arr+5 • allocates 7 integer objects and assigns to arr the starting address, which is also the address of the first object arr[0]. int arr[7]; *arr accesses the same data as arr[0] does *arr = 20; • arr + i is the address of arr[i] *(arr+i) is the same as arr[i] *(arr+5) = 30; Address(arr + i) = arr + i * 4 bytes 20 30

12 Arrays and Pointers arr arr[0] arr[6] arr[5] arr[4] arr[3] arr[2] arr[1] arr+7 arr+2 arr+1 6000 6028 6020 6016 6012 6008 6004 6032 arr+5 arr[2] = 50; *(arr+3) = 60; 50 60 int *p; P = arr; *p = 90; *(p+1) = 70; P[3] = 40; arr arr[0] arr[6] arr[5] arr[4] arr[3] arr[2] arr[1] arr+7 arr+2 arr+1 6000 6028 6020 6016 6012 6008 6004 6032 arr+5 50 40 90 70 P[i] is equivalent to *(p + i) and arr[i] We may assign arr (starting address) to a pointer 20 30 30

13 Pointers and Class Types class Employee { public: Employee (string inName) {name = inName; salary = 0.0 }; void setSalary(double inSl) { salary = inSl; } void print() { cout << “Name: “ << name << “ Salary: “ << salary << endl; } private: string name; double salary; }; int main() { // create an employee object Employee emp(“Tom”); // declare a pointer Employee *empPtr; // set empPtr to point at emp empPtr = &emp; // Use dereference operator * // *empPtr is the object emp (*empPtr).setSalary(900); // Use dereference-and-select operator -> // to access the member function empPtr->print(); return 0; } • We may assign address of an object to a pointer, e.g. ptr • Note * operator has a lower precedence than the . operator • Suppose f() is a member function of the object ptr is pointing at, Ptr -> f() is shorthand for (*ptr).f(). -> is the dereference-and-select operator

14 Dynamic Memory • Memory management  Two types of memory spaces: Stack and Heap  int b; // b is created on stack, also called static allocation, // i.e., before the execution of the program  Stack variables like b is destroyed when the function in which it was declared returns, e.g. return 0; for variables declared in main() • Dynamic allocation is created and destroyed during execution, which can save space in memory.  is stored on the Heap, a large area of memory  is accessed through pointers.  created with operator new and deleted with operator delete

15 Use operator new for dynamic allocation • int *iPtr; // declares a pointer (on stack) iPtr stack iPtr stack heap dynamic allocation 5000 5000 ? • Again, we use the dereference operator, ‘*’ with the pointer to access the integer *iPtr = 80; iPtr stack heap dynamic allocation 5000 5000 80 • Use operator new to allocate storage space for an integer on heap iPtr = new int; The integer is pointed to by pointer iPtr which holds its address (e.g., 5000).

16 To Deallocate Dynamic Memory • The operator delete is used: delete iPtr; • This deallocates the space for the integer pointed to by pointer iPtr. • NOTE: the pointer iPtr still exists (on stack), which will be deleted (automatically) when the function in which it was declared returns iPtr stack Study NOTES ON POINTERS

17 Example 1: int type int *p, *q; // asterisk * needed for each pointer p = new int; q = new int; *p = 55; *q = 0; cout << *p <<“ “ << *q << endl; *q = *p; cout << *p << “ “ << *q << endl; delete p; // deallocate the dynamic memory pointed to by p delete q; // deallocate the dynamic memory pointed to by p // p and q are still alive 55 0 55 55

18 Dynamic Allocation of Objects p = new time24; // *p is 00:00 (midnight) q = new time24(8, 15); // *q is 8:15 AM H eap p.hour q.m inute q.hour p.m inute 00 15 08 00 p q // calls the default constructor ptr = new className; // pass arguments to constructor ptr = new className (arguments);

19 Example 2: Dynamic allocation of objects class Employee { public: Employee () {name = “”; salary = 0.0 }; Employee (string inName) {name = inName; salary = 0.0 }; void setName(string inName) { name = inName; } string getName() {return name;} void setSalary(double inSl) { salary = inSl; } double getSalary() {return salary;} void print() { cout << “Name: “ << name << “ Salary: “ << salary << endl; } private: string name; double salary; }; int main() { // regular object created on stack Employee emp1; emp1.setName(“Tom”); // create pointers (on stack) Employee *emp2Ptr, *emp3Ptr; // calls default constructor to create // dynamic Employee object (on heap) emp2Ptr = new Employee; // member-selection operator (the dot) (*emp2Ptr).setName(“Jerry”); (*emp2Ptr).setSalary(900); // calls custom constructor emp3Ptr = new Employee(“Mary”); // To access member functions, we can // use dereference-and-select operator -> emp3Ptr->setSalary(1000); emp3Ptr->print(); // deallocate dynamic objects delete emp2Ptr, emp3Ptr; // pointer still alive return 0; }

20 Dynamic Arrays • GO OVER NOTES ON ARRAYS • int *dynArr; dynArr can be a pointer to either a single integer or to an array of integers. • dynArr = new int [5]; allocates an array of 5 integers on heap and stores in dynArr the address of the zero-th element in this array. dynArr

21 The Index Operator, operator[ ] • Random-access: any item in an array can be accessed or modified immediately, given the index of the item: for (int i = 0; i < 5; i++) cin >> dynArr [i]; • [ ] is used to reference the individual items: dynArr[0] = 3; This is equivalent to *dynArr = 3; • In general, for any array a and non-negative integer i, a[i] is equivalent to *(a + i), e.g., dynArr[1] = 8; is the same as *(dynArr + 1) = 8;

22 Dynamic Allocation • A regular array’s capacity is fixed once created • But for a dynamic array, we can specify the size as follows: int capacity; cin >> capacity; int *dynArr = new int [capacity]; • Note that the capacity need not be known until run time.

23 Destroy A Dynamic Array • Let pointer dynArr point to a new resized array: capacity *= 2; // double the capacity dynArr = new int [capacity]; • To deallocate the space for an dynamic array, place square brackets (i.e., index operator) between delete and the pointer’s name: delete [] dynArr;

24 Class with Pointer Members // student.h class Student { public: Student(); void setID(int inID); int getID(); ~Student(); // destructor private: int *id; // declare pointer }; int main() { Student stu; stu.setID(1234); cout << “The ID is: “ << stu.getID(); return 0; } // student.cpp #include “student.h” Student::Student() { id = new int; } // create dynamic variable void Student::setID(int inID) { *id = inID; } // use dynamic variable int Student::getID() { return *id; } Student::~Student() { delete id; } // delete dynamic variable

Data structure and problem solving ch05.ppt

More Related Content

Similar to Data structure and problem solving ch05.ppt

More from Ping261512

Recently uploaded

Data structure and problem solving ch05.ppt