Transcript PPT - The School of Electrical Engineering and Computer Science

Cpt S 122 – Data Structures
Pointers
Nirmalya Roy
School of Electrical Engineering and Computer Science
Washington State University
Topics









Definitions and Initialization
Pointer Operators
Passing Arguments to Functions by Reference
const qualifiers with Pointers
sizeof operator
Pointer Expressions and Arithmetic
Relationship between Pointers and Arrays
Array of Pointers
Pointers to Functions
Pointer


One of the most powerful features of C.
Enables programs to simulate pass-by-reference.


pass functions between functions.
For creating and manipulating dynamic data
structures (i.e., data structures that can grow and
shrink at execution times).

Linked lists, queues, stacks, trees.
Pointer Variable Definitions and Initialization


Pointers are variables whose values are memory
addresses.
Normally, a variable directly contains a specific value.


A pointer contains an address of a variable that
contains a specific value.


A variable directly references a value.
A pointer indirectly references a value.
Indirection means referencing a value through a
pointer.
Pointer Variable Definitions and Initialization

Directly and indirectly referencing a variable
count
7
countPtr
count
Memory
Location of 7
7
count directly references
a variable that contains the value 7.
Pointer countPtr indirectly
references a variable that contains
the value 7.
Pointer Variable Declaration


Syntax: <data type> *<pointer variable>;
Example: int *countPtr;



What is the difference between count and countPtr?

int *countPtr, count;

specifies that variable countPtr is of type int * (i.e., a
pointer to an integer)
the variable count is defined to be an int, not a pointer to an
int.


“countPtr is a pointer to an int”
“countPtr points to an object of type int”
Naming convention for pointers

Include the letter ptr in pointer variable names
Pointer Variable Initialization

Pointers should be initialized either when they’re
defined or in an assignment statement.




Values: NULL, 0, or an address.
A pointer with the value NULL points to nothing.
NULL is a symbolic constant defined in <stddef.h>
header.
The value 0 is the only integer that can be assigned
directly to a pointer variable.
Example of NULL Pointers

The null pointer is the only integer literal that may be assigned to
a pointer



The null pointer is never a valid target


If you try to dereference the null pointer, you will get a segmentation fault.
The null pointer is typically used as a placeholder to initialize
pointers


int * ptr = 0; // OK. assignment of null pointer to p.
int * z; z = 900; // BAD! Cannot assign other literals to pointers.
If you make sure your pointer is ALWAYS set to either a valid target, or to
the null pointer, then you can test for it
if (ptr != 0) //safe to dereference
printf(“%d”, *ptr);
To prevent dangling pointers
Pointer Operators


The &, or address operator, is a unary operator that returns the
address of its operand.
For example, assuming the definitions

int y = 5;
int *yPtr;
the statement


yPtr = &y;
assigns the address of the variable y to pointer variable yPtr.
Variable yPtr is then said to “point to” y.
yPtr
yPtr
y
Location
500000
600000
5
y
yPtr “points to” y.
Location
600000
5
Pointer Operators (Cont.)
The Indirection (*) Operator
 The unary * operator, commonly referred to as the
indirection operator or dereferencing operator



returns the value of the object to which its operand (i.e., a
pointer) points.
For example, printf( "%d", *yPtr ); prints the
value of variable y, namely 5.
Using * in this manner is called dereferencing a
pointer.
Passing Arguments to Functions by Reference

There are two ways to pass arguments to a function




Note. All arguments in C are passed by value.
Many functions require the capability to modify variables
in the caller or to pass a pointer to a large data object to
avoid the overhead of passing the object by value


pass-by-value/call-by-value and
pass-by-reference/call-by-reference.
pass-by-value incurs the time and memory overheads of making a
copy of the object
We can simulate pass-by-reference using pointers.
Passing Arguments to Functions by Value
void swap(int a, int b) {
int temp;
temp = a;
a = b;
b = temp;
}
void main(void) {
int x = 3; y = 5;
printf(“x = %d, y = %d\n”, x, y);
swap(x, y);
printf(“x = %d, y = %d\n”, x, y);
}
Passing Arguments to Functions by Reference
void swap(int *a, int *b) {
int temp;
temp = *a;
*a = *b;
*b = temp;
}
void main(void) {
int x = 3; y = 5;
printf(“x = %d, y = %d\n”, x, y);
swap(&x, &y);
printf(“x = %d, y = %d\n”, x, y);
}
Example of pass-by-value
Example of pass-by-reference
Example of pass-by-reference

A function receiving an address as an argument must define a
pointer parameter to receive the address.

For example, the header for function cubeByReference is:


void cubeByReference( int *nPtr )
The header specifies that cubeByReference receives the
address of an integer variable as an argument,

stores the address locally in nPtr and does not return a value.
Using the const Qualifier with Pointers


The const qualifier enables you to inform the
compiler that the value of a particular variable
should not be modified.
Four ways to pass a pointer to a function




Non-constant pointer to non-constant data
Non-constant pointer to constant data
Constant pointer to non-constant data
Constant pointer to constant data
Using the const Qualifier with Pointers

Non-constant pointer to non-constant data


The data can be modified through the dereferenced
pointer, and the pointer can be modified to point to
other data items.
Non-constant pointer to constant data

The non-constant pointer to constant data can be
modified to point to any data item of the appropriate
type, but the data to which it points cannot be modified.
Using the const Qualifier with Pointers

Constant pointer to non-constant data


A constant pointer to non-constant data always points to
the same memory location, and the data at that location
can be modified through the pointer.
Constant pointer to constant data

Such a pointer always points to the same memory
location, and the data at that memory location cannot
be modified.
Non-Constant Pointer to Non-Constant Data


The highest level of data access is granted by a nonconstant pointer to non-constant data.
The data can be modified through the dereferenced
pointer



the pointer can be modified to point to other data items.
A declaration for a non-constant pointer to nonconstant data does not include const.
Such a pointer might be used to receive a string as
an argument to a function that processes (and
possibly modifies) each character in the string.
Example: Non-Constant Pointer to Non-Constant
Data
Example: Non-Constant Pointer to Non-Constant
Data
Non-Constant Pointer to Constant Data

A non-constant pointer to constant data can be
modified to point to any data item of the appropriate
type


the data to which it points cannot be modified.
Such a pointer might be used to receive an array
argument to a function that will process each
element without modifying the data.
Example: Non-Constant Pointer to Constant Data
Example: Non-Constant Pointer to Constant Data
Non-Constant Pointer to Constant Data (Cont.)


For example, function printCharacters declares
parameter sPtr to be of type const char * .
The declaration is read from right to left as “sPtr is a
pointer to a character constant.”


The function uses a for statement to output each character
in the string until the null character is encountered.
After each character is printed, pointer sPtr is
incremented to point to the next character in the string.
Compilation Error: Non-Constant Pointer to
Constant Data
Compilation Error: Non-Constant Pointer to
Constant Data

This is an attempt to compile a function that receives a
non-constant pointer (xPtr) to constant data.

This function attempts to modify the data pointed to by
xPtr results in a compilation error.
Arrays and Structure: pass-by-reference
and pass-by-value



Arrays are aggregate data types that store related data items
of the same type under one name.
Another form of aggregate data type called a structure
(sometimes called a record in other languages).
A structure is capable of storing related data items of
different data types under one name


When a function is called with an array as an argument,


storing information about each employee of a company.
the array is automatically passed to the function by reference.
However, structures are always passed by value

a copy of the entire structure is passed.
Arrays and Structure: pass-by-reference
and pass-by-value

This requires the execution-time overhead


When structure data must be passed to a function,


making a copy of each data item in the structure and storing it on
the computer’s function call stack.
we can use non-constant pointers to constant data to get the
performance of pass-by-reference and the protection of pass-byvalue.
When a pointer to a structure is passed,


a copy of the address at which the structure is stored must be
made.
a copy of four bytes of memory is made rather than a copy of
possibly large structure.
When to use What?



If memory is low and execution efficiency is a
concern, use pointers.
If memory is in abundance and efficiency is not a
major concern, pass data by value to enforce the
principle of least privilege.
Remember that some systems do not enforce
const well, so pass-by-value is still the best way to
prevent data from being modified.
Using the const Qualifier with Pointers (Cont.)


The const qualifier enables you to inform the
compiler that the value of a particular variable
should not be modified.
Four ways to pass a pointer to a function




Non-constant pointer to non-constant data
Non-constant pointer to constant data
Constant pointer to non-constant data
Constant pointer to constant data
Constant Pointer to Non-Constant Data

A constant pointer to non-constant data always points to
the same memory location, and





the data at that location can be modified through the pointer.
This is the default for an array name.
An array name is a constant pointer to the beginning of the
array.
All data in the array can be accessed and changed by using
the array name and array subscripting.
A constant pointer to non-constant data can be used to
receive an array as an argument to a function that accesses
array elements using only array subscript notation.
Compilation Error: Constant Pointer to NonConstant Data
Compilation Error: Constant Pointer to NonConstant Data (Cont.)

Pointers that are declared const must be initialized when
they’re defined



Pointer ptr is defined to be of type int * const ptr.
The definition is read from right to left as “ptr is a
constant pointer to an integer.”


if the pointer is a function parameter, it’s initialized with a pointer
that’s passed to the function.
The pointer is initialized with the address of integer variable x.
The program attempts to assign the address of y to ptr

compiler generates an error message.
Constant Pointer to Constant Data



The least access privilege is granted by a constant
pointer to constant data.
Such a pointer always points to the same memory
location, and the data at that memory location
cannot be modified.
This is how an array should be passed to a function
that only looks at the array using array subscript
notation and does not modify the array.
Example: Constant Pointer to Constant Data
Constant Pointer to Constant Data (Cont.)

A pointer variable ptr to be of type const int
*const


read from right to left as “ptr is a constant pointer to an
integer constant.”
The error messages generated when


an attempt is made to modify the data to which ptr points
an attempt is made to modify the address stored in the pointer
variable.
sizeof Operator



A unary operator to determine the size in bytes of an
array (or any other data type) .
When applied to the name of an array the sizeof
operator returns the total number of bytes in the array.
Variables of type float are stored in 4 bytes of
memory, and if array is defined to have 20 elements.

Then there are a total of 80 bytes in array.
Example sizeof Operator
Example sizeof Operator
Pointer Expressions and Pointer Arithmetic

Arithmetic operations that may be performed on
pointers





Increment, ++
Decrement, -Integer addition, + or +=
Integer subtraction, - or -=
Subtraction of one pointer from another

Meaningful only when both pointers point to elements of the
same array.
Pointer Expressions and Pointer Arithmetic


Assume that array int v[5] has been defined and
its first element is at location 3000 in memory.
Assume pointer vPtr has been initialized to point
to v[0]


i.e., the value of vPtr is 3000.
Variable vPtr can be initialized to point to array v
with either of the statements
Pointer Expressions and Pointer Arithmetic

In conventional arithmetic, 3000+2 yields the value 3002.


An integer is added to or subtracted from a pointer, the pointer is
not incremented or decremented simply by that integer


This is normally not the case with pointer arithmetic.
But by that integer times the size of the object to which the pointer refers.
The number of bytes depends on the object’s data type.

For example, the statement
produce 3008 (3000 + 2 * 4)
assuming an integer is stored in 4 bytes of memory.
In the array v, vPtr would now point to v[2].
When performing pointer arithmetic on a character array,




vPtr += 2;would
the results will be consistent with regular arithmetic, because each
character is 1 byte long.
Pointer Expressions and Pointer Arithmetic

If vPtr had been incremented to 3016, which points to
v[4], the statement



vPtr -= 4;would set vPtr back to 3000
the beginning of the array.
If a pointer is being incremented or decremented by one,
the increment (++) and decrement (--) operators can be
used.

Either of the statements

++vPtr;
vPtr++;
increments the pointer to point to the next location in the
array.
Pointer Expressions and Pointer Arithmetic

For example, if vPtr contains the location 3000,
and v2Ptr contains the address 3008, the
statement



x = v2Ptr - vPtr; would assign to x the number
of array elements from vPtr to v2Ptr, in this case 2
(not 8).
Pointer arithmetic is undefined unless performed on
an array.
We cannot assume that two variables of the same
type are stored contiguously in memory unless
they’re adjacent elements of an array.
Void Pointer


A pointer can be assigned to another pointer if both
have the same type.
The exception to this rule is the pointer to void (i.e.,
void *),




a generic pointer that can represent any pointer type.
All pointer types can be assigned a pointer to void,
and a pointer to void can be assigned a pointer of
any type.
In both cases, a cast operation is not required.
A pointer to void cannot be dereferenced.
Void Pointer

Consider this: The compiler knows that a pointer to
int refers to 4 bytes of memory,




a pointer to void simply contains a memory location for
an unknown data type
the precise number of bytes to which the pointer refers is
not known by the compiler.
The compiler must know the data type to determine
the number of bytes to be dereferenced for a particular
pointer.
Dereferencing a void * pointer is a syntax error.
Pointer Expressions and Pointer Arithmetic

Pointers can be compared using equality and
relational operators,



Pointer comparisons compare the addresses stored in
the pointers.
A comparison of two pointers pointing to elements
in the same array could show,


the pointers point to elements of the same array.
one pointer points to a higher-numbered element of the
array than the other pointer does.
A common use of pointer comparison is determining
whether a pointer is NULL.
Relationship: Pointers and Arrays





Arrays and pointers are intimately related in C and often
may be used interchangeably.
An array name can be thought of as a constant pointer.
Pointers can be used to do any operation involving array
subscripting.
Assume that integer array b[5] and integer pointer
variable bPtr have been defined.
Because the array name (without a subscript) is a pointer
to the first element of the array,

we can set bPtr equal to the address of the first element in array
b with the statement bPtr = b
Relationship: Pointers and Arrays

This statement is equivalent to taking the address of the array’s
first element as follows:



Array element b[3] can alternatively be referenced with the
pointer expression



*( bPtr + 3 )
The 3 in the expression is the offset to the
pointer.
If a pointer points to the array’s first element,



bPtr = &b[ 0 ]
equivalent to bPtr = b
the offset indicates which array element should be referenced
the offset value is identical to the array subscript.
This notation is referred to as pointer/offset notation.
Relationship: Pointers and Arrays

For example, the expression

*( b + 3 ) also refers to the array element b[3].

Subscripted array expressions can be written with a
pointer and an offset.

Pointer/offset notation was used with the name of the
array as a pointer.

This does not modify the array name in any way

b still points to the first element in the array.
Relationship: Pointers and Arrays


Pointers can be subscripted like arrays.
If bPtr has the value b, the expression



An array name is essentially a constant pointer


bPtr[ 1 ] refers to the array element b[1].
This is referred to as pointer/subscript notation.
It always points to the beginning of the array.
The expression b += 3 is invalid

It attempts to modify the value of the array name with
pointer arithmetic.
Relationship: Pointers and Arrays

Four methods we’ve discussed for referring to array
elements to print the elements of the integer array b.




array subscripting; b[i]
pointer/offset with the array name as a pointer; * ( b + i )
pointer subscripting; bPtr [ i ]
pointer/offset with a pointer *( bPtr + i )
Arrays of Pointers



Arrays may contain pointers.
A common use of an array of pointers is to form an
array of strings, referred to simply as a string array.
Each entry in the array is a string



In C a string is essentially a pointer to its first character.
So each entry in an array of strings is actually a
pointer to the first character of a string.
Consider the definition of string array suit, which
might be useful in representing a deck of cards.

const char *suit[ 4 ] = { "Hearts",
"Diamonds", "Clubs", "Spades" };
Arrays of Pointers
Pointers to Functions




A pointer to a function contains the address of the
function in memory.
An array name is really the address in memory of the
first element of the array.
Similarly, a function name is really the starting address
in memory of the code that performs the function’s task.
Pointers to functions can be




passed to functions,
returned from functions,
stored in arrays and
assigned to other function pointers.
Pointers to Functions



Let’s see the use of pointers to functions using a
bubble sort program.
It consists of main and functions bubble, swap,
ascending and descending.
Function bubbleSort receives



a pointer to a function.
function ascending or function descending as an
argument.
an integer array and the size of the array.
Pointers to Functions


The program prompts the user to choose whether the
array should be sorted in ascending or in descending
order.
If the user enters 1, a pointer to function ascending is
passed to function bubble


causing the array to be sorted into increasing order.
If the user enters 2, a pointer to function descending
is passed to function bubble

causing the array to be sorted into decreasing order.
Pointers to Functions

The following parameter appears in the function header
for bubble


int (*compare)( int a, int b )
This tells bubble to expect a parameter (compare)
that’s a pointer to a function

receives two integer parameters and returns an integer result.
Pointers to Functions

Parentheses are needed around *compare to group
the * with compare to indicate that compare is a
pointer.

If we had not included the parentheses, the declaration
would have been

int *compare( int a, int b ) which declares
a function that receives two integers as parameters and
returns a pointer to an integer.
Pointers to Functions

The pointer to function parameter in the prototype could have
been written as


int (*)( int, int ) without the function-pointer name and
parameter names.
The function passed to bubble is called in an if statement
as follows:


if ((*compare)( work[count], work[count + 1]))
Just as a pointer to a variable is dereferenced to access the value of
the variable, a pointer to a function is dereferenced to use the
function.
Pointers to Functions

The call to the function could have been made without
dereferencing the pointer as in



if (compare(work[count], work[count + 1]))
which uses the pointer directly as the function name.
We prefer the first method of calling a function through a
pointer

It explicitly illustrates that compare is a pointer to a function that’s
dereferenced to call the function.

The second method of calling a function through a pointer
makes it appear as if compare is an actual function.

This may be confusing to a programmer reading the code who
would like to see the definition of function compare and finds
that it’s never defined in the file.
Exercise: Array of Pointers to Functions
Conclusions







Pointer Definitions, Initialization and Operators
Passing Arguments by Value and Reference
const qualifiers with Pointers
Pointer Expressions and Arithmetic
Pointers and Arrays Relationship
Array of Pointers
Pointers to Functions