3
ARRAYS
In this chapter we will be concerned with non-primitive data structures that are linear. A number of possible storage representations for these linear structures are available. We will concentrate here on array structures only. Others will be discussed in the succeeding chapters.
3.1 LINEAR ARRAYS
An array is an ordered set that consists of a fixed number of identical type of objects. No deletion or addition operations are performed on arrays. At best, elements can be changed to a value that represents an element to be ignored. The setting of an element in an array to zero means to delete it. The storage representation of array structure is based on sequential allocation
An array can be considered as the computer's set of pigeon-holes. Each hole, or element, has the same attributes (i.e. it can hold the same amount of like information, and has the same name). An array can be used to hold a table of information — for example, a set of parameters — or a series of similar results.
The simplest data structure that makes use of computed addresses to locate its elements is the one-dimensional array, which we have called a vector. Normally, a number of (contiguous) memory locations are sequentially allocated to the vector. Assuming that each element requires one word of memory, an n-element vector will occupy n consecutive words in memory. A vector size is fixed and, therefore, requires fixed number of storage locations.
Arrays occur in our daily life, where they are called tables. For example,
(a) A table of train departure time is an array. If we call the array DEP, we can denote the departure time of the i-th train by DEPi (this terminology is borrowed from mathematics).
(b) A table of the number of days in each month is an array. If we call this array NDAYS, we can denote by NDAYSmay, the number of days in May.
3.2 ARRAYS IN C
Arrays are a data type that is used to represent a large number of homogeneous values. C language allows both single-dimensional arrays as well as multidimensional arrays. It is an important property of an array that every element has the same type. Arrays may be of stroage class automatic, external, or static, but not register. The general format for a single-dimensional array is
type_specifier variable_name[size];
For example, to create an array called ‘A’ with ten integer elements, we can declare it as follows.
int A[10];
The indexing of array elements always starts at 0. Thus the above array reserves memory locations that are referred to by A[0],A[1],…,A[9]. This is one of the characteristics of the C language.
A typical array declaration allocates memory starting from a base address. The array name is in effect a pointer constant to this base address. To store the elements of the array, the compiler assigns an appropriate amount of memory starting from a base address. The elements of an array are accessed using a subscript, also called an index. We can write A[i] to access an element of the array. More generally, we may write A[expr], where expr is an integral expression, to access an element of the array. The value of the subscript must lie in the range 0 to size-1 if the declaration of the array is of the form A[size]. An array subscript value outside this range will cause a run-time error. This is a common and serious programming error which must always be avoided since it will cause the program to fail.
Arrays of all types are possible, including arrays of arrays. Strings are just arrays of characters, but they are sufficiently important to be treated separately. We may have an array of any type: int, char, float, double, another array, a structure, a union, or a pointer to any type. The size of the array must be a constant. The following example will illustrate the idea:
#define SIZE 25 int A [SIZE+1];
To illustrate the concept of an array, let us write a program that fills an array, prints out values, and sums the elements of the array.
Example 3.1
#include <stdio.h>
#define N 5 /* Size of array */
main( )
{
int A[N]; /* Space for A[0].........A[4] is allocated */
int j,sum=0;
for(i=0; i<N; i++) A[i]=i*i; /* Initialize the array */
for(i=0;i<N; i++) /* Display array elements */
printf(“ A[%d]=%d”, i, A [i] );
for(i =0; i <N; ++i) /* Find total */
sum + = A[i];
printf (“
sum=%dn/n”, sum);
return;
}
Output: The output of this programme is
A[0]=0 A[l]=l A[2]=4 A[3]=9 A[4]=16
sum = 30
Consider an election contested by four candidates. Let us write a program to read the ballots and count the votes cast for each candidate. Assume that the candidates are numbered 0 to 3 and each ballot is presented as a line of input containing one of these members. Assume that there are n number of ballot papers.
Example 3.2
# include < stdio.h>
# define N 50
main ( )
{
int ballot;
int count0 =0,countl= 0;
int count2=0, count3 =0;
int i, invalid = 0;
for (i = 1; i < = N; i ++)
{
scanf (“ %d”, & ballot);
switch ( ballot)
{
case 1: countO ++;
break;
case 2: countl ++;
break;
case 3: count2 ++;
break;
case 4: count3 ++;
break;
default: invalid ++;
}
}
printf (“Candidate-1 :% d
”, count0);
printf (“ Candidate-2 :% d
”, count1);
printf (“ Candidate-3 :% d
”, count2);
printf (“Candidate-4 : %d
”, count3);
printf (“Invalid votes : %d
”, invalid);
return;
}
You might feel that this solution is rather clumsy. Imagine how much worse it would be if the program were modified to handle ten or fifty candidates. We observe that the variables count0, count1, count2, count3, and so on are used in exactly the same way, however, we have a clue for better solution. Let us rename the variables count0 as count [0], countl as count [1], and so on. The variables now form an array, with a single variable count. Thus we can rewrite the program as in Example 3.3.
Example 3.3: The modified program is listed below.
#include <stdio.h>
#define N 50
#define NCANDIDATES 4
main( )
{
int i, count [NCANDIDATES], ballot, invalid = 0;
for(i =0; i<4; i++) /* Initialize all vote count */
count[i]= 0;
for(i = 1; i < = N; i++)
{
scanf( “% d”,, &ballot); /* Read a ballot */
/* Add 1 to the chosen candidate's vote count unless
ballot is invalid */
if(ballot > 0&& ballot<5) count[ballot - 1]++;
else
invalid++;
for(i = 1; i <= NCANDIDATES; i++)
printf ( “Candidate % d obtained %d n”, i, count [--i] );
printf( “Invalid vote count; %d”, invalid);
}
}
Note that the refinement of ‘Initialize all vote counts to 0’ is a loop that assigns 0 to each element of count in turn. The use of NCANDIDATES makes the program more flexible. If the program had to be modified to handle more contesting candidates, then only the define statement needs to be altered. This is also true for the n if the number of ballot papers need to be modified. The above program is much more elegant and moreover, requires no modification if the number of candidates is changed. It also highlights the utility of arrays instead of using a number of variables.
3.3 INITIALIZING ARRAYS
A definition of an array reserves one or more cells in internal memory and associates a name with the cell or cells that the programmer can use to access the cells. An array, like a variable, can be initialized at definition time. A static or extern array can only be initialized in the definition. The initial values are enclosed in braces and separated by commas. For example, the following definition
static int marks[4]={55,67,92,45};
creates and initializes the array marks as shown in Fig. 3.1 below.
Fig. 3.1 Array marks with values
Note that we can ignore the integer within the brackets if we define and initialize the static or extern arrays. The compiler will allocate exactly as many cells as are needed to store the initial values. Thus the above example can also be written as
static int marks[ ] = {55,67,92,45};
If, in a definition, we specify fewer initial values than the number of cells, the cells beginning with the first will be initialized with the given values. The rest of the cells will be initialized to zero. It may be an error to supply more initial values than there are cells. For example, the following statement will create and initialize values as shown in Fig. 3.2.
Fig. 3.2 An array cost with float values
A set of ten readings is stored in an array number. Write a program to check whether each reading is positive or negative. Add all positive readings and store the resulting Sum variable.
Example 3.4
#include<stdio.h>
main( )
{
static int number[10]={50,-30,20,70,-25,19,18,78,-
225,719};
intSum=0,i,j=0;
for(i=0,i<10;i++)
if(Number[i]>0)
{
Sum+=Number[i];
j++;
}
printf(“Total positive number %d Sum: %d”,
j, Sum);
return;
}
The symbolic name ‘Number’ here denotes the name of the array. The array is initialized with ten values. The ‘for’ loop contains an ‘if’ statement to test for the positive values in the array. Finally the ‘Sum’ will hold result and j will store the total number of positive values in the given array.
3.4 INSERTION AND DELETION
These two operations are often required in the applications of array processing. Insertion refers to the operation of adding another element to a linear array, and deletion, on the other hand, performs the operation of removing one of the elements from the array. This section deals with C programs for insertion and deletion operations.
Inserting an element at the end of the linear array can be easily performed, provided the memory space is available to accommodate the additional element. If we want to insert an element in the middle of the array then it is required that half of the elements must be moved rightwards to new locations to accommodate the new element and keep the order of the other elements. Similarly, if we want to delete the middle element of the linear array, then each subsequent element must be moved one location ahead of the previous position of the element. The deletion operation is somewhat simpler if we want to delete the last element of the array. The problem of insertion and deletion is more complex if we want to add or delete the first element of the array. Thus we conclude that if many deletions or insertions are to be made in a collection of data elements, then a linear array may not be the most efficient way of storing the data.
We now present two example programs in Example 3.5 and Example 3.6 for inserting and deleting an item ‘Item’ in an array ‘Linear’.
Example 3.5
#include <stdio.h>
/* Inserting an item at Kth position of an
array,where K<=N */
#define N 100
#define P N*2
main( )
{
int Linear[P], K, item;
int i; /* Loop index */
/* Read elements in an array */
for(i=0; i<N; i++)
scanf (*%d", &Linear[i]);
printf(“
Enter the position and item
” );
scanf (“%d %d”, &K, &item);
/* Insert an element in the array */
i=N-1;
while(i>=K)
{
Linear[i+1] = Linear[i];
i++;
}
Linear[K] = Item;
N++;
/* Print the array */
for( i=0; i<=N; i++)
printf( “
Linear[%d] =”, Linear[i] );
}
Example 3.6
/* Example program for deleting an element from an array*/
# include < stdio.h>
# define N 100
# define P 2*N
main ( )
{
int Linear[P], Item, i, k;
/* Read elements in an array*/
for(i=0; i<N; i++)
scanf(“%d”, &Linear[i] );
printf(“
Enter the position
”);
scanf (“%d”, &K);
/* Delete an element from the array */
Item = Linear[k];
for(i=k; i<N-l; i++)
Linear[i] = Linear[i+1];
N--;
for(i=0; i<N; i++)
printf(“
Linear [%d]=”, linear [i]);
return;
}
Example 3.7: Suppose an array of 10 integer values is given. Find the content of the array on execution of the following program.
#include < stdio.h >
main( )
{
int A[10], i;
for(i=0; i<10; i++)
scanf (“%d”, &A[i] );
for(i = 0, i< 9; i++)
A[i+1] = A[i];
for (i=0; i<10; i++)
printf ( “
A [%d] =”, A[i] );
return;
}
3.5 MULTIDIMENSIONAL ARRAYS
The arrays discussed so far are called one-dimensional arrays, since each element in the array is referenced by a single subscript. A vector in mathematics can be represented by a one-dimensional array, and a matrix by a two-dimensional array. Most programming languages allow two-dimensional and three-dimensional arrays by two and three subscripts. In C language we can use the higher number of dimensions for an array. The general form of a two-dimensional array declaration in C is as follows:
type_specifier Variable_name[Rows] [Columns];
For example, the following is a two-dimensional array A of integer type with m rows and n columns.
int A[m] [n];
It is assumed here that m and n have already been defined with #define compiler directive. Each element is specified by a pair of integers ( such as j, k) called subscripts, with the property that
0 <= j<= m - 1 and 0 <= k =< n - 1
There is a standard way of representing a m × n two-dimensional array A where the elements of A form a rectangular array with m number of rows and n number of columns.
The element A[j] [k] appears in row j and column k. Fig. 3.3 shows the array A which has 3 rows and 4 columns.
Fig. 3.3 Two-dimensional array
We illustrate the procedure for reading and writing a two-dimensional array with the following example program given in Example 3.8.
Example 3.8
#include<stdio.h>
#define ROW 5
#define COLUMN 6
main( )
{
Int A[ROW][COLUMN], i, j;
/* Read the array A*/
for( i = 0; <ROW; i++)
for(j = 0; j<COLUMN; j++)
scanf(“ % d”, & A[ ROW ][ COLUMN]);
/ * Print the array elements */
for(i=0; i<ROW; i++)
{
for( j= 0; j< column; j++)
printf(“A[%d] [%d]”, A [ ROW ] [ COLUMN]);
}
}
As mentioned earlier, C language allows arrays with more than two-dimensions. For example, a three-dimensional integer array is defined as
int x[3] [2] [5];
An array element x [1][2][3] specifies second plane, the first row, and the fourth column number. For example, an array of marks of a student in a particular class number might be indexed as
int A[class_no] [roll_no] [marks];
If we want to refer to an element of the array A, three subscripts are required. The number of elements in an array is the product of the ranges of all its dimensions. The array x may contain 3×2×5 = 30 elements. In general, if we multiply together the numbers of brackets in the definition of an array, we will obtain the total number of memory locations that would be necessary for storing all the elements.
In general, an n dimensional array A is denoted by A[S1] [S2]…[Sn] and subscript limits by 0<S1<=U1,0<S2<= U2,…,0< Sn<=Un, where U1,U2, and so on indicate upper bounds on its subscript. The array will be stored in memory in a sequence of memory locations. Specifically, the programming languages will store the array A either in row-major order or in column-major order. In row-major order, the last subscript changes first, the next-to-last subscript second, and so on. In case of column-major order, the first subscript varies most rapidly, then the second subscript, and so on. Suppose that B is an n-dimensional array declared by:
int B[I1]B[I2]…[In];
where I1, I2, and other are declared as the ranges of first dimension, second dimension, and so on. The base (B) is the address of the first element of the B array, that is, B[0][0]…[0]. Assume that the array B is stored in row-major order and each element of B reserves m bytes. Thus the address of B[il] [i2]…[in] is written as follows:
base (B) + m * [i1 * i1 *…* in + i2 * i3 * i4 *…* in+…+ in]
The number of elements in the array B is the product of I1*i2*…*in. For example, an array X with seven subscripts is declared as
int X [7] [15] [3] [5] [8] [2] [2];
The number of elements array X contains is 7×15×3×5×8×2×2=50,400. In C an integer reserves two bytes and X array stores 50,400×2 bytes.
3.6 ROW-MAJOR AND COLUMN-MAJOR ORDER
Memory storage locations are not arranged as a rectangular array of elements with rows and 2 columns. Instead, they are arranged in a linear sequence beginning with location 1, and then 2,3,…. For this reason, there must be some manipulation behind the screen when a program requests the entry in the 3rd row and 4th column of a two-dimensional array. Essentially, the desired coordinates must be transformed into an address in this linear sequence of memory location. The nature of the transformation is dependent upon how the programming language will store the two-dimensional array. It will store the array either (i) column by column or (ii) row by row. The first one is called column-major order whereas the second one refers to row-major order. Let A be a two-dimensional array having 3 rows and 4 columns. Then the 12 entries of the array are stored as indicated in Fig. 3.4.
Fig. 3.4 Linear storage of data in row-major order
According to this arrangement, the first row would take up the first four locations in the list allocated for the array, the second row the second four locations, and so on. This arrangement is called row-major order. The element in the 3rd row and 2nd column, will in fact, be located in the 10th position within the list. In this two-dimensional array, the ith row and jth column must be transformed into the following position in the list according to C-language.
[4*(i-1) + (j-1)]th
In general, if N is the number of columns in the array, then the entry in the ith row and jth column is given as the
[N * (i-1) + (j-1)]th
Similarly, Fig. 3.5 indicates the approach for storing elements in the column-major order.
Fig. 3.5 Linear storage of data in column-major order
To access the entry in the ith row and jth column of a two-dimensional array stored in column-major order, the transformation N1 × (j-1) + i +1 is required, where N1 represents the number of rows in the array.
Let us consider a problem . An array A has 25 rows and 4 columns. Suppose the two-dimensional array is stored in column-major order.
Then the position of A[3][2] may be computed as
25 × (4-1) + 2-1=75+1=76
Note that C language stores two-dimensional arrays using row-major order. An n-dimensional (P1 × P2…×Pn) array C is a collection of P1, P2…, Pn data elements in which each element is specified by a list of n number of integers, say k1, k2,…,kn called subscripts with the following properties:
0<=k1<P1, 0<=k2<P2,….Ο<=kn<Pn
The element of C with subscripts kl,k2,…kn will be denoted by
Ck1k2…kn or C[1][k2]…[kn]
The array will be stored in memory in consecutive locations. The programming language will store the array C either in row-major order or in column-major order. In row-major order the elements are listed in such a way that the last subscript varies first, the next-to-last subscript varies second, and so on. In the column-major order, the elements are listed so that the first subscript varies first, the second subscript second, and so on. Suppose C is a three-dimensional 2x4x3 array. Then C array contains 2×4×3=24 elements. Figs. 3.6(a) and Fig. 3.6(b) indicate the arrangements in column-major order and row-major order, respectively.
Fig. 3.6 Arrangement of C array
Consider an array A to be an n × n square matrix. The value n is defined as a constant. We need to write a program which will do the following:
(a) Find the number of non-zero elements in A.
(b) Find the sum of the elements above the diagonal.
(c) Find the product of the diagonal elements.
A program code in C is given in Example 3.9.
Example 3.9
# include < stdio.h>
# dwfine n 3
main ( )
{
int A[n][n],i,j;
int Number=0, Sum=0, Product=l;
/* Read elements of the array — A*/
for(i=0; i<n; i++)
for(j=0; j<n; j++)
scanf( “%d”, & A[i][j] );
/* Write the array - A */
for(i =0, i<n, i++)
{
for( j=0; j<n; j++)
printf( *A[%d] [%d]', A[i][j] );
printf(“
”);
}
/* Search for non-zero elements */
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(A[i][j])
Number++;
/* Sum of elements above diagonal */
for(j=l; j<n; j++)
for(i=0; i<j; i++)
Sum + = A[i][j];
/* Product of diagonal elements */
for( i=0; i<n; i++)
Product * = A[i][i];
printf( “
Number = %d
Sum =%d
Product = %d
”. Number, Sum, Product) ;
}
Sample Input:
1 2 3
A[3] [3]= 4 0 6
7 8 9
Output:
Number = 8
Sum = 11
Product = 0
The program in Example 3.10 prints the elements of a two-dimensional array in row-major and column-major order.
Example 3.10
# include <stdio.h>
main ( )
{
int Temp[5][4],i,j;
/* Read the array Temp */
for( i=0 ; i<5; i++)
for( j=0; j<4 ; j++)
scanf ( “ %d”,, &Temp[i][j]);
/* Print the array Temp in row-major order */
for( i=0 ; i<5 ; i++)
for( j=0 ; j<4 ; j++)
printf( “ %d
”, Temp[i][j] );
/* Print the array Temp in column-major order */
for(j=0; j<4; j++)
for( i=0 ; i<5 ; i++)
printf( “%d
”, Temp[i][j]) ;
}
A program to illustrate the idea of lower-triangular matrix and tridiagonal matrix is given in Example 3.11. A square matrix is a lower-triangular if non-zero elements are below the diagonal. In case of a tridiagonal matrix, all elements of the square matrix other than those on the major diagonal and on the diagonal immediately above and below this one are zero. For example, an n-square tridiagonal array B has n elements on the diagonal, n-1 elements above, and n-1 elements below the diagonal. Thus B contains almost 3n-2 non-zero elements.
Example 3.11
/* This program tests the input matrix to find whether it is
a lower triangular matrix or a tridiagonal matrix */
# include < stdio.h >
main ( )
{
int i,k,1,n,p,r,x,mat[25];
printf( “
Give the order of the matrix: ”);
scanf( “%d”, &n);
printf( “
Enter the elements of the matrix:
”, );
p = n* n;
for( i=0 ; i<p ; i++)
scanf( “%d”,, &mat[i]);
1=1; r=0; i=l;
while( i <= ( p - n) )
{
i+= r;
while (i<n*l)
{
if( mat[i]!=0 )
{
printf( “
It is not a lower triangular matrix */” );
i=p;
}
i++;
}
i++;
r++;
1++;
}
if ( i == p-n+1)
printf ( “
It is a lower triangular matrix
”; );
k = 1 ; i = 2 ;
while(i<p-l)
{
while( k<= 2)
{
if( mat[i] )
{
printf( “
It is not a tridiagonal matrix,
” );
i = p - n ; k = 3 ;
}
k++, i++;
}
i=i+n-l; k=l;
}
k++; i ++;
}
i=i+n-l; k=l;
}
if( i== p+1)
printf ( “
It is a tridiagonal matrix
”) ;
}
We now present more examples on arrays.
Example 3.12: Given is a decimal number, find its binary equivalent and the number of l's in the binary number.
/* Decimal to binary conversion and */
/* Counting of 1's in the binary number */
# include < stdio.h>
# include < math.h >
# define SIZE 20
main ( )
{
int result[SIZE], num, temp, count, tag;
printf( “
Enter the decimal number :”);
scanf( “%d”,, &num );
/* Find the binary number */
for( count =0, count <SIZE ; ++count )
{
temp = num /2;
result[count] = num % 2;
num = temp;
if( temp = = 0 )
{
tag = count;
break ;
}
}
/* Print the result */
printf( “
The binary number is :”);
for( count = tag ; count > = 0 ; -- count )
{
printf( “%d, result[count]);
if( result [count] == 1 )
temp+= 1;
}
printf( “
There are %d l's in the binary number ”, temp );
}
We now explain the above program through the following tables. Assume that inputis 910
Table 3.1
Table 3.2
Example 3.13: Write a program to generate pascal triangle for a given number of rows. The output is given in the following form:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
: : : : :
/* Generate Pascal triangle */
# include < stdio.h >
# include < math.h >
main ( )
{
int h, t[40] [40], i, j;
printf( “Enter the height of the Pascal triangle:”);
scanf( “ %d”, &h );
t[0][0]= 1;
printf( “ % 6d”, t[0][0] );
printf( “
” );
for( i =1 ; i< h ; i++)
{
t [ i ] [ 0 ] = 1;
printf ( “ % 6d”, t [ i ][ 0 ] );
for( j = 1 ; j < = i; j++)
printf( “
”);
}
}
This program generates a Pascal triangle of height h, given as input. The triangle here is a right-angled triangle. The first column consists of number 1 and the rightmost column also has a number 1. The intermediate rows and columns consist of numbers whose values are de-termined by the following formula:
t [i] [j] = t [i-1] [j] +1 [i-1] [j-1]
The first row has only one number, that is, 1, so it is printed separately. The other rows are printed in a nested for loop. The variables i and j start from 1 since ‘for loop’ prints output from second row and other rows are generated using the formula.
Example 3.14: Write a program to obtain the secondary numbers by progressively cancelling the numbers from a list of integers 1,2,3,…, n which are multiples of 2 in the first pass, multiples of 3 in the second pass, and so on. The process will continue until there are less numbers in the list than the specified pass.
/* Generate secondary numbers from a list */
# include < stdio.h >
# include < math.h >
main ( )
{
int n, a[200], i, j, z;
printf( “ Enter the number:”);
scanf( “%d”, &n );
printf ( “
Write the numbers from 1 to n:”);
for( i=0; i<n; i++)
printf( “ %3d”, a[i]=i );
printf( “
” ) ;
a[ i+1] = 0 ; /* The last position is used as */
/* a sentinal value */
for( j =2 ; j <= sqrt( n ) ; j++)
{
i = j ;
while( a [i]!= 0 )
{
z = i;
while( a [z]!= 0 )
{
a[z]= a[ z+1];
z = z +1;
}
i = i + j -1;
}
}
printf( “
”) ;
printf{ “The secondary numbers are
”);
i = 1;
while( a[i] ! =0 )
printf( “
”, );
printf( “ The secondary numbers are
”,);
i = 1;
while( a[i] ! = 0 )
{
printf( “ %3d”, a[i]);
i++;
}
printf( “
” );
}
Input: Enter the number:10
Output: Write the numbers from 1 to n
1 2 3 4 5 6 7 8 9 10
The secondary numbers are
1 3 7
Example 3.15: A pair of positive numbers is said to be AMICABLE if the sum of the divisors of the first number is equal to the second number and the sum of the divisors of the second num-ber is equal to the first number. The divisors should include 1 but leave the number itself. Write a program to find if a pair of numbers num [0] and num [1], as input, are AMICABLE or not AMICABLE.
# include < stdio.h >
# include < math.h >
/* AMICABLE NUMBERS */
main ( )
{
int num[2], sum [2], i, j;
printf( “
Enter the two numbers to be tested” );
scanf( “ %d %d”, &num[0], &num [1] );
sum[0] = 1 ; sum[1] = 1;
for( i=0, i<= 1 ; i++);
{
/* Search for factors */
for{ j = 2 ; j <= num[i] /2 ; j++)
if( num[i] % j == 0 )
sum[i] + = num[i] / j;
}
If ( num[0] = = sum[1] & & num[1] <= = sum[0] )
printf( “
The numbers are AMICABLE : %d, %d”, num
[0], num[1] );
else
printf( “
The numbers are not AMICABLE”, );
}
At the beginning, the program prompts for two inputs. Next, the factors of each number are found using ‘for' loop. The number whose factors are to be calculated is divided repeatedly with 2, 3, 4,…, upto num [i] /2 where num [i] stores two numbers (i =0 and i = 1). If there is no remainder then the quotient is added to the variable sum [i] at the end of the second ‘for loop.' The first ‘for loop' is used to find sum [i] twice for i = 0 and i= 1, since two numbers have been taken as input. Lastly, we test for the amicability of the two numbers. It should be noted that the sum of factors of a number should exclude the number itself. Also since 1 is a factor of every number, so sum [i] is assigned a value 1 initially for i=0 and i= 1.
Example 3.16: Write a program to sort the list of 100 vouchers in their increasing order of voucher numbers. Also trap and list out the in-between missing voucher numbers.
# include < stdio.h >
/* Sorting of 100 vouchers in ascending */
/* order of sequence */
main ( )
{
int i, j, Vno[100], temp;
for( i=0 ; i < 100 ; i++)
scanf ( “%d”, &Vno[i] );
for( i =0 ; i < 99 ; i++)
for( j = i + 1 ; j < 100; j++)
if( Vno[i] > = Vno[ j] )
{
temp = Vno[i];
Vno[ i] = Vno[j];
Vno[ j] = temp;
}
temp = Vno[0];
for ( i =1 ; i < 100 ; i++)
{
while ( temp < Vno[i] )
{
printf ( “ % d
”, temp + 1 );
temp++;
}
temp=Vno [i];
}
}
Example 3.17: The three numbers 192,384, and 576 are called triad numbers since they have the following properties:
(a) Each is a three-digit number.
(b) Each of the digits 1,2,…, 9 occurs only once in all the three numbers.
(c) The second number is twice the first and the third number is three times the first. Write a program to find all triad numbers below 1000.
# include < stdio.h >
/* Triad numbers */
main ( )
{
int a [q], p, i, r, j;
int H, T. U, X, flag;
printf( “
Triad numbers are
” );
for( i=123 ; i<= 329 ; i++)
{
flag = 0;
for( P = 0 ; P< q ; P++) /* Initialize with zeroes */
a [P] = 0;
for( j = 1 ; j <3 ; j++)
{
x = j * i;
H = x/100;
r = x % 100;
T = r / 10;
U = r % 10;
if( H != 0 & & T != 0 && U !=0 )
{
a [H-1]= H;
a [T-1]= T;
a [U- 1]= U;
}
}
for( P =0 ; P<q ; P++)
if( a [p] == 0
flag = 1;
if( ! flag )
printf( “ i = %d, i*2 = %d, i*3 = %d
”, i, i * 2, i * 3 );
}
}
This chapter described the representation of linear data structure by using one of the methods of sequential allocation storage. Other methods will be discussed later. Although this method of allocation is suitable for certain applications, there are many other applications where the sequential allocation method is unacceptable. This chapter illustrated initially the representation of arrays in C language. Next, the different operations on arrays were given and explained the process for initializing elements in the array. Finally, multidimensional arrays and the concept of row-major order and column-major order were introduced. Examples are given to illustrate different methods.
E
XERCISES
1. Why is an array preferred instead of using a number of variables?
2. Write a program to initialize an array letter [26] with twenty-six uppercase characters.
3. What is the error in the definition statement?
static int s[3]={l,2,3,4,5};
4. Write a program to find the kth smallest element in an array number [n], where n and k are given as input.
5. A company has four salesmen A,B,C, and D. They returned sales order at the end of each day. There is a possibility that some of the orders may not be returned by the salesmen. Write a C program to find the missing orders at the end of a particular day. Assume that there are n number of sales orders to be processed during a day.
6. In an examination there are four subjects — Subject 1, Subject 2, Subject 3, and Subject 4. In a particular year, 1000 students sat for the examination. Write a program to read marks for each student and calculate total marks obtained by each student.
7. Assume that an array A has n numeric values. Write a C function to calculate arithmetic mean or average x of the values x1,x2…xndefined by
x = (x1 + x2+…+ xn)/n
8. An automobile company uses an array, items, to store the number of automobiles sold each year starting from 1983 to 1997. Write a C program for each of the following tasks:
(a) To find total sale for all the items.
(b) To print the years in which maximum items were sold.
(c) To print the years in which minimum items were sold.
9. Professor Guess lives in a hostel where the rooms are sequentially numbered from 1. It is interesting to note that the sum of the room numbers before the professor's room number is equal to the sum of the room numbers after his room number. Write a C program to print all the room numbers starting from 1 to the last room number of the Hostel and store these numbers into an array, called Hostel.
10. A magic square is a NxN matrix with each element being an integer from 1 to n-square and the sum of each row, column, and the two main diagonals being the same. Here is a magic square of N = 3:
6 1 8
7 5 3
2 9 4
Write a C program to generate and print a magic square for a given N, which should be odd.
11. The following table shows the average rainfall of a city month-wise during a year.
Determine the following:
(a) Which months have an average rainfall less than 4 centimeters?
(b) Which months have the highest and which has the lowest average rainfall?
(c) What is the average rainfall during the months June to October?