PattPatelCh16.ppt
Chapter 16
Pointers and Arrays
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-2
Pointers and Arrays
We’ve seen examples of both of these
in our LC-3 programs; now we’ll see them in C.
Pointer
• Address of a variable in memory
• Allows us to indirectly access variables
! in other words, we can talk about its address
rather than its value
Array
• A list of values arranged sequentially in memory
• Example: a list of telephone numbers
• Expression a[4] refers to the 5th element of the array a
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-3
Address vs. Value
Sometimes we want to deal with the address
of a memory location,
rather than the value it contains.
Recall example from Chapter 6:
adding a column of numbers.
• R2 contains address of first location.
• Read value, add to sum, and
increment R2 until all numbers
have been processed.
R2 is a pointer — it contains the
address of data we�re interested in.
x3107
x2819
x0110
x0310
x0100
x1110
x11B1
x0019
x3100
x3101
x3102
x3103
x3104
x3105
x3106
x3107
x3100 R2
address
value
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-4
Another Need for Addresses
Consider the following function that’s supposed to
swap the values of its arguments.
void Swap(int firstVal, int secondVal)
{
int tempVal = firstVal;
firstVal = secondVal;
secondVal = tempVal;
}
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-5
Executing the Swap Function
firstVal
secondVal
valueB
valueA
3
4
4
3
R6
before call
tempVal
firstVal
secondVal
valueB
valueA
3
4
3
4
3
R6
after call
These values
changed…
…but these
did not.
Swap needs addresses of variables outside its own
activation record.
Swap
main
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-6
Pointers in C
C lets us talk about and manipulate pointers
as variables and in expressions.
Declaration
int *p; /* p is a pointer to an int */
A pointer in C is always a pointer to a particular data type:
int*, double*, char*, etc.
Operators
*p — returns the value pointed to by p
&z — returns the address of variable z
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-7
Example
int i;
int *ptr;
i = 4;
ptr = &i;
*ptr = *ptr + 1;
store the value 4 into the memory location
associated with i
store the address of i into the
memory location associated with ptr
read the contents of memory
at the address stored in ptr
store the result into memory
at the address stored in ptr
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-8
Example: LC-3 Code
; i is 1st local (offset 0), ptr is 2nd (offset -1)
; i = 4;
AND R0, R0, #0 ; clear R0
ADD R0, R0, #4 ; put 4 in R0
STR R0, R5, #0 ; store in i
; ptr = &i;
ADD R0, R5, #0 ; R0 = R5 + 0 (addr of i)
STR R0, R5, #-1 ; store in ptr
; *ptr = *ptr + 1;
LDR R0, R5, #-1 ; R0 = ptr
LDR R1, R0, #0 ; load contents (*ptr)
ADD R1, R1, #1 ; add one
STR R1, R0, #0 ; store result where R0 points
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-9
Pointers as Arguments
Passing a pointer into a function allows the function
to read/change memory outside its activation record.
void NewSwap(int *firstVal, int *secondVal)
{
int tempVal = *firstVal;
*firstVal = *secondVal;
*secondVal = tempVal;
} Arguments are
integer pointers.
Caller passes addresses
of variables that it wants
function to change.
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-10
Passing Pointers to a Function
main() wants to swap the values of valueA and valueB
passes the addresses to NewSwap:
NewSwap(&valueA, &valueB);
Code for passing arguments:
ADD R0, R5, #-1 ; addr of valueB
ADD R6, R6, #-1 ; push
STR R0, R6, #0
ADD R0, R5, #0 ; addr of valueA
ADD R6, R6, #-1 ; push
STR R0, R6, #0
tempVal
firstVal
secondVal
valueB
valueA
xEFFA
xEFF9
4
3
xEFFD
R6
R5
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-11
Code Using Pointers
Inside the NewSwap routine
; int tempVal = *firstVal;
LDR R0, R5, #4 ; R0=xEFFA
LDR R1, R0, #0 ; R1=M[xEFFA]=3
STR R1, R5, #4 ; tempVal=3
; *firstVal = *secondVal;
LDR R1, R5, #5 ; R1=xEFF9
LDR R2, R1, #0 ; R1=M[xEFF9]=4
STR R2, R0, #0 ; M[xEFFA]=4
; *secondVal = tempVal;
LDR R2, R5, #0 ; R2=3
STR R2, R1, #0 ; M[xEFF9]=3
tempVal
firstVal
secondVal
valueB
valueA
3
xEFFA
xEFF9
3
4
xEFFD
R6
R5
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-12
Null Pointer
Sometimes we want a pointer that points to nothing.
In other words, we declare a pointer, but we�re not ready
to actually point to something yet.
int *p;
p = NULL; /* p is a null pointer */
NULL is a predefined macro that contains a value that
a non-null pointer should never hold.
• Often, NULL = 0, because Address 0 is not a legal address
for most programs on most platforms.
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-13
Using Arguments for Results
Pass address of variable where you want result stored
• useful for multiple results
Example:
return value via pointer
return status code as function result
This solves the mystery of why �&� with argument to
scanf:
scanf(“%d “, &dataIn);
read a decimal integer
and store in dataIn
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-14
Syntax for Pointer Operators
Declaring a pointer
type *var;
type* var;
Either of these work — whitespace doesn’t matter.
Type of variable is int* (integer pointer), char* (char pointer), etc.
Creating a pointer
&var
Must be applied to a memory object, such as a variable.
In other words, &3 is not allowed.
Dereferencing
Can be applied to any expression. All of these are legal:
*var contents of mem loc pointed to by var
**var contents of mem loc pointed to by
memory location pointed to by var
*3 contents of memory location 3
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-15
Example using Pointers
IntDivide performs both integer division and remainder,
returning results via pointers. (Returns –1 if divide by zero.)
int IntDivide(int x, int y, int *quoPtr, int *remPtr);
main()
{
int dividend, divisor; /* numbers for divide op */
int quotient, remainer; /* results */
int error;
/* …code for dividend, divisor input removed… */
error = IntDivide(dividend, divisor,
"ient, &remainder);
/* …remaining code removed… */
}
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-16
C Code for IntDivide
int IntDivide(int x, int y, int *quoPtr, int *remPtr)
{
if (y != 0) {
*quoPtr = x / y; /* quotient in *quoPtr */
*remPtr = x % y; /* remainder in *remPtr */
return 0;
}
else
return –1;
}
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-17
Arrays
How do we allocate a group of memory locations?
• character string
• table of numbers
How about this?
Not too bad, but…
• what if there are 100 numbers?
• how do we write a loop to process each number?
Fortunately, C gives us a better way — the array.
int num[4];
Declares a sequence of four integers, referenced by:
num[0], num[1], num[2], num[3].
int num0;
int num1;
int num2;
int num3;
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-18
Array Syntax
Declaration
type variable[num_elements];
Array Reference
variable[index];
all array elements
are of the same type
number of elements must be
known at compile-time
i-th element of array (starting with zero);
no limit checking at compile-time or run-time
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-19
Array as a Local Variable
Array elements are allocated
as part of the activation record.
int grid[10];
First element (grid[0])
is at lowest address
of allocated space.
If grid is first variable allocated,
then R5 will point to grid[9].
grid[0]
grid[1]
grid[2]
grid[3]
grid[4]
grid[5]
grid[6]
grid[7]
grid[8]
grid[9]
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-20
LC-3 Code for Array References
; x = grid[3] + 1
ADD R0, R5, #-9 ; R0 = &grid[0]
LDR R1, R0, #3 ; R1 = grid[3]
ADD R1, R1, #1 ; plus 1
STR R1, R5, #-10 ; x = R1
; grid[6] = 5;
AND R0, R0, #0
ADD R0, R0, #5 ; R0 = 5
ADD R1, R5, #-9 ; R1 = &grid[0]
STR R0, R1, #6 ; grid[6] = R0
x
grid[0]
grid[1]
grid[2]
grid[3]
grid[4]
grid[5]
grid[6]
grid[7]
grid[8]
grid[9]
R5
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-21
More LC-3 Code
; grid[x+1] = grid[x] + 2
LDR R0, R5, #-10 ; R0 = x
ADD R1, R5, #-9 ; R1 = &grid[0]
ADD R1, R0, R1 ; R1 = &grid[x]
LDR R2, R1, #0 ; R2 = grid[x]
ADD R2, R2, #2 ; add 2
LDR R0, R5, #-10 ; R0 = x
ADD R0, R0, #1 ; R0 = x+1
ADD R1, R5, #-9 ; R1 = &grid[0]
ADD R1, R0, R1 ; R1 = &grix[x+1]
STR R2, R1, #0 ; grid[x+1] = R2
x
grid[0]
grid[1]
grid[2]
grid[3]
grid[4]
grid[5]
grid[6]
grid[7]
grid[8]
grid[9]
R5
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-22
Passing Arrays as Arguments
C passes arrays by reference
• the address of the array (i.e., of the first element)
is written to the function’s activation record
• otherwise, would have to copy each element
main() {
int numbers[MAX_NUMS];
…
mean = Average(numbers);
…
}
int Average(int inputValues[MAX_NUMS]) {
…
for (index = 0; index < MAX_NUMS; index++)
sum = sum + indexValues[index];
return (sum / MAX_NUMS);
}
This must be a constant, e.g.,
#define MAX_NUMS 10
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-23
A String is an Array of Characters
Allocate space for a string just like any other array:
char outputString[16];
Space for string must contain room for terminating zero.
Special syntax for initializing a string:
char outputString[16] = "Result = ";
…which is the same as:
outputString[0] = 'R';
outputString[1] = 'e';
outputString[2] = 's';
...
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-24
I/O with Strings
Printf and scanf use "%s" format character for string
Printf -- print characters up to terminating zero
printf("%s", outputString);
Scanf -- read characters until whitespace,
store result in string, and terminate with zero
scanf("%s", inputString);
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-25
Relationship between Arrays and Pointers
An array name is essentially a pointer
to the first element in the array
char word[10];
char *cptr;
cptr = word; /* points to word[0] */
Difference:
Can change the contents of cptr, as in
cptr = cptr + 1;
(The identifier "word" is not a variable.)
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-26
Correspondence between Ptr and Array Notation
Given the declarations on the previous page,
each line below gives three equivalent expressions:
cptr word &word[0]
(cptr + n) word + n &word[n]
*cptr *word word[0]
*(cptr + n) *(word + n) word[n]
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-27
Common Pitfalls with Arrays in C
Overrun array limits
• There is no checking at run-time or compile-time
to see whether reference is within array bounds.
int array[10];
int i;
for (i = 0; i <= 10; i++) array[i] = 0;
Declaration with variable size
• Size of array must be known at compile time.
void SomeFunction(int num_elements) {
int temp[num_elements];
…
}
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
16-28
Pointer Arithmetic
Address calculations depend on size of elements
• In our LC-3 code, we've been assuming one word per element.
! e.g., to find 4th element, we add 4 to base address
• It's ok, because we've only shown code for int and char,
both of which take up one word.
• If double, we'd have to add 8 to find address of 4th element.
C does size calculations under the covers,
depending on size of item being pointed to:
double x[10];
double *y = x;
*(y + 3) = 13;
allocates 20 words (2 per element)
same as x[3] -- base address plus 6