C.A. Bertulani

These notes are intended to give an introduction to the C++ programming language. They have been adapted and extended from several sources (see credits at the end of these notes). The material can be easily covered in a week for the reader with some experience in programming. At the end of that the reader will be able to write and run his own programs.
 
 

1.1 The Origins of C++

C is in many ways hard to categorise. Compared to assembly language it is high-level, but it nevertheless includes many low-level facilities to directly manipulate the computer's memory. It is therefore an excellent language for writing efficient "systems" programs. But for other types of programs, C code can be hard to understand, and C programs can therefore be particularly prone to certain types of error. The extra object-oriented facilities in C++ are partly included to overcome these shortcomings.

1.2 ANSI C++

1.3 The Programming Environment

1.4 An Example C++ Program

        // The C++ compiler ignores comments which start with  
        // double slashes like this, up to the end of the line.
        
        /* Comments can also be written starting with a slash 
        followed by a star, and ending with a star followed by
         a slash. As you can see, comments written in this way 
        can span more than one line. */
                
        /* This program prompts the user for the current year, the user's 
        current age, and another year. It then calculates the age
        that the user was or will be in the second year entered. */ 
        
        #include <iostream.h>
                
        int main() 
        {
                int year_now, age_now, another_year, another_age; 
        
                cout << "Enter the current year then press RETURN.\n";
                cin >> year_now;
        
                cout << "Enter your current age in years.\n";
                cin >> age_now;
        
                cout << "Enter the year for which you wish to know your age.\n";
                cin >> another_year;
        
                another_age = another_year - (year_now - age_now);
                if (another_age >= 0) {
                        cout << "Your age in " << another_year << ": ";
                        cout << another_age << "\n";
                }
                else { 
                        cout << "You weren't even born in ";
                        cout << another_year << "!\n";
                }
        
                return 0;
        }

This program illustrates several general features of all C++ programs. It begins (after the comment lines) with the statement

This statement is called an include directive. It tells the compiler and the linker that the program will need to be linked to a library of routines that handle input from the keyboard and output to the screen. The header file "iostream.h" contains basic information about this library.

Because the program is short, it is easily packaged up into a single list of program statements and commands. After the include directive, the basic structure of the program is:

        int main() 
        {
                First statement;
                ...
                ...
                Last statement;
        
                return 0;
        }

When at the end of the main program, the line

means "return the value 0 to the computer's operating system to signal that the program has completed successfully". More generally, return statements signal that the particular sub-program has finished, and return a value, along with the flow of control, to the program level above. More about this later.

Our example program uses four variables:

Program variables are not like variables in mathematics. They are more like symbolic names for "pockets of computer memory" which can be used to store different values at different times during the program execution. These variables are first introduced in our program in the variable declaration

        int year_now, age_now, another_year, another_age;

1.6 Very Simple Input, Output and Assignment

        Enter current year then press RETURN.
        1996
        Enter your current age in years.
        36
        Enter the year for which you wish to know your age.
        2001
        Your age in 2001: 41

        cout << Expression1 << Expression2 << ... << ExpressionN;

        Expression1Expression2...ExpressionN

        cout << Expression1; 
        cout << Expression2;
        ... 
        ... 
        cout << ExpressionN;

The numbers in bold in the example screen output above have been typed in by the user. In this particular program run, the program statement

        cin >> year_now;

        another_age = another_year - (year_now - age_now);

1.7 Simple Flow of Control

        if (another_age >= 0) {
                cout << "Your age in " << another_year << ": ";
                cout << another_age << "\n";
        }
        else { 
                cout << "You weren't even born in ";
                cout << another_year << "!\n";
        }

        if (condition) {
                Statement1;
                ...
                ...
                StatementN;
        }
        else {
                StatementN+1;
                ...
                ...
                StatementN+M;
        }

        if (condition)
                Statement;

It is quite common to find "if statements" strung together in programs, as follows:

        ...
        ...
        if (total_test_score < 50)
                cout << "You are a failure. You must study much harder.\n";
        else if (total_test_score < 65)
                cout << "You have just scraped through the test.\n";
        else if (total_test_score < 80)
                cout << "You have done quite well.\n";
        else if (total_test_score < 95)
                cout << "Your score is excellent. Well done.\n";
        else {
                cout << "You cheated!\n";
                total_test_score = 0;
        }
        ...
        ...

Below is the syntax diagram for an "if statement". It is best understood in conjunction with the syntax diagram for a "statement" .
In particular, notice that the diagram doesn't explicitly include the ";" or "{}" delimiters, since these are built into the definition (syntax diagram) of "statement".

1.7.1 Syntax diagram for an If Statement

The C++ compiler accepts the program fragment in our example by counting all of the bold text in

        ...
        ...
        if (total_test_score < 50)
                cout << "You are a failure. You must study much harder.\n";
        else if (total_test_score < 65)
                cout << "You have just scraped through the test.\n";
        else if (total_test_score < 80)
                cout << "You have done quite well.\n";
        else if (total_test_score < 95)
                cout << "Your score is excellent. Well done.\n";
        else {
                cout << "You cheated!\n";
                total_test_score = 0;
        }
        ...
        ...

1.8 Preliminary Remarks about Program Style

    #include <iostream.h> int main() { int year_now, age_now, another_year, another_age; cout << 
"Enter the current year then press RETURN.\n"; cin >> year_now; 
        cout << "Enter your current age in years.\n"; cin >> age_now; cout << 
    "Enter the year for which you wish to know your age.\n"; cin >> 
    another_year; another_age = another_year - (year_now - age_now); if 
    (another_age >= 0) { cout << "Your age in " << another_year << ": "; 
    cout << another_age << "\n"; } else { cout << 
    "You weren't even born in "; cout << another_year << "!\n"; } return 
    0; }

2.1 Identifiers

1. Reserved Words. These are words such as if, int and else, which have a predefined meaning that cannot be changed. Here's a more complete list:

asm auto break case catch char class const

continue default delete do double else enum extern

float for friend goto if inline int long

new operator private protected public register return short

signed sizeof static struct switch template this throw

try typedef union unsigned virtual void volatile while

2. Library Identifiers. These words are supplied default meanings by the programming environment, and should only have their meanings changed if the programmer has strong reasons for doing so. Examples are cin, cout and sqrt (square root).

 
3. Programmer-supplied Identifiers. These words are "created" by the programmer, and are typically variable names, such as year_now and another_age.

2.2 Data Types

Integers

        unsigned short int year_now, age_now, another_year, another_age;

Some rules have to be observed when writing integer values in programs:

1. Decimal points cannot be used; although 26 and 26.0 have the same value, "26.0" is not of type "int".

 
2. Commas cannot be used in integers, so that (for example) 23,897 has to be written as "23897".

 
3. Integers cannot be written with leading zeros. The compiler will, for example, interpret "011" as an octal (base 8) number, with value 9.

Real numbers

Type Casting

        answer = double(numerator) / denominator

Characters

Character constants of type "char" must be enclosed in single quotation marks when used in a program, otherwise they will be misinterpreted and may cause a compilation error or unexpected program behaviour. For example, "'A'" is a character constant, but "A" will be interpreted as a program variable. Similarly, "'9'" is a character, but "9" is an integer.

There is, however, an important (and perhaps somewhat confusing) technical point concerning data of type "char". Characters are represented as integers inside the computer. Hence the data type "char" is simply a subset of the data type "int". We can even do arithmetic with characters. For example, the following expression is evaluated as true on any computer using the ASCII character set:

However, declaring a variable to be of type "char" rather than type "int" makes an important difference as regards the type of input the program expects, and the format of the output it produces. For example, the program

        #include <iostream.h>
        
        int main()
        {
                int number;
                char character;
        
                cout << "Type in a character:\n";
                cin >> character;
        
                number = character;
        
                cout << "The character '" << character;
                cout << "' is represented as the number ";
                cout << number << " in the computer.\n";
        
                return 0;
        }

produces output such as

        Type in a character:
        9
        The character '9' is represented as the number 57 in the computer.

We could modify the above program to print out the whole ASCII table of characters using a "for loop". The "for loop" is an example of a repetition statement - we will discuss these in more detail later. The general syntax is:

        for (initialisation; repetition_condition ; update) {
                Statement1;
                ...
                ...
                StatementN;
        }

Hence to print out the ASCII table, the program above can be modified to:

        #include <iostream.h>

        int main()
        {
                int number;
                char character;
        
                for (number = 32 ; number <= 126 ; number = number + 1) {
        
                        character = number;
                        cout << "The character '" << character;
                        cout << "' is represented as the number ";
                        cout << number << " in the computer.\n";
                }

                return 0;
        }

which produces the output:

        The character ' ' is represented as the number 32 in the computer.
        The character '!' is represented as the number 33 in the computer.
        ...
        ...
        The character '}' is represented as the number 125 in the computer.
        The character '~' is represented as the number 126 in the computer.

Strings

in programs. In fact, "string" is not a fundamental data type such as "int", "float" or "char". Instead, strings are represented as arrays of characters, so we will return to subject of strings later, when we discuss arrays in general.

User Defined Data Types

2.3 Some Tips on Formatting Real Number Output

        #include <iostream.h>
        #include <math.h>
        
        int main() 
        {
                float number;
        
                cout << "Type in a real number.\n";
                cin >> number;
                cout.setf(ios::fixed);    //    LINE 10          
                cout.precision(2);
                cout << "The square root of " << number << " is approximately "; 
                cout << sqrt(number) << ".\n";
        
                return 0;
        }

This produces the output

        Type in a real number.
        200
        The square root of 200.00 is approximately 14.14.

        Type in a real number.
        200
        The square root of 2.00e+02 is approximately 1.41e+01.

        #include <iostream.h>
        #include <math.h>
        
        int main() 
        {
                int number;
        
                cout.width(20);
                cout << "Number" << "Square Root\n\n";
                
                cout.setf(ios::fixed);          
                cout.precision(2);
                for (number = 1 ; number <= 10 ; number = number + 1) {
                        cout.width(20);
                        cout << number << sqrt(number) << "\n";
                }
        
                return 0;
        }

This program produces the output

        Number              Square Root
        
        1                   1.00
        2                   1.41
        3                   1.73
        4                   2.00
        5                   2.24
        6                   2.45
        7                   2.65
        8                   2.83
        9                   3.00
        10                  3.16

2.4 Declarations, Constants and Enumerations

        float number;

        float PI = 3.1416;

Enumerations

        enum { MON, TUES, WED, THURS, FRI, SAT, SUN };

        const int MON = 0;
        const int TUES = 1;
        const int WED = 2;
        const int THURS = 3;
        const int FRI = 4;
        const int SAT = 5;
        const int SUN = 6;

        enum { MON = 1, TUES, WED, THURS, FRI, SAT = -1, SUN };

Where to put Constant and Variable Declarations

        #include <iostream.h>
        
        const float PI = 3.1416;
        const float SCREEN_WIDTH = 317.24;
        
        int drawCircle(float diameter); /* this is a "function prototype" */
        
        int main() 
        {
                float radius = 0;
        
                cout << "Type in the radius of the circle.\n";
                cin >> radius;
        
                drawCircle(radius * 2);
        
                cout.setf(ios::fixed);          
                cout.precision(2);
                cout << "The circumference of a circle of radius " << radius; 
                cout << " is approximately " << 2 * PI * radius << ".\n";

                return 0;
        }
        
        int drawCircle(float diameter)
        {
                float radius = 0;
        
                if (diameter > SCREEN_WIDTH) 
                        radius = SCREEN_WIDTH / 2.0;
                else
                        radius = diameter / 2.0;
                ...
                ...
        }

In any case, notice that the program above incorporates the safety measure of echoing the input. In other words, the given value of "radius" is printed on the screen again, just before the circumference of the circle is output.
 

2.5 Assignments and Expressions

Shorthand Arithmetic Assignment Statements

        number = number + 1;

The first of the above examples may written in even shorter form. Using the increment operator "++", we may simply write

        number++;

        ++number;

        x = 4;
        y = x++;

        x = 4;
        y = ++x;

In general, assignment statements have a value equal to the value of the left hand side after the assignment. Hence the following is a legal expression which can be included in a program and which might be either evaluated as true or as false:

        (y = ++x) == 5

Boolean Expressions and Operators

The fourth of these expressions is true because the operator "&&" has a higher precedence than the operator "||". You can check the relative precedence of the different C++ operators in a C++ programming manual or text book. But if in doubt use ( ) parentheses, which in any case often make the program easier to read.

Compound Boolean expressions are typically used as the condition in "if statements" and "for loops". For example:

        ...
        ...
        if (total_test_score >= 50 && total_test_score < 65)
                cout << "You have just scraped through the test.\n";
        ...
        ...

        ...
        ...
        if (number_of_people = 1)
                cout << "There is only one person.\n";
        ...
        ...

3.1 The Need for Sub-programs

We have already been using sub-programs. For example, in the program which generated a table of square roots, we used the following "for loop":

        ...
        #include<math.h>
        ...     
        ...
                for (number = 1 ; number <= 10 ; number = number + 1) {
                        cout.width(20);
                        cout << number << sqrt(number) << "\n";
                }
        ...
        ...

In this chapter we will discuss how the programmer can define his or her own functions. At first, we will put these functions in the same file as "main". Later we will see how to place different functions in different files.
 

3.2 User-defined Functions

        #include<iostream.h>
        
        int area(int length, int width);                /* function declaration */
        
        /* MAIN PROGRAM: */
        int main()
        {
                int this_length, this_width;      
        
                cout << "Enter the length: ";             /* <--- line 9 */
                cin >> this_length;
                cout << "Enter the width: ";
                cin >> this_width;
                cout << "\n";                             /* <--- line 13 */
        
                cout << "The area of a " << this_length << "x" << this_width;
                cout << " rectangle is " << area(this_length, this_width);
        
                return 0;
        }
        /* END OF MAIN PROGRAM */
        
        /* FUNCTION TO CALCULATE AREA: */
        int area(int length, int width)   /* start of function definition */
        {
                int number;
        
                number = length * width;
        
                return number;
        }                                 /* end of function definition */
        /* END OF FUNCTION */

Although this program is not written in the most succinct form possible, it serves to illustrate a number of features concerning functions:

• The structure of a function definition is like the structure of "main()", with its own list of variable declarations and program statements.

 
• A function can have a list of zero or more parameters inside its brackets, each of which has a separate type.

 
• A function has to be declared in a function declaration at the top of the program, just after any global constant declarations, and before it can be called by "main()" or in other function definitions.

 
• Function declarations are a bit like variable declarations - they specify which type the function will return.

 

        double absolute_value(double number)
        {
                if (number >= 0)
                        return number;
                else
                        return 0 - number;
        }

3.3 Value and Reference Parameters

Functions which use Value Parameters are Safe

        Enter a positive integer:
        4
        The factorial of 4 is 24, and the square root of 4 is 2.

It would make sense to use the predefined function "sqrt(...)" in our program, and write another function "factorial(...)" to compute the factorial n! = (1 x 2 x ... x n) of any given positive integer n. Here's the complete program:

        #include<iostream.h>
        #include<math.h>
        
        int factorial(int number);
        
        /* MAIN PROGRAM: */
        int main()
        {
                int whole_number;      
        
                cout << "Enter a positive integer:\n";
                cin >> whole_number;
                cout << "The factorial of " << whole_number << " is ";
                cout << factorial(whole_number);
                cout << ", and the square root of " << whole_number << " is ";
                cout << sqrt(whole_number) << ".\n";

                return 0;
        }
        /* END OF MAIN PROGRAM */
        
        /* FUNCTION TO CALCULATE FACTORIAL: */
        int factorial(int number)
        {
                int product = 1;
        
                for ( ; number > 0 ; number--)
                        product *= number;
        
                return product;
        }
        /* END OF FUNCTION */

By the use of a value parameter, we have avoided the (correct but unwanted) output

        Enter a positive integer:
        4
        The factorial of 4 is 24, and the square root of 1 is 1.

Reference Parameters

        int area(int length, int width);

Notice that, although the function "get_dimensions" permanently alters the values of the parameters "this_length" and "this_width", it does not return any other value (i.e. is not a "function" in the mathematical sense). This is signified in both the function declaration and the function heading by the reserved word "void".

3.4 Polymorphism and Overloading

        #include<iostream.h>
        
        int average(int first_number, int second_number, int third_number);
        
        int average(int first_number, int second_number);
        
        /* MAIN PROGRAM: */
        int main()
        {
                int number_A = 5, number_B = 3, number_C = 10;      
        
                cout << "The integer average of " << number_A << " and ";
                cout << number_B << " is ";
                cout << average(number_A, number_B) << ".\n\n";
        
                cout << "The integer average of " << number_A << ", ";
                cout << number_B << " and " << number_C << " is ";
                cout << average(number_A, number_B, number_C) << ".\n";
                
                return 0;
        }
        /* END OF MAIN PROGRAM */
        
        /* FUNCTION TO COMPUTE INTEGER AVERAGE OF 3 INTEGERS: */
        int average(int first_number, int second_number, int third_number)
        {
                return ((first_number + second_number + third_number) / 3);
        }  
        /* END OF FUNCTION */
        
        /* FUNCTION TO COMPUTE INTEGER AVERAGE OF 2 INTEGERS: */
        int average(int first_number, int second_number)
        {
                return ((first_number + second_number) / 2);
        }  
        /* END OF FUNCTION */

This program produces the output:

        The integer average of 5 and 3 is 4.
        
        The integer average of 5, 3 and 10 is 6.

3.5 Procedural Abstraction and Good Programming Style

Developing functions in this manner is referred to as functional or procedural abstraction. This process is aided by the use of value parameters and local variables declared within the body of a function. Functions written in this manner can be regarded as "black boxes". As users of the function, we neither know nor care why they work.

3.6 Splitting Programs into Different Files

• The header file "math.h" contains the function declarations for "sqrt(...)" (and for many other mathematical functions). This is why in the example programs which call "sqrt(...)" we are able to write "#include<math.h>", instead of having to declare the function explicitly.

 
• The implementation file "math.cp" or "math.cpp" contains the actual function definitions for "sqrt(...)" and other mathematical functions. (In practice, many C++ systems have one or a few big file(s) containing all the standard function definitions, perhaps called "ANSI.cp" or similar.)

 

The code in the main program file is as follows:

        #include<iostream.h>
        #include"averages.h"
        
        int main()
        {
                int number_A = 5, number_B = 3, number_C = 10;
                
                cout << "The integer average of " << number_A << " and ";
                cout << number_B << " is ";
                cout << average(number_A, number_B) << ".\n\n";
                
                cout << "The integer average of " << number_A << ", ";
                cout << number_B << " and " << number_C << " is ";
                cout << average(number_A, number_B, number_C) << ".\n";
                
                return 0;
        }

Notice that whereas "include" statements for standard libraries such as "iostream.h" delimit the file name with angle ("<>") brackets, the usual convention is to delimit user-defined library file names with double quotation marks - hence the line " #include"averages.h" " in the listing above.

The code in the header file ">averages.h>" is listed below. Notice the use of the file identifier "AVERAGES_H", and the reserved words "ifndef" ("if not defined"), "define", and "endif". "AVERAGES_H" is a (global) symbolic name for the file. The first line and last two lines of code ensure that the compiler (in fact, the preprocessor) only works through the code in between once, even if the line " #include"averages.h" " is included in more than one other file.

Constant and type definitions are also often included in header files. You will learn more about this in the object-oriented part of the course.

        #ifndef AVERAGES_H
        
        /* (constant and type definitions could go here) */
        
        /* FUNCTION TO COMPUTE INTEGER AVERAGE OF 3 INTEGERS: */
        int average(int first_number, int second_number, int third_number);
        
        /* FUNCTION TO COMPUTE INTEGER AVERAGE OF 2 INTEGERS: */
        int average(int first_number, int second_number);
        
        #define AVERAGES_H
        #endif

Finally, the code in the implementation file "averages.cp" is as follows:

        #include<iostream.h>
        #include"averages.h"
        
        /* FUNCTION TO COMPUTE INTEGER AVERAGE OF 3 INTEGERS: */
        int average(int first_number, int second_number, int third_number)
        {
                return ((first_number + second_number + third_number) / 3);
        }
        /* END OF FUNCTION */
        
        /* FUNCTION TO COMPUTE INTEGER AVERAGE OF 2 INTEGERS: */
        int average(int first_number, int second_number)
        {
                return ((first_number + second_number) / 2);
        }
        /* END OF FUNCTION */

Note the modularity of this approach. We could change the details of the code in "averages.cp" without making any changes to the code in "averages.h" or in the main program file.
 

4.1. Why Use Files?

The easiest way to think about a file is as a linear sequence of characters. In a simplifed picture (which ignores special characters for text formatting) these lecture notes might be stored in a file called "Lecture_4" as:

4.2 Streams

In fact, input and output streams such as "cin" and "cout" are examples of (stream) objects. So learning about streams is a good way to introduce some of the syntax and ideas behind the object-oriented part of C++. The header file which lists the operations on streams both to and from files is called "fstream.h". We will therefore assume that the program fragments discussed below are embedded in programs containing the "include" statement

As we shall see, the essential characteristic of stream processing is that data elements must be sent to or received from a stream one at a time, i.e. in serial fashion.
 

Creating Streams

        ifstream in_stream; 
        ofstream out_stream;

Connecting and Disconnecting Streams to Files

To connect the ifstream "in_stream" to the file "Lecture_4", we use the following statement:

        in_stream.open("Lecture_4");

To connect the ofstream "out_stream" to the file "Lecture_4", we use an analogous statement:

        out_stream.open("Lecture_4");

To disconnect connect the ifstream "in_stream" to whatever file it is connected to, we write:

        in_stream.close();

The statement:

        out_stream.close();

In this case, the file "Lecture_4" still exists, but is empty.
 
 
 
 
 

4.3 Checking for Failure with File Commands

        in_stream.fail();

        #include <iostream.h>
        #include <fstream.h>
        #include <stdlib.h>
        
        int main()
        {
                ifstream in_stream;
        
                in_stream.open("Lecture_4");
                if (in_stream.fail())
                {
                        cout << "Sorry, the file couldn't be opened!\n";
                        exit(1);
                }
                ...

4.4 Character Input and Output

Input using "get(...)"

        in_stream.get(ch);

Output using "put(...)"

        out_stream.put('4');

The "putback(...)" Function

        in_stream.putback(ch);

Indeed, we can "putback" any character we want to. The alternative statement

        in_stream.putback('7');

4.5 Checking for the End of an Input File

4.5.1 End-of-file Checking For Systems Which Implement "eof()"

In such systems, when an ifstream is initially connected to a file, the EOF flag is set to FALSE (even if the file is empty). However, if the ifstream "in_stream" is positioned at the end of a file, and the EOF flag is FALSE, the statement

        in_stream.get(ch);

and then execute the statement

        in_stream.get(ch);

If we again execute the statement

        in_stream.get(ch);

The boolean expression

        in_stream.eof()

Below is a simple program which uses these techniques to copy the file "Lecture_4" simultaneously to the screen and to the file "Copy_of_4". Note the use of a while loop in this program. "While" loops are simplified versions of "for" loops, without the initialisation and update statements in the "()" parentheses (we will look at such statements again in the next section).
 

        #include <iostream.h>
        #include <fstream.h>
        
        int main()
        {
                char character;
                ifstream in_stream;
                ofstream out_stream;
        
                in_stream.open("Lecture_4");
                out_stream.open("Copy_of_4");
        
                in_stream.get(character);
                while (!in_stream.eof())
                {
                        cout << character;
                        out_stream.put(character);
                        in_stream.get(character);
                }

                out_stream.close();
                in_stream.close();
        
                return 0;
        }

4.5.2 End-of-file Checking For Systems Which Don't Implement "eof()"

        in_stream.get(ch);

This doesn't matter too much, as long as we are careful not to use "in_stream" for any more operations. For such systems, the program can be rewritten as
 

        #include <iostream.h>
        #include <fstream.h>
        
        int main()
        {
                char character;
                ifstream in_stream;
                ofstream out_stream;
        
                in_stream.open("Lecture_4");
                out_stream.open("Copy_of_4");
        
                in_stream.get(character);
                while (!in_stream.fail())
                {
                        cout << character;
                        out_stream.put(character);
                        in_stream.get(character);
                }
        
                out_stream.close();
                in_stream.close();
        
                return 0;
        }

4.6 Streams as Arguments in Functions

        #include <iostream.h>
        #include <fstream.h>
        
        void copy_to(ifstream& in, ofstream& out);
        
        /* MAIN PROGRAM: */
        int main()
        {
                ifstream in_stream;
                ofstream out_stream;
        
                in_stream.open("Lecture_4");
                out_stream.open("Copy_of_4");
                copy_to(in_stream, out_stream);
                out_stream.close();
                in_stream.close();
        
                return 0;
        }
        /* END OF MAIN PROGRAM */
        
        /* FUNCTION TO COPY A FILE TO ANOTHER FILE AND TO THE SCREEN: */
        void copy_to(ifstream& in, ofstream& out)
        {
                char character;
        
                in.get(character);
                while (!in.fail())
                {
                        cout << character;
                        out.put(character);
                        in.get(character);
                }
        }
        /* END OF FUNCTION */

4.7 Input and Output Using ">>" and "<<"

However, the operators ">>" and "<<", which we have already met in the context of keyboard input and screen output, do some of this conversion automatically. For example, from the state

execution of the statement

        out_stream << 437 << ' ';

When using these higher level facilities, it is important to include at least one "' '" (blank) character (or a new-line character) after each item of data written. This ensures that the data items are correctly separated in the file, ready for input using ">>". For example, from the state

where "n" has been declared as of data type "int", execution of the statement

        in_stream >> n;

Notice that the operation ">>" has skipped over the blank space "' '" before the number 437. It always does this, no matter what data type it has been reading or expects to read (even characters).

The following program, which first creates a file called "Integers" containing the integers 51, 52, 53, 54 and 55, further illustrates these techniques.

        #include <iostream.h>
        #include <fstream.h>
        
        int main()
        {
                char character;
                int number = 51;
                int     count = 0;
                ofstream out_stream;
                ifstream in_stream1;   /* Stream for counting integers. */
                ifstream in_stream2;   /* Stream for counting characters. */
        
                /* Create the file */
                out_stream.open("Integers");
                for (count = 1 ; count <= 5 ; count++)
                        out_stream << number++ << ' ';
                out_stream.close();
        
                /* Count the integers in the file */
                in_stream1.open("Integers");
                count = 0;
                in_stream1 >> number;
                while (!in_stream1.fail())
                {
                        count++;
                        in_stream1 >> number;
                }
                in_stream1.close();
                cout << "There are " << count << " integers in the file,\n";
        
                /* Count the non-blank characters */
                in_stream2.open("Integers");
                count = 0;
                in_stream2 >> character;
                while (!in_stream2.fail())
                {
                        count++;
                        in_stream2 >> character;
                }
                in_stream2.close();
                cout << "represented using " << count << " characters.\n";
        
                return 0;
        }

This program produces the following output:

        There are 5 integers in the file,
        represented using 10 characters.

5.1 Boolean Values, Expressions and Functions

As we have seen, in reality C++ represents "True" as the integer 1, and "False" as 0. However, expressions such as

or

aren't particularly clear - it would be better to be able to follow our intuition and write

and

Furthermore, it is desirable to have a seperate type for variables such as "condition1", rather than having to declare them as of type "int". We can achieve all of this with a named enumeration:

        enum Logical {False, True}

        enum Logical {False = 0, True = 1}

        Logical condition1, condition2;

        #include <iostream.h>
        
                enum Logical {False, True};
        
                Logical acceptable(int age, int score);
        
        /* START OF MAIN PROGRAM */
        int main() 
        {
                int candidate_age, candidate_score;
        
                cout << "Enter the candidate's age: ";
                cin >> candidate_age;
                cout << "Enter the candidate's score: ";
                cin >> candidate_score;
        
                if (acceptable(candidate_age, candidate_score))
                        cout << "This candidate passed the test.\n";
                else
                        cout << "This candidate failed the test.\n";
        
                return 0;
        }
        /* END OF MAIN PROGRAM */

        /* FUNCTION TO EVALUATE IF TEST SCORE IS ACCEPTABLE */
        Logical acceptable(int age, int score)
        {
                if (age <= 14 && score >= 50)
                        return True;
                else if (age <= 16 && score >= 55)
                        return True;
                else if (score >= 60)
                        return True;
                else
                        return False;
        }
        /*END OF FUNCTION */

Note that since "True" and "False" are constants, it makes sense to declare them outside the scope of the main program, so that the type "Logical" can be used by every function in the file. An alternative way to write the above function "acceptable(...)" would be:

        /* FUNCTION TO EVALUATE IF TEST SCORE IS ACCEPTABLE */
        Logical acceptable(int age, int score)
        {
                Logical passed_test = False;
        
                if (age <= 14 && score >= 50)
                        passed_test = True;
                else if (age <= 16 && score >= 55)
                        passed_test = True;
                else if (score >= 60)
                        passed_test = True;
                
                return passed_test;
        }
        /*END OF FUNCTION */

5.2 "For", "While" and "Do ... While" Loops

        #include <iostream.h>

        int main()
        {
                int number;
                char character;
        
                for (number = 32 ; number <= 126 ; number = number + 1) {
        
                        character = number;
                        cout << "The character '" << character;
                        cout << "' is represented as the number ";
                        cout << number << " in the computer.\n";
                }

                return 0;
        }

can be written equivalently as

        #include <iostream.h>
        
        int main()
        {
                int number;
                char character;
        
                number = 32;
                while (number <= 126)
                {
                        character = number;
                        cout << "The character '" << character;
                        cout << "' is represented as the number ";
                        cout << number << " in the computer.\n";
                        number++;
                }

                return 0;
        }

Moreover, any "while" loop can be trivially re-written as a "for" loop - we could for example replace the line

        while (number <= 126)

        for ( ; number <= 126 ; )

There is a third kind of "loop" statement in C++ called a "do ... while" loop. This differs from "for" and "while" loops in that the statement(s) inside the {} braces are always executed once, before the repetition condition is even checked. "Do ... while" loops are useful, for example, to ensure that the program user's keyboard input is of the correct format:

        ...
        ...
        do
        {
                cout << "Enter the candidate's score: ";
                cin >> candidate_score;
                if (candidate_score > 100 || candidate_score < 0)
                        cout << "Score must be between 0 and 100.\n";
        }
        while (candidate_score > 100 || candidate_score < 0);
        ...
        ...

This avoids the need to repeat the input promt and statement, which would be necessary in the equivalent "while" loop:

        ...
        ...
        cout << "Enter the candidate's score: ";
        cin >> candidate_score;
        while (candidate_score > 100 || candidate_score < 0)
        {
                cout << "Score must be between 0 and 100.\n";
                cout << "Enter the candidate's score: ";
                cin >> candidate_score;
        }
        ...
        ...

5.3 Multiple Selection and Switch Statements

        ...
        ...
        if (total_test_score >=0 && total_test_score < 50)
                cout << "You are a failure - you must study much harder.\n";
        else if (total_test_score < 60)
                cout << "You have just scraped through the test.\n";
        else if (total_test_score < 80)
                cout << "You have done quite well.\n";
        else if (total_test_score <= 100)
                cout << "Your score is excellent - well done.\n";
        else
                cout << "Incorrect score - must be between 0 and 100.\n";
        ...
        ...

        score_out_of_ten = total_test_score / 10;

        ...
        ...
        score_out_of_ten = total_test_score / 10;
        
        switch (score_out_of_ten)
        {
                case 0:
                case 1:
                case 2:
                case 3:
                case 4:     cout << "You are a failure - you ";
                            cout << "must study much harder.\n";
                            break;
        
                case 5:     cout << "You have just scraped through the test.\n";
                            break;

                case 6:
                case 7:     cout << "You have done quite well.\n";
                            break;
        
                case 8:
                case 9:
                case 10:    cout << "Your score is excellent - well done.\n";
                            break;

                default:    cout << "Incorrect score - must be between ";
                            cout << "0 and 100.\n";
        }
        ...
        ...

In general, the syntax of a "switch" statement is (approximately):

    switch (selector)
    {
        case label1:    <statements 1>
                        break;
        ...
        ...
        ...
    
        case labelN:    <statements N>
                        break;
    
        default:        <statements>
    }

• The statements which are executed are exactly those between the first label which matches the value of selector and the first "break" after this matching label.

 
• The "break" statements are optional, but they help in program efficiency and clarity and should ideally always be used to end each case. When a "break" is encountered within a case's statement, control is transfered immediately to the first program statement following the entire "switch" statement. Otherwise, execution continues.

 
• The selector can have a value of any ordinal type (e.g. "char" or "int" but not "float").

 
• The "default" is optional, but is a good safety measure.

5.4 Blocks and Scoping

        #include <iostream.h>
        
        int integer1 = 1;
        int integer2 = 2;
        int integer3 = 3;
        
        int main()
        {
                int integer1 = -1;
                int integer2 = -2;
                {
                        int integer1 = 10;
                        cout << "integer1 == " << integer1 << "\n";
                        cout << "integer2 == " << integer2 << "\n";
                        cout << "integer3 == " << integer3 << "\n";
                }
                cout << "integer1 == " << integer1 << "\n";
                cout << "integer2 == " << integer2 << "\n";
                cout << "integer3 == " << integer3 << "\n";
        
                return 0;
        }

produces the output

        integer1 == 10
        integer2 == -2
        integer3 == 3
        integer1 == -1
        integer2 == -2
        integer3 == 3

        #include <iostream.h>
        
        int main()
        {
                int number;
        
                for (number = 1 ; number <= 10 ; number++)
                {
                        int multiplier;
        
                        for (multiplier = 1 ; multiplier <= 10 ; multiplier++)
                        {
                                cout << number << " x " << multiplier << " = ";
                                cout << number * multiplier << "\n";
                        }
                        cout << "\n";
                }
                ...
                ...

However, we can achieve the same effect, and end up with a clearer program, by using a function:

        #include <iostream.h>
        
        void print_times_table(int value, int lower, int upper);
        
        int main()
        {
                int number;
        
                for (number = 1 ; number <= 10 ; number++)
                {
                        print_times_table(number,1,10);
                        cout << "\n";
                }
                ...
                ...
        }
        
        void print_times_table(int value, int lower, int upper)
        {
                int multiplier;
        
                for (multiplier = lower ; multiplier <= upper ; multiplier++)
                {
                        cout << value << " x " << multiplier << " = ";
                        cout << value * multiplier << "\n";
                }
        }

or eliminate all variable declarations from "main()" using two functions:

        #include <iostream.h>
        
        void print_tables(int smallest, int largest);
        
        void print_times_table(int value, int lower, int upper);
        
        int main()
        {
                print_tables(1,10);
                ...
                ...
        }
        
        void print_tables(int smallest, int largest)
        {
                int number;
        
                for (number = smallest ; number <= largest ; number++)
                {
                        print_times_table(number,1,10);
                        cout << "\n";
                }
        }
        
        void print_times_table(int value, int lower, int upper)
        {
                int multiplier;
        
                for (multiplier = lower ; multiplier <= upper ; multiplier++)
                {
                        cout << value << " x " << multiplier << " = ";
                        cout << value * multiplier << "\n";
                }
        }

5.5 A Remark about Nested Loop Statements

6.1 The Basic Idea and Notation

Declaring an array

        <component type>  <variable identifier>[<integer value>];

        int hours[6];

        const int NO_OF_EMPLOYEES = 6;
        int hours[NO_OF_EMPLOYEES];

        const int NO_OF_EMPLOYEES = 6;
        typedef int hours_array[NO_OF_EMPLOYEES];
        hours_array hours;
        hours_array hours_week_two;

        hours[0]   hours[1]   hours[2]   hours[3]   hours[4]   hours[5]

Assignment Statements and Expressions with Array Elements

        hours[4] = 34;
        hours[5] = hours[4]/2;

        if (number < 4 && hours[number] >= 40) { ...

        #include <iostream.h>
        
        const int NO_OF_EMPLOYEES = 6;
        typedef int hours_array[NO_OF_EMPLOYEES];
        
        int main()
        {
                hours_array hours;
                int count;
        
                for (count = 1 ; count <= NO_OF_EMPLOYEES ; count++)
                {
                        cout << "Enter hours for employee number " << count << ": ";
                        cin >> hours[count - 1];
                }
        
                return 0;
        }

A typical run might produce the following input/output:

        Enter hours for employee number 1: 38
        Enter hours for employee number 2: 42
        Enter hours for employee number 3: 29
        Enter hours for employee number 4: 35
        Enter hours for employee number 5: 38
        Enter hours for employee number 6: 37

It is instructive to consider what would have happened had we forgotten to subtract 1 from the variable "count" in the "cin ..." statement (within the "for" loop) in the above program Unlike some languages, C++ does not do range bound error checking, so we would have simply ended up in the state:

In other words, C++ would have simply put the value "37" into the next integer-sized chunk of memory located after the memory block set aside for the array "hours". This is a very undesirable situation - the compiler might have already reserved this chunk of memory for another variable (perhaps, for example, for the variable "count").

Array elements can be of data types other than "int". Here's a program that prints itself out backwards on the screen, using an array of type "char".

        #include <iostream.h>
        #include <fstream.h>
        
        const int MAX = 1000;
        typedef char file_array[MAX];
        
        int main()
        {
                char character;
                file_array file;
                int count;
                ifstream in_stream;
        
                in_stream.open("6-1-2.cp");
                in_stream.get(character);
                for (count = 0 ; ! in_stream.fail() && count < MAX ; count++) 
                {
                        file[count] = character;
                        in_stream.get(character);
                }
                in_stream.close();
        
                while (count > 0)
                        cout << file[--count];

                return 0;
        }

Note the use of the condition "... && count < MAX ; ..." in the head of the "for" loop, to avoid the possibility of a range bound error.
 

6.2 Arrays as Parameters in Functions

        float average(hours_array hrs)
        {
                float total = 0;
                int count;
                for (count = 0 ; count < NO_OF_EMPLOYEES ; count++)
                        total += float(hrs[count]);
                return (total / NO_OF_EMPLOYEES);
        }

We could make this function more general by including a second parameter for the length of the array:

        float average(int list[], int length)
        {
                float total = 0;
                int count;
                for (count = 0 ; count < length ; count++)
                        total += float(list[count]);
                return (total / length);
        }

Although array parameters are not declared with an "&" character in function declarations and definitions, they are effectively reference parameters (rather than value parameters). In other words, when they execute, functions do not make private copies of the arrays they are passed (this would potentially be very expensive in terms of memory). Hence, like the reference parameters we have seen in Lecture 3, arrays can be permanently changed when passed as arguments to functions. For example, after a call to the following function, each element in the third array argument is equal to the sum of the corresponding two elements in the first and second arguments:

        void add_lists(int first[], int second[], int total[], int length)
        {
                int count;
                for (count = 0 ; count < length ; count++)
                        total[count] = first[count] + second[count];
        }

As a safety measure, we can add the modifier "const" in the function head:

        void add_lists(const int fst[], const int snd[], int tot[], int len)
        {
                int count;
                for (count = 0 ; count < len; count++)
                        tot[count] = fst[count] + snd[count];
        }

        void no_effect(const int list[])
        {
                do_nothing(list);
        }
        
        void do_nothing(int list[])
        {
                ;
        }

This is because, although we can see that "do_nothing(...)" does nothing, its head doesn't include the modifier "const", and the compiler only looks at the head of "do_nothing(...)" when checking to see if the call to this function from within "no_effect(...)" is legal.
 

6.3 Sorting Arrays

The basic idea of selection sort is:

For each index position I in turn:

1. Find the smallest data value in the array from positions I to (Length - 1), where "Length" is the number of data values stored.

 
2. Exchange the smallest value with the value at position I.

 

        int a[5];

Selection sort takes the array through the following sequence of states:

Each state is generated from the previous one by swapping the two elements of the array marked with a "bullet".

We can code this procedure in C++ with three functions. The top level function "selection_sort(...)" (which takes and array and an integer argument) sorts its first (array) argument by first calling the function "minimum_from(array,position,length)", which returns the index of the smallest element in "array" which is positioned at or after the index "position". It then swaps values according to the specification above, using the "swap(...)" function:

        void selection_sort(int a[], int length)
        {
                for (int count = 0 ; count < length - 1 ; count++)
                        swap(a[count],a[minimum_from(a,count,length)]);
        }
        
        int minimum_from(int a[], int position, int length)
        {
                int min_index = position;
        
                for (int count = position + 1 ; count < length ; count ++)
                        if (a[count] < a[min_index])
                                min_index = count;
        
                return min_index;
        }
        
        void swap(int& first, int& second)
        {
                int temp = first;
                first = second;
                second = temp;
        }

6.4 Two-dimensional Arrays

A bitmap consists of a grid of Boolean values representing the state of the dots or pixels on a screen. "True" means "on" or that the pixel is white; "False" means "off" or the pixel is black. Let's suppose the screen is 639 pixels wide and 449 pixels high. We can declare the coresponding array as follows:

        enum Logical {False, True};
        const int SCREEN_WIDTH = 639;
        const int SCREEN_HEIGHT = 449;
        Logical screen[SCREEN_WIDTH][SCREEN_HEIGHT];

        screen[3][1] = True;

        void clear_bitmap(Logical bitmap[][SCREEN_HEIGHT], int screen_width)
        {
                for (int row = 0 ; row < SCREEN_HEIGHT ; row++)
                        for (int column = 0 ; column < screen_width; column++)
                                bitmap[row][column] = False;
        }

6.5 Strings

The Sentinel String Character '\0'

In other words, although both "phrase" and "list" are arrays of characters, only "phrase" is big enough to contain the string value ""Enter age: "". We don't care what characters are stored in the variables "phrase[12]" and "phrase[13]", because all the string functions introduced below ignore characters after the "'\0'".
 

String Variable Declarations and Assignments

        char phrase[14];

        char phrase[14] = {'E','n','t','e','r',' ','a','g','e',':',' ','\0'};

        char phrase[14] = "Enter age: ";

        char phrase[] = {'E','n','t','e','r',' ','a','g','e',':',' ','\0'};
char phrase[] = "Enter age: ";

        char phrase[12] = "Enter age: ";

        phrase = "You typed: ";

Some Predefined String Functions

        #include<string.h>

        strcpy(a_string, "You typed: ");

        strcpy(a_string, another_string);

We can, however, check the length of the value stored in "another_string" using the function "strlen(...)". The call "strlen(another_string)" returns the length of the current string stored in "another_string" (the character "'\0'" is not counted).

The comparison function "strcmp(...)" returns "False" (i.e. 0) if its two string arguments are the same, and the two argument function "strcat(...)" concatenates its second argument onto the end of its first argument. The previuos program illustrates the use of these functions. Again, care must be taken with "strcat(...)". C++ does not check that the first variable argument is big enough to contain the two concatenated strings, so that once again there is a danger of undetected range bound errors.
 
 
 

String Input using "getline(...)"

        ...
        ...
        cout << "Enter name: ";
        cin >> a_string;
        ...
        ...

        ...
        ...
        Enter name: Carlosler
        ...
        ...

        cin.getline(a_string,80);

allows the user to type in a string of up to 79 characters long, including spaces. (The extra element is for the sentinel character.) The following program illustrates the use of "getline(...)", "strcmp(...)", "strcpy(...)" and "strcat(...)":

        #include <iostream.h>
        #include <string.h>
        
        const int MAXIMUM_LENGTH = 80;
        
        int main()
        {
                char first_string[MAXIMUM_LENGTH];
                char second_string[MAXIMUM_LENGTH];
        
                cout << "Enter first string: ";
                cin.getline(first_string,MAXIMUM_LENGTH);
                cout << "Enter second string: ";
                cin.getline(second_string,MAXIMUM_LENGTH);
        
                cout << "Before copying the strings were ";
                if (strcmp(first_string,second_string)) 
                        cout << "not ";
                cout << "the same.\n";
        
                strcpy(first_string,second_string);
        
                cout << "After copying the strings were ";
                if (strcmp(first_string,second_string))
                        cout << "not ";
                cout << "the same.\n";
        
                strcat(first_string,second_string);
        
                cout << "After concatenating, the first string is: ";
                cout << first_string;
        
                return 0;
        }

        Enter first string: Hello class.
        Enter second string: Hello Rob.
        Before copying the strings were not the same.
        After copying the strings were the same.
        After concatenating, the first string is: Hello Rob.Hello Rob.

7.1 Introducing Pointers

Declaring Pointers

        int *number_ptr;

        typedef int *IntPtrType;

        IntPtrType number_ptr1, number_ptr2, number_ptr3;

Assignments with Pointers Using the Operators "*" and "&"

Given a particular data type, such as "int", we can write assignment statements involving both ordinary variables and pointer variables of this data type using the dereference operator "*" and the (complementary) address-of operator "&". Roughly speaking, "*" means "the variable located at the address", and "&" means "the address of the variable". We can illustrate the uses of these operators with a simple example program:

        #include <iostream.h>
        
        typedef int *IntPtrType; 
        
        int main()
        {
                IntPtrType ptr_a, ptr_b;
                int num_c = 4, num_d = 7;
                
                ptr_a = &num_c;              /* LINE 10 */
                ptr_b = ptr_a;                   /* LINE 11 */
                        
                cout << *ptr_a << " " << *ptr_b << "\n";
                
                ptr_b = &num_d;              /* LINE 15 */
                
                cout << *ptr_a << " " << *ptr_b << "\n";
        
                *ptr_a = *ptr_b;                 /* LINE 19 */
                        
                cout << *ptr_a << " " << *ptr_b << "\n";
                
                cout << num_c << " " << *&*&*&num_c << "\n";
                
                return 0;
        }

        4 4
        4 7
        7 7
        7 7

after the assignment at line 15 this changes to:

and after the assignment at line 19 it becomes:

Note that "*" and "&" are in a certain sense complementary operations; "*&*&*&num_c" is simply "num_c".
 

The "new" and "delete" operators, and the constant "NULL".

        ptr_a = &num_c;

Dynamic variables are "created" using the reserved word "new", and "destroyed" (thus freeing-up memory for other uses) using the reserved word "delete". Below is a program analogous to the previous program, which illustrates the use of these operations:

        #include <iostream.h>
        
        typedef int *IntPtrType; 
        
        int main()
        {
                IntPtrType ptr_a, ptr_b;    /* LINE 7 */
        
                ptr_a = new int;            /* LINE 9 */
                *ptr_a = 4;
                ptr_b = ptr_a;              /* LINE 11 */
        
                cout << *ptr_a << " " << *ptr_b << "\n";
        
                ptr_b = new int;            /* LINE 15 */
                *ptr_b = 7;                 /* LINE 16 */
        
                cout << *ptr_a << " " << *ptr_b << "\n";
        
                delete ptr_a;
                ptr_a = ptr_b;              /* LINE 21 */
        
                cout << *ptr_a << " " << *ptr_b << "\n";
        
                delete ptr_a;               /* LINE 25 */
        
                return 0;
        }

The output of this program is:

        4 4
        4 7
        7 7

after the assignments in lines 9, 10 and 11 this changes to:

after the assignments at lines 15 and 16 the state is:

and after the assignment at line 21 it becomes:

Finally, after the "delete" statement in lines 25, the program state returns to:

In the first and last diagrams above, the pointers "ptr_a" and "ptr_b" are said to be dangling. Note that "ptr_b" is dangling at the end of the program even though it has not been explicitly included in a "delete" statement.

If "ptr" is a dangling pointer, use of the corresponding dereferenced expression "*ptr" produces unpredictable (and sometimes disastrous) results. Unfortunately, C++ does not provide any inbuilt mechanisms to check for dangling pointers. However, safeguards can be added to a program using the special symbolic memory address "NULL", defined in the library "stddef.h". Any pointer of any data type can be set to "NULL". For example, if we planned to extend the previous programand wanted to safeguard against inappropriate use of the dereferenced pointer identifiers "*ptr_a" and "*ptr_b", we could add code as follows:

        #include <iostream.h>
        #include <stddef.h>
        ...
        ...
                delete ptr_a;
                ptr_a = NULL;
                ptr_b = NULL;
                ...
                ...
                if (ptr_a != NULL)
                {
                        *ptr_a = ...
                        ...
                        ...

In the case that there is not sufficient memory to create a dynamic variable of the appropriate data type after a call to "new", C++ automatically sets the corresponding pointer to "NULL". Hence the following code typifies the kind of safety measure that might be included in a program using dynamic variables:

7.2 Array Variables and Pointer Arithmetic

        int hours[6];

        hours[0]   hours[1]   hours[2]   hours[3]   hours[4]   hours[5]

        int *ptr;

        ptr = hours;

        *(hours + 1)   *(hours + 2)   ...

        *(ptr + 1)   *(ptr + 2)   ...

Pointer arithmetic gives an alternative and sometimes more succinct method of manipulating arrays. The following is a function to convert a string to upper case letters:

        void ChangeToUpperCase(char phrase[])
        {
                int index = 0;
                while (phrase[index] != '\0')
                {
                        if (LowerCase(phrase[index]))
                                ChangeToUpperCase(phrase[index]);
                        index++;
                }
        }
        
        int LowerCase(char character)
        {
                return (character >= 'a' && character <= 'z');
        }
        
        void ChangeToUpperCase(char &character)
        {
                character += 'A' - 'a';
        }

Note the use of polymorphism with the function "ChangeToUpperCase(...)" - the compiler can distinguish the two versions because one takes an argument of type "char", whereas the other takes an array argument. Since "phrase" is really a pointer variable, the array argument version can be re-written using pointer arithmetic:

void ChangeToUpperCase(char *phrase)
        {
                while (*phrase != '\0')
                {
                        if (LowerCase(*phrase))
                                ChangeToUpperCase(*phrase);
                        phrase++;
                }
        }

This re-writing is transparent as far as the rest of the program is concerned - either version can be called in the normal manner using a string argument:

        char a_string[] = "Hello World";
        ...
        ...
        ChangeToUpperCase(a_string);

7.3 Dynamic Arrays

        int *number_ptr;
        number_ptr = new int[10];

        number_ptr[0]   number_ptr[1]   ...             number_ptr[9]

        *number_ptr   *(number_ptr + 1)   ...   *(number_ptr + 9)

        delete [] number_ptr;

        cout << "Enter number of integers in the list: ";
        cin >> no_of_integers;

Dynamic arrays can be passed as function parameters just like ordinary arrays, so we can simply use the definition of the function "average()" from the previous section
with this program.
 

7.4 Automatic and Dynamic Variables

(N.B. It is also possible to declare variables as being static , i.e. remaining in existence throughout the subsequent execution of the program, but in a well designed, non-object based program it should not be necessary to use any static variables other than the constants declared at the beginning.)
 
 

7.5 Linked Lists

In the implementation given below, a linked list consists of a series of nodes, each containing some data. Each node also contains a pointer pointing to the next node in the list. There is an additional separate pointer which points to the first node, and the pointer in the last node simply points to "NULL". The advantage of linked lists over (for example) arrays is that individual nodes can be added or deleted dynamically, at the beginning, at the end, or in the middle of the list.

In our example, we will describe how to implement a linked list in which the data at each node is a single word (i.e. string of characters). The first task is to define a node. To do this, we can associate a string with a pointer using a structure definition:

        struct node
        {
                char word[MAX_WORD_LENGTH];
                node *ptr_to_next_node;
        };

        struct node;
        typedef node *node_ptr;
        
        struct node
        {
                char word[MAX_WORD_LENGTH];
                node_ptr ptr_to_next_node;
        };

The "." and "->" Operators

        node my_node, my_next_node;

        cin >> my_node.word;
        my_node.ptr_to_next_node = &my_next_node;

        node_ptr my_node_ptr another_node_ptr;
        my_node_ptr = new node;
        another_node_ptr = new node;

        cin >> (*my_node_ptr).word;
        (*my_node_ptr).ptr_to_next_node = another_node_ptr;

        cin >> my_node_ptr->word;
        my_node_ptr->ptr_to_next_node = &my_next_node;

Creating a Linked List

        void assign_list(node_ptr &a_list)
        {
                node_ptr current_node, last_node;
        
                assign_new_node(a_list);
                cout << "Enter first word (or '.' to end list): ";
                cin >> a_list->word;
                if (!strcmp(".",a_list->word))
                {
                        delete a_list;
                        a_list = NULL;
                }
                current_node = a_list;                  /* LINE 13 */
        
                while (current_node != NULL)
                {
                        assign_new_node(last_node);
                        cout << "Enter next word (or '.' to end list): ";
                        cin >> last_node->word;
                        if (!strcmp(".",last_node->word))
                        {
                                delete last_node;
                                last_node = NULL;
                        }
                        current_node->ptr_to_next_node = last_node;
                        current_node = last_node;
                }
        }

We will assume that the function "assign_new_node(...)" used in the above definition is exactly analogous to the function "assign_new_int(...)" in the program above.

Here's how the function "assign_list(...)" works in words and diagrams. After the line

        assign_new_node(a_list);

Assuming the user now types in "my" at the keyboard, after line 13 the program state is:

After the first line inside the "while" loop, the program state is:

Assuming the user now types in "list" at the keyboard, after the "while" loop has finished executing for the first time the situation is:

After the first line in the second time around the "while" loop, we have:

Assuming the user now types in "." at the keyboard, after the "while" loop has finished executing for the second time the situation is:

Since the condition for entering the "while" loop no longer holds, the function exits, the temporary pointer variables "current_node" and "last_node" (which were declared inside the function body) are automatically deleted, and we are left with:

Printing a Linked List

8.1 The Basic Idea

Recursion is a familiar idea in mathematics and logic. For example, the natural numbers themselves are usually defined recursively. Very roughly speaking, the definition is:

• 0 is a natural number.

 
• if n is a natural number then s(n) (i.e. n+1) is a natural number, where s is the "successor function".

 

Another familiar mathematical example of a recursive function is the factorial function "!". Its definition is:

• 0! = 1

 
• for all n > 0, n! = nx(n-1)!

 

Again, notice that the definition of "!" includes both a base case (the definition of 0!) and a recursive part.
 

8.2 A Simple Example

        #include<iostream.h>
        
        void print_backwards();
        
        int main()
        {
                print_backwards();
                cout << "\n";
        
                return 0;
        }
        
        void print_backwards()
        {
                char character;
                
                cout << "Enter a character ('.' to end program): ";
                cin >> character;
                if (character != '.')
                {
                        print_backwards();
                        cout << character;
                }
        }

A typical input/output session is:

        Enter a character ('.' to end program): H
        Enter a character ('.' to end program): i
        Enter a character ('.' to end program): .
        iH

        void print_backwards()
        {
                char character;
                
                cout << "Enter a character ('.' to end program): ";
                cin >> character;
                if (character != '.')
                {
                        print_backwards();
                        cout << character;
                }
                else
                {
                        ;
                }
        }

8.3 The Mechanics of a Recursive Call

Figure 8.3.1a

The internal execution of this call begins with a character input, and then a second call to "print_backwards()" (at this point, nothing has been output to the screen). Again, space is set aside for this second call:

Figure 8.3.1b

The process repeats, but inside the third call to "print_backwards()" a full-stop character is input, thus allowing the third call to terminate with no further function calls:

Figure 8.3.1c

This allows the second call to "print_backwards()" to terminate by outputting an "i" character, which in turn allows the first call to terminate by outputting an "H" character:

Figure 8.3.1d

Technically speaking, C++ arranges the memory spaces needed for each function call in a stack. The memory area for each new call is placed on the top of the stack, and then taken off again when the execution of the call is completed. In the example above, the stack goes through the following sequence:

Figure 8.3.2

C++ uses this stacking principle for all nested function calls - not just for recursively defined functions. A stack is an example of a "last in/first out" structure (as opposed to, for example, a queue, which is a "first in/first out" structure).
 
 

8.4 Three More Examples

        int factorial(int number)
        {
                if (number < 0)
                {
                        cout << "\nError - negative argument to factorial\n";
                        exit(1);
                }
                else if (number == 0)
                        return 1;
                else
                        return (number * factorial(number - 1));
        }

As a second example, here's a function which raises its first argument (of type "float") to the power of its second (non-negative integer) argument:

        float raised_to_power(float number, int power)
        {
                if (power < 0)
                {
                        cout << "\nError - can't raise to a negative power\n";
                        exit(1);
                }
                else if (power == 0)
                        return (1.0);
                else
                        return (number * raised_to_power(number, power - 1));
        }

In both cases, care has been taken that a call to the function will not cause an "infinite loop" - i.e. that the arguments to the functions will either cause the program to exit with an error message, or are such that the series of recursive calls will eventually terminate with a base case.

The third example recursive function sums the first n elements of an integer array "a[]".

        int sum_of(int a[], int n)
        {
                if (n < 1 || n > MAXIMUM_NO_OF_ELEMENTS)
                {
                        cout << "\nError - can only sum 1 to "; 
                        cout << MAXIMUM_NO_OF_ELEMENTS << " elements\n";
                        exit(1);
                }
                else if (n == 1)
                        return a[0];
                else
                        return (a[n-1] + sum_of(a,n-1));
        }

8.5 Recursion and Iteration

        void print_backwards()
        {
                char chars[MAX_ARRAY_LENGTH];
                int no_of_chars_input = 0;
        
                do {
                        cout << "Enter a character ('.' to end program): ";
                        cin >> chars[no_of_chars_input];
                        no_of_chars_input++;
                }
                while (chars[no_of_chars_input - 1] != '.' 
                                && no_of_chars_input < MAX_ARRAY_LENGTH);

        for (int count = no_of_chars_input - 2 ; count >=0 ; count--)
                        cout << chars[count];
        }

        int factorial(int number)
        {
                int product = 1;
        
                if (number < 0)
                {
                        cout << "\nError - negative argument to factorial\n";
                        exit(1);
                }
                else if (number == 0)
                        return 1;
                else
                {
                        for ( ; number > 0 ; number--)
                        product *= number;
        
                        return product;
                }
        }

Because of extra stack manipulation, recursive versions of functions often run slower and use more memory than their iterative counterparts. But this is not always the case, and recursion can sometimes make code easier to understand.

8.6 Recursive Data Structures

        struct node
        {
                char word[MAX_WORD_LENGTH];
                node *ptr_to_next_node;
        };

8.7 Quick Sort - A Recursive Procedure for Sorting

Suppose we start with the following array of 11 integers:

The idea is to use a process which separates the list into two parts, using a distinguished value in the list called a pivot. At the end of the process, one part will contain only values less than or equal to the pivot, and the other will contain only values greater than or equal to the pivot. So, if we pick 8 as the pivot, at the end of the process we will end up with something like:

We can then reapply exactly the same process to the left-hand and right-hand parts separately. This re- application of the same procedure leads to a recursive definition.

The detail of the rearranging procedure is as follows. The index of the pivot value is chosen simply by evaluating

        (first + last) / 2

so that "left_arrow" and "right_arrow" initially represent the lowest and highest indices of the array components. Starting on the right, the "right_arrow" is moved left until a value less than or equal to the pivot is encountered. This produces:

In a similar manner, "left_arrow" is moved right until a value greater than or equal to the pivot is encountered. This is already the situation in our example. Now the contents of the two array components are swapped to produce:

We continue by moving "right_arrow" left to produce:

and then "left_arrow" right to produce:

These values are exchanged to produce:

This part of the process only stops when the condition "left_arrow > right_arrow" becomes TRUE. Since in Figure 8.7.8 this condition is still FALSE, we move "right_arrow" left again to produce:

and "left_arrow" right again to produce:

Because we are looking for a value greater than or equal to "pivot" when moving left, "left_arrow" stops moving and an exchange is made (this time involving the pivot) to produce:

It is acceptable to exchange the pivot because "pivot" is the value itself, not the index. As before, "right_arrow" is moved left and "left_arrow" is moved right to produce:

Figure 8.7.12

The procedure's terminating condition "left_arrow > right_arrow" is now TRUE, and the first sub-division of the list (i.e. array) is now complete.

Here is the procedure Quick Sort coded up as a C++ function:

        void quick_sort(int list[], int left, int right)
        {
                int pivot, left_arrow, right_arrow;
        
                left_arrow = left;
                right_arrow = right;
                pivot = list[(left + right)/2];
        
                do
                {
                        while (list[right_arrow] > pivot)
                                right_arrow--;
                        while (list[left_arrow] < pivot)
                                left_arrow++;
                        if (left_arrow <= right_arrow)
                        {
                                swap(list[left_arrow], list[right_arrow]);
                                left_arrow++;
                                right_arrow--;
                        }
                }
                while (right_arrow >= left_arrow);
        
                if (left < right_arrow)
                        quick_sort(list, left, right_arrow);
                if (left_arrow < right)
                        quick_sort(list, left_arrow, right);
        }

Acknowledgments:

1. Thinking in C++, by Bruce Eckel, downloadable from www.BruceEckel.com
2. The C++ Programmin Language, by Bjarne Stroustrup, Addison-Wesley, Reading, MA, 1997