Transcript Arrays and Matrices

Arrays and Matrices
1
One-Dimensional Arrays

Suppose, you need to store years of 100 cars. Will you
define 100 variables:
int y1, y2,…, y100;

An array is an indexed data structure to represent several
variables having the same data type:
int y[100];
y[0]
y[1]
y[2]
…
y[k-1]
y[k]
y[k+1]
…
y[98] y[99]
2
One-Dimensional Arrays



An element of an array is accessed using the array name
and an index or subscript, e.g., y[5]
In C, the subscripts always start with 0 and increment by 1,
so y[5] is the sixth element
The name of the array is the address of the first element and
the subscript is the offset
y[0]
y[1]
y[2]
…
y[k-1]
y[k]
y[k+1]
…
y[98] y[99]
3
Definition and Initialization

An array is defined using a declaration
statement.
data_type array_name[size];




allocates memory for size elements
subscript of first element is 0
subscript of last element is size-1
size must be a constant
4
Example
int list[5];





allocates memory for 5 integer variables
subscript of first element is 0
subscript of last element is 4
C does not check bounds on arrays
list[6] =5; /* will give segmentation fault later */
list[0]
list[1]
list[2]
list[3]
list[4]
5
Initializing Arrays


Arrays can be initialized at the time they
are declared.
Examples:
double taxrate[3] ={0.15, 0.25, 0.3};
char list[5] = {‘h’, ’e’, ’l’, ’l’, ’o’};
double vector[100] = {0.0};
/* assigns
zero to all 100 elements */
int s[] = {5,0,-5}; /*the size of s is 3*/
6
Assigning values to an array
for loops are often used to assign values to an array
Example:
int list[5], i;
for(i=0; i<5; i++)
{
list[i] = i;
}
0
1
2
3
4
list[0]
list[1]
list[2]
list[3]
list[4]
7
Assigning values to an array
Give a for loop to assign the below values to list
4
3
2
1
0
list[0]
list[1]
list[2]
list[3]
int list[5], i;
for(i=0; i<5; i++)
{
list[i] = 4-i;
}
list[4]
8
Input from a data file
Arrays are often used to store information from a data file
int k;
double time[10], motion[10];
FILE *sensor3;
sensor3 = fopen(“sensor3.dat”, “r”);
for(k=0; k<10; k++) {
fscanf(sensor3, “%lf %lf”,
&time[k], &motion[k]);
}
9
Exercise
Show the contents of the arrays defined in
each of the following sets of statements.
int x[10] = {-5, 4, 3};
char letters[] = {'a', 'b', 'c'};
double z[4];
10
Exercise



int data[100], i;
Store random numbers [0,99] in data
for (i=0; i<100; i++)
data[i] = rand() % 100;
Store random numbers [10,109] in data
for (i=0; i<100; i++)
data[i] = (rand() % 100) + 10;
OR
for (i=0; i<100; i++)
data[i] = rand_int(10,109);
11
Computations on arrays
12
Maximum in an array
0
1
2
3
4
5
6
3
1
9
7
2
6
9
max
13
Find Maximum

Find maximum value in data
int data[100], max, i;
for (i=0; i<100; i++)
data[i] = rand() % 100;
max = data[0];
for (i=0; i<100; i++){
if (data[i] > max)
max = data[i];
}
printf("Max = %d\n",max);
14
Find average

Find average of values in data
int data[100], sum, i, avg;
for (i=0; i<100; i++)
data[i] = rand() % 100;
sum = 0;
for (i=0; i<100; i++){
sum = sum + data[i];
}
avg = (double)sum/100;
printf(“Avg = %lf\n", avg);
15
Number of elements greater than average

After finding the average as shown in previous slide
count = 0;
for (i=0; i<100; i++){
if (data[i] > avg)
count++;
}
printf(“%d elements are greater than avg”,
count);
16
Reverse an array
Set array B to the reverse of array A
0
1
2
3
4
5
A
6
3
1
9
7
2
B
2
7
9
1
3
6
0
1
2
3
4
5
17
Reverse an Array
int A[100], B[100];
...
int bindex = 0, aindex = 99;
while (bindex < 100)
{
B[bindex] = A[aindex]
bindex = bindex + 1;
aindex = aindex -1’
}
18
Find pair sum

Find sum of every pair in data and write into pair array
data[0]=5
data[1]=7
data[2]=15
data[3]=5
…
…
data[98]=3
data[99]=12
}
}
pair[0]=12
pair[1]=20
.
.
.
}
…
pair[49]=15
19
Solution
int data[100], pair[50], i;
for (i=0; i<100; i++)
data[i] = rand() % 100;
for (i=0; i<50; i++){
pair[i]= data[2*i]+ data[2*i+1];
}
20
Function Arguments

Individual elements of an array can be passed as regular arguments.
void donothing(int a, int b)
{
…
}
int main(void)
{
/* Declare variables and functions */
int array[5] = {1,2,3,4,5};
}
donothing(array[2], array[4]);
.
.
21
Passing Arrays to Functions

Arrays are always pass by reference
Modifications to the array are reflected to main program
The array name is the address of the first element
The maximum size of the array must be specified at the
time the array is declared.
The actual number of array elements that are used will
vary, so the actual size of the array is usually passed as
another argument to the function




22
Exercise
int data[100]
Write a function to find maximum value in the array data
int maximum(int fdata[], int n)
{
int i, fmax;
fmax = fdata[0];
for (i=0; i<n; i++)
if (fdata[i] > fmax)
fmax = fdata[i];
return(fmax);
}
int main()
{
int data[100],i, max;
for (i=0; i<100; i++)
data[i] = rand() % 100;
max = maximum(data,100);
printf("Max = %d\n",max);
return(0);
}
23
Exercise
What is the output of the following program?
void print(int pdata[], int n)
{
int i;
for (i=0; i<n; i++)
printf("data[%d]=%d\n",i,pdata[i]);
return;
}
void modify(int fdata[], int n)
{
int i;
for (i=0; i<n; i++)
fdata[i] = 1;
return;
Lectute4e3.c
}
int main()
{
int data[10];
for (i=0; i<10; i++)
data[i] = rand() % 100;
print(data,10);
modify(data,10);
print(data,10);
return(0);
}
24
Exercise
fdata and data use the same copy of the array
void modify(int fdata[], int n)
{
…
}
int main()
{
int data[10];
…
modify(data,10);
…
}
25
Sorting an array
0
1
2
3
4
5
6
3
1
9
7
2
1
3
6
9
7
2
1
2
6
9
7
3
1
2
3
9
7
6
1
2
3
6
7
9
1
2
3
6
7
9
26
Selection Sort
void selection_sort(double x[], int n)
{
int min_pos, i;
}
for(i=0; i<n-1; i++)
{
min_pos = find_min_pos(x, n, i);
swap(x, i, min_pos);
}
lecture4e4.c
27
Selection Sort
int find_min_pos(double fx[], int fn, int fi)
{
int i;
int index=fi;
for (i=fi; i<fn; i++)
if (fx[i] <fx[index])
index = i;
return(index);
}
28
Selection Sort
void swap(double sx[], int si, int smin_pos)
{
double temp;
temp = sx[si];
sx[si] = sx[smin_pos];
sx[smin_pos] = temp;
return;
}
29
Reverse an array
0
1
2
3
4
5
6
3
1
9
7
2
2
7
9
1
3
6
30
Reverse an Array
void reverse(double x[], int n)
{
int i=0, j=n-1;
while (i<j)
{
swap(x,i,j);
i = i + 1;
j = j - 1;
}
return;
}
31
Matrices
A matrix is a set of numbers arranged in a grid with rows and columns.
A matrix is defined using a type declaration statement.

datatype array_name[row_size][column_size];

int matrix[3][4];

4
1
0
2
Row 0
-1
2
4
3
Row 1
0
-1 3
1
Row 2
Column 0
Column 1
in memory
Row 0 Row 1 Row 2
Column 3
Column 2
32
Accessing Array Elements

int matrix[3][4];





matrix has 12 integer elements
matrix[0][0] element in first row, first column
matrix[2][3] element in last row, last column
matrix is the address of the first element
matrix[1] is the address of the second row
33
Initialization

int matrix[3][4];
for (i=0; i<3; i++)
for (j=0; j<4; j++)
matrix[i][j] = 1;
j
0
i
0
4
1
1
2
0
3
2
1
-1
2
4
3
2
0
-1 3
1
for (i=0; i<12; i++)
maxrix[i/4][i %4] = 1;
34
2-Dim Arrays as Arguments to Functions

Print the array int matrix[3][4]
void print(int pmatrix[3][4])
{
int i,j;
for (i=0; i<3; i++)
{
for (j=0; j<4; j++)
printf("%.5d ",pmatrix[i][j]);
printf("\n");
}
printf("\n");
return;
}
35
2-Dim Arrays as Arguments to Functions
void transpose(int b[NROWS][NCOLS], int bt[NCOLS][NROWS])
{
/* Declare Variables. */
int i, j;
}
/* Transfer values to the transpose matrix. */
for(i=0; i<NROWS; i++)
{
for(j=0; j<NCOLS; j++)
{
bt[j][i] = b[i][j];
}
}
return;
36
Exercise

Find the maximum of int matrix[3][4]
int max = matrix[0][0];
for (i=0; i<3; i++)
for (j=0; j<4; j++)
if (matrix[i][j] > max)
max = matrix[i][j];
0
0
0
1
1
2
0
3
2
1
-1
2
4
3
2
0
-1 3
1
37
Exercise

Find the number of times x appears in int matrix[3][4]
int count = 0;
for (i=0; i<3; i++)
for (j=0; j<4; j++)
if (matrix[i][j] == x)
count = count + 1;
0
0
0
1
1
2
0
3
2
1
-1
2
4
3
2
0
-1 3
1
38
Exercise

Compute the addition of two matrices
0
1
2
3
0
0
1
0
2
1
-1
2
4
3
2
0
-1 3
1
+
0
1
2
3
0
3
-1 3
1
1
1
4
2
0
2
2
1
1
3
0
=
0
3
1
0
2
3
3
3
1
0
6
6
3
2
2
0
4
4
39
Exercise

Compute the addition of two matrices
int matrix1[3][4], matrix2[3][4], sum[3][4];
// initialize matrix1 and matrix2
for (i=0; i<3; i++)
for (j=0; j<4; j++)
sum[i][j] = matrix1[i][j]+matrix2[i][j];
40
Exercise

Insert random numbers into an array so that each
number appears in the array at most once.
6
3
1
9
6
2
A
for (i=0; i<6; i++)
A[i] = rand() % 10;
Produces
Duplicates
41
Exercise

Insert random numbers into an array so that each
number appears in the array at most once.
void initialize(int idata[], int n)
{
int i=0, j, elem;
}
while (i<=n)
{
elem = rand() % 10;
if (find_count(idata,i,elem) == 0)
{
idata[i] = elem;
i = i + 1;
}
}
6
3
1
9
6
2
A
Try a new
number
42
Exercise
Counts how many times x appears in first n elements of array cdata
int find_count(int cdata[], int n, int x)
{
int count = 0;
int i;
6
3
1
9
7
2
0
1
2
3
4
5
for (i = 0; i<n; i++)
if (cdata[i] == x)
count = count + 1;
}
find_count(A,6,2) returns 1
find_count(A,4,2) returns 0
return (count);
43
Exercise


6
3
Arrays A and B represents sets.
Find the intersection of A and B
1
9
7
2
4
2
A
5
6
1
8
B
6
1
2
Intersection
44
Exercise
int intersection(int ndata1[], int ndata2[], int n, int result[])
{
int i=0, j=0 , elem;
6
3
1
}
while (i<=n)
{
elem = ndata1[i];
if (find_count(ndata2,n,elem) == 1)
{
result[j] = elem;
j = j + 1;
}
i = i + 1;
}
return(j);
4
2
5
6
1
2
9
7
2
6
1
8
45
Exercise: Pairwise Swap
0
1
2
3
4
5
6
3
1
9
7
2
3
6
9
1
2
7
0
1
2
3
4
5
46
Exercise: Second Largest in an array
0
1
2
3
4
5
6
3
1
9
7
2
6
-1
9
7
3
6
-1
max
max2
47