CHAPTER 8
Solving with Modules
In order to solve a problem, with or without using a computer, one has to know the procedure or the method of solving the problem. Once the method is known, to solve the problem using a computer, it has to be coded using some computer language. These codes which have the method of solving a problem embedded within them are called computer programs. During the early days of programming, programmers used to write a single program to solve a problem completely, regardless of the fact how much big they are. This style of writing complete programs having a continuous sequence of computer codes is generally known as procedural programming. As the days passed by programmers started facing problems like error fixing, eliminating errors, logic checking etc., particularly with the larger programs. Here, a larger program means a program having too many code lines. As a result those programmers used to spend lot of time in identifying the errors and correcting them. The process of finding out the errors and correcting them is known as debugging. In order to circumvent such time consuming debugging activities, they naturally thought of dividing larger programs into smaller and independent segments called subprograms and to solve the given problem part by part. Developing subprograms was possible because a number of problems naturally permit their division into smaller and independent ones. Almost all the present computer languages provide facilities using which these subproblems can be coded, tested and used.
For example, consider the problem of finding mean, variance and standard deviation of a given set of numeric elements (discussed in Section 6.6). Though this is not a very big problem, it is considered here as the idea of subproblems and hence the concept of subprograms can be grasped very easily. A careful study of this problem indicates that it may be divided into three smaller problems, viz., finding the mean, finding the variance and computing the standard deviation. In order to solve the complete problem, independent small programs to find mean, to find variance and to compute standard deviation are first written, test run and finally put together in the main program. This strategy of dividing a problem into smaller ones and getting a solution to the entire problem by tailoring them together is called the Divide and Conquer strategy. This strategy has been already discussed very briefly in Chapter 1.
These independent programs of smaller problems which are a part of some bigger problem are called subprograms in FORTRAN, procedures in Pascal and functions in C.
Though many claim that the real power of C lies with pointers and its manipulation strategies, facilities available in C for the development of functions has also contributed significantly to its power and popularity. Developing independent functions provide certain additional advantages. Functions can be developed, tested and debugged independently as well as, if necessary, they can be used by others.
Functions are developed not only for subproblems of some larger problem, but are also written for smaller problems that are very frequently used.
The style of developing complete programs with the aid of smaller functions is generally known as functional programming. It may be noted that C is not a functional language.
One or more interrelated independent functions, after testing, can be stored in a separate file. Such files are called modules. These files are used, by including them in a proper directory, as and when they are required. This technique of developing individual modules and using them as and when required is known as modular programming. Modular programming is one of the very popular current software development practices.
This chapter discusses some examples, which involve the development of one or more functions and using them in a main program. Many of these examples have been already discussed in earlier chapters and have been reconsidered here for the sake of better understanding. The important aspect one has to really understand in this chapter is to “know when an user defined function is called from another function, how the program execution control goes to the called function and comes back to the calling function.” These control flow paths have been visually shown using thin dotted lines with arrowheads on flowcharts. These arrowheads indicate the direction of control flow. Also, in this chapter, with some examples, certain additional information about C beyond the scope of C-Tips have been presented in a section called … beyond.
8.1 FUNCTION TO PRINT A LINE MADE UP OF ONLY HASH (#) CHARACTERS
As one could see this is not a very big problem. A simple program for this problem could be written straight away. Yet, development of a function for this is recommended as one might need to print hash lines quite often. In other words, functions are not only written for independent parts of a larger problem but are also written based on its frequency of usage, i.e. the utility.
The Method
Normally a line on a display will be made up of 80 characters. In this example 80 hash (#) characters are printed in a line using a printf( ) function. Note that printf( ) itself is a C library function, which is put into use by including the <stdio.h> file in the beginning. Though, developing flowcharts for such a simple example is not a necessity, they have been developed for the sake of continuity. These flowcharts will really help in understanding how the link between a function and the one which uses that function gets developed.
C-Tips
Though, theoretically, functions can physically appear either before or after the main ( ) function, the normal practice is to place the functions after the main( ). Note that the word main is a C keyword and is used to name the main ( ) program. It is very important to note that:
- Every program should have a main ( ) function.
- The execution of a C program begins from the main( ) function and ends with the main ( ) function.
During the execution of the main( ), when the control comes across a function name, the corresponding function is invoked or called. Automatically, the program execution control goes to the called function. This shifting of the control takes place via the function prototype along with the arguments of the invoking or calling function.
Once the control shifts to the called function, the called function is executed as usual. After the execution of the called function, the control goes back to the calling function. Infact, the control goes back to the point on the called function from where the control had come to the calling function. The completion of the execution of a function is signaled by using one or more return statements in it.
A return statement can be used with an expression or without an expression associated with it as follows.
When a return statement without an expression with it is used, the control simply goes back to the calling function immediately after its execution. However, when a return statement with an expression is used, the associated expression will be first evaluated and then the control goes back to the calling function with the value of the expression. Though a return statement need not be present in a function, it is recommended to use one.
… beyond
As seen from the flowchart and the program that follows, there are no arguments associated with the function definition. As a result no arguments are used while calling the function from within the main( ) function. In other words, no parameters are passed from the calling function to the called function.
In this example, when the function is called, the control goes to the function, prints the required number of hash characters in a hashed line and returns back without any values. In other words, the function does not return any value. When no values are returned the function must be declared as of the data type void.
Every user defined function will have a name, optional list of arguments along with their data type, and the type of the value returned by the function. All these will appear in the first line of a function definition. This first line is called the function header. In this example void hashline ( ) is the function header. The pattern of this first line is known as the function prototype. In order to use a user defined function, its prototype must be included in the beginning of the function that intends to use it. A careful observation of the program that follows gives a clear idea about the function prototype, the position where it has to be included and the function body.
Flowchart
The Program
/* Printing a line made up of #(hash) characters using function */ #include<stdio.h> #include<conio.h> main() { void hashline(); /* Function prototype */ clrscr(); hashline(); /* Invoking the function hashline() */ } /* Function to print a line made up of # (hash) characters */ void hashline() /* Function definition made here */ { /* Function body starts here */ int i; /* Declaring local variable i */ for(i=0; i<80; ++i) printf(“#”); return; /* Returning control back to main() */ } /* Function body ends here */
8.2 FUNCTION TO MULTIPLY TWO GIVEN INTEGER NUMBERS
The Method
A function, multiply( ), for the multiplication of any two given integers, say x and y, is first developed. While developing functions it is assumed that the input values are readily available. In other words, generally functions do not deal with input statements. Thus, in this example, values of x and y are assumed to be available and hence the product is obtained using the relation product = x * y. Finally, this computed product is returned using a return statement. As this returned value is an integer value, the return type of the function should be declared as int.
Then the main program is written. The prototype of the function is included along with the declaration of other variables. The numbers to be multiplied are input. Let these numbers be numl and num2. The required product is obtained by invoking the function multiply ( ) in a statement of the form product = multiply (numl, num2). Invoking a required function is also referred to as calling the function. Finally the returned value, i.e. the product, is output.
C-Tips
The execution of the program begins from the main( ) function. When the control comes across the function name multiply(num1,num2), the control shifts to the function multiply(num1,num2). Along with the control the values of num1 and num2 are also passed on to the function. Infact, the values of numl and num2 will be copied on to the arguments of the called function. In other words, the values of num1 and num2 will be copied into the variables x and y respectively. With these values for x and y, the function multiply ( ) gets executed and the value of the variable product will be returned to the calling function, i.e. the main( ) function. The execution of the main( ) function resumes from the point from where it had gone to the called function.
… beyond
Within a function any required function is used by writing its name at the point required along with the arguments or parameters. Arguments or parameters that are used along with a function name in the calling program are called actual arguments or actual parameters. The arguments that are assumed to be available during a function definition are called formal arguments or dummy arguments: The names of the variables used as actual arguments and as formal arguments may be same or different.
In this example, different variable names have been used as actual arguments and formal arguments, deliberately. It must be noted that the number, type and order of the actual arguments and formal arguments must match. Other variable names used in the main ( ) function and in the user-defined function also could be either same or different. Ordinarily, variable names and the values associated with them are valid only within those functions in which they are declared. Such variables that are valid only in the function in which they are declared are called local variables. In this example, variables num1, num2 and product are local to the main( ) function and the variables x, y and product are local to the user defined function multiply( ). It may be observed that product is a local variable both in main( ) as well as in multiply( ) functions. This is permitted. Required memory locations for the variables num1, num2 and product are allocated under the main ( ) function. Similarly, required memory locations for the variables x, y and product are allocated under the multiply( ) function. Thus memory location allocated for the variable product in the main ( ) will be totally different from the memory location allocated for the variable product in the multiply( ). In C local variables are also called auto variables. By default, all variables are local variables.
The method of invoking or calling a function by using the function name along with real or actual arguments is known as call by name. When a function is invoked or called in this manner, formal arguments in the function header will get the values of the actual arguments. Infact, the values of actual arguments will be copied into the dummy or formal variable names as shown in the following figure.
This technique of calling a function by passing on the values to the dummy or formal arguments of the function via actual arguments is also known as call by value. It should be carefully noted that all the variables used here are single valued, i.e. scalars.
The multiply( ) function defined in this section is a function with two arguments and one return value.
Flowchart
/* Finding product of two numbers using function */ #include<stdio.h> #include<conio.h> main() { int numl, num2, product; /* Declaring the local variables */ int multiply(int numl, int num2); /* Function prototype */ clrscr(); printf(“Input two integer numbers ”); scanf(“%d%d”, &num1, &num2); /* Reading two numbers */ /* Printing two numbers */ printf(“Given two numbers are : %d and %d. ”, numl, num2); /* Calling the function multiply() */ product = multiply(numl, num2); printf(“ The product is : %d ”, product); } /* Function to multiply two given numbers */ int multiply(int x, int y) /* Function header */ { /* The body of the function begins here…*/ int product; /* Declaring local variable */ product = x * y; return (product); /* Returning product to main() */ } /* The body of the function ends here...*/
8.3 FUNCTION TO COMPUTE THE GCD OF GIVEN THREE NUMBERS
The Method
Finding the GCD of two given integers has been already discussed in Section 4.6. A function named gcd(int num1,int num2) is written first using the method discussed there. The flowchart and the program for this are given in the following page. It may be noted that the necessary input to the gcd function is passed on from the main ( ) function during the function call. The computed result is returned back using the return statement.
All the three given integers, say num1, num2 and num3, are input in the main ( ) function. The user defined function gcd( ) is called twice: once with num1 and num2 and next with the gcd of the first two integers and num3. A statement of the form result=gcd ( gcd (num1,num2) ,num3) is used for this purpose. After the execution of these statements, the gcd of the given three numbers will be available in the variable result.
C-Tips
As already mentioned the gcd( ) function is invoked or called twice. It may be noted that a function may be called or used any number of times. As it could be observed, here the function call is nested. First the gcd( ) is invoked with num1 and num2 as arguments. It may be observed that this call itself is an argument of the outer gcd ( ). After getting the gcd of num1 and num2, the function gcd( ) is once again called or invoked, now with the gcd ( ) of num1 and num2 as first argument and num3 as the second argument.
It may be observed that num1 and num2 have been used both as actual arguments as well as formal arguments. Whenever the gcd ( ) function is invoked, values associated with the actual arguments num1 and num2 will be copied onto the formal argument variables num1 and num2. The gcd ( ) function is a function with two arguments and one return value.
The Program
/* Finding gcd of three non zero integer numbers using function */ #include<stdio.h> #include<conio.h> main() { int numl, num2, num3,result; /* Declaring the variables */ int gcd(int numl, int num2); /* Function prototype */ clrscr(); printf(“Input three non zero integers. ”); scanf(“%d%d%d”, &numl, &num2, &num3); /*Reading three integer numbers*/ printf(“Given three integer numbers are: ”); printf (“numl = %d num2 = %d num3 = %d ” , numl, num2, num3 ); result = gcd(gcd(numl,num2), num3); printf(“GCD of %d, %d and %d is %d ”, numl, num2, num3,result); } /* Function to find the gcd of two integers */ int gcd(int numl, int num2) /* Function header */ { /* Function body starts here */ int rem; /* Declaring local variable */ rem = numl % num2; /* Computing remainder */ while (rem != 0) /* Repeat while remainder is not zero */ { numl = num2; num2 = rem; rem = num1 % num2; } return(num2); /* Return gcd to main()*/ } /* Function body ends here */
8.4 FUNCTION TO SUM FIRST N TERMS OF SINE SERIES EXPANSION AND TO TABULATE SINE VALUES FOR DIFFERENT ANGLES
The method to generate the different terms of the sine series and hence to find the sum of the generated terms has been already discussed in Section 4.11.
The Method
Assuming the values for the variable x of sin(x) and the value for ‘n’, the number of terms to be summed, the function sinevalue ( float x , int n) is developed. This function returns a float type answer. The sinevalue( ) function is repeatedly used for various values of deg in the main ( ) function in order to tabulate the sine values for different angles.
In the main( ), the value of n, the number of terms to be summed, and the value of a variable step are input. Different values of the angle (i.e. variable deg) beginning from 0 up to an upper limit, say 180°, are generated in given steps under the control of a for statement. The user-defined sinevalue( ) function is repeatedly called with each one of these generated angles. Every call gets back a value for sin(deg) from the user-defined sinevalue( ) function. The number of sin(deg) values ‘obtained back’ will be equal to the number of calls made. All these values are displayed or printed out as and when they arrive at the called function. The values for sin(deg) are also obtained and output using the C library function for the purpose of verification.
C-Tips
It is known that the value of sin(x) will be of float type. Hence the type of the returned value of sinevalue ( ) function has to be a float type value. Therefore, the function sinevalue ( ) has been declared as float type.
When the main ( ) comes across the name of the function sinevalue ( ), the control automatically shifts to the sinevalue ( ) function along with the values of the arguments. In other words, value of deg gets passed on to x and is copied onto it. Similarly, the value of ‘n’ in main( ) gets passed on to ‘n’ in the sinevalue( ) function. As the variables involved are scalars, i.e. single valued, the function is called by value.
/* Tabulating the results of the Sine function for different
angles */
#include<stdio.h>
#include<math.h>
#include<conio.h>
main()
{
int n, step; /* Declaring variables */
float deg, result;
float sinevalue(float x, int n); /* Function prototype */
clrscr();
printf(“Read number of terms to be added
”);
scanf(“%d”, &n); /* Accepting number of terms */
printf(“Read the step value in numeric degrees
”);
scanf(“%d”, &step); /* Accepting step value */
/* Calling function sinevalue() in printf statement */
for(deg=0; deg<=180; deg = deg+step)
{
result = sinevalue(deg, n);
printf(“sin(% 3.0f)=%f, %f
” deg, result, sin(deg * 3.14/180));
}
}
/* Function to calculate sine value of x upto n terms */
float sinevalue (float x, int n)
{
int i;
float term, sum=0; /* Declaring local variables */
x = x*3.l4/l80; /* Converting x value to radians */
term = x; /* term is initialized to x */
for(i = l; i <= n; ++i) /* Finding sum of n terms */
{
sum += term;
term *= -x*x/((2*i)*(2*i+l));
}
return(sum); /* Returning sum to main()*/
}
8.5 FUNCTIONS TO COMPUTE MEAN AND VARIANCE AND HENCE TO COMPUTE STANDARD DEVIATION OF GIVEN SET OF NUMBERS
The mean, variance and standard deviation are computed using the relations
The Method
Procedures to compute mean, variance and standard deviation using the above given relations have been already discussed in Section 6.6. Function meanvalue ( ) that computes the mean or average and returns, it is developed assuming that the entire array (say, a) and the information about the number of elements (n) are available. The value returned from this function will be of type float. Function varvalue( ) that computes the variance and returns its value is developed assuming that the entire array (say, a), information about the number of elements in the array (n) and the mean are available. The type of the value returned by this function will be of type float.
In the main ( ) the value for n, and all the ‘n’ elements of the array are input. The meanvalue( ) and varvalue( ) functions are called one after the other, in that order. The standard deviation is computed using the value of variance. Finally, the values of mean, variance and standard deviation are output.
C-Tips
As the mean of all the ‘n’ elements of an array (say, a), is to be found out, the array a and ‘n’ are taken as the formal arguments of the function to be defined. Also, as the type of the returned mean value will be of float type, the type of the defined function must be taken as of type float. Thus the function header and hence the function prototype have been taken as: float meanvalue(float a[ ], int n).
As the computation of variance needs an array (say, a), information about the number of elements in the array ‘n’ and the mean or average of all the array elements, all these three are taken as the formal arguments of the function developed to compute the variance. Since the type of the returned variance value will be of float type, the type of the defined function must be taken as of type float. Thus the function header and the function prototype of this function have been taken as:
float varvalue(float a[ ], int n, float avg)
… beyond
A careful study of the examples discussed till now in this chapter reveals an important fact that whenever user-defined functions are used, they are first recognized by their names and the values of their (actual) arguments are passed on and made as the values of the formal arguments of the invoked or called function. All the arguments or parameters used till now were scalars (i.e. single valued) in nature. It is important and interesting to note how arrays (i.e. multivalued variables) are handled during function calls. Here it may be recalled that when single valued variables are used as actual arguments as well as formal arguments, they will be local to their functions. Memory locations of these local variables will be allocated at the point of their declarations within their respective functions and hence will be different. Therefore, the values of actual arguments are transmitted or passed on and copied into formal arguments. But in the case of arrays, memory locations to the arrays are allocated only in the main function. When these arrays are used in user-defined functions the starting address of these allocated memory locations is transmitted or passed on to the user-defined functions. The C- compiler does this implicitly by passing on the address of the array to the called function. Thus the arrays inside user-defined functions will be accessing the same memory locations as that of the corresponding arrays in the main( ) and manipulating the values stored in them. The size of the array is explicitly mentioned only in the main( ) during its declaration in the main( ). It is not necessary to mention the size of the arrays explicitly in the function header, in the function prototype declaration as well as during the calling of a user-defined function. Also, it may be noted that the array names used in the calling function and the called function may be different. Even then they refer to the same memory locations. In other words, different array names pointing to same memory locations behave like alternate names, i.e. aliases.
/* Computing mean, variance and standard deviation of a given set of numbers using functions */ #in!clude <stdio.h> #include <math.h> #include <conio.h> main() { int i, n; /* Declaring variables */ float a[20], mean, variance, stdev; float meanvalue(float a[], int n); /* Function prototype */ float varvalue(float a[], int n, float avg); clrscr(); printf(“ Read value of n ”); scanf(“%d”, &n); /* Accepting n */ printf(“n = %d ”, n); printf(“Read elements of array ”); for(i=0; i < n; ++i) scanf(“%f”, &a[i]); /* Reading elements of array */ printf(“Elements are ”); for(i = 0; i < n; ++i) printf(“%f ”, a[i]); /* Printing elements of array */ /* Calling function meanvalue() to find the mean of given list of elements */ mean = meanvalue(a, n); /* Calling function varvalue() to find the variance of given list of elements */ variance = varvalue(a, n, mean); /* Computing standard deviation */ stdev = sqrt(variance); printf(“Mean = %f Variance = %f Standard Deviation = %f ”, mean, variance,stdev); } /*Function to compute mean */ float meanvalue(float a[], int n) { int i; float sum=0,mean; /* Declaring local variables */ for(i=0; i<n; ++i) sum += a[i]; /* Computing sum of all the elements */ mean = sum/n; /* Computing mean */ return(mean); } /* Function to compute variance */ float varvalue(float a[], int n, float avg) { int i; float sum=0, var; /* Declaring local variables */ for(i = 0; i < n; ++i) /* Computing difference sum */ sum + = ( a [ i ] - avg ) * ( a [ i ] - avg ); var = sum / n; /* Computing variance */ return(var); /* Returning variance to main()*/ }
8.6 FUNCTIONS TO READ AND WRITE ONE DIMENSIONAL ARRAY
The Method
This example has been already discussed in Section 6.1. The array reading function readarr ( ) has been developed assuming that the array, say a, and n, the number of elements, are available. In readarr ( ) function, all the elements of the array are input under the control of a for loop. This function does not return any value. Therefore the type of this function is declared as void.
The array reading function writearr ( ) has been developed assuming that the array, say a, and n, the number of elements, are available. In writearr( ) function all the elements of the array are output under the control of a for loop. This function also does not return any value and therefore has been declared as of type void.
In the main( ) function, first the value of n, number of elements is read in. Then the readarr( ) and writearr( ) functions are used, in that order, to input and output the array.
C-Tips
In this example two parameters, one the array(a) and the other n, number of elements, are passed on to both the functions readarr( ) and writearr( ). The scalar quantity n is passed on by-value and the array is passed on by-address or call by-reference. These techniques have been already discussed in detail in Sections 8.2 and 8.5, respectively.
Flowchart
/* Functions to read and write an one dimensional array. */ #include<stdio.h> #include<conio.h> main() { int i, n, a [20]; /* Declaring variables */ void readarr(int a[], int n); /* Function prototypes */ void writearr(int a[], int n); clrscr(); printf(“ Read n ”); scanf(“%d”, &n); printf(“n = %d ”, n); printf(“Input elements of the array ”); /* Reading elements of array by calling readarr() function */ readarr(a,n); printf(“ Printing Elements of the array ”); /* Printing elements of array by calling writearr() function */ writearr(a,n); } /* Function to read array elements */ void readarr(int a[], int n) { int i; /* Declaring local variable */ for(i = 0; i < n; ++i) scanf(“%d”, &a[i]); /* Reading array elements */ } /* Function to write array elements */ void writearr(int a[], int n) { int i; /* Declaring local variable */ for(i = 0; i < n; ++i) printf(“%d ”, a[i]); /* Printing array elements */ }
8.7 FUNCTION TO SORT AN ARRAY USING BUBBLE SORT METHOD
The Method
The procedure used to sort a given set of integer elements is discussed in Section 6.8. In this example a function called sort( ) to sort a given array ‘a’ of ‘n’ integer elements is developed. Also a main( ) function has been developed that using this user-defined function sort( ). The unsorted array of integer elements is input in the main( ) function and the sorted array is also output in the main( ) function. The corresponding flowchart is given in the next page.
C-Tips
The user defined function sort( ) is developed assuming all the ‘n’ elements of the array ‘a’ are available. Thus the array ‘a’ and the number of elements ‘n’ are taken as the formal arguments of the sort ( ) function. The passing of array from the calling function to the called function takes place implicitly via address passing. Since the user-defined function works on the same memory locations of the array that are allocated within the main, the elements of the array are sorted in those memory locations itself. Thus, in this case, no values are returned from the called function to the calling function. Hence the type of the user-defined sort ( ) function has to be taken as void. Thus the function header and the function prototype have been taken as:
void sort(int a[ ], int n)
… beyond
Though an explicit return statement is shown in the flowchart of the sort( ) function, it has not been used explicitly in the program. Under such a situation the control from the called function goes back to the calling function as soon as it comes across the last closing curly brace(‘}’).
/* Sorting given list of n numbers in ascending order using bubble sort */ #include<stdio.h> #include<conio.h> main() { int i, n, a [20] , /* Declaring variables */ void sort(int a[], int n); /* Function prototype */ clrscr(); printf(“ Read n ”); scanf(“%d”, &n); printf(“n = %d ”, n); printf(“Read elements of array ”); 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 */ sort(a, n); /* Calling function sort() */ printf(“Sorted array is: ”); for(i = 0; i < n; ++i) printf(“%d ”, a[i]); } /* Function to sort the array elements in ascending order */ void sort(int a[], int n) { int i,j,temp; /* Declaring local arguments */ /* 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 elements 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; } }
8.8 FUNCTION TO SEARCH FOR A REQUIRED ELEMENT USING BINARY SEARCH METHOD
The method employed to search for a required element (i.e. a key) in a sorted array using binary search method has been already discussed in Section 6.17. The same is re-presented here in the form of a user defined function. It should be noted that this method is applicable only to sorted arrays.
The Method
A function called binsearch ( ) is developed assuming that the array a, the information about the number of elements in the array ‘n’ and the ‘key’ to be searched are available. Naturally these three, i.e. a[ ], n and key, are taken as the formal arguments of the function binsearch ( ). In this example, the result of searching is output within the binsearch ( ) function itself. As such this function does not return any value to the calling function. Therefore, the function is declared as of type void.
In the main( ) first all the ‘n’ elements of the array are input. Next the ‘key’ to be searched is input. Then the function binsearch( ) is invoked with actual arguments.
C-Tips
When the binsearch( ) function is called the value of ‘n’, the number of elements in the array, and the key to be searched get transmitted to it by value. The array is transmitted to the called function by implication. In otherwords, the address of the array gets transmitted automatically from the calling function to the called function. Since the success or failure is reported suitably within the binsearch ( ) function itself, no value will be returned to the calling function. Therefore, the type of the function binsearch ( ) has been taken as of type void. As already mentioned the array size is mentioned only during the array declaration in the main( ). In other words, there is no need to mention the array size in the function header, function prototype and during a function call. The function prototype must be included during the beginning of the main( ) function. Thus the function header and the function prototype have been taken as
void binsearch (int a[ ], int n, int key)
It may be observed that no return statement has been used explicitly.
Flowchart
/* Searching for the specified number in a sorted array using binary search */ #include<stdio.h> #include<conio.h> main() { int i, n, a[20],key; /* Declaring local variables */ void binsearch(int a[], int n, int key); /* Function prototype */ clrscr(); printf(“ Read n ”); scanf(“%d”, &n); printf(“n = %d ”, n); printf(“Input elements of the array in ascending order ”); /* Reading elements of array in ascending order */ 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]); /* Printing elements of array */ printf(“Enter key element to be searched ”); scanf(“%d”, &key); /*Reading Key element to be searched*/ printf(“key = %d ”, key); /* Printing key element */ binsearch(a,n,key); /* Calling function binsearch() */ } /* Function to search for the key element */ void binsearch(int a[], int n, int key) { int low, high, mid; high = n-1; low = 0; while(low <= high) { mid = (low + high)/2; /* mid is the 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 /* If key is lesser than middle element then it must be in first half. Make high = mid-1 */ high = mid - 1; } if (a[mid] == key) printf(“Search is successful, %d is found in position number %d ”, key, mid+1); else printf(“Search is unsuccessful, %d is not found ”, key); }
8.9 FUNCTIONS TO SORT A GIVEN UNSORTED ARRAY USING SELECTION SORT
The procedure involved in sorting an unsorted array of elements using selection sort has been already discussed in Section 6.18. As pointed out in that section, this sorting procedure has two distinctly independent actions to be taken, viz. “finding the position of a minimum value” and “exchanging the minimum value at that position with a value at the beginning of the current search space.”
The Method
As this method involves finding the position of a minimum value and exchanging it with the value at the beginning of the current search space on the array, two independent functions are developed to implement these actions. The two user-defined functions developed here are:
int min(int a[ ], int n, int i ) and
void exch(int a[ ], int i, int m)
These two functions are called one after the other repeatedly for (n-2) times. During each such repetition the search space is reduced by one count. Finally the sorted array is output.
C-Tips
As two independent subtasks have been identified two functions
int min(int a[ ], int n, int i) and
void exch(int a[ ], int i, int m) have been developed.
The given array a, information about the total number of elements in the array (n) and information about the beginning of the current search space i are assumed to be available and have been used as formal arguments of the function min ( ). Since this function is expected to return a position value which will be an integer value, the function min( ) has been declared as of type int. As it could be seen from the flowchart and the program, a local variable j is used to move along the array.
The given array a, information about the beginning of the current search space i, and value of the position of the minimum element m are all assumed to be available and have been used as formal arguments of the function exch( ). Since this function just exchanges the values stored in two locations of an array, no value will be returned from this to the calling function. As such the function exch ( ) has been declared as of type void.
Of course, the values of m, n and i are being passed by call by value method and the arrays are passed by implication.
/* Sorting given list of n numbers in ascending order using selection sort */ #include<stdio.h> #include<math.h> #include<conio.h> main() { int i, n, m, a [20]; /* Declaring variables */ int min(int a[] , int n, int i); void exch(int a[] , int i, int m); /* Function prototype */ clrscr(); printf(“ Read n ”); scanf(“%d”, &n); printf(“n = %d ”, n); printf(“Read elements of array ”); 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 */ /* Calling functions */ for (i = 0; i<n-1; ++i) { /* Calling function min() to find the position of smallest element */ m = min (a, n, i); /* Calling function exch() to exchange a[i] and a[m] */ exch(a, i, m); } printf(“Sorted array is: ”); for(i = 0; i < n; ++i) printf(“%d ”, a[i]); } /* Function to find the position of smallest element */ int min(int a[],int n, int i) { int j,minpos=i; /* Declaring local variables */ /* Finding position of minimum element */ for(j=i+1; j<n; ++j) if (a[j] < a[minpos]) minpos = j; return(minpos); /* Returning position of minimum element */ } /* Function to exchange a[i] and a[m] */ void exch(int a[] , int i, int m) { int temp; temp = a[i]; a[i] = a[m]; /* Exchanging */ a[m] = temp; return; /* Returning control back to main() */ }
8.10 FUNCTIONS TO READ, WRITE AND COMPUTE TRACE OF GIVEN MATRIX
As already mentioned in Section 8.12 the trace of a square matrix is the sum of all the elements on its principal diagonal.
The Method
The dimensions of the matrix is first input and then all the elements of the matrix, say a, are read in using a user defined function readmatrix( ). Since square matrix is assumed, testing for the equality of the row size and the column size is not done. The input matrix is printed out using another user defined function writematrix( ). The trace of the matrix is obtained by using another user defined function tracevalue ( ) and output.
C-Tips
In order to read and write matrices an array a, of dimensions m rows and n columns are assumed to be available. As such, array a, m and n are used as formal arguments of the user-defined functions readmatrix ( ) and writematrix ( ). As these two functions just perform certain task, no values will be returned to the calling function. Thus these functions are declared as of type void.
The user-defined function tracevalue ( ) is developed assuming that a square matrix, say a, along with one of its dimensions is available. Thus array a, and either row size m or column size n are taken as its formal arguments. The type of value returned from this function to a calling function depends on the type of elements of the array. Since, in this example, integer type array elements have been used, the returned value from the function tracevalue( ) will be of type int. Thus the type of the function has to be taken as of type int. As such, in this example, the following function headers and function prototypes have been developed and used.
void readmatrix(int a[ ][10], int m, int n) void writematrix(int a[ ] [10], int m, int n) int tracevalue(int a[ ] [10],int m)
… beyond
In the case of two-dimensional arrays, like in matrices, the beginning address is passed from a calling function to the called function. When a two dimensional array of size (m × n) is declared in a main( ) function, continuous memory locations for all the m × n elements will be allocated. Like with one-dimensional arrays all the corresponding arrays, regardless of the fact wherever they are, access only these memory locations. However, first n memory locations will be reserved for the first row, second n memory locations will be reserved for the second row and so on. In otherwords, elements of this type of array will be stored row wise. Here, it is important to note that the second row will be stored starting from the (n + 1)th memory location, third row will be stored starting from the (2n + 1)th memory location and so on. Thus the system expects the value of n, i.e. the size of the row. Hence, while handling two-dimensional arrays (infact any multidimensional array) all the sizes of additional dimensions must be provided explicitly. However, C allows the user to use a blank ‘b’ as the size of various dimensions. This sets a predefined value (usually 32) to the different dimensions of the array automatically.
/* Finding the trace of a given matrix a (m x n) using function */ #include<stdio.h> #include<math.h> main() { int a[10][10], trace=0, i, j, m, n; /* Declaring variables */ void readmatrix(int a[][10], int m, int n); int mattrace(int a[][10], int m); /* Function prototypes */ void writematrix(int a[][10], int m, int n); clrscr(); printf(“Read order of the matrix ”); scanf(“%d%d”, &m, &n); /* Reading order of the matrix */ printf (“Order of the given matrix is : %d X %d ” , m, n); /* Is it a square matrix? */ if ( m ! = n) { printf(“Trace not possible ”); /* Not a square matrix */ exit(); } printf(“Read elements of matrix ”); readmatrix (a, m, n); /* Calling function readmatrix() */ printf(“ Given matrix is: ”); writematrix(a, m, n); /* Calling function writematrix() */ printf(“ Trace of the given matrix = %d ”, mattrace(a, m)); } /* Function to read matrix */ void readmatrix(int a[][10], int m, int n) { int i, j; for(i=0; i<m; ++i) for(j=0; j<n; ++j) scanf(“%d”, &a[i][j]); /* Reading elements of matrix */ return; /* Return control back to main() */ } /* Function to print matrix */ void writematrix(int a[][10], int m, int n) { int i, j; for(i=0; i<m; ++i) { for(j=0; j<n; ++j) printf(“%4d ”, a[i][j]); /* Printing the matrix */ printf(“ ”); } return; /* Return control back to main() */ } /* Function to find the trace of a given matrix */ int mattrace(int a[][10], int m) { int i, trace=0; /* Declaring local variables */ for(i = 0; i<m; ++i) trace += a[i][i]; /* Computing trace */ return(trace); /* Returning trace back to main() */ }
8.11 FUNCTIONS TO COMPUTE SUM OF EACH ROW, SUM OF EACH COLUMN AND SUM OF ALL ELEMENTS OF GIVEN MATRIX
In this example, three user-defined functions rowsum ( ) that computes the sum of a row, columnsum( ) that computes the sum of a column and matsum( ) that computes the sum of all the elements of a given matrix have been developed.
The Method
The sum of all the elements of a row, say ith row, is obtained by using a relation of the type sum = sum + aij for a known value of i and for all the values of j from 0 to (n-1).
The sum of all the elements of a column, say jth column, is obtained by using a relation of the type sum = sum + aij for all the values of i from 0 to (m-1) and for a known value of j.
The sum of all the elements of the matrix is obtained by using a relation of the type sum = sum + aij for all the values of i from 0 to (m-1) and for all the values of j from 0 to (n-1).
The functions readmatrix ( ) and writematrix( ) developed in the previous section, i.e 8.10 have been used to input and output the required matrix in the main( ).
C-Tips
The rowsum ( ) function has been developed assuming that the array a, the rowvalue i of which the elements are to be summed, and the columnsize n are available. Thus, array a, rowvalue i and columnsize n have been taken as the formal arguments of rowsum( ).
The columnsum ( ) function has been developed assuming that the array a, the column value j of which the elements are to be summed up, and the rowsize m are available. Thus the array a, column value j and the rowsize m have been taken as the formal arguments of columnsum ( ).
The matsum ( ) function is developed on the same lines using the array a and its dimensions m and n as formal arguments.
Since all the three functions developed here return a sum, an integer value, all of them have been declared as of type int. The function headers and the function prototypes of the functions developed are :
int rowsum (int a[ ][10], int n, int i) int columnsum (int a[ ][10], int m, int j) int matsum (int a[ ][10], int m, int n)
As is known, values of the scalars i, j, m and n are transmitted by-value and matrices are transmitted by implication.
/* Computing row sum, column sum and the sum of all the elements of a matrix using functions */ #include<stdio.h> #include<conio.h> main() { int m, n, i, j, a [10] [10]; /* Declaring variables */ void readmatrix(int a[][10], int m, int n); void writematrix(int a[][10], int m, int n); int rowsum(int a[][10], int n,int i); /* Function prototypes */ int columnsum(int a[][10], int m,int j); int matsum(int a[][10], int m ,int n); clrscr(); printf(“ Read order of matrix ”); scanf(“%d%d”, &m, &n); printf(“Order of matrix is : %dX%d ”, m,n); printf(“Read elements of Matrix ”); readmatrix(a,m,n); /* Calling function readmatrix() */ printf(“Printing given matrix ”); writematrix(a,m,n); /* Calling function writematrix() */ printf(“ Given matrix with row sum and column sum ”); for(i=0; i<m; ++i) { for(j=0; j<n; ++j) printf(“%4d ”, a[i][j]); /* Calling function rowsum() to find the sum of elements of row i */ printf(“| %4d ”, rowsum(a, n, i)); } printf(“_______________ ”); for(j=0; j<n; ++j) /* Calling function columnsum () to find the sum of elements of column j */ printf(“%4d ”, columnsum(a, m, j)); /* Calling function matsum() to find the sum of all elements in the matrix */ printf(“ Sum of all the elements of the matrix is %d ”, matsum(a, m,n)); } /* Function to compute row sum */ int rowsum(int a[][10], int n,int i) { int j, sum=0; for(j=0; j<n; ++j) sum += a[i][j]; /* Computing row sum */ return(sum); /* Returning row sum back to main()*/ } /* Function to compute column sum */ int columnsum(int a[][10], int m,int j) { int i, sum=0; for(i=0; i<m; ++i) sum += a[i][j]; /* Computing column sum */ return(sum); /* Returning column sum back to main()*/ } /* Function to compute sum of all elements of a matrix */ int matsum(int a[][10], int m ,int n) { int i,j, sum=0; for(i=0; i<m; ++i) for(j=0; j<n; ++j) sum += a[i] [j]; /* Computing sum of all the elements */ return(sum); /* Returning sum back to main()*/ }
8.12 FUNCTIONS TO READ, WRITE AND COMPUTE PRODUCT OF TWO GIVEN MATRICES
The conditions for the multipliability of two given matrices and the process of multiplication have been elaborately discussed in Section 6.15.
The Method
In this example, it is assumed that the two given matrices are multipliable. Functions readmatrix( ) and writematrix ( ) developed in Section 8.10 have been used to input and output the given matrices as well as the product matrix. A user defined function called matprod ( ) is developed in this section and is used to compute the product of the given two matrices. The fact that functions developed by someone else or somewhere could be used has been demonstrated in this example. Here only the matprod ( ) function has been developed. The complete flowchart for the main ( ) and the matprod ( ) are given in the following pages.
C-Tips
While developing the matprod( ) function, it is assumed that the two given matrices a, b and the product matrix c, information about the number of rows of the first matrix, information about the columns of both the first and second matrices are available. As such, all these have been taken as the formal arguments of the matprod( ) function. This function computes the product of the matrices a and b and stores it in the matrix c. Then the control goes back to the calling function without any values. Therefore the function matprod( ) has been declared as of type void. Thus the function header and the function prototype will be as given below:
void matprod (int a[ ] [10], int b[ ] [10], int c[ ] [10], int m, int n, int q)
Obviously the values of the scalar quantities viz. m, n, and q, are transmitted on call, i.e. by call by value method and the arrays are transmitted by implication.
The Program
/* Functions to read, write and compute the product of two given matrices. */ #include<stdio.h> #include<conio.h> main() { int m, n, p, q,i, j, 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 */ void readmatrix(int a[][10], int m, int n); void writematrix(int a[][10], int m, int n);/* Function prototypes*/ void matprod(int a[][10], int b[][10], int c[][10],int m,int n, int q ); clrscr(); printf(“ Read the order of first matrix a ”); scanf(“%d%d”, &m, &n); printf(“ Read the order of 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); printf(“ Read elements of Matrix a ”); readmatrix(a, m, n); /* Calling readmatrix( ) */ printf(“ Matrix a ”); writematrix(a, m, n); /* Calling writematrix( ) */ printf(“ Read elements of Matrix b ”); readmatrix(b, p, q); /* Calling readmatrix( ) */ printf(“ Matrix b ”); writematrix(b, p, q); /* Calling writematrix( ) */ matprod(a,b,c,m,n,q); /* Calling matprod( ) */ printf(“ Product Matrix c ”); writematrix(c, m, q); /* Calling writematrix( ) */ } /* Function to compute product */ void matprod(int a[][10], int b[][10], int c[][10],int m, int n, int q) { int i, j , k, sum; 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; } } return; /* Return */ }
8.13 PROGRAM TO SEARCH FOR REQUIRED ELEMENT IN A GIVEN UNSORTED ARRAY USING FUNCTIONS ON SEPARATE FILE
This example has been discussed to illustrate the meaning of a module and hence the modular programming.
The method
By carefully studying the given problem one can identify the following activities that could be performed independently.
- Reading in a one-dimensional array.
- Writing out a one-dimensional array.
- Sorting an array.
- Searching for a key element in the sorted array.
Independent functions that perform the above mentioned activities have been already developed in Sections 8.6, 8.7 and 8.8 respectively. A main ( ) function has been developed here that uses the previously developed functions to search for the required key in a given unsorted array. A flowchart that depicts the behaviour of the main program is presented in the following page.
C-Tips
All the required functions that have been already developed are put onto a separate file, say rwss.h. Now this file is made available to every one who works with the same C compiler by storing it in the bin directory of the compiler. (At this stage if the reader is not able to understand the meaning of a bin directory, do not worry, just proceed.) These separate files are called modules. Developing any useful program with the help of one or more modules is known as modular programming. Any required module is included in a main program as usual i.e. with the help of the preprocessor directive #include. Here the reader is advised to observe its usage in the program presented at the end of this section.
/* Program to search for a required element in a given unsorted array using functions on a separate file. */ #include<stdio.h> #include<conio.h> #include “rwss.h” /* Module included here */ main() { int i, n, a[20],key; /* Declaring variables */ clrscr(); printf(“ Read n ”); scanf(“%d”, &n); /* Value of n is input */ printf(“n = %d ”, n); printf(“Read elements of array ”); /* Reading elements of array by calling readarr() from rwss.h header file */ readarr(a,n); printf(“Elements are ”); /* Printing elements by calling writearr() from rwss.h header file */ writearr(a,n); printf(“Enter key element to be searched ”); scanf(“%d”, &key); /* Reading Key element */ printf(“key = %d ”, key); /* Printing key element */ /* Calling function sort() from rwss.h header file */ sort(a, n); printf(“Sorted array is: ”); /* Printing sorted elements by calling writearr() from rwss.h file */ writearr(a,n); /* Calling function binsearch() from rwss.h header file */ binsearch(a,n,key); }
8.14 UNDERSTANDING THE MEANING OF LOCAL AND GLOBAL VARIABLES
One of the advantages that the solving of problems using functions has brought in is that different persons can develop programs for different functions that are parts of a common problem. In such situations, there are every chances that same variable names might be used across different functions. Such usage of common variable names across different functions is permitted. This is because a variable name in a function is valid or alive only in that specific function. Such variable names that are valid or alive in which they are declared and used are called local variables. However, we need certain variable names to be valid throughout a program i.e. across various constituent functions of a single program. Such variable names that are valid across an entire program are called global variables. As already mentioned, local variables are declared within the body of a function in which they are used. However, global variables are declared in the beginning of a program i.e. even before the main( ) function, but just after the preprocessor directives.
Global variables provide certain advantages, like a value required by more than one function can be propagated to them, more than one value can be returned back to a calling function from a called function etc.
The Method
In this example a main ( ) function and a user-defined function illustration ( ) without any arguments are developed. x and y variables have been declared as global variables. x and z variables have been used as local variables in illustration( ). As it is required to check the validity of values of the variables, they have been output from various parts of the program.
C-Tips
Under certain situations names of local variables and some global variable names could be same. Under such circumstances, local variables of a function will be valid within that function. In other words, when there exists a conflict between a local variable and a global variable, local variable wins over the global variable. However, values of global variables remain intact. This fact is demonstrated in the program.
… beyond
Local variables (i.e. auto variables) are always declared within a function and are valid/active only in the function in which they are declared; i.e. their scope is limited to that function only.
Global variables (i.e. external variables) are always declared outside a function. Generally they are declared before the main( ) and their values will be available to all the functions that follow their declarations. Thus, the scope of global variables extends to all the functions in a program.
In addition to the above two types of variables, C provides two more types of variables called static variables and register variables.
Flowchart
/* Understanding the meaning of local and global variables */ #include<stdio.h> #include<conio.h> /* Declaration and initialization of global variables */ int x=13,y=15; main() { void illustration(); /* Function prototype */ clrscr(); /* Printing the values of x and y before calling the illustration() function */ printf(“ The values of x = %d & y = %d before the function is called. ”,x,y); illustration(); /* Calling illustration() */ /* printing the values of x and y after calling the illustration() function */ printf (“ The values of x = %d & y = %d after the function is called. ”,x,y); } void illustration() { int x,z; /* Declaring the local variables */ x=20; z=5; x=x+z; /* printing the values of variables within the function */ printf(“ The values of x = %d , y = %d & z = %d within the function. ”,x,y,z); return; /* Returning */ }
8.15 FUNCTION TO SWAP CONTENTS OF TWO VARIABLES—THE WRONG ONE
As explained in Section 2.2 swapping of the contents of two given variables is one of the most frequently used activities. As this is a frequently used activity one is naturally tempted to develop a user-defined function for the same and use it as and when required.
By now the reader is aware of the fact that most of the examples discussed in this chapter are the migrated ones from the earlier chapters. A careful observation of all these examples reveal the fact that while developing functions, the input and output operations are not done, normally. Rather it is assumed that the values for the required variables are available, which will be obtained during program execution and if there are any computed results they are returned back to the calling program.
The Method
The flowchart and program segments developed in Section 2.2 have been migrated and re-presented here in the form of a user-defined function and a main ( ) function. This program does not work, i.e. the wrong one. However, the correct one is presented in the next chapter on pointers.
C-Tips
It may be observed that variables a and b have been used as local variables both in the main ( ) function as well as in the swap ( ) function. Since they are local to their respective functions, a and b in main( ) and a and b in swap ( ) will have different memory locations. When main( ) calls swap( ), values stored in the memory locations of a and b pertaining to main ( ) will be copied in to the memory locations of a and b pertaining to swap( ). Here, it should be carefully observed that the swap( ) function manipulates the contents of the memory locations of its own a and b. In other words, the contents in the memory locations of a and b of the main ( ) function does not get manipulated. Thus, when the control goes back to the calling function, it finds that the contents of the local variables of main ( ) have not got swapped. In other words, the technique of call-by-value method has failed. In practice such situations are circumvented by using another very popular technique known as call-by-reference technique. More about this type of parameters passing is discussed in the next chapter.
Flowchart
/* To swap the contents of two variables using function */ #include<stdio.h> #include<conio.h> main() { void swap (int a , int b); /* Function prototype */ int a,b; clrscr(); printf(“Enter the values of a & b ”); scanf(“%d %d”,&a,&b); /* printing the values of a & b before swapping */ printf(“ Before swapping (in the calling function). a = %d & b = %d ”,a,b); swap(a,b); /* Calling swap() function */ /* printing the values of a & b after swapping */ printf(“ After swapping ( in the calling function). a = %d & b = %d ”,a,b); } /* The swap() function */ void swap(int a, int b) { int temp; /* Declaring the local variable */ /* interchanging the contents of variables a & b */ temp=a; a=b; b=temp; /* printing the values of a & b within the function */ printf (“ The values of a = %d & b = %d within the swap function ”, a,b); return; /* Returning back to the main() function */ }
EXERCISES
- Develop flowcharts to print the message “Programming Techniques using C” using a function and a main function to print the message using the above developed function. Code the same in C.
- Develop flowcharts to find the biggest among three given numbers using a function and a main function to print the biggest. Code the same in C.
Develop flowcharts to compute real and equal roots, real and distinct roots and complex roots of a given quadratic equation using functions depending upon the three different cases of the discriminant. Also, develop a flowchart to use the above developed functions in a main function. Code the same in C.
[Hint: Use global variables to return the roots to the calling function.]
- Develop flowcharts to count the number of occurrences of a given integer in a given set of integers using a function and a main function to print out the same. Code the same in C.
- Develop flowcharts to transpose a given matrix using a function and a main function to output the same. Code the same in C.
- Develop flowcharts to find the norm of a given matrix using a function and a main function to output the same. Code the same in C.