CS1010E Lecture 6

Arrays

Henry Chia (hchia@comp.nus.edu.sg)

Semester 1 2014 / 2015

1 / 24
Lecture Outline

 1D array and 2D arrays:

– Declaration and initialization
– Array element access
– Array as function argument
 Problem solving with arrays

2 / 24
Primitive vs Array Declaration

declaration

type primitiveDeclaration ;

arrayDeclaration

,
primitiveDeclaration

identifier

= value

 Use primitive variables to work with individual data values

double x;

3 / 24
1D Array Declaration
arrayDeclaration

identifier [ integerVal ]

= initializer

 Use arrays to work with a set of data values of the same type
 Example:
double x[8]; x ? ? ? ? ? ? ? ?
 An array represents a sequential group of memory locations
 integerVal: size of the array
– pre-determined number of array elements
– must be as large as, or larger than, the maximum number
of values to be stored
4 / 24
1D Array Initialization

double x[8]={16.0,12.0,6.0,8.0,2.5,12.0,14.0,-54.5};
x 16.0 12.0 6.0 8.0 2.5 12.0 14.0 -54.5

 initializer: (initializer list)

– specifies the initial values
– used during declaration only
– may be shorter than the array size
⊲ double x[8]={16.0,0,0,0,0,0,0,0};
⊲ double x[8]={16.0};
The above are equivalent
 To zero the entire array: double x[8]={0.0};

5 / 24
Array Subscripts

 Subscripts distinguish between values within an array

 A subscripted variable (like any variable) is an expression

subscriptedVariable

identifier [ integerExpr ]

 Subscripts start with 0 and increment by 1

 Example:
x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7]
x 16.0 12.0 6.0 8.0 2.5 12.0 14.0 -54.5
– First value in array x is x[0]; last value is x[7].

6 / 24
Accessing Array Elements
 Array elements are accessed individually
 Example: fill array sq with squared values 02 , 12 , 22 , . . . , 102
#include <stdio.h>
#define SIZE 11
int main(void)
{
int i, sq[SIZE];
for (i = 0; i < SIZE; i++)
sq[i] = i * i;
for (i = 0; i < SIZE; i++)
printf("%d ", sq[i]);
printf("\n");
return 0;
}

 Looping condition must ensure a final loop with i as 10, and

not 11, since the array elements are sq[0] through sq[10]
7 / 24
Accessing Array Elements – Caution!

 It is a common mistake to specify a subscript that is outside

the bounds of the array:
– negative subscript
– positive subscript that is one value more than the largest
valid subscript
 An error occurs because it accesses values outside the array
– may produce runtime errors such as “segmentation fault”
or “bus error”
– may not produce runtime errors but causes unpredictable
program results, since program modified a memory
location outside of the array reserved for other variables

8 / 24
1D Array as Function Argument
 Passing an array to a function requires two parameters:
– the array (specifically, its location)
– the number of array elements to process

#include <stdio.h> /*
printArray prints first n
#define SIZE 11 elements of the array.
void printArray(int array[], Precondition: n >= 0
int n); */
int main(void) void printArray(int array[],
{ int n)
int i, sq[SIZE]; {
int i;
for (i=0; i<SIZE; i++)
sq[i] = i * i; for (i=0; i<n; i++)
printf("%d ", array[i]);
printArray(sq,SIZE); printf("\n");
return 0; return;
} }

9 / 24
1D Array as Function Argument

 array in printArray declared as function output parameter

 The array is shared between the two functions
 No need to specify size in array parameter
– any 1D array of the same type can be passed

main

sq 0 1 4 9 16 25 36 49 64 81 100
printArray
6
array

11 n
sq, 11
printArray(sq,11); -

10 / 24
Example: Cumulative Sum

 The cumulative sum of the sequence {a, b, c, . . . } is given by

{a, a + b, a + b + c, . . . }.
#include <stdio.h>
#define SIZE 100
void readData(int s[], int n);
void printArray(int s[], int n);
void cumulativeSum(int s[], int n);
int main(void)
{
int s[SIZE], n;
scanf("%d", &n);
readData(s,n);
cumulativeSum(s,n);
printArray(s,n);
return 0;
}

11 / 24
Example: Cumulative Sum

void readData(int s[], int n)

{
int i;
for (i = 0; i < n; i++)
scanf("%d", &(s[i]));
return;
}
void printArray(int s[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", s[i]);
printf("\n");
return;
}

12 / 24
Example: Cumulative Sum

void cumulativeSum(int s[], int n)

{
int i;
for (i = 1; i < n; i++)
s[i] = s[i] + s[i-1];
return;
}
 Note that i loops from 1 to n-1
 Another way to express the loop
for (i = 0; i < n-1; i++)
s[i+1] = s[i+1] + s[i];
 Ensure that array access stays within bounds

13 / 24
Declaring Arrays in main

 A function cannot return an array

– Array must be declared in the caller to be passed to the
function via its output parameter
 Typically, an array is declared in the main function so that it
can be passed to different functions to
– input data into array
– perform computation on the array
– output array values

14 / 24
2D Array Declaration

 Use 1D array when a set of data values is visualized as a list

 Use 2D array when a set of data values is visualized as a
table having both rows and columns
arrayDeclaration

identifier [ intVal ]

= initializer

 Example:
int t[4][3];
 Assuming row-major ordering, specify the number of rows
followed by the number of columns

15 / 24
2D Array Initialization
int t[4][3]={{ 2, 3,-1},
{ 0,-3, 5},
{ 2, 6, 3},
{-2,10, 4}};

 Initializer used only during declaration

 If the initializing sequence is shorter than the array, the rest
of the values are set to zero
 Zero entire array: int t[M][N]={{0}};
16 / 24
Multi-Dimensional Array Subscripts

subscriptedVariable

identifier [ integerExpr ]

 Each element in a 2D array is referenced using an identifier

followed by row and column subscripts
 Each subscript value has its own set of brackets
 Each subscript value begins with 0
 In the preceding declaration,
– value in position t[1][2] is 5
– value in position t[2][1] is 6

17 / 24
Accessing 2D Array Elements
 Use nested for loops to access all elements
 Example: multiplication table
#include <stdio.h>
#define NROWS 21
#define NCOLS 11
int main(void)
{
int i, j, mulTable[NROWS][NCOLS];
for (i = 0; i < NROWS; i++)
for (j = 0; j < NCOLS; j++)
mulTable[i][j] = i*j;
for (i = 1; i < NROWS; i++)
{
for (j = 1; j < NCOLS; j++)
printf("%4d", mulTable[i][j]);
printf("\n");
}
return 0;
}
18 / 24
2D Array as Function Argument
 When using 2D array as function argument, pass the array
together with the number of rows and columns to process

#include <stdio.h> /*
#define NROWS 21 print2D prints r x c
#define NCOLS 11 table of elements, t
Precondition: r>=0, 0<= c<NCOLS
void print2D(int t[][NCOLS], */
int r, int c); void print2D(int t[][NCOLS],
int main(void) int r, int c)
{ {
int i, j;
int i, j, t[NROWS][NCOLS];
for (i = 1; i < r; i++)
for (i = 0; i < NROWS; i++) {
for (j = 0; j < NCOLS; j++) for (j = 1; j < c; j++)
t[i][j] = i*j; printf("%4d", t[i][j]);
print2D(t,NROWS,NCOLS); printf("\n");
return 0; }
} return;
}

 Note column size in function parameter int t[][NCOLS]

19 / 24
Example: 2D Cumulative Sum

 The cumulative sum of an element tx,y is the sum of all

values above and to the left of it, including itself
X
sx,y = tx,y
i≤x,j≤y

 Example:
   
1 2 3 1 3 6
T =  4 5 6  ⇒ S =  5 12 21 
7 8 9 12 27 45

 One-pass strategy: sx,y = tx,y + sx−1,y + sx,y−1 − sx−1,y−1

20 / 24
Example: 2D Cumulative Sum

#include <stdio.h>
#define SIZE 100
void readData(int t[][SIZE], int r, int c);
void print2D(int t[][SIZE], int r, int c);
void cumulativeSum(int t[][SIZE], int r, int c);
int main(void)
{
int t[SIZE][SIZE]={{0}}, r, c;
scanf("%d%d", &r, &c);
readData(t,r,c);
cumulativeSum(t,r,c);
print2D(t,r,c);
return 0;
}

21 / 24
Example: 2D Cumulative Sum
void readData(int t[][SIZE], int r, int c)
{
int i, j;
for (i = 1; i <= r; i++) /* start from row 1 */
for (j = 1; j <= c; j++) /* start from col 1 */
scanf("%d", &(t[i][j]));
return;
}
void print2D(int t[][SIZE], int r, int c)
{
int i, j;
for (i = 1; i <= r; i++) /* start from row 1 */
{
for (j = 1; j <= c; j++) /* start from col 1 */
printf("%4d", t[i][j]);
printf("\n");
}
return;
}

22 / 24
Example: 2D Cumulative Sum

void cumulativeSum(int t[][SIZE], int r, int c)

{
int i, j;
for (i = 1; i <= r; i++) /* start from row 1 */
for (j = 1; j <= c; j++) /* start from col 1 */
t[i][j] = t[i][j] +
t[i-1][j] +
t[i][j-1] -
t[i-1][j-1];
return;
}

23 / 24
Lecture Summary

 1D arrays
– Declaration/initialization with pre-determined size
– Subscripting to assess individual elements
– Loops to access array elements
– Arrays as function arguments
 2D arrays are simple extensions of 1D arrays

24 / 24