CSCI 240 Lecture Notes - Part 7

Arrays - Part 1

Up to now, we have used simple data types (int, char, etc.) except for strings.

Now we look at the first data structure. A data structure is a compound data type; that is, it is a single entity made up of numerous parts.

It's kind of like a numbered list of things.  All the things must be of the same data type - all ints or all chars, etc.

We can solve problems which would otherwise be quite difficult.

Also, we can often make our solutions clearer.

As an example of a problem that is difficult without arrays, consider the following:

Problem: read n values and calculate an average. This is easy; we've done it.  But now...

Add to problem: for each number: print whether it is above or below average.

Given the normal way to read values and calculate an average, we can't do this, since after each cin in the loop, we lose the value of the previous one.

The program can't tell if a given number is above or below until all numbers are read; by that time the program has "forgotten" all of them except the last.

All we have is total and count.

Solution 1: if we know there are exactly n numbers, declare n variables.   If there are 3 numbers:

int n1, n2, n3;
double avg;

cin >> n1;
cin >> n2;
cin >> n3; 

avg = (n1 + n2 + n3) / 3.0;
 
if (n1 > avg)
  cout << "n1 is above";
else if (n1 < avg)
  cout << "n1 is below";
else
  cout << "n1 is equal to avg";

// same pattern of code repeated for n2 and n3…

Problem: what if there are 50 or 500 or 5000 numbers? This solution, awkward when n = 3, is terrible when n get big.

Solution 2: read the numbers twice

Read in all the numbers and calculate average.
Read in all the numbers again, this time checking each as it is read against previously calculated average.

If input is from keyboard, then the user has to enter each number twice. (Accurately, with no mistakes.)

If input is from an explicitly opened file (which we will be able to do later), this works, but is inefficient.
Not too much code. But it is inefficient to read the whole file twice.

(Note: this will not work with I/O redirection - we can't re-open the file and read from the beginning again.)

Solution 3: use arrays to store all the values as they are read and thus "remember" them.

First some information on how to create and manipulate arrays.

Definition: an array is a data structure consisting of an ordered set of data values of the same type.  Think of it as a numbered list, but all items on the list must be the same kind of thing (the same data type).

When defining an array in a program, we have to specify three things:

To declare an array that can hold up to 10 integers:

int ar[10];

This reserves space for 10 integers.  It does not place any values into the array.

Each position in the array is called an array element.

The elements in this array are numbered from 0 to 9.  (Not 1 to 10.)

Notice that when you declare an array, you specify how many items it can hold.  And that these elements are numbered starting at 0 and ending at one less than the number of elements.  This array holds 10 integers, which are numbered from 0 to 9.

You must use a literal number or a previously declared const int or #defined constant in an array declaration.  No variables.

In our code when we need to refer to a particular element in an array , we use subscript notation: [n]

n can be:

NOTE: that in this example, the ['A'] example refers to a non-existent array element - since 'A' is 65 and the array only has room for elements up to [9]. This would almost certainly result in a program bug.

(But if we had declared ar[100] it would be perfectly fine).

Note that you never use [n] by itself.  You use it to specify which array element you refer to, but you need also to say which array:

So to refer to the value of a particular array element, we write

arrayname[arrayelement];

So, for example, to assign values to (i.e. store values into) an array:

ar[0] = 1;
ar[1] = 3;
ar[2] = 5;
...
ar[9] = 19;
Or:
for (i = 0; i < 10; i++)
  ar[i] = (i*2) + 1;

Notice how the variable i, used as a subscript, runs from 0 to "less than" 10, i.e. from 0 to 9.

To use values in an array, we use the same notation:

cout << ar[2];
thirdOdd = ar[2];
nthOddSquared = ar[n-1] * ar[n-1];

Example: To add up the 1st ten elements in an array:

sum = 0;
for (i = 0; i < 10; i++)
  sum += ar[i];
 

Remember:

Now we can solve the problem posed earlier. Assume we are reading from a file using I/O redirection, and that a negative number is the end-of-file signal.

Solution 3:

#include ...
const int ARSIZE = 100;
 
int main()
  {
  int ar[ARSIZE];   //Note use of constant
  int lastElem = 0; //subscript of last entry
  double avg;
  int i;
  int sum = 0;
 
// ------read numbers into the array
// 1st read into ar[0]
  cin >> ar[lastElem]; 
  
  while (true)
    {
    //break out on minus
    if (ar[lastElem] < 0)
      break;     
    lastElem++;
    //get next value into next element    
    cin >> ar[lastElem]; 
    }
 

// ---- add up elements
// Note that lastElem is element number 
// of the neg value
  for (i = 0; i < lastElem; i++)
    sum += ar[i];

//if lastElem is 3 then there are 3 values
  avg = (double) sum / lastElem;  
 
// ---- now go through array and print < > =
  for (i = 0; i < lastElem; i++)
    if (ar[i] < avg)
      cout << "less";
    else if (ar[i] == avg)
      cout << "equal";
    else
      cout << "greater";
return 0;
}

More Notes on arrays:

You can initialize small arrays in the array declaration:

int ar[5] = {1, 3, 5, 7, 9}; // exactly enough values
int ar[5] = {2, 4, 6};       // the rest are 0
int ar[] = {1, 4, 9, 16};    // allocs 4 elements, 0..3
char vowels[] = {'a', 'e', 'i', 'o', 'u'}; // 5 elements
double sqrts[4] = {1.0, 1.414, 1.732, 2.0};

Also to initialize array elements, you can use executable program statements to assign computed values, or you can read data from keyboard or disk file.

You don't have to use all the declared array elements.  You normally declare the array to hold more values than you expect, and your program keeps track of how many array elements are actually used as it puts them into the array. We did that in Solution 3.

Sometimes it is more natural to start at 1, so you could just not use ar[0]:

int monthlenAr[13] = {0, 31, 28, 31, …};

Then for January, use monthlenAr[1], for February use [2], etc.

Other Misc. Operations

To increment the ith element:

ar[i]++;
ar[i] += 1;
ar[i] = ar[i] + 1;

To add n to the ith element:

ar[i] += n;
ar[i] = ar[i] + n;

To copy the contents of the ith element to the kth element:

ar[k] = ar[i];

To exchange the values in ar[i] and ar[k]:

First, understand that you must declare a "temporary" variable to hold one value, and that it should be the same data type as the array elements being swapped:

int temp;
temp  = ar[i]; //save a copy of value in i
ar[i] = ar[j]; //copy value from j to i
ar[j] = temp;  //copy saved value from i to j
 

Sample Exercises:

1. Given a character in variable ch, determine if it is a vowel, i.e. if ch matches one of the values in

char vowels[] = {'a', 'e', 'i' 'o', 'u'};

2. An array of 10 elements exists. Find and print the smallest element in it.

3. A Fibonnacci sequence consists of a series of integers in which each is equal to the sum of the of the previous two numbers. The first two are 1 and 1. So the series is: 1, 1, 2, 3, 5, 8, 13…

Write a program to store the first N Fibonnaci numbers in an array using executable statements. (NOT ar[] = {…}) Then fill a second array with the squares of these numbers.

4. Write a program to read numbers from the keyboard and then print them out in reverse order.