1-d Arrays

1
Array
◼ Many applications require multiple data
items that have common characteristics
 Inmathematics, 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
Printing in Reverse Using Arrays

void 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]);
for (i = n -1; i >= 0; --i)
printf(“%d ”, A[i]);
printf(“\n”);
}
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
6
A first example
“data refers to a block of 10
void main()
integer variables, data[0], data[1],
{
…, data[9]
int i;
int data[10];
for (i=0; i<10; i++) data[i]= i;
i=0;
while (i<10)
{
printf("Data[%d] = %d\n", i, data[i]);
i++;
}
}

7
 The result
Array size should be a constant

void main()
Output
{
int i; Data[0] = 0
int data[10]; Data[1] = 1
for (i=0; i<10; i++) data[i]= i; Data[2] = 2
i=0; Data[3] = 3
while (i<10)
Data[4] = 4
{
Data[5] = 5
printf("Data[%d] = %d\n", i, data[i]);
i++; Data[6] = 6
} Data[7] = 7
} Data[8] = 8
Data[9] = 9
8
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 element 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
9
integers
◼ 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,
we can define an array of a large size
int marks[50];
though in a particular run we may only be using,
say, 10 elements
10
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
◼ In C, the index of an array starts from zero
◼ 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.
11
Contd.
◼ The array index must evaluate 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,…)

12
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

◼ x: starting address of the array in memory

◼ k: number of bytes allocated per array element

➔ is allocated memory location at

 a[i]
address x + i*k
13
Storage Output
&Data[0] = 3221224480
&Data[1] = 3221224484

void main() &Data[2] = 3221224488

{ &Data[3] = 3221224492
int i; &Data[4] = 3221224496
int data[10];
&Data[5] = 3221224500
for(i=0; i<10; i++)
printf("&Data[%d] = %u\n", i, &data[i]); &Data[6] = 3221224504
} &Data[7] = 3221224508
&Data[8] = 3221224512
&Data[9] = 3221224516

14
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. 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’};

15
How to read the elements of an
array?
◼ By reading them one element at a time
for (j=0; j<25; j++)
scanf (“%f”, &a[j]);
◼ The ampersand (&) is necessary
◼ The elements can be entered all in one line or in
different lines

16
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 17
Reading into an array
void main()
{
const int MAX_SIZE = 100; Output
int i, size;
4
float marks[MAX_SIZE];
float total; 2.5
scanf("%d",&size); 3.5
for (i=0, total=0; i<size; i++)
4.5
{
scanf("%f",&marks[i]); 5
total = total + marks[i]; Total = 15.500000
} Avg = 3.875000
printf("Total = %f \n Avg = %f\n", total,
total/size);
18
}
How to print the elements of an
array?
◼ By printing them one element at a time
for (j=0; j<25; j++)
printf (“\n %f”, a[j]);
 The elements are printed one per line
printf (“\n”);
for (j=0; j<25; j++)
printf (“ %f”, a[j]);
 The elements are printed all in one line
(starting with a new line) 19
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
20
Example 1: Find the minimum of a
set of 10 numbers
void main()
{
int a[10], i, min;

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

scanf (“%d”, &a[i]);

min = a[0];
for (i=1; i<10; i++)
{
if (a[i] < min)
min = a[i];
}
printf (“\n Minimum is %d”, min);
}
21
Alternate Version 1
const int size = 10;

void 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);
}
22
Alternate Version 2
#define size 10

void 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);
}
23
#define macro
◼ #define X Y
◼ Preprocessor directive
◼ Compiler will first replace all occurrences of
string X with string Y in the program, then
compile the program
◼ Similar effect as read-only variables (const), but
no storage allocated
◼ We prefer you use const instead of #define

24
Alternate Version 3
void 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);
}

25
 const int nsub = 6;
Example 2:
void main()
Computing {
int grade_pt[nsub], cred[nsub], i,
cgpa gp_sum=0, cred_sum=0;
double gpa;

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

Handling two arrays scanf (“%d %d”, &grade_pt[i], &cred[i]);
at the same time
for (i=0; i<nsub; i++)
{
gp_sum += grade_pt[i] * cred[i];
cred_sum += cred[i];
}
gpa = ((float) gp_sum) / cred_sum;
printf (“\n Grade point average: is %.2lf”, gpa);
}
26
Example: Binary Search
◼ Searching for an element k in a sorted array A with n
elements
◼ Idea:
 Choose the middle element A[n/2]
 If k == A[n/2], we are done
 If k < A[n/2], search for k between A[0] and A[n/2 -1]
 If k > A[n/2], search for k between A[n/2 + 1] and
A[n-1]
 Repeat until either k is found, or no more elements
to search
◼ Requires less number of comparisons than linear
search in the worst case (log2n instead of n)
27
void main() {
int A[100], n, k, i, mid, low, high;
scanf(“%d %d”, &n, &k);
for (i=0; i<n; ++i) scanf(“%d”, &A[i]);
low = 0; high = n – 1; mid = low + (high – low)/2;
while (high >= low) {
printf(“low = %d, high = %d, mid = %d, A[%d] = %d\n”,
low, high, mid, mid, A[mid]);
if (A[mid] == k) {
printf(“%d is found\n”, k);
break;
}
if (k < A[mid]) high = mid – 1;
else low = mid + 1;
mid = low + (high – low)/2;
}
If (high < low) printf(“%d is not found\n”, k);
} 28
 Output
8 21
9 11 14 17 19 20 23 27
low = 0, high = 7, mid = 3, A[3] = 17
low = 4, high = 7, mid = 5, A[5] = 20
low = 6, high = 7, mid = 6, A[6] = 23
21 is not found

8 14
9 11 14 17 19 20 23 27
low = 0, high = 7, mid = 3, A[3] = 17
low = 0, high = 2, mid = 1, A[1] = 11
low = 2, high = 2, mid = 2, A[2] = 14
14 is found
29
Example: Selection Sort
◼ Sort the elements of an array A with n
elements in ascending order
◼ Basic Idea:
 Find the min of the n elements, swap it with
A[0] (so min is at A[0] now)
 Now find the min of the remaining n-1
elements, swap it with A[1] (so 2nd min is at
A[1] now)
 Continue until no more elements left

30
void main() {
int A[100], n, i, j, k, min, pos, temp;
scanf(“%d”, &n);
for (i=0; i<n; ++i) scanf(“%d”, &A[i]);
for (i = 0; i < n - 1; ++i) {
min = A[i]; pos = i;
for (j = i + 1; j < n; ++j) {
if (A[j] < min) {
min = A[j];
pos = j;
}
}
temp = A[i];
A[i] = A[pos];
A[pos] = temp;
for (k=0; k<n; ++k) printf(“%d ”, A[k]);
printf(“\n”);
}
31
}
 Output
6
7 12 5 15 17 9
5 12 7 15 17 9
5 7 12 15 17 9 8
5 7 9 15 17 12 98765432
5 7 9 12 17 15 2 8 7 6 5 4 3 9
5 7 9 12 15 17 2 3 7 6 5 4 8 9
2 3 4 6 5 7 8 9
2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9
2 3 4 5 6 7 8 9
32
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);

33
Character Arrays and Strings
char C[8] = { 'a', 'b', 'h', 'i', 'j', 'i', 't', '\0' };
◼ C[0] gets the value 'a', C[1] the value 'b', and so on.
The last (7th) location receives the null character ‘\0’
◼ Null-terminated (last character is ‘\0’) character arrays
are also called strings
◼ Strings can be initialized in an alternative way. The
last declaration is equivalent to:
char C[8] = "abhijit";
◼ The trailing null character is missing here. C
automatically puts it at the end if you define it like this
◼ Note also that for individual characters, C uses single
quotes, whereas for strings, it uses double quotes
34
Reading strings: %s format
void main()
{
char name[25];
scanf("%s", name);
printf("Name = %s \n", name);
}

%s reads a string into a character array

given the array name or start address.
It ends the string with ‘\0’

35
An example
void main()
{
#define SIZE 25 Seen on screen
int i, count=0;
char name[SIZE]; Typed as input
scanf("%s", name); Satyanarayana
printf("Name = %s \n", name);
Name = Satyanarayana
for (i=0; name[i]!='\0'; i++)
if (name[i] == 'a') count++; Total a's = 6
printf("Total a's = %d\n", count);
}
Printed by program
Note that character strings read
in %s format end with ‘\0’

36
Palindrome Checking
void main()
{
const int SIZE = 25;
int i, flag, count=0;
char name[SIZE];
scanf("%s", name); /* Read Name */
for (i=0; name[i]!='\0'; i++); /* Find Length of String */
printf("Total length = %d\n",i);
count=i; flag = 0;
/* Loop below checks for palindrome by comparison*/
for(i=0; i<count; i++) if (name[i]!=name[count-i-1]) flag = 1;
if (flag ==0) printf ("%s is a Palindrome\n", name);
else printf("%s is NOT a Palindrome\n", name);
} 37
Some Exercises
1. Write a C program that reads an integer n and stores the
first n Fibonacci numbers in an array.
2. Write a C program that reads an integer n and uses an
array to efficiently find out the first n prime numbers.
3. Read in an integer n, read in n integers and print the integer
with the highest frequency.
4. Read in an integer n, read in n numbers and find out the
mean, median and mode.
5. Read in two names and compare them and print them in
lexicographic (dictionary) order.
6. Read in an integer n, read in n names and print the last
name when compared in lexicographic order.

38
2-d Arrays

39
Two Dimensional Arrays
◼ We have seen that an array variable can store
a list of values
◼ Many applications require us to store a table
of values

Subject 1 Subject 2 Subject 3 Subject 4 Subject 5

Student 1 75 82 90 65 76
Student 2 68 75 80 70 72
Student 3
88 74 85 76 80
Student 4
50 65 68 40 70
40
Contd.
◼ The table contains a total of 20 values, five
in each line
 The table can be regarded as a matrix
consisting of four rows and five columns
◼ C allows us to define such tables of items
by using two-dimensional arrays

41
Declaring 2-D Arrays
◼ General form:
type array_name [row_size][column_size];
◼ Examples:
int marks[4][5];
float sales[12][25];
double matrix[100][100];

42
Initializing 2-d arrays
◼ int a[2][3] = {1,2,3,4,5,6};
◼ int a[2][3] = {{1,2,3}, {4,5,6}};
◼ int a[][3] = {{1,2,3}, {4,5,6}};

All of the above will give the 2x3 array

1 2 3
4 5 6

43
Accessing Elements of a 2-d
Array
◼ Similar to that for 1-d array, but use two indices
 First indicates row, second indicates column
 Both the indices should be expressions which
evaluate to integer values (within range of the
sizes mentioned in the array declaration)
◼ Examples:
x[m][n] = 0;
c[i][k] += a[i][j] * b[j][k];
a = sqrt (a[j*3][k]);

44
Example
int a[3][5];

A two-dimensional array of 15 elements

Can be looked upon as a table of 3 rows and 5 columns

col0 col1 col2 col3 col4

row0 a[0][0] a[0][1] a[0][2] a[0][3] a[0][4]
row1 a[1][0] a[1][1] a[1][2] a[1][3] a[1][4]
row2 a[2][0] a[2][1] a[2][2] a[2][3] a[2][4]

45
How is a 2-d array is stored in
memory?
◼ Starting from a given memory location, the elements
are stored row-wise in consecutive memory locations
(row-major order)
◼ x: starting address of the array in memory
◼ c: number of columns
◼ k: number of bytes allocated per array element
 a[i][j] ➔ is allocated memory location at
address x + (i * c + j) * k
a[0]0] a[0][1] a[0]2] a[0][3] a[1][0] a[1][1] a[1][2] a[1][3] a[2][0] a[2][1] a[2][2] a[2][3]

Row 0 Row 1 Row 2

46
Array Addresses Output

3221224480
int main() 3221224484
{ 3221224488
int a[3][5]; 3221224492
3221224496
int i,j;
3221224500
for (i=0; i<3;i++) 3221224504
3221224508
{ 3221224512
for (j=0; j<5; j++) printf("%u\n", &a[i][j]); 3221224516
printf("\n");
3221224520
} 3221224524
return 0; 3221224528
} 3221224532
3221224536
47
 More on Array Addresses
int main()
{
int a[3][5];
printf("a = %u\n", a);
printf("&a[0][0] = %u\n", &a[0][0]); Output
printf("&a[2][3] = %u\n", &a[2][3]); a = 3221224480
printf("a[2]+3 = %u\n", a[2]+3); &a[0][0] = 3221224480
&a[2][3] = 3221224532
printf("*(a+2)+3 = %u\n", *(a+2)+3); a[2]+3 = 3221224532
printf("*(a+2) = %u\n", *(a+2)); *(a+2)+3 = 3221224532
printf("a[2] = %u\n", a[2]); *(a+2) = 3221224520
a[2] = 3221224520
printf("&a[2][0] = %u\n", &a[2][0]); &a[2][0] = 3221224520
printf("(a+2) = %u\n", (a+2)); (a+2) = 3221224520
printf("&a[2] = %u\n", &a[2]); &a[2] = 3221224520
return 0;
48
}
How to read the elements of a
2-d array?
◼ By reading them one element at a time
for (i=0; i<nrow; i++)
for (j=0; j<ncol; j++)
scanf (“%f”, &a[i][j]);
◼ The ampersand (&) is necessary
◼ The elements can be entered all in one
line or in different lines

49
How to print the elements of a
2-d array?
◼ By printing them one element at a time
for (i=0; i<nrow; i++)
for (j=0; j<ncol; j++)
printf (“\n %f”, a[i][j]);
 The elements are printed one per line

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

for (j=0; j<ncol; j++)
printf (“%f”, a[i][j]);
 The elements are all printed on the same line50
Contd.
for (i=0; i<nrow; i++)
{
printf (“\n”);
for (j=0; j<ncol; j++)
printf (“%f ”, a[i][j]);
}
 The elements are printed nicely in matrix form

51
Example: Matrix Addition
int main()
{ for (p=0; p<m; p++)
int a[100][100], b[100][100], for (q=0; q<n; q++)
c[100][100], p, q, m, n; c[p][q] = a[p][q] + b[p][q];

scanf (“%d %d”, &m, &n); for (p=0; p<m; p++)

{
for (p=0; p<m; p++) printf (“\n”);
for (q=0; q<n; q++) for (q=0; q<n; q++)
scanf (“%d”, &a[p][q]);
printf (“%d ”, c[p][q]);
for (p=0; p<m; p++) }
for (q=0; q<n; q++) return 0;
scanf (“%d”, &b[p][q]); }
52
Passing 2-d Arrays as Parameters
◼ Similar to that for 1-D arrays
 The array contents are not copied into the function
 Rather, the address of the first element is passed
◼ For calculating the address of an element in a 2-d
array, we need:
 The starting address of the array in memory
 Number of bytes per element
 Number of columns in the array
◼ The above three pieces of information must be known
to the function
53
Example Usage
void add (int x[][25], int
y[][25], int rows, int cols)
int main() {
{ :
int a[15][25], b[15]25]; }
:
:
add (a, b, 15, 25);
:
} We can also write
int x[15][25], y[15][25];
But at least 2nd dimension
must be given
54
Dynamic Allocation of 2-d Arrays
◼ Recall that address of [i][j]-th element is found
by first finding the address of first element of i-
th row, then adding j to it
◼ Now think of a 2-d array of dimension [M][N]
as M 1-d arrays, each with N elements, such
that the starting address of the M arrays are
contiguous (so the starting address of k-th row
can be found by adding 1 to the starting
address of (k-1)-th row)
◼ This is done by allocating an array p of M
pointers, the pointer p[k] to store the starting
address of the k-th row 55
Contd.
◼ Now, allocate the M arrays, each of N
elements, with p[k] holding the pointer for
the k-th row array
◼ Now p can be subscripted and used as a
2-d array
◼ Address of p[i][j] = *(p+i) + j (note that
*(p+i) is a pointer itself, and p is a pointer
to a pointer)

56
 Dynamic Allocation of 2-d Arrays
int **allocate (int h, int w)
{ void read_data (int **p, int h, int w)
int **p; Allocate array {
int i, j; of pointers int i, j;
for (i=0;i<h;i++)
p = (int **) malloc(h*sizeof (int *) ); for (j=0;j<w;j++)
for (i=0;i<h;i++) scanf ("%d", &p[i][j]);
p[i] = (int *) malloc(w * sizeof (int)); }
return(p);
} Allocate array of Elements accessed
integers for each like 2-D array elements.
row

57
 Contd.
void print_data (int **p, int h, int w) int main()
{ {
int i, j; int **p;
for (i=0;i<h;i++) int M, N;
{ printf ("Give M and N \n");
for (j=0;j<w;j++) scanf ("%d%d", &M, &N);
printf ("%5d ", p[i][j]); p = allocate (M, N);
printf ("\n"); read_data (p, M, N);
} printf ("\nThe array read as \n");
} print_data (p, M, N);
return 0;
}

58
 Contd.
void print_data (int **p, int h, int w) int main()
{ {
int i, j; int **p;
for (i=0;i<h;i++) int M, N;
{ printf ("Give M and N \n");
for (j=0;j<w;j++) scanf ("%d%d", &M, &N);
printf ("%5d ", p[i][j]); p = allocate (M, N);
printf ("\n"); read_data (p, M, N);
Give M and N
} 33 printf ("\nThe array read as \n");
} 123 print_data (p, M, N);
456 return 0;
789
}
The array read as
1 2 3
4 5 6
7 8 9
59
 Memory Layout in Dynamic Allocation
int **allocate (int h, int w)
int main() {
{ int **p;
int **p; int i, j;
int M, N;
printf ("Give M and N \n"); p = (int **)malloc(h*sizeof (int *));
scanf ("%d%d", &M, &N); for (i=0; i<h; i++)
p = allocate (M, N); printf(“%10d”, &p[i]);
for (i=0;i<M;i++) { printf(“\n\n”);
for (j=0;j<N;j++) for (i=0;i<h;i++)
printf ("%10d", &p[i][j]); p[i] = (int *)malloc(w*sizeof(int));
printf(“\n”); return(p);
} }
return 0;
}
60
Output
Starting address of each
row, contiguous (pointers
33 are 8 bytes long)
31535120 31535128 31535136

31535152 31535156 31535160

Elements in each row
31535184 31535188 31535192 are contiguous

31535216 31535220 31535224

61