West Publishing - Chapter 4 - Introduction to Computer Science With C - Hicks, Nance, & Naps [1]
Structuring Program
Logic
Introduction to Computer Science With C:
Programming,
Problem Solving,
& Data Structures
Thomas E. Hicks
Douglas W. Nance
Thomas L. Naps
Copyright Pending for West Publishing Co.
Great things are not done by impulse, but by a series of small things brought together.
Vincent van
Gogh / Memory Management &
Functions for Problem
Solving
Advances in software engineering are often expected to keep pace with advances in computer hardware. The writing of software has indeed become more complex. Programs are expected to be more user-friendly, faster, more stable, and more portable than ever before. Most major projects are designed by teams of computer scientists and implemented by even larger teams of highly trained individuals.
This chapter is designed to help us more efficiently reach computer solutions by successively subdividing a problem until we have directly solvable tasks to code and implement. Section 4.1 explains the need for modularity and structure. Section 4.2 introduces both (a) the scope of global and local variables and (b) user-defined explicit-functions. Section 4.3 introduces user-defined void-functions, memory maps, and execution program execution flow. Section 4.4 introduces the passing of value variables to functions. Section 4.5 introduces pointers and the dereferencing of pointers. Section 4.6 provides suggestions for subprogram documentation, program documentation, and the writing of quality subprograms. Section 4.7 introduces stubs, drivers, and their construction.
A computer program is only as good as its design. This chapter will help to lay a sound foundation on which to build quality software.
4.1 ProgramDesign
Modularity
We have previously discussed and illustrated the process of solving a problem by top-down design. Top-down design is even more important when creating a large computer program, sometimes called a system. Using this method, we divide the main task into major subtasks, and then continue to divide the subtasks (stepwise refinement) into smaller subtasks until all subtasks can be easily performed. Once an algorithm for solving a problem has been developed using top-down design, the programmer then writes code to translate the general solution into a C program.
As you have seen, code written to perform one well-defined subtask is referred to as a subprogram. Collections of related subprograms are often grouped in a file called a module. Theoretically, one should be able to design, code, and test each subprogram with a small test driver program independently from the rest of the system. In this sense, a subprogram contains all definitions and declarations needed to perform the indicated subtask. Everything required for the subtask (but not needed in other parts of the program) should be created in the subprogram. Consequently, the definitions and declarations have meaning only when the subprogram is being used.
A program that has been created using subprograms to perform various tasks is said to possess modularity. In general, modular programs are easier to test, debug, maintain, and correct than programs that are not modular because each independent subprogram can be tested by running it from a test driver. An example of such a driver may be found in function main of program Cube.c (section 4.2). Once the subprograms are running correctly, they can be integrated into a longer program.
Structured Programming
Structured programming is the process of developing a program where emphasis is placed on the correspondence between independent subprograms. Structured programming breaks program logic, regardless of complexity, into sequence, selection, and iteration (see Structured Programming Note of Interest). Connections between these subprograms are specified in parameter lists. Structured programming is especially suitable to large programs being worked on by teams. By carefully designing the subprograms and specifying what information is to be received by and returned from the subprogram, a team of programmers can independently develop and test their subprogram and then have it connect to the complete program.
From a compiler construction view, all subprograms are functions; however, most structured programming languages define a function to be a subprogram which explicitly returns information and a procedure to be a subprogram which does not explicitly return information. C is indeed a functional language, but not all C subprograms have an explicit return. For organizational purposes, it is best to separate subprogram with explicit returns from those with no explicit returns. This text shall refer to subprograms with no explicit returns as void-functions and those subprograms with explicit returns as explicit-functions. Functions printf, scanf, abs, sin, cos, sqrt, ceil, floor, fabs, pow, and log are among the explicit-functions that have been previously described.
A NOTE OF INTEREST
Structured Programming
From 1950 to the early 1970s programs were designed and written on a linear basis. A program written and designed on such a basis can be called an unstructured program. Structured programming, on the other hand, organizes a program around separate semi-independent subprograms that are linked together by a single sequence of simple commands.
In 1964, mathematicians Corrado Bohm and Guiseppe Jacopini proved that any program logic, regardless of complexity, can be expressed by using sequence, selection, and iteration. This result is termed the structure theorem. This result, combined with the efforts of Edger W. Dijkstra, led to a significant move toward structured programming and away from the use of GOTO statements.
The first time structured programming concepts were applied to a large-scale data processing application was the IBM Corporation "New York Times Project'' from 1969 to 1971. Using these techniques, programmers posted productivity figures from four to six times higher than those of the average programmer. In addition, the error rate was a phenomenally low 0.0004 per line of coding.
4.2
Global vs Local
User-Defined
Functions
Local Variables
Program blocks are a bounded collection of code; they begin with a left brace ({) and end with a right brace (}). Each subprogram, including main, begins and ends with braces; therefore, each function forms at least one programming block. Program Local1.c has one programming block; this block begins at line 3 and ends at line 10.
PROGRAMLocal1.c
1-# include <stdio.h>
2main()
3-{/* <------Beginning of Block 1 */
4-int
5-W = 5;
6-
7-printf ("W = %d\n",W);
8-W++;
9-printf ("W = %d\n",W);
10-}/* <------End of Block 1 */
Several of the examples in this chapter include line numbers for easier reference; they must be removed prior to compilation.
Local Variables are those variables (of data types int, float, char, etc.) declared and initialized at the top of any programming block. Memory, for local variables, is allocated by the memory manager at the beginning of a block; these local variable exists until its memory is deallocated (returned to the memory manager) at the end of the block. A Local variable may be used, changed, within its block.
When line 3 of program Local1.c is executed, the memory manager allocates two bytes of memory for local variable W (it is initialized to 5). Local variable W may be used, printed, or changed only within its block.
Programming blocks may be nested (i.e. they be inserted within other programming blocks). Program Local2.c has two blocks; they are nested.
PROGRAMLocal2.c
1-# include <stdio.h>
2main()
3-{/* <------Beginning of Block 1 */
4-int
5-X = 5;
6-
7-printf ("X = %d\n",X);
8-{/* <------Beginning of Block 2 */
9-int
10-Y = 8;
11-
12-printf ("X = %d Y = %d\n",X,Y);
13-X++;
14-Y++;
15-printf ("X = %d Y = %d\n",X,Y);
16-}/* <------End of Block 2 */
17-printf ("X = %d\n",X);
18-}/* <------End of Block 1 */
Block 1 extends from the opening brace on line 3 to its corresponding closing brace on line 18; local variable X may be used, printed, or changed within this block. Block 2 extends from the opening brace on line 8 to its corresponding closing brace on line 16; local variable Y may be used, printed, or changed only within this block. A compile error would be generated if line 17 attempted to print the value of Y; it does not exist beyond the closing brace in line 16. Program blocks may be nested several levels deep; consult your compiler manual for exact specifics. A local variable exists only within the block in which it is declared.
Most variables will be declared at the beginning of the subprogram. When a subprogram has more than one block, the code should be indented to help identify the scope of the blocks and the intended logic.
Global Variables
Most programming languages support some type of global variables. As previously mentioned in chapter 3, global variables are variables whose symbolic names and contents are available within any of the program's subprograms (including main); in the C programming language global variables are declared at the bottom of Section II.
PROGRAMGlobal.c
1-# include <stdio.h>
2-int
3-A = 2;
4-
5main()
6-{/* <------Beginning of Block 1 */
7-int
8-B = 9;
9-
10-printf ("A = %d B = %d\n",A,B);
11-A++;
12-B++;
13-printf ("A = %d B = %d\n",A,B);
14-}/* <------End of Block 1 */
Just as a submerged submarine can only see that portion of the topside world visible in the periscope at any given instant in time, well-written computer programs are capable of accessing (print, change, etc.) only a portion of all of the variables that exist in the program at any given instant in time. Those global and local variables that can be accessed are said to be in-scope or visible; all other variables are said to be out-of-scope or invisible.
In Global.c, A is a global variable; it is declared in section II. Global variables are in-scope to all functions that do not have a local variable or a parameter with the same symbolic name. Since function main has no local variable or parameter named A, global variable A may be used, changed, or printed from function main; it is in-scope. Function main has a local variable named B and no parameters.
Other subprograms could be added to Global.c; any other subprogram, that has no local variable or parameter named A, would be able use, change, or print global variable A as well.
One of the guidelines of good structured programming is to keep global variables to a minimum. Programs Global.c, Cube.c, PizaCost2.c, and AddProb.c are included in the text only to illustrate the scope of global variables. Although most well-written programs will have no global variables, it is important for students to understand the scope of both global and local variables.
If you have programmed in ANSI BASIC, all variables were global. The disadvantages of global variables are not always obvious to students writing small programs. Large computer programs, called systems, of today are generally constructed by teams of computer scientists. Each team completes and tests their own part of the system. The working parts are then combined to form a complete system. Imagine the problems that arise when multiple teams have used the same names for global variables; code which once worked independently is suddenly filled with errors. Programs that include global variables tend to be more difficult to maintain.
User-Defined Explicit-Functions
Section 3.5 illustrates many calls to standard library explicit-functions. Each of these functions explicitly return information. Notice that in explicit-function calls
x = fabs(-25);
y = sqrt (25);
w = sqrt (fabs(-20–5));
essential information is passed/transmitted (within parentheses) to the function. One or more arguments, sometimes called actual parameters, will normally be passed to an explicit-function. These arguments may be variables, constants, pointers (to addresses in memory), and/or expressions.
y = sqrt (25);/* Constant */
y = sqrt (No);/* Variable */
y = sqrt (20+10);/* Expression */
y = sqrt (*Ptr)/* Pointer - section 4.5 */
It is relatively easy to envision the need for functions that are not on the list of standard mathematical functions available in C. For example, if you must frequently cube numbers, it would be convenient to have a user-defined function Cube so you could make an assignment such as
Total = Cube(No); /* First user-defined function */
In this example, the integer argument No is passed to explicit-function Cube in the function call above; if No contains 3, then the function call would replace the contents of integer Total with 27. When a function has more than one argument, they are separated by commas.
In business, a motel might like to have available a function to determine a customer's bill given the number in the party, the length of stay, and any telephone charges. Similarly, a hospital might like a function to compute the room charge for a patient given the type of room (private, ward, and so on) and various other options, including telephone (yes or no) and television (yes or no). Functions such as these are not standard functions. However, in C, we can create user-defined functions to perform these tasks.
Form for User-Defined Functions (explicit return)
Subprograms are generally placed in logical clusters after function main. The explicit-return-type for user defined functions may be a int, short int, long int, float, double, long double, char, pointer, etc. The form for a function is
Heading / / Explicit-Return-Type FunctionName (parameter list)Declaration Section
{ Define Local Variables
User-Defined Data types} /
Executable Section / / {
(function statements)
}
The parameter list in the explicit-function will generally contain one or more parameters, sometimes called a formal parameters; there will generally be one parameter associated with each and every argument passed. One solution to function cube might be
int Cube (int X) /* Function Header */
{ /* <------Beginning of Function */
int /* Local Variables */
CubedNo;
CubedNo = X * X * X; /* Body of Function */
return (CubedNo); /* Body of Function */
} /* <------End of Function */
Function Cube, above, has one parameter. We shall return to examine function Cube in Example 4.1.
Function Prototypes
Since C allows subprograms to be randomly placed within the executable section of the program, a prototype for each void–function and explicit-function (except main) must be placed at the bottom of the global declaration section of the program (Section II).
For beginning C programmers, the prototype is created by adding a semicolon the end of a copy of the subprogram header. The prototype for function Cube, above, would be
int Cube (int X);
The subprogram header should match the prototype. The most common prototype error that beginners make is forgetting the semicolon at the end. Beginners also make the mistake of placing a semicolon at the end of the subprogram header.
Function Guidelines
1. "FunctionName'' is any valid identifier.
2. The function name should be descriptive.
3. There will almost always be at least one element in the parameter list; thus, sqrt(Y) and fabs(-21) are appropriate.
4. In the calling program, the function name cannot be used on the left side of an assignment statement.
5. "Parameter list'' is a list of formal parameters. The number and order of parameters in the parameter list should match the number and order of variables used when calling the explicit–function from subprograms.
6. The data type of parameters should match the corresponding data type of variables or values used when calling the explicit–function from subprograms. Casting these arguments is sometimes the easiest way to create matching data types.
7. "Return Type'' declares the data type for the required explicit return. This indicates what type of value will be returned to the calling function.
8. Explicit-functions can be used in expressions and assignment statements; for example,
X = sqrt(Y) - sqrt(Z);
9. Explicit-functions can be used in output statements; for example,
printf ("%8.3f\n", sqrt(3));
Explicit Function
Example 4.1Suppose we have an engineering application that requires the cubing of integers in more than a dozen of the calculations. Let us write a function to compute and explicitly return the cube of an integer.
This explicit-function is to return an integer with a return statement. Let us build a small program which tests function Cube. Section I contains the include for stdio.h.
PROGRAM
Cube.c
# define <stdio.h> /* Section I */
Section II contains global variable Total and the prototype for explicit-function Cube.
int Total = 10; /* Section II */
int Cube (int X);
A small main program which can be used to test explicit-function cube is as follows:main ()
{
int
No = 3;
/* ------Memory Map Cube-1 ------*/
Total = Cube (No);
printf ("Total = %d\n", Total);
/* ------Memory Map Cube-4 ------*/
}
A memory map includes a snapshot of all variables in-scope at some instant in time. Program execution begins with function main. Memory Map Cube-1 contains all of the variables that are in-scope at that instant in time:
When the line
Total = Cube (No);
is executed, execution flow transfers to function Cube. The code for function Cube is
int Cube (int X)
{
int
CubedNo;
/* ------Memory Map Cube-2 ------*/
CubedNo = X * X * X;
/* ------Memory Map Cube-3 ------*/
return (CubedNo);
}
X is the only parameter in the parameter list of function Cube. It is called a value parameter because the memory manager allocates two bytes of contiguous memory for local integer X and copies the value passed into the new variable. Since function Cube is called by line
Total = Cube (No);->Total = Cube (3);
the value 3 is placed in value parameter X. The memory manager also allocates two bytes of contiguous memory for local integer variable CubedNo. Local variables X and CubedNo will be in-scope until the flow of execution exits function Cube. Memory Map Cube-2 contains
Notice that No, from main, is not in-scope at this time. The calculation fills CubeNo with X * X * X. Memory Map Cube-3 reflects the variables in-scope after the calculation.