CS 206 – C9 – Arrays and Pointers
9.1One-Dimensional Arrays
. Array – a deriveddata type used to represent a large number of homogeneous items in contiguous memory, i.e., an ExCel spreadsheet row or column.
. Array declaration allocates memory starting from a base address. Therefore the
array name is effectively a pointer constant to the beginning of the array, or its
base address.
. Elements of an array are accessed via the array name and an integer valued,
positivesubscript (or index).
. Example:
intgrade[3];
where grade[3] specifies a one dimensional array named grade with 3
elements for small class, or grade[250000] for a large class…
Indexing (subscripting) to access an array element starts at 0 in C, so index values for grade[3] are grade[0], grade[1] and grade[2].
Example:
Array Storage Example…
Array Initialization…
floatx[7] = {1.0,2.0,3.0,3.0,2.0,0.,0.5};
. For a short initializalion list, such as
int q[3] = {0,1};
the remaining elements are set to 0.
. extern and static arrays, if not initialized, are set to 0.
. auto arrays, if not initialized, contain garbage.
. An array declared without a size but with initialization values, i.e.,
int q[] = {3,5};
will be stored as the size of the number of initial values, i.e., int q[2], in this
case.
Array Subscripting…
float a[size];
Subscript i in a[i] must be between 0 and size-1. Otherwise, array bounds will be exceeded. Results are always system dependent and often catastrophic…
9.2Example – Counting Each Letter…
Dissection Notes:
. Note indices running from 0 – 25…
. Note library function getchar().
. Note macro isupper(c) from <ctype.h>.
. Note ++letter[c – ‘A’]; System Dependent – ASCII vs EBCDIC.
On ASCII computers, [c-‘A’] = 0 if c contains an ‘A’. Not so for EBCDIC
computers.
9.3 Relationship Between Arrays and Pointers
Definitions:
Array name – a fixed (actually relocatable…) address in memory assigned to the array by the compiler/linker. Can be thought of as a constant pointer.
Pointer – a variable that takes machine addresses as its value.
Example (array name vs pointer):
int a[100], *p;
p = a;and p = &a[0];are equivalent statements.
Example (pointer arithmetic):
p = a + 1;and p = &a[1]; are equivalent statements.
Examples Using Pointers to Sum an Array:
sum = 0;
for (p = a, p &a[100)]; ++p)
sum += *p;
or
sum = 0;
for (i = 0; i < 100; ++i)
sum += *(a + i);
Note that the expression *(a + i) is equivalent to a[i].
Or
p = a;
sum = 0;
for (i = 0; i < 100; ++i)
sum += p[i];
Note that the expression *(p + i) is equivalent to p[i].
Personal choice on which of the above to use in which situation…
Note that p can change but a cannot… Therefore
a = p;++a;a += 2;are all illegal, since array addresses are fixed.
9.4 Pointer Arithmetic and Array Element Size
Pointer Arithmetic - If p is a pointer to a particular data type array element, then
p + 1 points to the next element in the array. (See example code below)
Pointer Expressions ARE NOT Arithmetic Expressions!
Fact: Difference between two pointer variables is the number of data elements
between the pointers, and NOT the difference between the pointer variable
contents,the machine addresses contained in the pointer variables.
Example:
9.5Passing Arrays to Functions
The array name, representing the pointer to the array’s base address, is passed as an argument in the calling sequence to a function. The actual array is not moved from the calling module, so any modifications made to an array element in a function actually change the array data.
Example:
…
q = sum(v, 100)
…
int sum(int a[], int num)/* Note equivalence: int a[] same as *a */
{
int i, s=0;
for (i=0; i<num; ++i)
s += a[i];
return s;
}
9.6The Bubble Sort
Sort Applications…
Given inta[] = {7, 3, 66, 3, -5, 22, -77, 2}
What are the results of the statement bubble (a,8); ?
9.7Two Dimensional Arrays
Array Dimension Examples:
inta[100];1 D array
doublex[2][3];2 D array
longar[5][10][5];3 D array
Storage reserved for a: 100 ints1 ExCel row (or column)
x: 2 x 3 = 6 DPs1 spreadsheet
ar: 5 x 10 x 5 = 250 long intsmultiple spreadsheets
The logical structure for x is:
x[0][0] x[0][1] x[0][2]
x[1][0] x[1][1] x[1][2]
whereas the storage sequence for x is rowwise, or, by rows:
x[0][0] x[0][1] x[0][2] x[1][0] x[1][1] x[1][2].
Linear storage element number for x[i][j]:
x{(row number -1) * (column dimension) + (column number + 1)}, or,
x[1][1] = x{(2-1) * 3 + (1 + 1)} => x{5}.
Example:
Accessing Elements of a 2 D Array
IMHO, Poor Programming Practice…
Storage Mapping Function – Mapping between Pointers and Array Indices
For int a[3][5];
a[i][j] is equivalent to *(&a[0][0] + 5*i + j)
Multidimensional Arrays as Parameters to Functions
All dimensions (except the first) must be exactly specified so that the compiler can properly determine the address of a[i][j]…
Example;
Initialization of 2D Arrays (Note that indexing is by rows…)
9.8Multidimensional Arrays
int a[7][9][2];
Storage mapping function:
a[i][j][k] is equivalent to *(&a[0][0][0] + 9*2*i+ 2*j +k)
Summing Function Example:
9.9Dynamic Memory Allocation
Memory Allocation -malloc (memory_size)
Contiguous Memory Allocation – calloc (n, memory_size)
(Function prototypes in stdlib.h.)
calloc (n,size) returns pointer (type void *) to enough contiguous memory to store ‘n’ objects of size ‘size.’ Pointer value NULL is returned if the operating system cannot allocate memory.
p=calloc(n,sizeof(int));p=malloc(n*sizeof(int)); are equivalent except that
calloc storage initialized to zero; malloc storage not initialized.
Example:
Note the free(a); statement…
Created on 3/22/2006 10:40 AMC:\cs dept\2006 cs 206 spring\c9\c9 notes.docPage 1 of 11