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
