Transcript Arrays

Programming
Arrays
Question

Write a program that reads 3 numbers
from the user and print them in ascending
order.

How many variables do we need to store the
input?
How could we cope with 100 numbers? 1000?


We need a “variable” that can store a series of
values
Arrays

Sequence of variables of a single type
int a[10];

Defines an array of integers of size 10

a block of 10 consecutive ints named
a[0], a[1], ... , a[9]
a[0]
a[1]
a[2]
a[3]
a[4]
a[5]
a[6]
a[7]
a[8]
a[9]
Array Definition
type name[size];
 size
must be a constant expression
char sentence[100];
 int grades[30 + 15];
 double numebrs[30];

Reverse
The following example is of a program that
reads 10 numbers from the user and prints
them in reverse order.
 If the input is:
1 2 3 4 5 6 7 8 9 10
the output will be:
10 9 8 7 6 5 4 3 2 1

Example - Reverse
An array of 10
integers,
called numbers.
int main(void)
{
intisi,
numbers[10];
The first output
is the
one
stored in numbers[9], the
printf(“Please
enter 10 numbers:\n");
second
in numbers[8]
and so
A single
variable
on. int, called
for (i = 0; i < 10;
++i)
We can
use a single
of type
stored in
scanf("%d",
&numbers[i]);
variable to go over both
i. The last output is
numbers[0]
loops
printf("numbers in reversed order:\n");
The --i)
first input is stored in
for (i = 9; i >= 0;
the second in
printf("%d\n", numbers[0],
numbers[i]);
return 0;
}
numbers[1] and so on.
The last input is stored in
numbers[9]
Questions
What is that 10 in your program?
 Do all the 10s mean the same thing?
 How many changes you have to make if
you need to go from 10 to 20?


In large programs finding all those places
may be extremely difficult
Compilation Revisited
source
code
Preprocessor
source
code*
Compiler
object
file
stdio
math
Textual modifications
ctype
Linker
• #include adds function declaration
executable
#define

Define a symbolic name
#define ARRAY_SIZE 10

During preprocessing phase, symbolic
names are replaced by the replacement
text
Reverse with #define
#define ARRAY_SIZE 10
int main(void)
{
int i;
int numbers[ARRAY_SIZE];
printf(“Please enter %d numbers:\n", ARRAY_SIZE);
for (i = 0; i < ARRAY_SIZE; ++i)
scanf("%d",&numbers[i]);
printf("numbers in reversed order:\n");
for (i = ARRAY_SIZE - 1; i >= 0; --i)
printf("%d\n",numbers[i]);
return 0;
}
After Preprocessing
This is what the compiler “see”
int main(void)
{
int i;
int numbers[10];
All ARRAY_SIZE were
replaced by 10
printf(“Please enter %d numbers:\n", 10);
for (i = 0; i < 10; ++i)
scanf("%d",&numbers[i]);
printf("numbers in reversed order:\n");
for (i = 10 - 1; i >= 0; --i)
printf("%d\n", numbers[i]);
return 0;
}
From 10 to 20
#define ARRAY_SIZE 20
int main(void)
{
int i;
int numbers[ARRAY_SIZE];
printf(“Please enter %d numbers:\n", ARRAY_SIZE);
for (i = 0; i < ARRAY_SIZE; ++i)
scanf("%d",&numbers[i]);
printf("numbers in reversed order:\n");
for (i = ARRAY_SIZE - 1; i >= 0; --i)
printf("%d\n",numbers[i]);
return 0;
}
Limitation

Define expansion does not occur within a
quoted string
printf("Please enter ARRAY_SIZE numbers:\n");
Please enter ARRAY_SIZE numbers:
printf("Please enter %d numbers:\n", ARRAY_SIZE);
Please enter 10 numbers:
From now on

Variable and function names

lowercase letters only
–

size, array, power, num1, is_digit
Defines

All caps
–
ARRAY_SIZE, TRUE, FALSE
Array Initialization

We can initialize the array during declaration.
int array[8] = {2, 4, 6, 8, 10, 12, 14, 16};

The number of initializers cannot be more
than the number of elements in the array
 but it can be less
 in which case, the remaining
elements are initialized to 0
Array Initialization

The array size can be inferred from the
number of initializers by leaving the
square brackets empty

These are identical declarations :
int array1[8] = {2, 4, 6, 8, 10, 12, 14, 16};
 int array2[] = {2, 4, 6, 8, 10, 12, 14, 16};

Exercise

Write a program that gets an input line
from the user (until ‘\n’) and displays the
number of times each lowercase letter
appears in it.
input line:
The
The
The
The
The
The
The
letter
letter
letter
letter
letter
letter
letter
hello, world!
'd'
'e'
'h'
'l'
'o'
'r'
'w'
appears
appears
appears
appears
appears
appears
appears
1
1
1
3
2
1
1
time(s).
time(s).
time(s).
time(s).
time(s).
time(s).
time(s).
Solution
#define ABC_LEN 26
int main(void)
{
int i = 0,
count[ABC_LEN] = {0};
int c;
printf("Please enter a line of text: \n");
c = getchar();
while (c != '\n') {
if (c <= 'z' && c >= 'a')
++count[c - 'a'];
c = getchar();
}
printf("The letter distribution in your line :\n");
for (i = 0; i < ABC_LEN; ++i) {
if (count[i] > 0)
printf("The letter '%c' appears %d time(s).\n", 'a' + i, count[i]);
}
return 0;
}
Arrays as Function Arguments

Calculate the sum of an array’s elements
int calc_sum(int arr[], int size)
{
int i = 0, sum = 0;
for (i = 0; i < size; ++i)
sum += arr[i];
return sum;
}
Arrays as Function Arguments
int calc_sum(int arr[], int size);

The function takes an array of integers.

The size of the array is unknown
 another argument specifies the size
int calc_sum(int arr[10], int size);

Counterintuitive, this doesn’t change anything

The size of the array is still unknown and another
argument is needed.
Arrays as Function Arguments

For example:
int calc_sum(int arr[], int size);
Within the function, arr is accessed in
the usual way
 Changes to elements of the array from
within the function are seen outside.


The original array is changed!!
Arrays as Function Arguments

Using calc_sum
int main(void)
{
int input[ARRAY_SIZE], sum = 0;
...
sum = calc_sum(input, ARRAY_SIZE);
...
}
Sorting

We would like to sort the elements in an
array in an ascending order.
7 2 8 5 4
sort
2 4 5 7 8
Bubble Sort
7 2 8 5 4
2 7 5 4 8
2 5 4 7 8
2 4 5 7 8
2 7 8 5 4
2 7 5 4 8
2 5 4 7 8
2 4 5 7 8
2 7 8 5 4
2 5 7 4 8
2 4 5 7 8
2 7 5 8 4
2 5 4 7 8
2 7 5 4 8
(done)
Bubble Sort
void bubble_sort(int a[], int size)
{
int i, j, temp;
for (i = size - 1; i >= 0; --i) /* counting down
*/
{
for (j = 0; j < i; ++j)
/* bubbling up
*/
{
if (a[j] > a[j+1])
/* if out of order... */
{
/* ... then swap */
temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;
}
}
}
}
Using sort
#define ARRAY_SIZE 5
void bubble_sort(int a[], int size);
int main()
{
int array[ARRAY_SIZE] = {7, 2, 8, 5, 4};
int i = 0;
bubble_sort(array, ARRAY_SIZE);
/* print the sorted array */
for (i = 0; i < ARRAY_SIZE; ++i)
printf("%d ", array[i]);
return 0;
}
Exercise

Implement the function:
int compare_arrays(int arr1[],
int arr2[],
int size);


The function takes two integer arrays and
returns true if they are equal, false otherwise
Write a program that accepts two arrays of
integers from the user and checks for equality
using the above function
Solution
int compare_arrays(int arr1[], int arr2[], int size)
{
int i = 0;
for (i = 0; i < size; ++i)
{
if (arr1[i] != arr2[i])
return 0;
}
/* if we got here, the arrays are identical */
return 1;
}
Two-dimensional Arrays
4 x 11

Declaration:
columns
int matrix[4][11];
rows
Element Access

In order to access the j-th element
(column) of the i-th array (row)
column
matrix[i][j]
row
Initializing Two-dimensional Arrays
int arr[2][3] = { {1, 2, 3}, {4, 5, 6} };
1
2
3
4
5
6
As with regular array size can be inferred
from the initialization
 Unlike regular array, this is only true for
the number of rows.

int arr[][3] = { {1, 2, 3}, {4, 5, 6} };
Example: Matrix Addition
#define MATRIX_SIZE 3
int main(void)
{
int a[][MATRIX_SIZE] = {{1,2,3}, {4,5,6}, {7,8,9}};
int b[][MATRIX_SIZE] = {{1,1,1}, {2,2,2}, {3,3,3}};
int c[MATRIX_SIZE][MATRIX_SIZE_SIZE];
int i = 0, j = 0;
for (i = 0; i < MATRIX_SIZE; ++i)
for (j = 0; j < MATRIX_SIZE; ++j)
c[i][j] = a[i][j] + b[i][j];
/* print c */
...
return 0;
}
Exercise



Write a program that defines 3 matrices a,b and
c of size 3x3 with int elements; initialize the first
two matrices (a and b).
Compute the matrix multiplication of a and b and
store it in c (i.e. c = a*b)
Print all the matrices on the screen
c[i ][ j ] 
SIZE 1

k 0
a[i ][k ]  b[ k ][ j ]
Solution
#define MATRIX_SIZE 3
int main(void)
{
int a[][MATRIX_SIZE] = { {1,2,3}, {4,5,6}, {7,8,9}};
int b[][MATRIX_SIZE] = { {1,0,0}, {0,2,0}, {0,0,3}};
int c[MATRIX_SIZE][MATRIX_SIZE];
int i = 0, j = 0, k = 0;
/* Compute the product c = a * b */
for (i = 0; i < MATRIX_SIZE; ++i)
for (j = 0; j < MATRIX_SIZE; ++j)
{
c[i][j] = 0;
for (k = 0; k < MATRIX_SIZE; ++k)
c[i][j] += a[i][k] * b[k][j];
}
/* Print c */
...
return 0;
}