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
Reading Strings from the Keyboard
• Two different cases will be considered: – Reading words – Reading an entire line
14
Spring Semester 2007 Programming and Data Structure 27
Reading “words”
• 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
Reading a “line of text”
• 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
Example: Matrix Addition
#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.