COMPUTER SCIENCE - C++

LESSON 31: POINTERS & DYNAMIC DATA STRUCTURES

OBJECTIVES: The student will define the terms: pointer variable, indirection,
and address.

The student will define static versus dynamic data structures.

The student will define and demonstrate understanding of the new

and delete commands.

ACTIVITIES/TIME: One Day: Presentation - 50 minutes

Worksheet - Homework

MATERIALS: Student Outline O.A.31.1

Worksheet W.A.31.1, Pointer Types
Answer Sheet W.A.31.1

REFERENCES: Adams, Joel, Sanford Leestma, and Larry Nyhoff. C++, An

Introduction to Computing. Chapter 15.

Deitel, Harvey M. and Paul J. Deitel. C++ How to Program.

Chapter 15.

INSTRUCTOR
NOTES: This lesson will provide a thorough introduction to pointer
variables, address, and indirection. Students were introduced to
pointers in Lesson 30 when learning how to work with this
pointers. The lesson will teach the use of the new and delete
commands and how to work with pointers. The idea of indirect
referencing takes some time to get used to. Be patient with the
students and encourage lots of questions during the lecture
presentation.

APCS - C++, Lesson 31 ©1998, ICT

 STUDENT OUTLINE

Lesson 31: Pointers & Dynamic Data Structures

INTRODUCTION: Pointer variables open up a new world of programming.

The power and creativity of pointer-based data structures give the
programmer a much broader range of tools for problem solving.
This lesson will serve as an introduction to pointers and an
overview of pointer-based data structures.

The key topics for this lesson are:

A. Pointer Variables
B. Syntax of Pointer Variables
C. Allocation of Dynamic Memory
D. Pointer Variable Manipulations
E. Dynamic Data Structures

VOCABULARY: POINTER VARIABLES ADDRESS

INDIRECTION NEW
DELETE NULL
STATIC DYNAMIC
DEREFERENCE

DISCUSSION: A. Pointer Variables

1. A pointer variable is a variable that stores a different kind of

value, an address.

2. The random access memory of a computer is mapped with

locations called addresses. But instead of 123 Main Street,
memory addresses are labeled with hexadecimal numbers like
F5A2. Fortunately, we will not have to worry about or work
with hexadecimal numbers (base 16), but it is helpful to know
what type of values are stored in pointer variables.

3. Indirection is a technique where information directs you to the

actual location of an object. This concept of indirection is
what makes pointer variables difficult to understand at first.

4. Suppose you are driving from San Jose to San Francisco on

Interstate 280. When a large sign stating “San Francisco”
 appears above the road, it is a pointer directing you to the
object you are seeking. The sign is not the city of San
Francisco, it is a method of indirection pointing you to your
destination.

5. A pointer variable is like a traffic sign. It will provide

information about where data is stored. It points to a memory
location.
B. Syntax of Pointer Variables

1. A pointer variable is declared by using the asterisk operator (*)

with already defined or existing types. In a declaration, the
asterisk operator (*) must precede the identifier being declared
as a pointer.

int *a, *b; // a and b are pointer variables

2. Each of the variables a and b will not directly store integers.

They will store the addresses where an integer is stored in
memory.

3. A declared pointer in C++ is uninitialized and therefore

contains a garbage address value. To use such garbage
addresses in a program is to invite disaster and usually results
in a program crash.

4. Pointer variables are often used in conjunction with the address

operator (&) which returns the address of a variable. Here is a
familiar example, used in Lesson 30.

Program 31-1

#include <iostream.h>

main()
{
int num = 5;
int *where; // where is a pointer, stores an address

where = &num; // where now stores the address of num

cout << "The address stored in where = " << where << endl;
cout << "The contents of *where = " << *where << endl;
return 0;
}

Run output (the address is machine-dependent):

The address stored in where = a7b2

The contents of *where = 5

5. The declaration int *where implements a pointer variable.

The statement where = &num assigns the address of num to
the pointer variable where. The address stored in where is
machine-dependent.
6. The (*) operator is called the dereferencing operator. This
unary operator returns the contents of the address it is applied
to. The effect of *where is to return the contents of address
a7b2. Another way to translate *where is to think of it as
*(a7b2). The first cout statement prints out the address stored
in where, address a7b2. The second cout statement prints out
the contents of *where, which is 5.
7. Notice that the (*) operator is used in two different ways in this
program. When it is part of a variable declaration (int
*where) it is setting up a pointer variable. When it is used as
part of a statement, (*where) it is dereferencing a memory
address.

8. A pointer variable can point to no address. This is

accomplished in one of two ways. Assume a is a pointer
variable.

a = 0;
a = NULL;

In either case, the pointer variable a is holding no address.

C. Allocation of Dynamic Memory

1. The term dynamic refers to change. A program which uses

dynamic memory is one which adjusts the amount of memory
used depending on the changing needs of a program. For
example a small word processing document needs little
memory. As the document gets longer, the word processing
program allocates more memory to store the growing number
of characters.

2. When a C++ program is run, a certain segment of RAM is

available for the program to use. This stack of memory is
called a heap. Memory is allocated for use from the top of the
heap.

3. C++ provides a new command which allocates memory for use

with pointer variables. The general form of the new command
is the following:

new type

This command will return a block of memory large enough to

hold an object with the specification of type. If the allocation
is successful, the operation returns the starting address of a
block of memory, otherwise it returns the NULL address 0.

4. The new command is applied to a specific type and the

memory block returned is stored in a pointer variable. For
example the code
 int *a;
a = new int;

allocates a block of memory (address D2F6 in Diagram 31-1)

to store an integer and returns that address to a. It is in this
address that the integer value will eventually be stored.

5. To store an integer in this newly allocated memory location

requires the use of the indirection (asterisk) operator, *.

*a = 5;
 Diagram 31-1

a D2F6

D2F6 5

a. The memory location allocated is D2F6.

b. The pointer variable a stores a memory location, D2F6.
c. The indirection operator (*) performs a dereference. In a
sense, the pointer variable a is a reference variable for
another address. However that address has no other
variable name. The statement (*a) means to dereference a
and work directly with the memory location that was
aliased.
d. Another way of thinking about the statement (*a) is "to
inspect the memory location referenced by a."
e. This is an example of assignment to a location through a
pointer variable.

6. The above is indirection in action. The pointer variable a does

not store an integer; it redirects you to where the desired
information is located.

7. We do not need to know the actual memory locations although

C++ will allow us to print out such information. The statement

cout << a;

will print out the address D2F6 if applied to diagram 31-1.

8. To streamline our thinking about pointers and data structures it

will be best to eliminate the actual addresses from our pictures.
Therefore, we will use abbreviated terminology and diagrams
to illustrate pointers. The previous diagram as shown above in
key topic C, #5, will now be shown as the following:

a 5

D. Pointer Variable Manipulations

1. Assume the following declarations apply in section D.

 int *a, *b;

2. This fragment of code demonstrates the assignment of one

address stored by a pointer to another pointer. Here is another
way of thinking about this assignment: a pointer is made to
point to the same address as another pointer.

a = new int;
*a = 5;
b = a;

C6F2
a
(C6F2)
5

b
(C6F2)

a. The new command allocates memory (C6F2) and a stores

this address.
b. The statement *a= 5; places the integer value 5 in the
address which the pointer a is storing.
c. The pointer b now stores the same memory location
(C6F2) which a is storing. We now have two pointers
pointing to the same memory address (C6F2).

3. This next example demonstrates the transfer of data from one

memory location to another, using pointer variables.

a = new int;
b = new int;
*a = 8;
*b = 10;
*b = *a;

a 8

b 10 8

a. a points to an address holding the integer value 8 and b

points to the address holding the integer value 10.
 b. In the statement *b = *a, the value of 8 is transferred from
one memory location to another. We are using the pointer
variables, going through them to access the integer values.

4. A last example illustrates something we do not want to do with

pointer variables:

a = new int;
b = new int;
*a = 2;
*b = 5;
b = a;

a 2

b 5

a. The last statement causes the pointer variable b to receive

the address stored in a. This is legal code, except we have
lost track of the original address of b and the value of 5
stored in that address. There will be occasions when we
wish to eliminate unwanted information stored in data
structures, but we do not want to waste memory.

b. To avoid losing track of memory and wasting space, the

delete operation is needed. The delete operation causes
the address stored by a pointer variable to be returned to
the heap.

a = new int;
b = new int;
*a = 2;
*b = 5;
delete b;
b = a;
 a heap
2

b 5

more memory

c. The delete operation returns unwanted memory back to the

heap, which will be the first memory allocated when the
next new operation is invoked.

5. And finally, a look at an incorrect pointer statement:

a = 5;

This attempts to assign the memory location 5 to the pointer a.

While this is possible in C++, you do not want to work with
random memory locations. Memory location 5 could be the
location of critical system information.

E. Dynamic Data Structures

1. During the next month of the course, you will learn how to use
pointer variables to build dynamic data structures.

2. A dynamic data structure is one which is created during the

running of the program. Its size and memory usage fluctuate
according to the needs of the program.

3. The apvector class created objects that had characteristics of

both static and dynamic data structures. When the vector was
allocated it had a certain fixed size of cells. It is possible to
resize a vector but constant resizing will slow down the
program.

4. A linked list is conceptually similar to a vector but the resizing

will be handled in a more efficient and direct manner.

5. The two most important types of dynamic data structures you

will learn about are linked lists and binary trees.
SUMMARY/REVIEW: Like a single record variable, a single pointer variable is
interesting but not very useful. It is when we put pointer variables
together in a data structure that pointers become powerful
programming tools.

ASSIGNMENT: Worksheet W.A.31.1, Pointer Types