C++ Lab #2

C++ Lab 2 - Arrays and Strings

Download the example programs from this page or copy them from the course home page to your directory for this lab as follows (assuming you are currently in the directory):

    cp ~cpsc/public_html/Spring2011/CPSC270A/lab2/*.cc .

Constants in C++

There are two ways to define constants in C++. As in Java, the convention is to use all caps for the constant identifiers.

Defining constants using const is similar to using final in Java. An example:
```
      const int DOZEN = 12;
```
This is done inside a function.
Constants can also be defined using the preprocessor directive #define. For example,
```
    #define DOZEN 12
```
This is done outside of a function (before main or, later when we use header files, in the header file).

Arrays in C++

The following declares list to be an array of 10 integers.

      const int MAX_SIZE = 10;

      int list[MAX_SIZE];

This declaration allocates space for 10 ints. The space is allocated at compile-time and cannot be changed while the program is running. One consequence of this is that the following is not legal in standard C++:


     int size;
     cin >> size;
     int list[size];         // NOT LEGAL - size was not known at compile-time

Later we will see a way to allocate space at run-time - dynamic rather than static allocation.

Length of an Array: Unlike Java, there is no a.length to determine the length of an array. There is an operator sizeof that can be applied to any variable to determine the number of bytes allocated to that variable. So you could use sizeof(list) to determine the number of bytes allocated to the array list. The result would be the number of ints allocated times the size of an int (typically 4 bytes). For the list declared above the result would be 40.

C++ allows the programmer to be careless with array subscripts. For this (and other reasons) it is generally best to use the vector class (later!) than the built-in arrays. HOWEVER, there is a lot of code written with arrays so a computer science major should be familiar with them and their idiosyncracies (hazards!).

Exercise: The programs JavaArrays.java and CPlusArrays.cc use arrays.

Examine each program to see what it does.
Compile and run JavaArrays.java. Try at least two different scenarios for input - in one have the number of elements to print be less than or equal to the number generated; in the other have the number of elements to print larger than the number generated.
Compile and run CPlusArrays.cc. As above, try different combinations of input.
Run the CPlusArrays.cc with 20 (or more) for the number of elements to fill and the same the number of elements to print. You may (you should but it doesn't always happen!) get a segmentation fault because the code only allocated 10 spaces for the array. If you didn't get a segmentation fault keep using larger numbers until you get one. A segmentation fault occurs in C++ when your program tries to access memory that has not been allocated to it.
***CPlusArrays2.cc is the same as the program above except it has 4 additional variables of type int declared (two before the array declaration and two after). These variables are assigned values in the program (look at the code to see what these are). Compile and run the program with 10 for the number of integers to generate and 20 the number to print. What do you notice? What is going on?

IMPORTANT FACTS ABOUT ARRAYS AS PARAMETERS:

The formal parameter list for the function does NOT give the size of the array. For example, the following is the header for a function that finds and returns the sum of the elements in an integer array a. The first parameter is the number of elements actually in the array (not just the number of spaces allocated).
```
     int sum (int size, int a[])
```
The value of an array is a constant reference to the first element in the array. Just as in Java the parameters above are passed by value but since the value of the array parameter is a reference the function can change the actual values in the array. That is, a[3] = 17 would change the value of the fourth element in the actual parameter array.

*** Exercise:

First study the program ArrayFunctions.cc, then compile. Fix the problem by adding something that is missing (don't rearrange any code)!
Now run the program, then add a function that doubles every other element in the array starting at the first one. Put the function declaration before main and the function definition after main. Note that this function will have void return type. In main add a statement that prints the new array (or add a function to print an array then call it) after the current statement that prints the original sum, then call the sum function to print the new sum.

Strings in C++

A string in C++ is an array of characters (type char) that has the null character (escape sequence \0) at the end). The null character is automatically added to the characters in a string when the string is read in or is assigned as a literal. The program StringBasics.cc gives an example. This program uses two functions provided by C++ (actually C) - the sizeof function can be applied to any variable to find out how much space (number of bytes) the variable occupies. The function strlen is a function in the standard C library that gives the number of characters in the string. To use it you need to use the include preprocessor directive to include the header file for C string function (string.h).

The program also uses the function strcpy to copy one string to another. Note that the first argument is the destination, the second is the string to be copied. This function (or a loop where you copy character by character) can be used when you need to copy. However, you must use it with caution - it does not check to see if there is enough space in the destination string so you can get unexpected results! You cannot use assignment.

Exercise:

Compile and run the program. Note that for the string literal the number of bytes is one more than the number of characters - that accounts for the null character. For the string you typed in, the number of bytes is the number declared for the array.
1. Note what happened when string4 (the letters of the alphabet) was copied into string3. What exactly is going on here? Explain the behavior you observed.
2. Things can get worse! Try an input string that is too big. What happens? (The answer is going to depend on how big you try!)
3. Change MAX_LENGTH to something large enough to accomodate string4. Rerun the program to make sure it works on reasonable input!
See what happens when you try assigning strings. There is already a declaration for string3 in the program. Add an assignment statement to assign string3 to be the same as string1. Try compiling and see what the error message is.
Now change your assignment to assign string3 to be the same as string2. Try compiling. This is a more general error message that applies to any type of array in C++.
Now try assigning string3 to be a literal. What happens?
Use strcpy to assign string3 to be a literal (copy a literal value into string3). Does it work?

Reading in Strings

If you didn't already do it run the program above again entering a string with more than one word. Do it again putting several white space characters in front of the sentence. What happened?

You should have noticed that using the extraction operator >> on cin skips over whitespace and stops reading at whitespace. So it doesn't work to read a whole line that may contain spaces. To do that you need to use one of the functions get or getline that operate on cin.

The program ReadStrings.cc reads in two lines of text and prints them. Note the alternate syntax for using get and getline.

Exercise:

Study the code then compile and run the program.
Comment out the line that adds the null character. Run the program at least twice:
1. Enter a shorter string for the second input than the first. What happened?
2. Enter a longer string for the second but less than the maximum length. What happened?

The point - if you create your own string character by character you must explicitly add the null character to the end.

char

Variables and literals of type char can be manipulated just as in Java. Casting to an int gives the ASCII code and casting an int to char gives the character. The program Frequency.cc reads in a string character by character and determines the frequency of each letter in the alphabet. Study the code to be sure you understand it. Compile and run.

Homework - Due, Thursday, February 3

Complete this lab, including writing answers to the questions about program behavior.
Write a C++ program that implements the string-matching algorithm referred to in problem #3 on page 24. Use a function that is called from main for your algorithm. In particular your program should take in a line of text and another string (which may contain spaces). It should return the index of the first character in the string if the string is found in the text or -1 if the string is not in the text. Note: You only need to find the first instance of the string in the case that it appears more than once. You may not use any library functions except possibly strlen or strcpy. Do straight string processing where the string is an array of characters.
Write a C++ program that implements an anagram checking algorithm (problem #10 on page 39). You may assume the two strings have no whitespace. As for #1 no library functions.
Write a C++ program to implement the modified middle school algorithm (we did in class) for finding the GCD. You should implement the Sieve of Eratosthenes as a function. Instead of returning an array of primes that is allocated in the function (there are problems with this given what you know so far) that array should be a parameter. Use the following header for the sieve function:
```
    // Finds all primes less than or equal to n.
    // PRE:  n is a positive integer > 1
    // POST: prime is an array containing all primes less than or
    //       equal to n; numPrimes is the number of primes in the array
    void sieve (int n, int[] prime, int& numPrimes)
```