One-Dimensional Arrays

Random access lists of elements

CS10003 PROGRAMMING AND DATA STRUCTURES

1
INDIAN INSTITUTE OF TECHNOLOGY KHARAGPUR
Array
Many applications require multiple data items that have common characteristics
• In mathematics, we often express such groups of data items in indexed
form:
• x1, x2, x3, …, xn

Array is a data structure which can represent a collection of data items which
have the same data type (float/int/char/…)

2
 Example: Printing Numbers in Reverse

4 numbers
3 numbers int a, b, c, d;
int a, b, c; scanf(“%d”, &a);
scanf(“%d”, &a); scanf(“%d”, &b);
scanf(“%d”, &b); scanf(“%d”, &c);
scanf(“%d”, &c); scanf(“%d”, &d);
printf(“%d ”, c); printf(“%d ”, d);
printf(“%d ”, b); printf(“%d ”, c);
printf(“%d \n”, a); printf(“%d ”, b);
printf(“%d \n”, a);

3
 The Problem
Suppose we have 10 numbers to handle
Or 20
Or 100
Where do we store the numbers ? Use 100 variables ?
How to tackle this problem?
Solution:
• Use arrays

4
 Using Arrays
All the data items constituting the group share the same name
int x[10];
Individual elements are accessed by specifying the index

x[0] x[1] x[2] x[9]

X is a 10-element one
dimensional array

5
 Declaring Arrays
Like variables, the arrays used in a program must be declared before they are used
General syntax:
type array-name [size];
• type specifies the type of elements that will be contained in the array (int,
float, char, etc.)
• size is an integer constant which indicates the maximum number of
elements that can be stored inside the array
int marks[5];
• marks is an array that can store a maximum of 5 integers

6
Array Declarations: examples
Examples:
int x[10];
char line[80];
float points[150];
char name[35];

If we are not sure of the exact size of the array that we will need, we
can define an array of a large enough size
int marks[50];
though in a particular run we may only be using, say, 10 elements

7
 Accessing Array Elements
A particular element of the array can be accessed by specifying two things:
• Name of the array
• Index (relative position) of the element in the array
Important to remember: In C, the index of an array starts from 0, not 1
Example:
• An array is defined as int x[10];
• The first element of the array x can be accessed as x[0], fourth element as
x[3], tenth element as x[9], etc.

8
 A First Example Array size should be a constant

int main() “data” is a block of 10 integer variables:

{ data[0], data[1], …, data[9]
int i;
int data[10];
for (i=0; i<10; i++) Data[0] = 0
data[i]= i; Data[1] = 1
i=0;
Data[2] = 2
while (i<10)
Data[3] = 3
{
printf("Data[%d] = %d\n", i, data[i]); Data[4] = 4
i++; Data[5] = 5
} Data[6] = 6
return 0; Output
Data[7] = 7
}
Data[8] = 8

9
Data[9] = 9
How is an array stored in memory?

Starting from a given memory location, the successive array elements are allocated
space in consecutive memory locations

Array A
• Let x: starting address of the array in memory
• k: number of bytes allocated per array element (e.g., 4 for each int, 1 for
each char)

• The array element A[i] is allocated memory location at address x + i*k

10
 A Special Operator: AddressOf (&)
Remember that each variable is stored at a memory location with a unique address
Putting & before a variable name gives the starting address of the variable in the
memory (where it is stored, not the value)
Can be put before any variable (with no blank in between)
int a =10;
printf(“Value of a is %d, and address of a is %d\n”, a, &a);

Similarly, if we have an array Data,

Memory address of the first array element is &Data[0]
Memory address of the second array element is &Data[1]
Memory address of the third array element is &Data[2]

11
 Example Output
&Data[0] = 3221224480
int main()
&Data[1] = 3221224484
{
int i; &Data[2] = 3221224488
int data[10]; &Data[3] = 3221224492
for(i=0; i<10; i++)
&Data[4] = 3221224496
printf("&Data[%d] = %u\n", i, &data[i]);
return 0; &Data[5] = 3221224500
} &Data[6] = 3221224504
&Data[7] = 3221224508
Note: memory addresses are being printed
&Data[8] = 3221224512
as unsigned integers using %u in printf
&Data[9] = 3221224516

12
How to read the elements of an array?
By reading them one element at a time

Suppose we have declared an array: float a[25];

for (j=0; j<25; j++)
scanf (“%f”, &a[j]);

Note the ampersand (&) in scanf

The elements can be entered all in one line or in different lines

13
 Reading into an array: example Input a list of marks from the user
int main() { and compute their total and average
const int MAX_SIZE = 100;
int i, size;
float marks[MAX_SIZE]; Output
float total; 4
scanf("%d", &size);
2.5
for (i=0, total=0; i<size; i++)
{ 3.5
scanf("%f", &marks[i]); 4.5
total = total + marks[i]; 5
}
Total = 15.500000
printf("Total = %f \n Avg = %f\n", total,
total/size); Avg = 3.875000
return 0;
}
14
Printing in Reverse Using Arrays
int main()
{
int n, A[100], i;
printf(“How many numbers to read? “);
scanf(“%d”, &n);
for (i = 0; i < n; ++i)
scanf(“%d”, &A[i]); // input the i-th array element
for (i = n -1; i >= 0; --i) // note – loop counts downward
printf(“%d ”, A[i]); // output the i-th array element
printf(“\n”);
return 0;
}
Indexes into Arrays
The array index can be any expression that evaluates to an integer between 0 and n-
1 where n is the maximum number of elements possible in the array
a[x+2] = 25;
b[3*x-y] = a[10-x] + 5;
Remember that each array element is a variable in itself, and can be used anywhere a
variable can be used (in expressions, assignments, conditions,…)

16
 Initialization of Arrays
General form:
type array_name[size] = { list of values };
Examples:
int marks[5] = {72, 83, 65, 80, 76};
char name[4] = {‘A’, ‘m’, ‘i’, ‘t’};

The size may be omitted if all initializers are specified. In such cases the compiler automatically
allocates enough space for all initialized elements
int flag[ ] = {1, 1, 1, 0};
char name[ ] = {‘A’, ‘m’, ‘i’, ‘t’};

17
A Warning
In C, while accessing array elements, array bounds are not checked
Example:
int marks[5];
:
:
marks[8] = 75;
• The above assignment would not necessarily cause an error
• Rather, it may result in unpredictable program results, which are very hard to debug

18
How to copy the elements of one array to another?

By copying individual elements

for (j=0; j<25; j++)
a[j] = b[j];

The element assignments will follow the rules of assignment

expressions
Destination array must have sufficient size

19
Things you cannot do
You cannot
• use = to assign one array variable to another
a = b; /* a and b are arrays */
• use == to directly compare array variables
if (a = = b) ………..
• directly scanf or printf arrays
printf (“……”, a);

20
Example: Find the minimum of a set of 10 numbers
int main()
{
int a[10], i, min;

for (i=0; i<10; i++)

scanf (“%d”, &a[i]);
Change only one
min = a[0]; line to change the
for (i=1; i<10; i++) problem size
{
if (a[i] < min)
min = a[i];
}
printf (“\n Minimum is %d”, min);
return 0;
}

21
 Alternate Version 1
const int size = 10;

int main()
{
int a[size], i, min;

Change only one for (i=0; i<size; i++)

line to change the scanf (“%d”, &a[i]);
problem size
min = a[0];
for (i=1; i<size; i++)
{
if (a[i] < min)
min = a[i];
}
printf (“\n Minimum is %d”, min);
return 0;
}
22
 Alternate Version 2
#define size 10

int main()
{
int a[size], i, min;

Change only one for (i=0; i<size; i++)

line to change the scanf (“%d”, &a[i]);
problem size
min = a[0];
for (i=1; i<size; i++)
{
Used #define macro if (a[i] < min)
min = a[i];
}
printf (“\n Minimum is %d”, min);
return 0;
}
23
 Alternate Version 3
int main()
{
int a[100], i, min, n;

scanf (“%d”, &n); /* Number of elements */

for (i=0; i<n; i++)
Define an array of
scanf (“%d”, &a[i]);
large size and use
only the required
min = a[0];
number of elements
for (i=1; i<n; i++)
{
if (a[i] < min)
min = a[i];
}
printf (“\n Minimum is %d”, min);
return 0;
}
24
Example: const int nsub = 6;
Computing Grade int main()
Point Average {
int grade_pt[nsub], cred[nsub], i, gp_sum=0,
cred_sum=0;
double gpa;
Handling two arrays
at the same time for (i=0; i<nsub; i++)
scanf (“%d %d”, &grade_pt[i], &cred[i]);

for (i=0; i<nsub; i++)

cred[j] stores credit of {
subject j gp_sum += grade_pt[i] * cred[i];
cred_sum += cred[i];
grade_pt[j] stores grade }
point obtained by a student gpa = ((float) gp_sum) / cred_sum;
in subject j printf (“\n Grade point average: is %f”, gpa);
return 0;
}
25
More Examples

26
Reversing an Array: Find the mistake, reason for it and correct it
Correctly Reversing A = { 1, 2, 0, 5, 3 } results is A = { 3, 5, 0, 2, 1 }
The program below is wrong.
#include<stdio.h>
main()
{
int A[20], n,k,temp;
scanf("%d", &n);
printf("n= %d \n", n);
for (k=0; k<n; k++) scanf("%d", &A[k]);
printf("numbers read are: ");
for (k=0; k<n; k++) printf("%d ", A[k]);
printf("\n");
for(k=0; k<n; k++){
temp = A[k];
A[k]=A[n-k-1];
A[n-k-1] = temp;
}
for (k=0; k<n; k++) printf("%d ", A[k]);
printf("\n");
}

27
Finding the largest contiguous sequence of equal numbers
#include<stdio.h>
main() {
int i, n, A[20], k = 0, maxbegin = 0, maxcount = 1, ssbegin, count;
scanf("%d\n", &n); for(i=0; i<n; i++) scanf("%d", &A[i]);
printf("A = "); for(i=0; i<n; i++) printf("%d, ", A[i]); printf("\n");
while(k < n) {
ssbegin = k; count = 1; 10
while(A[k] == A[k+1]) { 1222322227
k++; count++; A = 1, 2, 2, 2, 3, 2, 2, 2, 2, 7,
Sequence starting from A[5] = of Length = 4, Value = 2
if (k == n-1) break;
}
if (count > maxcount) { maxbegin = ssbegin; maxcount = count; }
k++;
}
printf("Sequence starting from A[%d] = of Length = %d, Value = %d \n", maxbegin, maxcount,
A[maxbegin]);
}

28
Practice Problems
1. Read in an integer n (n < 25). Read n integers in an array A. Then do the following (write separate
programs for each, only the reading part is common).
a) Find the sum of the absolute values of the integers.
b) Copy the positive and negative integers in the array into two additional arrays B and C respectively.
Print A, B, and C.
c) Exchange the values of every pair of values from the start (so exchange A[0] and A[1], A[2] and A[3]
and so on). If the number of elements is odd, the last value should stay the same.

2. Read in two integers n and m (n, m < 50). Read n integers in an array A. Read m integers in an array B.
Then do the following (write separate programs for each part, only the reading part is common).
a) Find if there are any two elements x, y in A and an element z in B, such that x + y = z
b) Copy in another array C all elements that are in both A and B (intersection)
c) Copy in another array C all elements that are in either A and B (union)
d) Copy in another array C all elements that are in A but not in B (difference)

29