# CS1440-Lab 10 (Arrays)

In this lab we will learn about
• declaring, initializing, and using arrays,
• sending an array element to a function,
• sending an entire array to a function, and
• using partially filled arrays.

First create a subdirectory called lab10 under your 1440 directory, then change to that subdirectory and complete your lab there.

## Activity 10.1- Introduction to Arrays

So far all of our variables have been able to hold only one value at any one point in time. Such a variable is called a scalar variable. Now it is time for our first non-scalar variable, an array.

An array is one variable capable of storing multiple values. When we declare an array we tell the compiler how many values we want the array to hold. We also tell the compiler what type of values the array can store. All of the values in an array must be of the same type.

Here is a declaration of an array called numlist that will be used to store 8 integers:

`int numlist[8];       // an integer array that can store 8 values`
Each of the integers in the array is stored in the same number of bytes as a scalar integer, which on our cs machine is 4 bytes. Thus the entire array will occupy 32 bytes of memory. The compiler always stores an array in contiguous memory locations (all of the elements of the array are stored in one chunk of memory with no gaps.)

## Accessing Individual Array Elements

The individual values stored in an array are called the elements of the array. You will also hear them called indexed variables or subscripted variables. Each of the elements of an array is assigned an index. An index is a natural number in the range {0,1,2,...,K}, where K is one less than the number of elements in the array.

In C++, all arrays are indexed starting from 0. To access one of the elements of an array, you put the index of that element in square brackets after the name of the array. The 0th element in the array called numlist is numlist[0], the next one is numlist[1], and so forth. Since we begin numbering with 0, the last element in numlist is numlist[7].

To put a value of 17 into the 0th element of numlist, we would say

`numlist[0] = 17;`
If we wanted to have the user input a value to be stored in numlist[1] we would say
`cin >> numlist[1];`
An array element like numlist[4] can be used in any way that a scalar variable can be used. All of the following are legal ways to use an array element.
```if (numlist[2] > numlist[1]) ...

cout << numlist[5];

sum = sum + numlist[7];```
The index inside the square brackets does not have to be an integer constant like 3 or 4. It can be any integral expression that evaluates to an integer within the range of the array's indexes.

Suppose we wish to fill our array, numlist, with integers typed at the keyboard. A for loop is an easy way to do that. Here is a for loop that will allow the user to enter values that will be stored in numlist. Notice that we have used the variable i as an index to numlist.

```for (i=0; i<8; ++i)
{
cout << "Enter the next value: ";
cin >> numlist[i];
}```
It might be easier for our user to keep up with the different values to be entered if we print something more helpful than "Enter the next value: " Since users typically number items in a list starting from 1, we will say "Enter value #1: " when asking for numlist[0], "Enter value #2: " when asking for numlist[1], and so forth. Here is the improved loop:
```for (i=0; i<8; ++i)
{
cout << "Enter value #" << i+1 << ": ";
cin >> numlist[i];
}```
By asking for value 1, then value 2, etc., we are allowing our user to count in a more natural way than C++ forces us to count.

Exercise 10.1
Copy the following program to a file called p101.C, then run it to see that it allows you to enter 8 values.

```#include <iostream>

int main(void)
{
int numlist[8], i;

for (i=0; i<8; ++i)
{
cout << "Enter value #" << i+1 << ": ";
cin >> numlist[i];
}
return 0;
}```
Now edit the program so that after all the values are entered, they are printed out. Use a for loop and output one value per line. Make your program's output looks like this with the xx's replaced by the values you entered:
```Value #1 is xx
Value #2 is xx
...
Value #8 is xx```

## Activity 10.2-Array Index Out of Range

A common error when working with an array is attempting to access an element of the array but using an index that is out of range. In the above program, numlist has 8 values. The final value is called numlist[7]. If we try to access numlist[8], most C++ compilers (ours included) will not give us an error message. C++ does not verify that your index is within the proper range. If you print the value of numlist[8], the compiler will grab the 4 bytes following numlist[7], interpret whatever is stored there as an integer and print the value of that integer. If you store a value at numlist[8], the compiler will place that value into the first 4 bytes following numlist[7], even if those bytes happen to be storing a different variable! That is what happens in the following program.

Exercise 10.2
This program contains an error that causes it to use an index outside of the range 0 to 7. Copy the program to p102.C, compile and run it. Be sure you understand why the variable x, which is set to 1 initially, gets changed to 8.

```#include <iostream>

int main(void)
{
int numlist[8], x, y, i;

/*  This program contains an error.
Delete this comment when you fix the error.   */
x = 1;
y = 2;
cout << "x is " << x << " and y is " << y << endl;
for (i=0; i<=8; ++i)
numlist[i] = i;
for (i=0; i<8; ++i)
cout << "numlist[" << i << "] is " << numlist[i] << endl;
cout << "x is " << x << " and y is " << y << endl;

return 0;
}```
Now edit the program and correct that error. Hint: the first for loop stores 9 numbers!

## Activity 10.3-Initializing Arrays

A scalar variable can be initialized when it is declared, like this:
`int num = 4;`
An array can also be initialized when it is declared. Here we put the value 0 into numlist[0], the value 1 into numlist[1], etc.:

int numlist[8] = {0,1,2,3,4,5,6,7};

If you list fewer values within the braces than there are elements of the array, our C++ compiler will initialize all the rest of the elements to 0. However, not all C++ compilers will do this. If you initialize an array when it is declared, you can omit the size of the array. C++ will use the number of initializers in your list as the size of the array. The code

`char vowels[] = {'a', 'e', 'i', 'o', 'u'};`
creates a character array of size 5 which contains the lowercase vowels.

Exercise 10.3
For this exercise, you can modify the program that was given in the previous exercise and call the new program p103.C. Initialize two arrays in the main as:
char vowels[] = {'a', 'e', 'i', 'o', 'u'};
char letters[]={'h', 'l', 't', 'g','r'};

Now use the the two arrays vowels and letters to make three words by putting together letters and vowels.  Note that any word is acceptable as long as long is it has at least 2 characters (hello, tiger, hi, tall, hat, hate, ...) in it. Display the three words on the screen one on each line.

## Activity 10.4-Indexed Variables as Function Arguments

You can use an array element as a function argument just as if it was a scalar variable. The following is perfectly valid:
```double x[7] = {0.5,1.0,1.5,2.0,2.5,3.0,3.5};
double y[7];
int i;

for (i=0; i<7; ++i)
y[i] = sin(x[i]);
```
Here we send the value of x[i] to the sine function (in the math library.) The function's parameter, in this case, is a call-by-value parameter. We can also send an array element to a function which has a call-by-reference parameter.

Exercise 10.4
Study the following program, then copy it to a file called p104.C.

```#include <iostream>

// Obtains a grade from the user and stores it in parameter, grade.

int main(void)
{
int i;

for (i=0; i<5; ++i)

return 0;
}

{
cout << "Input a grade between 0 and 100: ";
}
```
Compile and run p104.C. As the program is now, you cannot tell whether the values you entered are stored in the grades array or not. Add a second for loop to the main that prints out the values stored in the array. Then run the program to verify that the function get_grade is correctly storing each value of the array.

Notice that the call-by-reference parameter of the function, get_grade, is not indexed like an array element. Instead, it is a scalar variable. You see, it doesn't matter whether the variable passed to the function is an array element or a scalar variable. The function receives an integer variable from its caller, then gets an integer from the user and places that integer into the variable that was passed to it. The function has no way of knowing whether that variable is part of an array or not, nor does it matter.

## Activity 10.5-Using a Defined Constant for the Size of an Array

In many cases we take a good guess at the size of an array, but have to modify the program later when we find out that the array needs to be larger or smaller than our guess. It is much easier to make such a change if the original programmer used a defined constant for the size of the array. Here is an example of an easy-to-modify program:
```#include <iostream>
#include <iomanip>
const int SIZE = 8; //Set the maximum size for the array

int main(void)
{
double average;
int numlist[SIZE]; //Create the array of size SIZE!
int i, sum=0;

for (i=0; i<SIZE; ++i) //Use the SIZE to go through all the elements of the array
{
cout << "Enter value #" << i+1 << ": ";
cin  >> numlist[i];
}
cout << endl;
for (i=0; i<SIZE; ++i)
cout << "Value #" << i+1 << " is " << numlist[i] << endl;
for (i=0; i<SIZE; ++i)
sum = sum + numlist[i];
average = (double)sum/SIZE;
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout << "\nThe average is " << setprecision(2) << average << endl;

return 0;
}
```
Exercise 10.5
Copy the program to p105.C and compile and run it. Now suppose that we need to find the average of 12 grades instead of 8. All we have to do is change the 8 in the initialization of SIZE to 12. If we had not used a defined constant, we would have to find every occurrence of 8 in the program and change it to 12. It is easy to miss an occurrence of 8 when doing such a change and thus create a logical error in the program.

Make the change of SIZE from 8 to 12 and rerun the program. See how easy it was to change it.  By the way, remember that to compute the average, you really didn't need an array. You could read the grades one-by-one and add them up and at the end, compute the average by dividing the sum by the number of grades.

## Activity 10.6-Passing a Whole Array to a Function

We have seen call-by-value parameters and call-by-reference parameters. A parameter for an entire array is a third kind of parameter, aptly named an array parameter. An array parameter is like a call-by-reference parameter in that any change made to the array within the function actually changes the array that was passed to the function (in main or some other calling function.) However, it is not necessary to use the ampersand on an array parameter. Instead, we put square brackets after the name of the array parameter. Here is a function that could get values for numlist:
```void get_values(int list[], int size)
{
int i;

for (i=0; i<size; ++i)
{
cout <<"Enter value: ";
cin  >> list[i];
}
}
```
You might think that an error was made in the above function definition because there is no number within the square brackets after the array name. That is not an error. We use empty square brackets to indicate that the parameter is an array parameter. If we put a number in the brackets, the compiler will not give us an error but it will ignore the number.

Notice that we have a second parameter, size, in the function above. This parameter is necessary because when C++ passes an entire array to a function, it does not inform the function of the array's size. It tells the function where the beginning of the array is in memory and that's all. The function call must include both the name of the array and the size of the array, like this:

`get_values(numlist, 8);`
or
`get_values(numlist, SIZE); // if we used a defined constant`
Notice in both of these calls, we do not put square brackets after the name of the array. When sending an entire array to a function, do not use square brackets.

It might seem like an inconvenience to have to include a separate parameter for the size of the array. But doing so makes a function usable for arrays of different sizes. Study the following program:

```#include <iostream>

const int SIZE_OF_SECTION = 5;

void get_values(int list[], int size);

int main (void)
{
int section[SIZE_OF_SECTION];
int i;

cout << "First enter a student ID number for each of "
<< SIZE_OF_SECTION << " students:\n";
get_values(section, SIZE_OF_SECTION);
cout << "\n\nNow enter two grades for each student:\n";
cout.setf(ios::fixed);
cout.setf(ios::showpoint);
cout.precision(2);
cout << endl;

for (i=0; i<SIZE_OF_SECTION; ++i)
{
cout << "The average score for student #" << section[i]
<< endl;
}
}

void get_values(int list[], int size)
{
int i;
for (i=0; i<size; ++i)
{
cout << "Enter value: ";
cin  >> list[i];
}
}
```
Exercise 10.6
Copy the program to a file called p106.C and run it. Enter ID numbers 3125, 4268, 5176, 5829, and 6013. Then enter grades 80, 88, 92, 95, 75, 60, 82, 97, 65, and 70. Does the output appear to be correct? It should be. Study the cout statement that is calculating the average. Notice the indexes 2*i and 2*i+1. Can you explain how these indexes allow the program to add the two grades for each student? Try to do so before reading the next paragraph.

The variable i in the for loop in main varies from 0 to 4. When i is 0, 2*i is 0 and 2*i+1 is 1. The first student's two grades are stored in grades[0] and grades[1]. When i is 1, 2*i is 2 and 2*i+1 is 3. The second student's two grades are stored in grades[2] and grades[3]. Our index formulas work correctly.

## Using const with an Array Parameter

If you place the reserved word const in front of an array parameter, the function cannot change the value of any element of the array. If it tries to do so, the compiler will report a syntax error.

This is a good idea if you are writing a function that will be used by other programmers and you want to make it clear to them that your function will not make any changes to the array it is passed. A prototype such as

```double average(const int list[], int size);
// This function returns the average of all the elements in the array.```
tells you that this function must be sent an integer array and an integer size when it is called, and that the function returns a double. In addition, it assures you that the values in any array passed to this function will not be changed by the function.

## Activity 10.7-Partially Filled Arrays

Sometimes we don't know in advance how many values we will have to store in an array. In such a case, we declare the array to be of a size large enough to contain the maximum number of values we expect to need. Then, as we fill the array, we count the number of values that we get and use that count as the size of the array.

Soon you will see an example of a partially filled array. First, let me describe a program that requires using this example.

Suppose we want to write a program to add very large integers. Our C++ compiler's integer data type is stored in 4 bytes. This means that the largest integer we can store in an integer variable is approximately 2 billion. If we need larger integers, we will have to develop a new way of storing them.

One way to store a large integer is to store the digits of the integer in a character array. Let's say that we will never need integers with more than 20 digits. Then we can declare an array of size 20 and be sure that any of our large integers will fit into it. As we fill the array with digit characters, we will count the digits so that we know how much of the array we are currently using. Here is the example:

```#include <iostream>
#include <cctype>

const int MAXSIZE = 20;

int main(void)
{
char digit_array[MAXSIZE], digit;
int size, i;

size = 0;
cout << "Enter an integer with no more than "
<< MAXSIZE << " digits: ";
do {
cin.get(digit);
if (isdigit(digit))
{
digit_array[size] = digit;
++size;
}
} while (size < MAXSIZE && isdigit(digit));
cout << "The integer you entered is: ";
for (i=0; i<size; ++i)
cout << digit_array[i];
cout << endl;
return 0;
}
```
Exercise 10.7
Copy this program to p107.C and run it. Does it behave as specified? What happens if you accidentally put in a letter somewhere in the integer? What happens if you put in more than 20 digits?

Now let's suppose that we need to reverse the digits of the integer so that the last digit becomes the first digit, the next-to-last becomes the second, and so forth.

Let's write a function that reverses a character array. We will pass the function a character array and the size of the array. Let's call the array parameter chlist (for character list.) The function will contain another character array as a local variable into which it will copy chlist. The function will copy chlist right to left but will put the copy into its other array in left to right order. Then it will copy the contents of this other array back into chlist from left to right.

Try to write such a function below the main in p107.C. Call the function reverse and give it the following prototype:

```void reverse(char chlist[], int size);
// This function reverses the contents of chlist.```
Once you have written the function, put a call to the function in main below the for loop. After the call, add another copy of the for loop so that the array will be printed again. If your function works correctly, the second printing should be backward. If you have trouble with this function, take a peek at the solution.

## Searching and Sorting Arrays

We will not deal with the topics of searching and sorting in this lab, but they are very important topics in computer science. Our text does a good job of explaining them. Be sure you read section 9.3.

What to submit today.  Assuming all files are saved in the directory lab10.  Make sure that all files p101.C to p107.C are in that directory.  You do not need to submit any files but all files must be in the lab10 directory.  we will grade your lab from your directory.

## Postlab

Write a program which reads a list of integers from the input file lab10.dat and outputs the list with duplicates removed to the file lab10.out . That is, any value which occurs at least once in the input file should occur once and only once in the output file. You may assume that there are no more than 100 numbers in the input file. This means that you should allocate space for 100 numbers as in
`int x[100];`
but keep track of the actual numbers read. Turn in a program listing and leave the source code of the program in a file named postlab.C in the Lab10 directory.

For example, suppose that the input file contains these values:

```2
8
3
4
6
8
2
1
4
1
1
1
6
5
5
```
(You can copy this file to your directory by typing
`pico lab10.dat`
and then cutting and pasting this list.)

If you examine lab10.out (say, with pico) the contents would be:

```2
8
3
4
6
1
5
```
Turn in hardcopy of your postlab program at the start of the next lab along with the cover sheet and prelab.

HINT

```void reverse(char chlist[], int size)
{
char copy[size];
int i, j;

for(i=0, j=size-1; i<=size-1; ++i, --j)
copy[i] = chlist[j];
for(i=0; i<=size-1; ++i)
chlist[i] = copy[i];
}
```
The call to the function should say:
`reverse(digit_array, size);`

Here's a different version of the function:

```void reverse(char chlist[], int size)
{
int  left, right;
char temp;

left  = 0;
right = size-1;

while( left < right )        {
temp          = chlist[left];
chlist[left]  = chlist[right];
chlist[right] = temp;
left++;
right--;
}
}
```