CHAPTER 6
Arrays
The question ‘why we deal with numbers so frequently?’ has been discussed in Chapter 3. Examples cited there dealt with the need of numerical values such as: university seat numbers, bank account numbers, file numbers etc. All register numbers will have some definite pattern. For example, let 76EE82 be a university seat number. Here 76 may indicate the year of admission, EE may indicate the department of study, say Electrical Engineering, and 82 may indicate the serial number of the candidate admitted during that year. Obviously, all the university seat numbers have to be and will be of the same pattern. This is true in all other (and many more) cases. In other words, all social security numbers will be of the same pattern, all file numbers will be of the same pattern and so on. Thus quite frequently, in real life situations, we come across groups of data items having similar properties. In the field of computers, under data processing environments groups of data items having similar properties are taken together and are called arrays. Just like individual data items every group i.e. array, will also have a name called array name. Obviously there should be some way for the computer (i.e. the language processor or compiler) to distinguish between an ordinary variable name (which is single valued) and an array name (which is multi valued). This is generally done by declaring array names as arrays in the beginning of a program, during variables declaration itself. As an array refers to a group of data items, the information regarding number of elements in the array (i.e. size of the array) must also be provided to the compiler, during the array declaration itself. In fact, appearance of the size information during variables' declaration informs the processor that this particular variable is an array.
Different elements of an array are accessed using subscripts such as i, j etc. Various data items in an array may be arranged in the form of a vector or a matrix or in some other definite form. These forms are referred to as ‘dimensions’ of the array. An array whose data items are arranged in the form of a vector is called a one-dimensional array. An array whose data items are arranged in the form of a matrix is called a two-dimensional array and so on. As in algebra, elements of a one-dimensional array are accessed using a single subscript, elements of a two dimensional array are accessed using two subscripts, and so on.
For example, If x is a vector (i.e. a one dimensional array name), then the first element is x[0], second element is x[1], third element is x[2] and so on. The general element of this array is represented by x[i]. Instead if x is a matrix ( i.e. a two-dimensional array name), then the first element is x[0][0], second element is x[0][1], third element is x[0][2] and so on. The general element of this array is represented by x[i][j].
During an array declaration if no exact information regarding the total number of elements in the array is available, a suitable guess has to be made.
6.1 READING IN AN ARRAY AND TO OUTPUT THE SAME
The Method
The elements of an array are input, one-by-one, repeatedly under the control of some loop control statement with the help of an input function. The elements of an array are output similarly with the help of some output function. During output, one has to first decide about the number of elements to be displayed or printed per line and then the output statement has to be written.
C-Tips
Let a be used as an array consisting of 25 integer elements. This array variable name a is declared as an array along with other variables as shown below
int a [25] , x=0;
When an array is declared, consecutive memory locations are allocated or reserved for the array, as shown in the following figure. Number of locations allocated will be equal to the size mentioned in the array declaration. The size of each memory location depends upon the data type of the elements to be stored in it.
For reading or writing the different elements of an array, for loop structures are used along with input or output functions such as scanf() and printf() as shown in the program.
/* Reading in an array and to print the same (1-dimensional)*/
#include<stdio.h>
#include<conio.h>
main()
{
int a[25],i,n;
clrscr();
printf(“Enter the value of n
”);
scanf(“%d”,&n);
printf(“
Size of the array is %d
”,n);
printf(“Enter the elements of the array
”);
/* Input segment */
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“
The elements of the array are
”);
/* Output segment */
for(i=0;i<n;i++)
printf(“ %d”,a[i]);
}
Note: It is only a practice that i, j, k etc. are used as subscript variables. There is no restriction that only such variables are to be used as subscripts. Infact, any integer variable or even integer expression can be used as a subscript. It may be noted that subscripts point to specific memory positions and position numbers can only be integers.
6.2 BIGGEST AMONG GIVEN ‘N’ INTEGER NUMBERS
The Method
As ‘n’ numbers are to be considered, all these elements are read into an array (say a) and then the biggest or the maximum among all these is found. To start with the very first element a[ 0 ] is assumed to be the maximum (max). Then this max is compared with the elements starting from the 2nd location i.e. starting from the elements at the locations a[1], a[ 2 ], a[ 3 ],…, a[n − 1], one by one. If at any comparison stage the max is found to be smaller than a[i] {a[i] means any one element in the array a} then the contents of a[i] is copied into max and the comparison process is continued till the end. At the end the value of the biggest element will be available in max.
Flowchart
/* Biggest among given ‘n’ integer numbers */
#include<stdio.h>
#include<conio.h>
main()
{
int a[25],i,n,max;
clrscr();
printf(“Input the value of n
”);
scanf(“%d”,&n);
printf(“Size of the array is %d”,n);
printf(“
Input the array elements
”);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“The elements of the array are
”);
for(i = 0;i < n; i++)
printf(“%d ”,a[i]);
/* a[0] is assumed as maximum, initially */
max=a[0];
/* comparison starts from the 2nd element of the array i.e. with
i = 1 */
for(i = 1; i < n; i++)
{
if (max < a [i] )
{
max = a[i]; /* value at a[i] is copied into max */
}
}
printf(“
The biggest is %d among the given elements of the
array”,max);
}
Note: If the position of the maximum element on the array is required then it can be reported by using the value of the subscript, i.e. i, by storing its value in a separate variable, say pos, whenever a value is copied into the max. Initially pos has to be zero (0), since a[0] is assumed to be the maximum element to begin with.
6.3 THE MAXIMUM AND MINIMUM AMONG GIVEN N INTEGER NUMBERS
The Method
Like in the previous example, here also ‘n’ numbers are to be considered and are, therefore, stored in an array, say a. Initially the first element {i.e. a[0]} is assumed to be both maximum (max) as well as minimum (min). Then these max and min terms are compared with all the elements of the array starting from the 2nd element (i.e. starting from a[1]) till the last element i.e. till a subscript value of (n - 1), one after the other, sequentially. At every comparison if max is less than a[i] then a[i]'s value is made maximum by storing its value in max. At the same time, if min is more than a[i] then element a[i]'s value is made minimum by storing its value in min.
Sometimes it is necessary to identify the location or position of the elements where maximum and minimum elements exist on the array. This can be done with the help of certain variables like posmax and posmin. As the very first element i.e. a[0], is assumed to be both maximum and minimum to begin with, values of posmax and posmin will be 0 (zero) initially. Whenever a new maximum or new minimum is found out, the subscript of that element is stored or copied into corresponding posmax or posmin variables. The complete flowchart is given in the adjoining figure.
C-Tips
People normally start counting from 1 where as in C the subscript value starts from zero (0). Therefore, the i's value will be 1 less than the normal human counting practice. Therefore (i + 1)'s value is used to display the position value.
Flowchart
/* Program to find the biggest and the smallest among the given elements in an array*/
#include<stdio.h>
#include<conio.h>
main()
{
int a[80],i,n,max,min,posmin=0,posmax=0;
clrscr();
printf(“Input the value of n
”);
scanf(“%d”,&n);
printf(“Size of the array is %d”,n);
printf(“
Input the elements
”);
for(i=0;i<n;i++)
scanf(“%d”,&a[i]);
printf(“The elements of the array are
”);
for(i=0;i<n;i++)
printf(“%d ”,a[i]);
max=a[0];
min=a[0];
/* Comparison starts from the 2nd element of the array i.e. with
i=1 */
for(i=1;i<n;i++)
{
if(max<a[i])
{
max=a[i];
posmax=i;
}
if(min>a[i])
{
min=a[i];
posmin=i;
}
}
printf (“
The biggest is %d and is at the %d position among the given
elements of the array”,max,posmax+1);
printf(“
The smallest is %d and is at the %d position among the given
elements of the array”,min,posmin+1);
}
6.4 AVERAGE OF A GIVEN SET OF N NUMBERS
The Method
As in the previous examples all the given numbers are stored in an array, say a. Average is found out by first summing all the elements and then dividing the sum by total number of elements ‘n’. This process can be mathematically represented as
It may be noted that average is also termed as mean.
C-Tips
Care should be taken to avoid integer division. As already discussed one of the methods to avoid integer division is to use the type cast facility available in C. However, in this example the problem of integer division is overcome by declaring the variable sum itself as of type float.
The complete flowchart showing the above process is given below.
/* Average of a given set of n numbers */
#include<stdio.h>
#include<conio.h>
main()
{
int a[2 0],i,n;
float sum,average;
clrscr();
printf(“How many number of elements?
”);
scanf(“%d”,&n);
printf(“Input %d number of elements
”,n);
for(i=0;i<n;++i)
scanf(“%d”,&a[i]);
printf(“Elements of the given array are:
”);
for(i=0;i<n;i++)
printf(“%d ”,a[i]);
printf(“
”);
sum=0.0;
for(i=0;i<n;i++)
sum= sum+a[i]; /* Finding the sum of all elements */
average=sum /n;
printf(“average=%.2f”, average);
}
6.5 GIVEN N INTEGERS (ZERO, +VE, -VE) TO FIND OUT THE SUM OF +VE NUMBERS, -VE NUMBERS AND THE AVERAGE OF ALL NUMBERS
The Method
After declaring ‘a’ as an array of required size, all the elements of the array are read in. Starting from the first element, each element is taken one by one and tested to determine whether it is +ve, -ve or zero. All positive numbers are added into a variable like psum, all negative numbers are added into a variable like nsum and nothing is done with zeros. Variables psum and nsum are initialized to zero. To find out the average, the sum of psum and nsum is obtained and the average is computed by dividing the sum by total number of elements, n. In this example, zero's have been considered as positive.
C-Tips
Care should be taken to avoid integer division. For this type casting facility of C may be used. For example, if sum is a integer variable then it can be converted into float type using a statement like (float) sum.
Flowchart
/* Program to read N integers(zero, +ve, -ve ) into an array a. To find
sum of -ve numbers, sum of +ve numbers and average of all input numbers
*/
/* Note: zero is taken as positive */
#include<conio.h> /* Including header file */
#include<stdio.h>
main()
{
int a [20], i,psum=0,nsum=0, n; /* Declaring array a and initializing psum and nsum to zero */
float avg;
clrscr();
printf(“
Enter n, the No. of elements.
”);
scanf(“%d”,&n);
printf(“n = %d
”,n);
printf(“Enter the elements
”);
for(i=0; i<n; ++i)
scanf(“%d”,&a[i]); /* Reading elements of array */
printf(“Elements are
”);
for(i=0; i<n; + + i)
printf(“%d ”,a[i]); /* Printing elements of array */
for(i=0; i<n; ++i) /* Repeating for each element */
{
/* If element is greater than or equal to zero it is added to psum,
otherwise it is added to nsum */
if (a[i] >= 0)
psum += a[i];
else
nsum + = a [i];
}
avg = (float) (psum + nsum)/n; /* Calculating average of all numbers */
/* Observe that RHS is type casted */
printf(“
Sum of positive numbers = %d
”,psum);
printf(“
Sum of negative numbers = %d
”,nsum);
printf(“
Average of all input numbers = %.2f
”,avg);
}
6.6 MEAN, VARIANCE AND STANDARD DEVIATION OF A GIVEN SET OF NUMBERS
The Method
Since relations to compute the required quantities mean, variance and standard deviation are given, solving this problem is straightforward. The procedure involved is shown in the adjoining flow chart.
C-Tips
Whenever average or mean is computed care should be taken to avoid integer division. As already discussed this can be done using the type casting facility.
/* Mean, variance and standard deviation of a given set of numbers */
#include<stdio.h>
#include<conio.h>
#include<math.h>
main()
{
int i, n;
float a[20], mean=0, sum=0, variance=0, stdev;
clrscr();
printf(“
Enter n, No. of elements
”);
scanf(“%d”, &n);
printf(“n = %d
”, n);
printf(“
Enter the elements
”);
for(i = 0; i < n; ++i) /* Reading elements of array */
scanf(“%f”, &a[i]);
printf(“Elements are
”); /* Printing elements of array */
for(i = 0; i < n; ++i)
printf(“%.2f
”, a[i]);
for(i = 0; i < n; ++i) /* summing array elements */
sum += a[i];
mean = sum/n; /* computing mean */
sum = 0;
for(i = 0; i < n; ++i) /* computing variance */
sum += (mean - a[i]) * (mean - a[i]);
Variance = sum/n;
stdev = sqrt(variance); /*computing standard deviation */
printf(“
Mean = %.3f
Variance = %. 3f
Standard Deviation = %.3f
”,
mean, variance ,stdev);
}
Note: In this example the variable sum has been used both to compute the mean as well as the variance. A careful observation of the flowchart as well as the program reveals the fact that after computing the mean, the value stored in sum is no more required. Therefore it is initialized once again to zero and employed to compute another sum, which is used in the computation of variance.
6.7 CLASSIFICATION OF THE ELEMENTS OF A GIVEN ARRAY INTO AN ARRAY CONSISTING OF ONLY ODD ELEMENTS AND ANOTHER ARRAY CONSISTING OF ONLY EVEN ELEMENTS.
The Method
Let there be ‘n’ elements in the given array, say a. Let o_array and e_array be two arrays which will hold only odd elements and only even elements respectively.
First the given array is read into the computer. Then every element of the array a is tested to find out whether it is odd or even. This testing is done by “modulo 2” division of the element. If the “modulo 2” division results in a zero remainder, then the element will be even. If the “modulo 2” division results in a non-zero remainder, then the element will be odd. In order to verify the array elements we have to move along the array a. This movement is made using the subscript i and varying its value from 0 to (n - 1). In order to store odd elements into odd-array (o_array) we have to move along the o_array. This movement is obtained using the subscript j the value of which has to be zero (0) to start with. In order to store even elements into even-array (e_array) we have to move along the e_array. This movement is obtained using the subscript k the value of which also has to be zero (0) to start with. Whenever required, the actual movement on an array is made by incrementing the value of the corresponding subscript variable.
If the element is odd, it is put into the odd array (o_array) and the odd count (j) is incremented.
If the element is found to be even, it is put into the even array (e_array) and the even count (k) is incremented.
The above process is repeated for all the elements of the given array. Finally, the given array, odd array (o_array) and the even array (e_array) are output with suitable messages.
C-Tips
In the program all the three arrays a, o_array and e_array have been declared to be of same size. This is to take care of the worst possible situation where all the given array elements could be either only odd or only even.
/* Classification of the elements of a given array into an array
consisting of only odd elements and another array consisting of only
even elements. */
#include <stdio.h>
main ( )
{
int a [80], o_array[80] , e_array[80] , n , i , k=0, j=0;
clrscr( );
printf( “ Enter the number of elements
”);
scanf( “%d”, &n);
printf (“Size of the given array is %d
”, n);
printf( “Input the elements of the array
”);
for (i = 0 ; i < n ; i++)
scanf(“%d”, &a[i]);
for ( i = 0 ; i < n ; i++ )
{
if ( a[i] % 2 == 0) /* Is it an even element ? */
{
e_array [k] = a [i]; /* Yes, even element */
k++;
}
else
{
o_array [j] = a [i]; /* Else, odd element */
j++;
}
}
printf ( “
The given array is
”);
for ( i = 0 ; i < n ; i++ )
printf ( “%d ”, a[i]) ;
printf( “
The array containing only even elements is
”);
for ( i = 0 ; i < k ; i++ )
printf ( “%d ”, e_array [ i ] ) ;
printf ( “
The array containing only odd elements is
”) ;
for ( i = 0 ; i < j ; i++ )
printf ( “%d ”, o_array [ i ] ) ;
}
6.8 SORTING N NUMBERS IN ASCENDING ORDER USING BUBBLE SORT
The Method
The Bubble sort procedure can be well understood through an illustration. Below is given an illustration.
Let there be four elements stored as an array, which are in the descending order (deliberately selected). In this method of sorting, elements in consecutive locations are compared from the beginning to the end of the array. If these two consecutive elements are not in the required order, they are interchanged. If they are in the required order, nothing is done and the comparison of next set of consecutive elements is made.
Thus, in this illustration, first 7 {i.e. A[0]} is compared with 5 {i.e. A[1]} and interchanged. Next, 7 {now A[1]} is compared with 4 {now A[2]} and are interchanged. Further, 7 {now A[2]} is compared with 2 {now A[3]} and are interchanged. No further comparisons can be made as we have already considered A[3], the last element. The array now looks as shown in the figure below.
Observe that in going once from the beginning till the end there were 3 comparisons. Comparison was made between A[i] and A[i + 1] elements with i ranging from 0 to 2. Going once from the beginning of the array till its end or traversing once across the entire array is known as a pass. Thus in a pass we will be making (n - 1) comparisons, where n is the total number of elements in the array. (Observe that from the given 4 elements, 3 comparisons were made.)
Obviously, one pass has put the largest element in its place. Th second pass will put second largest element in its place and so on. Thus in order to put all n elements in their places (n - 1) passes are required. Why (n - 1) passes? Why not n passes? This is so because after (n - 1) passes (n - 1) elements are forced to their proper positions and the last element has to be and will be in its proper position.
Thus the Bubble sort procedure needs (n - 1) traversals or passes and (n - 1) comparisons in every pass. The flow chart will be as shown below.
Flowchart
/* Sorting n numbers in ascending order using bubble sort */
#include<conio.h> /* Including header file */
#include<stdio.h>
main()
{
int i, j, n, a [20] , temp; /* Declaring array a */
clrscr();
printf(“
Enter n, No. of elements
”);
scanf(“%d”, &n);
printf(“n = %d
”, n);
printf(“Enter the elements
” ) ;
for(i =0; i<n; ++i)
scanf (“%d”, &a[i]); /* Reading elements of array */
printf(“
Elements are:
”);
for(i =0; i<n; ++i)
printf(“%d ”, a[i]); /* Printing elements of array */
printf(“
”);
/* This loop performs required number of passes */
for(j=0; j<n-1; ++j)
{
/* This loop performs all comparisons in a pass */
for(i=0; i<n-1; ++i)
if ( a[i] > a[i+1] )
/* if first among two adjacent element is greater than the
other then it is exchanged using temporary variable temp */
{
temp = a[i];
a[i] = a[i+1] ;
a[i+1] = temp;
}
}
printf(“
Sorted elements are:
”);
for(i =0; i<n; ++i)
printf(“%d ”, a[i]); /* Printing sorted array */
printf(“
”);
}
Note: The analysis here is known as the worst case analysis. This is because initially a descending order array was assumed. It may be noted that if the given array is either partially ordered or totally ordered, still this program works. However, unnecessarily it goes through all the passes and makes all comparisons. It is possible to avoid this with the help of a flag. Try.
6.9 EVALUATING A POLYNOMIAL
A polynomial will be as shown below
Evaluating the polynomial means, finding out the value of p(x), given the value of x and the coefficients a0, a1, a2, a3,......,an-1, an.
The Method
A specific polynomial can be evaluated by writing an arithmetic expression for the same. For example, if 5x3 + 4x2 + 2x + 3 is given, a statement of the form p(x) = 5 * x * x * x + 4 * x * x + 2 * x + 3 can be first written and then knowing the value of the variable x, the expression can be evaluated. However, a general procedure to solve any given polynomial is discussed below. Here, it may be noted that a given polynomial can be rewritten in the form of a nested parenthesis expression as:
All the coefficients of the polynomial are read in and stored as an array, say a. The element at 0th position in the array a refers to the coefficient a0, the element at 1st position in the array a refers to a1, and so on. A procedure for evaluating a polynomial can be formulated as discussed below. Here it may be recalled that in the case of nested parentheses expressions the inner most parenthesis are taken care-of first.
A verification of the above rewritten polynomial reveals the following facts:
First, an is taken as the value of a variable, say result. Then it is multiplied by x, and added to an-1 thus generating (an-1 + x* result). As at this stage an is the value of result, the expression evaluated will be (an-1 + x * an). This evaluated value is made as the new value of the result.
Next (an-2 + x * result) is evaluated. As at this stage the result holds the value of (an-1 + x * an), the expression evaluated will be (an-2 + x (an-1 + x * an)). This evaluated value is made as the new value of the result.
Further (an-3 + x * result) is evaluated. Since result already holds the value of (an-2 + x (an-1 + x * an)) , the expression now evaluated will be (an-3 + x * (an-2 + x (an-1 + x * an))). Again, this evaluated value is made as the new value of the result.
Steps discussed above are to be repeatedly executed till all the polynomial coefficients are taken care of.
From the above discussion one can observe that
- One should have a variable like result which is initialized to the coefficient of the highest order term i.e., an.
- As an has been taken as the initial value of the variable result we need only an-1, an-2, an-3 , an-4,…,a2, a1, a0 to be considered. By using the expression (n - 1 - i) as the subscript of the array a and varying i from 0 to (n - 1) one can generate all the remaining coefficients i.e. an-1, an-2, an-3 , an-4,…,a2, a1, a0, one after the other.
- The expression (an-1-i + x * result) is repeatedly evaluated for all the values of i varying from 0 to (n - 1).
Thus the important steps in evaluating a given polynomial are:
- Read in all the coefficients into an array, say a. Initialize a variable like result to an.
- Then repeatedly execute the statement
result = a + x * result;
for all values of i from 0 (zero) to (n - 1).
C-Tips
In this example, for the first time a format specifier like %+d has been used in the control string of a printf() statement. Here the + (plus) character is called the printf flag character. The use of + (plus) as shown here prints out the results along with the sign. A - (minus) character can also be used as a printf flag character. The use of this flag character prints the result in the left justified form.
The above procedure is shown in the form of a flowchart in the adjoining figure.
Flowchart
/* Evaluating a polynomial expression */
#include<stdio.h>
#include<conio.h>
main()
{
/*Declaring variables*/
int a[10], n, i, result,x;
/* clearing the screen*/
clrscr();
printf(“Enter the order of the polynomial
”);
/*Accepting the order of polynomial*/
scanf(“%d”, &n);
/* printing the order of the polynomial*/
printf(“Order of the polynomial is %d
”,n);
printf(“Enter the coefficients of the polynomial
”);
for(i=0; i<=n; ++i)
{
printf(“
Enter a[%d] = ”, i);
/*Accepting the coefficients of the polynomial*/
scanf(“%d”, &a[i]);
}
/*Printing the polynomial*/
printf (“
Given polynomial is :
”);
printf(“
p(x) = ”) ;
for(i=n; i > = 0; --i)
printf(“ %+d*x^%d ”, a[i], i) ; /* Observe the use of + with the format
specifier %+d with in the control
string. */
printf(“
Enter the value of x
”);
/* Accepting value of x */
scanf(“%d”, &x);
printf(“
x = %d
”, x);
/*Initializing the result with a[n]*/
result = a [n];
/*Evaluating the polynomial*/
for (i=0; i< n; ++i) /* Because an was first put in result */
result = a[n-1-i] + x * result;
printf(“
p(%d) = %d
”, x, result);
}
6.10 READING AND PRINTING OUT A GIVEN MATRIX
The Method
This example illustrates how a matrix (a two dimensional array) could be read in and printed out. In fact, this type of program will be a segment of some other programs like “Program to transpose” a given matrix, “Program to find the sum/difference” of given matrices, “Program to compute the product” of given matrices, and so on. Let a be the given matrix, having m rows and n columns, i.e. a m × n matrix.
The general element of this matrix is aij. Here the first subscript i represents a row and the second subscript j represents a column. This matrix could be read in row-wise, i.e. in the order a00, a01, a02, a10, a11 and so on, or could be read in column-wise, i.e. in the order a00, a10, a01, a11 and so on. But a matrix is always printed row-wise only.
By carefully going through the discussion in the above paragraph we see that, while handling the array row wise the first subscript (i.e. i) varies slowly and the second subscript (i.e. j) varies faster. Therefore, the fast varying subscript j must be taken care of before the slow varying subscript i. In other words, the loop under the control of j must constitute the inner loop and the loop under the control of i must constitute the outer loop. The matrix can be handled column-wise by first taking care of the i variable and then the j variable. It may be noted that the matrices are generally read in and printed out row-wise.
The flow chart below shows the process of reading a given matrix and printing the same.
Flowchart
/* To read in a given matrix and to print out the same */
#include<stdio.h>
#include<conio.h>
main()
{
int a[10][9],i,j,m,n;
clrscr();
printf(“Enter the values of m and n
”);/* Size of the matrix */
scanf(“%d%d”,&m,&n);
printf(“Enter the matrix
”);
for(i=0;i<m;i++) /* Outer loop begins */
{
for(j=0;j<n;j++) /* Inner loop begins */
scanf(“%d”,&a[i][j]);
}
printf(“ The elements of the array are
”);
for(i=0;i<m;i++) /* Outer loop begins */
{
printf(“
”);
for(j=0;j<n;j++) /* Inner loop begins */
printf(“ %3d”,a[i][j]);
}
}
Note: We are accustomed to the evaluation of nested arithmetic expressions like (7 + (5 - 2)). Because of the parenthesis, (5 - 2) is evaluated first, which results in 3 and then (7 + 3) is evaluated. In other words, when nested, inner parenthesis is taken care of first and then the outer parenthesis. A similar situation exists with nested for loop (or any loop control) statements, i.e. inner for loop will be taken care of first and then the outer for loop.
6.11 TO COMPUTE THE SUM/DIFFERENCE OF GIVEN MATRICES
The Method
In order to obtain the sum or difference of two given matrices, the size of the given matrices must be same. The sum of two matrices is obtained by summing the corresponding elements of the given matrices. The difference of two matrices is obtained by finding out the difference between the corresponding elements of the given matrices. For example:
If 
then sum, 
Thus every element of the sum matrix C is obtained using the relation cij = aij + bij for all values of i and j.
Difference, 
Thus every element of the difference matrix D is obtained using the relation dij = aij - bij for all values of i and j.
Flowchart
/* To compute the sum and difference of given matrices */
#include<conio.h>
#include<stdio.h>
main()
{
int a[10][10], b[10][10], c[10][10], d[10][10], i, j, m, n;
clrscr();
printf (“Enter value for m and n ie. , the order of matrices A and
B
”);
scanf(“%d%d”, &m, &n);
printf (“Order of Matrix A and B is %d X %d
” , m, n);
printf(“Enter the elements of matrix A
” ) ;
for(i=0; i <m; ++i) /* Reading matrix a */
for(j = 0; j<n; + +j)
scanf(“%d”, &a[i][j]);
printf(“Enter the elements of matrix B
”);
for(i=0; i<m; ++i) /* Reading matrix b */
for(j=0; j<n; ++j)
scanf(“%d”, &b[i][j]);
printf(“
Matrix A
”);
for(i=0; i <m; ++i) /* Printing matrix a */
{
for(j = 0; j<n; ++j)
{
printf(“%d ”, a[i][j]);
}
printf(“
”);
}
printf(“
Matrix B
”);
for(i=0; i <m; ++i) /* Printing matrix b */
{
for(j = 0; j<n; ++j)
{
printf(“%d ”, b[i][j]);
}
printf(“
”);
}
/* Finding the sum and difference */
for(i=0; i<m; ++i)
for(j = 0; j<n; ++j)
{
c[i][j] = a[i][j]+b[i][j] ; /* Addition of matrices */
d[i][j] = a[i][j]-b[i][j] ; /* Subtraction of matrices */
}
printf(“
Resultant Matrix C (Sum)
”);
for(i=0; i <m; ++i) /* Printing sum matrix c */
{
for(j = 0; j<n; ++j)
{
printf(“%d ”, c[i][j]);
}
printf(“
”);
}
printf(“
Resultant Matrix D (Difference)
”);
for(i=0; i <m; ++i) /* Printing diff matrix d */
{
for (j=0; j<n; ++j)
{
printf(“%d ”, d[i][j]);
}
printf(“
”);
}
}
Note: While developing the flowchart as well as coding, i.e. programming it has been assumed that the two matrices have same dimensions so that they can be added or subtracted. Sometimes it may be necessary to check for the dimensions. This checking must be done immediately after reading in the dimensions of the two matrices. If A is an (m × n) matrix and B is a (p × q) matrix then for addition or subtraction the relational expression {(m = p) and (n = q)} must be true and is therefore tested.
6.12 TRACE OF A GIVEN MATRIX
By definition the trace of a matrix is given by the sum of all the elements on its principle diagnol. Obviously the matrix has to be a square matrix.
The Method
First all the elements of the given matrix are read in. Then whether the given matrix is a square matrix or not is found out. This is done by comparing the two dimensions of the matrix. If number of rows is equal to number of columns then the trace can be found out. Otherwise the trace cannot be computed.
From the above figure it may be observed that the control moves down on the principal diagonal when both the subscripts are same. Thus the trace can be obtained using the following relation :
The above relation can be mathematically written as follows :
Obviously, a for statement is used to obtain the above sum, i.e. the trace.
C-Tips
When the given matrix is not a square matrix a proper message has to be displayed and the computation must stop. For this purpose the exit() function explained in Section 6.15 is used.
Flowchart
/* Trace of a given matrix */
#include<stdio.h>
main()
{
int m,n,i,j,a[10][20],trace;
clrscr();
printf(“Enter the order
”);
scanf(“%d%d”,&m,&n);
if (m!=n) /* Is it a square matrix ?*/
{
printf(“Trace Not Possible
”); /* Not a square matrix */
exit(1);
}
printf(“Enter a matrix
”);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
scanf(“%d”,&a[i][j]);
}
printf(“The given matrix is
”);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf(“%d ”,a[i][j]);
printf(“
”);
}
trace=0;
for(i=0;i<m;i++) /* Computing the trace */
trace=trace+a[i][i];
printf(“Trace of the given matrix is = %d”,trace);
}
6.13 NORM OF A GIVEN MATRIX
By definition norm of a matrix is the square root of the sum of the squares of all its individual elements.
The Method
Since all the elements are to be considered, one has to consider the general element aij, where a is a given matrix of m rows and n columns. The square of every element is obtained by simply multiplying it by itself once, i.e. by using (aij * aij). The sum of all (aij)2 is obtained by the relation:
After finding the sum the norm is obtained by finding the square root of the sum. using the relation
The flowchart is given in the adjoining figure.
Flowchart
/* The norm of a matrix */
#include<stdio.h>
#include<math.h>
main()
{
int m,n,i,j,a[10][10],sum;
float norm;
clrscr();
printf(“Enter the values of m and n
”);
scanf(“%d%d”,&m,&n);
printf(“Enter a matrix
”);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
scanf(“%d”,&a[i][j]);
}
printf(“The given matrix is
”);
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf(“%d ”,a[i][j]);
printf(“
”);
}
sum=0;
for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
sum=sum+a[i][j]*a[i][j];
}
norm=sqrt(sum);
printf(“
Norm of the given matrix is = %.2f”,norm);
}
6.14 TRANSPOSE OF A GIVEN MATRIX
The Method
Let A be the given matrix of size m by n. Also let B is the transpose of the given matrix. The transpose of a matrix is obtained by interchanging its row elements and column elements. For example :
If 
Also, 
By comparing the two representations of B given above we see that any element of B i.e. bij is equal to aji. Therefore, the relation bij = aji is used repeatedly to generate all the elements of the transposed matrix. Observe that if the size of matrix is (m × n) then the size of its transpose will be (n × m). The adjoining flowchart shows the above procedure.
Flowchart
/* Given a matrix A ( m * n ) , to find the transpose of the same and to
output both the input matrix and the transposed matrix. */
#include<stdio.h>
#include<conio.h>
main()
{
int a[10][10], b[10][10],i, j, m, n;
clrscr();
printf(“Enter value for m and n i.e., the order of matrix A
”);
scanf(“%d%d”, &m, &n);
printf (“Order of Matrix A is %d X %d
” , m, n);
printf(“Enter the elements of matrix A
”);
for(i=0; i <m; ++i) /* Reading matrix a */
for(j=0; j<n; ++j)
scanf(“%d”, &a[i][j]);
printf(“ Matrix A
”);
for(i=0; i <m; ++i) /* Printing matrix a */
{
for(j=0; j<n; ++j)
{
printf(“%d ”, a[i][j]);
}
printf(“
”);
}
for(i=0; i<n; ++i)
for(j=0; j<m; ++j)
b[i][j] = a[j][i]; /* Transposing */
printf(“
Transpose of Matrix A
”);
for(i=0; i <n; ++i) /* Printing transposed matrix */
{
for(j=0; j<m; ++j)
{
printf(“%d ”, b[i][j]);
}
printf(“
”);
}
}
6.15 PRODUCT OF TWO GIVEN MATRICES
The Method
Let A and B are two given matrices of dimensions (m × n) and (p × q) respectively. Also let C be the product matrix. For the multiplication of given two matrices, number of columns of the first matrix must be equal to number of rows of the second matrix, i.e. n must be equal to p. The product matrix C will be of size (m × q). The generation of each element of the product matrix (C [i, j]) can be easily understood by going through the following illustration.
Let 
Obviously,
A is a (2 * 3) matrix, i.e. m = 2 and n = 3
B is a (3 × 3) matrix, i.e. p = 3 and q = 3
Since n = p, multiplication is possible. The resultant product matrix C will be a m × q, i.e. 2 × 3 matrix.
Let 
The row elements of C are obtained as follows:
That is, moving on the row of the first matrix and on the column of the second matrix, as indicated by arrows in the above illustration.
By inspecting the above relations we find that any element of the product matrix C can be obtained using the relation :
The first subscript of a will be the first subscript of c and the second subscript of b will be the second subscript of c. Observe that the second subscript of a and the first subscript of b are same and vary from 0 upto (n - 1). Let this common subscript be k. Thus this subscript k varies from 0 to (n - 1). Since every element is a summation of certain product terms, one has to use a variable like sum in order to have the generated elements summed up and stored in it. The flowchart segment for this is given below.
All the elements of the product matrix C are generated by repeating the above process for all the values of i and j. Observe that i, the first subscript of C, should vary from 0 to (m - 1) and j, the second subscript of C, should vary from 0 to (q - 1). This can be shown in the form of a flow chart segment in page 117.
From the flowcharts we see that nested for loops are used. It may be noted that whenever nested for loops are used, the inside for is taken care of first. In other words, here, j varies faster than i. Since j varies faster than i, the elements of the product matrix are generated row-wise. If, by chance, the above two loops are interchanged, then the elements of C are generated column-wise.
Though care may be taken during the input operation itself to see that the input matrices are multipliable, it is advisable to check for the multipliability of the matrices by checking whether “number of rows” of the first matrix is equal to “number of columns” of the second matrix or not. The following flowchart segment may be used for this purpose.
C-Tips
In this program, the program execution has to terminate when the two given matrices are not multipliable, i.e. the number of columns of the first matrix is not equal to the number of rows of the second matrix. For such terminations we can use either the exit function or a goto statement. In general, the use of exit functions is recommended. Whenever an exit function is called the program terminates. Thus one can think of two types of program execution terminations. One is the normal termination and another is termination under error conditions. Normal terminations takes place after all the statements are executed. Abnormal termination, i.e. termination under error condition, takes place with the help of a call to a function like exit. In C termination of program execution returns a numeric value as status indication. This status value for normal termination will be zero (0) and it will be a non zero value for abnormal terminations. Therefore, to indicate error conditions the exit( ) function is always written with a non-zero value as its argument. Whenever an exit( ) function of this form is executed, the non-zero value is returned as the status value. If necessary, these status values returned by a program after the execution of an exit( ) function can be trapped and used or further processing. At this stage the reader is advised not to bother much about the status values returned. It is sufficient if one uses the exit( ) function by writing a statement like exit(1); whenever abnormal termination is required.
Flowchart
Note: Matrices are input and output under the control of a for loop. For further details Section 6.1 may be referred to.
The Program
/* To compute the product of two given matrices */
#include<stdio.h>
#include<conio.h>
main()
{
int m, n, i, j,k,p, q,sum,a[10][10],b[10][10],c[10][10];
/* a[10][10],b[10][10],c[10][10] are
2D arrays, each of size 10 * 10 */
clrscr();
printf(“
Enter the order of the first matrix A
”);
scanf(“%d%d”, &m, &n);
printf(“
Enter the order of the Second matrix B
”);
scanf(“%d%d”, &p, &q);
printf(“Order of matrix A = %d X %d Order of matrix B = %d X
%d
”, m,n,p,q);
if(n != p)
{
printf(“
Matrices are not multipliable
”);
exit(1); /* The use of an exit statement to terminate the program */
}
printf(“
Enter elements of Matrix A
”);
for(i=0; i<m; ++i)
for(j=0; j<n; ++j)
scanf(“%d”, &a[i][j]);
printf(“
Enter elements of Matrix B
”);
for(i=0; i<p; ++i)
for(j=0; j<q; ++j)
scanf(“%d”, &b[i][j]);
printf(“
Matrix A
”);
for(i=0; i<m; ++i)
{
for(j=0; j<n; ++j)
printf(“%4d ”, a[i][j]);
printf(“
”);
}
printf(“
Matrix B
”);
for(i=0; i<p; ++i)
{
for(j=0; j<q; ++j)
printf(“%4d ”, b[i][j]);
printf(“
”);
}
/* Finding the product */
for(i=0; i<m; ++i) /* for each row */
{
for(j=0; j<q; ++j) /* for each column */
{
sum = 0;
for(k=0; k<n; ++k) /* for each matrix element */
sum += a[i][k]*b[k][j];
c[i][j]= sum;
}
}
printf(“
Product Matrix
”);
for(i=0; i<m; ++i)
{
for(j=0; j<q; ++j)
printf(“%4d ”, c[i][j]);
printf(“
”);
}
}
6.16 SEARCHING A GIVEN ELEMENT IN A GIVEN LIST OF INTEGER ELEMENTS (LINEAR SEARCH ALGORITHM)
The Method
As a set of integer elements are to be handled, it is taken as an array, say a. Here the problem is to search for a required element in the given array. The required element is generally known as the search key. Let this search key be represented by a variable called key. The searching process for the key's presence in the array starts from the beginning of the array and continue till either the key is available or till the end of the array is reached. Therefore, this method is known as linear search or sequential search method. The following illustration and discussion gives an idea about the method used.
Search key = 36
Search key = 30
During a search for the required key, the search key is compared with each element in the array (for matching i.e. for equality), element by element, starting from the very first element. In otherwords the key is first compared with a[0], next with a[1], next with a[2], and so on. If a match is found for the key, the loop terminates; otherwise the comparison process continues till all the elements in the array are compared.
Under the loop control, whenever a match is found the control has to come out of the loop. Generally, leaving the loop prematurely is referred to as breaking and is achieved with a break statement. However, just before one breaks and tries to go out of the loop prematurely, following two things should be done:
- The index value, i.e. the subscript value of the array, must be saved in some variable (say, pos) which helps in reporting the result.
- A flag must be set which indicates the success or failure of the search.
If a match is not found, the loop gets past the last item of the array and the control comes out of the loop normally. When the loop control comes out of the loop normally the flag (success/failure indicator) remains unaltered i.e. remains the same as it was in the beginning. Obviously, a flag has to be initialized in the beginning itself. This flag is normally set to 0 (zero) initially, which signals failure. Whenever the search succeeds, the flag is set to 1 (one). Thus the final output depends upon the contents of this flag. At the end, if the flag value still remains 0 (zero), failure is reported where as if the flag has become 1 (one), success is reported along with the position value.
C-Tips
The break statement is used to come out of the loop prematurely after satisfying some condition. Generally, under all situations where the program control may come out of a loop, it is necessary to identify whether the control has come out normally or prematurely, and then act accordingly. A flag is used under all such situations. Here, flag means any variable used for the purpose of just flagging, i.e. indicating, the success or the failure, not necessarily the name flag.
Flowchart
/* Searching a given element in a given list of elements. */
/* Linear Search Problem */
#include<stdio.h>
#include<conio.h>
main()
{
int i, n, flag = 0,pos=0;
float a [20] , key; /* Declaring array a and key */
clrscr();
printf(“
Enter the value for n
”);
scanf(“%d”, &n);
printf(“n = %d
”, n);
printf(“Enter the elements of array a
”);
for(i=0; i<n; ++i)
scanf(“%f”, &a[i]); /* Reading elements of the array */
printf(“Elements of the given array are
”);
for(i=0; i<n; ++i)
printf(“%.2f ”, a[i]); /* Printing elements of array */
printf(“
Enter key number
”);
scanf(“%f”, &key); /* Reading the key number */
printf(“Key number = %.2f
”, key);
for(i=0; i<n; ++i) /* Repeating for each element */
{
if(a[i] == key) /* Whether element is equal to key number or not ? */
{
flag=1; /* if yes, flag is set to 1 to indicate key is found */
pos = i;
break; /* break from for loop */
}
}
if ( flag ) /* If flag is true (i.e,one) then key
is found */
printf(“%.2f is found in position number %d
”, key, pos+1);
else /* Otherwise key is not found */
printf(“%.2f is not found in the array
”, key);
}
6.17 SEARCHING FOR A GIVEN ELEMENT IN AN ARRAY USING BINARY SEARCH METHOD
The binary search method is applicable only for sorted arrays. Infact, if number of elements are more (how many?) they must be first sorted and then the binary search method has to be used.
The Method
In this method, the search starts by testing the data element at the middle of the array. If the required element is available at that position, then the search is complete. If it is not available at that point (i.e at the mid position) it may be available either in the first half or in the second half of the array. The actual half (of the array) in which the required data item may be present is determined by making the following test. If the search key is larger than the element at the middle of the array then the required element may be available in the second half of the array. If it is smaller than the element at the middle of the array then it may be available in the first half. If it is in the second half, first half is not searched and vice versa.
The above process is repeated until the required element is found or we get satisfied that the element is not available in the array. Let low represents the beginning of the search portion and high represents the ending of the search portion. Initially, the entire array will be the search portion. Therefore the value of low will be zero (0) and value of high will be (n - 1), where n is the number of elements to be sorted. The middle of the array is computed using the relation:
Whenever the required element is in the second half (mid + 1) position is made as low position and the search is continued.
Whenever the required element is in the first half (mid - 1) is made as high position and the search is continued.
The search process is terminated when we come across one of the following conditions
- search key = element at the mid position
or
- value of low > value of high
Below is given an illustration, the study of which gives a better understanding of the process involved.
Illustration
Consider a set of elements sorted in ascending order :
Let search key = 32
Step 1
The element at the mid position i.e., at 5 is 30, which is not the required key.
Step 2
Since the search key (32) is > the middle element (30), the search key (32) may be present in the second half. Therefore, low = mid + 1, i.e. 5 + 1 = 6. The value of high remains 11, unaltered. The new value of mid is:
Now the element at the new mid position, i.e. at 8 is 53. Since the search key (32) is < than the mid element (53), the search key (32) may be present in the first half of the current search space. Therefore, high = mid - 1 = 8 - 1 = 7. The value of low remains 6, i.e., unaltered.
Step 3
Here we find that the value at position 6 is 32 which is equal to the search key. Hence, at this stage success is reported along with the position value. Incase, even at this stage, if the search was not a success, the procedure discussed in the earlier steps is repeated. As already mentioned, the procedure is terminated when the condition low > high appears.
/* Searching for a given element in an array using binary search method. */
#include<conio.h> /* Including header files */
#include<stdio.h>
main()
{
int i, n, a[20],key,low, high, mid;
clrscr();
printf(“
Enter value for n
”);
scanf(“%d”, &n);
printf(“n = %d
”, n);
printf(“
Enter the elements of array a in ascending order
”);
/* Reading elements of array */
for(i = 0; i < n; ++i)
scanf(“%d”, &a[i]);
printf(“Elements are
”); /* Printing elements of array */
for(i = 0; i < n; ++i)
printf(“%d
”, a[i]);
printf(“
Enter key element to be searched
”);
scanf(“%d”, &key); /* Reading Key element */
printf(“key = %d
”, key); /* Printing key element */
high = n-1;
low = 0; /* Initializing high and low */
while(low <= high)
{
mid = (low + high)/2; /* mid is mean of low and high */
/* if key is equal to middle element then exit from loop */
if( key == a[mid] )
break;
else if ( key > a [mid] )
/* if key is greater than middle element then it
must be in second half. Make low=mid+1 */
low = mid + 1;
else
high = mid - 1;
}
if (a[mid] == key)
{
printf(“Search is successful
”);
printf(“%d is found in position number %d
”, key, mid+1);
}
else
printf(“Search is unsuccessful, %d is not found
”, key);
}
6.18 SORTING A GIVEN ARRAY OF ELEMENTS USING SELECTION SORT
The problem here is to sort a given set of unsorted integer elements into a required order, i.e. ascending or descending order.
The Method
By default it is assumed that we need to arrange the elements in ascending order, i.e. in the increasing order of their numeric values. A study of the following illustration gives an idea of the procedure to be followed in sorting by selection. Here ‘by selection’ means selecting the first minimum and storing it in the first place, selecting the second minimum and storing it in the second position, selecting the third minimum and storing it in the third position and so on. However, care should be taken not to loose the already existing values whenever we are storing the minimum values in their proper slots, i.e. locations. One of the general techniques employed not to loose the value of the element already existing in the place where a minimum value is stored, is to save the value of the element already existing in that location. This saved value is stored in the location from where the minimum value will be picked up.
Illustration
Consider a set of integers stored in an array, as shown in the figure below.
In the first step select a minimum value among a[0], a[1], a[2], a[3].....a[7] and store it at a[0]. Here, the minimum is 2 and is at a[5]. The values at a[0] and a[5] are exchanged.
In the second step, select a minimum value among a[1], a[2], a[3].....a[7] and store it at a[1]. Here, the minimum is 3 and is at a[4]. The values at a[1] and a[4] are exchanged.
In the third step, select a minimum value among a[2], a[3]…a[7] and store it at a[2]. Here minimum is 4 and is at a[7]. The values at a[2] and a[7] are exchanged. Now the array will be as shown in the following figure.
From the above illustration following conclusions are drawn. Let i is used as subscript for searching the minimum. In the first step search is made using ai where i varies from 0 to 7 and the minimum is stored at the starting point of the search range, i.e. at a0.
In the second step the search is made using ai where i varies from 1 to 7 and the minimum is stored at the starting point of this search range, i.e. at a1.
In the third step the search is made using ai where i varies from 2 to 7 and the minimum is stored at the starting of the search range i.e., at a2.
Thus, during first search i varies from 0 to 7
During second search i varies from 1 to 7
During third search i varies from 2 to 7 and so on.
It may be noted that during every search the control traverses from a specific starting point till the end of the array. Each of these traversal is called a pass. If number of elements to be sorted are ‘n’, then a minimum element is searched during every pass, using a counted loop structure as follows:
Also it may be noted that here it is necessary and sufficient to search for the position value where the minimum exist. During the first pass or iteration j has to be 0 (zero), during second pass or iteration j has to be 1, during third pass or iteration it has to be 2 and so on. After finding a minimum it has to be exchanged with the first element in that particular search range. Noting that during every iteration or pass j indicates the starting point of the present search range. We may use a statement like aj = minimum to put the minimum at its proper position. Thus the technique discussed till now can be pictorially shown in the form of a flowchart as follows.
/* Sorting the given set of elements in ascending order using
selection sort */
#include<stdio.h>
#include<conio.h>
main()
{
/* declaring variables */
int a[20], n, i, j, posmin,temp;
clrscr();
printf(“Enter the number of elements
”);
scanf(“%d”, &n);
printf(“Number of elements = %d
”,n);
printf(“Enter the elements
”);
/* Accepting elements */
for(i=0; i<n; ++i)
scanf(“%d”, &a[i]);
/* Printing elements */
printf(“
Given list of elements
”);
for(i=0; i<n; ++i)
printf(“%d ”, a[i]);
for(j=0; j<n-1; ++j)
{
posmin=j;
for(i=j+1; i<n ; ++i)
if(a[i]<a[posmin])
posmin=i ;
temp=a[j];
a[j]=a[posmin];
a[posmin]=temp;
}
/* Printing sorted array */
printf(“
Sorted list of elements
”);
for(i=0; i<n; ++i)
printf(“%d ”, a[i]);
}
EXERCISES
- Develop a flowchart to find the smallest element in a given set of elements. Code the same using C.
- Develop a flowchart to find the first biggest and the second biggest elements in a given set of elements. Code the same using C.
- Develop a flowchart to compute the average of given set of integers (both +ve and -ve) and to count the numbers above the average and below the average. Code it using C.
- Develop a flowchart to check whether a given set of elements is sorted or not with suitable messages. If sorted, print the order in which it is sorted. Code the same using C.
- It is necessary to prepare a merit list of 100 students given their total marks. Develop a flowchart for the same and code it using C.
- Develop a flowchart to compute the row sums of a given matrix and code it using C.
- Develop a flowchart to compute the column sums of a given matrix and code it using C.
- Develop a flowchart to convert a decimal integer number into binary number. Code the same using C.
- Develop a flowchart to generate a square matrix of given order with
- i) 0's as principal diagonal elements.
- ii) 1's as upper diagonal elements.
- iii) -1's as lower diagonal elements of the matrix.
- Develop a flowchart to insert a given integer element into its proper position in a given sorted array. Code the same using C.