## c notes arrays

Basic Concept
 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  Why are arrays essential for some applications?  Take an example.  Finding the minimum of a set of numbers.
2
Spring Semester 2007 Programming and Data Structure 3
if ((a <= b) && (a <= c)) min = a; else if (b <= c) min = b; else min = c;
if ((a <= b) && (a <= c) && (a <= d)) min = a; else if ((b <= c) && (b <= d)) min = b; else if (c <= d) min = c; else min = d;
3 numbers
4 numbers
Spring Semester 2007 Programming and Data Structure 4
The Problem
 Suppose we have 10 numbers to handle.  Or 20.  Or 100.
 How to tackle this problem?  Solution:  Use arrays.
3
Spring Semester 2007 Programming and Data Structure 5
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
Spring Semester 2007 Programming and Data Structure 6
Declaring Arrays
 Like variables, the arrays that are 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.  Example: int marks[5];  marks is an array containing a maximum of 5 integers.
4
Spring Semester 2007 Programming and Data Structure 7
 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.
Spring Semester 2007 Programming and Data Structure 8
How an array is stored in memory?
 Starting from a given memory location, the successive array elements are allocated space in consecutive memory locations.
x: starting address of the array in memory k: number of bytes allocated per array element  Element a[i] :: allocated memory location at address x + i*k  First array index assumed to start at zero.
Array a
x x+k x+2k
5
Spring Semester 2007 Programming and Data Structure 9
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.
Spring Semester 2007 Programming and Data Structure 10
Contd.
 The array index must evaluate to an integer between 0 and n-1 where n is the number of elements in the array. a[x+2] = 25; b[3*x-y] = a[10-x] + 5;
6
Spring Semester 2007 Programming and Data Structure 11
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.
Spring Semester 2007 Programming and Data Structure 12
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};  Some special cases:  If the number of values in the list is less than the number of elements, the remaining elements are automatically set to zero. float total[5] = {24.2, -12.5, 35.1};
total[0]=24.2, total[1]=-12.5, total[2]=35.1, total[3]=0, total[4]=0
7
Spring Semester 2007 Programming and Data Structure 13
Contd.
 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};
Spring Semester 2007 Programming and Data Structure 14
Example 1: Find the minimum of a set of 10 numbers
#include <stdio.h> main() { int a[10], i, min;
for (i=0; i<10; i++) scanf (%d, &a[i]);
min = 99999; for (i=0; i<10; i++) { if (a[i] < min) min = a[i]; } printf (\n Minimum is %d, min);
}
8
Spring Semester 2007 Programming and Data Structure 15
#include <stdio.h> #define size 10
main() { int a[size], i, min;
for (i=0; i<size; i++) scanf (%d, &a[i]);
min = 99999; for (i=0; i<size; i++) { if (a[i] < min) min = a[i]; } printf (\n Minimum is %d, min);
}
Alternate Version 1
Change only one line to change the problem size
Spring Semester 2007 Programming and Data Structure 16
#include <stdio.h>
main() { int a[100], i, min, n;
scanf (%d, &n); /* Number of elements */ for (i=0; i<n; i++) scanf (%d, &a[i]);
min = 99999; for (i=0; i<n; i++) { if (a[i] < min) min = a[i]; } printf (\n Minimum is %d, min);
}
Alternate Version 2
Define an array of large size and use only the required number of elements
9
Spring Semester 2007 Programming and Data Structure 17
Example 2: Computing gpa
#include <stdio.h> #define nsub 6
main() { int grade_pt[nsub], cred[nsub], i, gp_sum=0, cred_sum=0, gpa;
for (i=0; i<nsub; i++) scanf (%d %d, &grade_pt[i], &cred[i]);
for (i=0; i<nsub; i++) { gp_sum += grade_pt[i] * cred[i]; cred_sum += cred[i]; } gpa = gp_sum / cred_sum; printf (\n GPA is: %d, gpa);
}
Handling two arrays at the same time
Spring Semester 2007 Programming and Data Structure 18
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);
10
Spring Semester 2007 Programming and Data Structure 19
How to copy the elements of one array to another?
 By copying individual elements:
int a[25], b[25];  for (j=0; j<25; j++) a[j] = b[j];
Spring Semester 2007 Programming and Data Structure 20
How to read the elements of an array?
 By reading them one element at a time.
int a[25];  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.
11
Spring Semester 2007 Programming and Data Structure 21
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).
Spring Semester 2007 Programming and Data Structure 22
Character String
12
Spring Semester 2007 Programming and Data Structure 23
Introduction
 A string is an array of characters.  Individual characters are stored in memory in ASCII code.  A string is represented as a sequence of characters terminated by the null (\0) character.
\0leH olHello Ξ
Spring Semester 2007 Programming and Data Structure 24
Declaring String Variables
 A string is declared like any other array: char string-name [size];  size determines the number of characters in string_name.  When a character string is assigned to a character array, it automatically appends the null character (\0) at the end of the string.  size should be equal to the number of characters in the string plus one.
13
Spring Semester 2007 Programming and Data Structure 25
Examples
char name[30]; char city[15]; char dob[11];
 A string may be initialized at the time of declaration.
char city[15] = Calcutta; char city[15] = {C, a, l, c, u, t, t, a}; char dob[] = 12-10-1975;
Equivalent
Spring Semester 2007 Programming and Data Structure 26
 Two different cases will be considered:  Reading words  Reading an entire line
14
Spring Semester 2007 Programming and Data Structure 27
 scanf can be used with the %s format specification. char name[30]; : : scanf (%s, name);  The ampersand (&) is not required before the variable name with %s.  The problem here is that the string is taken to be upto the first white space (blank, tab, carriage return, etc.)  If we type Rupak Biswas  name will be assigned the string Rupak
Spring Semester 2007 Programming and Data Structure 28
 In many applications, we need to read in an entire line of text (including blank spaces).  We can use the getchar() function for the purpose.
15
Spring Semester 2007 Programming and Data Structure 29
char line[81], ch; int c=0; : : do { ch = getchar(); line[c] = ch; c++; } while (ch != \n);
c = c  1; line[c] = \0;
Read characters until CR (\n) is encountered
Make it a valid string
Spring Semester 2007 Programming and Data Structure 30
Reading a line :: Alternate Approach
char line[81]; : : scanf (%[ ABCDEFGHIJKLMNOPQRSTUVWXYZ], line);
char line[81]; : : scanf (%[^\n], line);
Ξ Reads a string containing uppercase characters and blank spaces
Ξ Reads a string containing any characters
16
Spring Semester 2007 Programming and Data Structure 31
Writing Strings to the Screen
 We can use printf with the %s format specification.
char name[50]; : : printf (\n %s, name);
Spring Semester 2007 Programming and Data Structure 32
Processing Character Strings
 There exists a set of C library functions for character string manipulation.  strcpy :: string copy  strlen :: string length  strcmp :: string comparison  strtcat :: string concatenation  It is required to add the line #include <string.h>
17
Spring Semester 2007 Programming and Data Structure 33
strcpy()
 Works very much like a string assignment operator. strcpy (string1, string2);  Assigns the contents of string2 to string1.  Examples: strcpy (city, Calcutta); strcpy (city, mycity);  Warning:  Assignment operator do not work for strings. city = Calcutta; Ξ INVALID
Spring Semester 2007 Programming and Data Structure 34
strlen()
 Counts and returns the number of characters in a string. len = strlen (string); /* Returns an integer */
 The null character (\0) at the end is not counted.  Counting ends at the first null character.
18
Spring Semester 2007 Programming and Data Structure 35
char city[15]; int n; : : strcpy (city, Calcutta); n = strlen (city);
n is assigned 8
Spring Semester 2007 Programming and Data Structure 36
strcmp()
 Compares two character strings. int strcmp(string1, string2);  Compares the two strings and returns 0 if they are identical; non-zero otherwise.  Examples: if (strcmp(city, Delhi) == 0) { . }
if (strcmp(city1, city2) != 0) { . }
19
Spring Semester 2007 Programming and Data Structure 37
strcat()
 Joins or concatenates two strings together. strcat (string1, string2);  string2 is appended to the end of string1.  The null character at the end of string1 is removed, and string2 is joined at that point.  Example: strcpy(name1, Amit ); strcpy(name2, Roy); strcat(name1, name2); \0imA t \0yoR imA t \0 yoR
Spring Semester 2007 Programming and Data Structure 38
Example
/* Read a line of text and count the number of uppercase letters */ #include <stdio.h> #include <string.h> main() { char line[81]; int i, n, count=0; scanf (%[^\n], line); n = strlen (line); for (i=0; i<n; i++) if (isupper(line[i]) count++; printf (\n The number of uppercase letters in the string %s is %d, line, count); }
20
Spring Semester 2007 Programming and Data Structure 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.
4070656850 7680748588 7072758068 6576829075Student 1 Student 2 Student 3 Student 4 Subject 1 Subject 2 Subject 3 Subject 4 Subject 5
Spring Semester 2007 Programming and Data Structure 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.
21
Spring Semester 2007 Programming and Data Structure 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];
Spring Semester 2007 Programming and Data Structure 42
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.  Examples: x[m][n] = 0; c[i][k] += a[i][j] * b[j][k]; a = sqrt (a[j*3][k]);
22
Spring Semester 2007 Programming and Data Structure 43
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. x: starting address of the array in memory c: number of columns k: number of bytes allocated per array element Element a[i][j] :: 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
Spring Semester 2007 Programming and Data Structure 44
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.
23
Spring Semester 2007 Programming and Data Structure 45
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 line.
Spring Semester 2007 Programming and Data Structure 46
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.  How to print two matrices side by side?
24
Spring Semester 2007 Programming and Data Structure 47
#include <stdio.h>
main() { int a[100][100], b[100][100], c[100][100], p, q, m, n;
scanf (%d %d, &m, &n);
for (p=0; p<m; p++) for (q=0; q<n; q++) scanf (%d, &a[p][q]);
for (p=0; p<m; p++) for (q=0; q<n; q++) scanf (%d, &b[p][q]);
for (p=0; p<m; p++) for (q=0; q<n; q++) c[p]q] = a[p][q] + b[p][q];
for (p=0; p<m; p++) { printf (\n); for (q=0; q<n; q++) printf (%f , a[p][q]); }
}
Spring Semester 2007 Programming and Data Structure 48
Passing Arrays to a Function  An array name can be used as an argument to a function.  Permits the entire array to be passed to the function.  The way it is passed differs from that for ordinary variables.  Rules:  The array name must appear by itself as argument, without brackets or subscripts.  The corresponding formal argument is written in the same manner.  Declared by writing the array name with a pair of empty brackets.
25
Spring Semester 2007 Programming and Data Structure 49
Example: Transpose of a matrix
void transpose (x, n) int x[][3], n; { int p, q;
for (p=0; p<n; p++) for (q=0; q<n; q++) { t = x[p][q]; x[p][q] = x[q][p]; x[q][p] = t; }
}
10 20 30 40 50 60 70 80 90
10 20 30 40 50 60 70 80 90
Spring Semester 2007 Programming and Data Structure 50
The Correct Version
void transpose (x, n) int x[][3], n; { int p, q;
for (p=0; p<n; p++) for (q=p; q<n; q++) { t = x[p][q]; x[p][q] = x[q][p]; x[q][p] = t; }
}
10 20 30 40 50 60 70 80 90
10 40 70 20 50 80 30 60 90
26
Spring Semester 2007 Programming and Data Structure 51
Example Usage
main() { int n; float list[100], avg; : avg = average(n,list); : }
float average(a,x) int a; float x[]; { : sum = sum + x[i]; }
We can also write float x[100]; But the way the function is written makes it general; it works with arrays of any size.
Spring Semester 2007 Programming and Data Structure 52
The Actual Mechanism
 When an array is passed to a function, the values of the array elements are not passed to the function.  The array name is interpreted as the address of the first array element.  The formal argument therefore becomes a pointer to the first array element.  When an array element is accessed inside the function, the address is calculated using the formula stated before.  Changes made inside the function are thus also reflected in the calling program.
27
Spring Semester 2007 Programming and Data Structure 53
Contd.
 Passing parameters in this way is called call-by-reference.  Normally parameters are passed in C using call-by-value.  Basically what it means?  If a function changes the values of array elements, then these changes will be made to the original array that is passed to the function.  This does not apply when an individual element is passed on as argument.
Spring Semester 2007 Programming and Data Structure 54
Example: Minimum of a set of numbers
#include <stdio.h>
main() { int a[100], i, n;
scanf (%d, &n); for (i=0; i<n; i++) scanf (%d, &a[i]);
printf (\n Minimum is %d, minimum(a,n));
}
int minimum (x,size) int x[], size; { int i, min = 99999;
for (i=0;i<size;i++) if (min < a[i]) min = a[i]; return (min);
}
28
Spring Semester 2007 Programming and Data Structure 55
Passing 2-D Arrays
 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.
Spring Semester 2007 Programming and Data Structure 56
Example Usage
#include <stdio.h>
main() { int a[15][25],b[15]25]; : : add (a, b, 15, 25); : }
void add (x,y,rows,cols) int x[][25], y[][25]; int rows, cols; { : }
We can also write int x[15][25], y[15][25];
29
Spring Semester 2007 Programming and Data Structure 57
Some Exercise Problems to Try Out
 Find the mean and standard deviation of a set of n numbers.  A shop stores n different types of items. Given the number of items of each type sold during a given month, and the corresponding unit prices, compute the total monthly sales.  Multiple two matrices of orders mxn and nxp respectively.