C++ Exercise 6

© 2011  cad18 ;  rcm27 ;  cpsm

ARRAYS

Please note that the material on this website is not intended to be exhaustive.  This is intended as a summary and supplementary material to required textbook.

INTRODUCTION

In this module we will be almost exclusively concerned with the built-in complex type array. Arrays make it possible to deal with sets of data (such as a set of student records, each of which has the same structure or type).

BASIC DEFINITIONS

An array is a finite set of elements stored in memory in which the elements are all of the same type. Hence, arrays are distinct from structures in that structures can contain elements of any type. The number of elements in an array is called its size. Arrays can consist of elements of any single type, but we will begin with character arrays.

Recall that characters typically require one byte of storage per character, so an array of 8 characters will require 8 bytes; we declare an array by naming the type, naming the array, and indicating its size inside the array symbol: [ ].

char myArray [8];

We can also initialize an array in its declaration.

char myArray [] = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};

Notice that in this case we did not have to indicate the size in between the brackets, as the size is indicated by the set of initial values (compilers can count).

Now that we have an array of 8 characters, we access an individual element by using the index of the individual element. The index of the first element in the array above ('A') is 0; the index of the last element ('H') is 7. In general (and this is true of all languages derived from C) an array with n elements has indices ranging from 0 to n-1. If you try to reference the nth (or higher) element you will be referencing a non-array element and this is an error: out of range; you will commit the same error if you use a negative index.

Arrays are most often processed by for loops, but usually any loop will do as well. Here is a code snippet that initializes an array, sums up the elements of that array, and computes the average. Note especially that the limit on the for loop uses <, NOT <=.

const int ARRAYSIZE = 10; ... int numArray [ARRAYSIZE] = {2, 6, 3, 8, 19, -1, 0, 22, -6, 10}; int i, sum = 0; double average; ... for (i = 0; i < ARRAYSIZE; i++) { sum += numArray[i]; } average = (double)sum / (double)ARRAYSIZE;

LAYOUT OF ARRAYS IN MEMORY

We will think of arrays as being laid out in memory sequentially. Our character array above has 8 elements, so 8 bytes are allocated to hold it, and each 1-byte element of the array has its own unique address in memory; memory is byte-addressable. Our int array above has 10 elements, and each element is 4 bytes (for a total of 40 bytes); the lowest address of each 4-byte integer accesses each of the 4-byte elements.

You can think of arrays in memory as laid out horizontally (with addresses increasing from left to right), OR you can think of arrays in memory as laid out vertically (with addresses increasing from bottom to top or top to bottom). However, because we usually reserve the vertical way of thinking for the stack, here we will think of arrays in memory as laid out horizontally.

PARITALLY FILLED ARRAYS AND ARRAY OVERFLOW

If you use an 8-byte character array such as that declared above, there is no requirement that you have to fill every byte. An 8-byte character array may only hold 4 bytes, or any number less than or equal to 8 bytes. However, you cannot use an 8-byte array to hold more than 8 characters, say 10, and if you try to do so you may get a runtime error; sometimes the compiler will pick this up. These runtime errors are devilishly hard to find, and finding them often requiresthat you use a debugger.

Note especially that if the compiler does not pick up any out-of-range references, then the runtime environment will not flag any either, unless the program attempts to reference memory outside of the program's allocated memory space. The implication here is that out-of-range memory reads/writes can wreak havoc for an executing program. Programmers need to be wary of this possibility.

PASSING ARRAYS TO FUNCTIONS

Arrays and elements of arrays can be passed to functions. If you want to pass the 4th element of a 10-element integer array, you can do so as follows; using numArray declared above:

int myFunction (int); // prototype ... int index = 3; int ret; ... ret = myFunction (numArray[index]); ...

You can pass in an array element and make it possible for the called function change the element by passing it by reference:

int myFunction (int&); // prototype ... int index = 3; int ret; ... ret = myFunction (numArray[index]); ...

The entire array can also be passed into a function, but in this case you must also pass in the size of the array:

int findLeast (int [], int); // prototype ... int ret; ret = findLeast (numArray, ARRAYSIZE); ...

However, if you pass the entire array into a function, the compiler will not put the entire array on the stack (who knows how many elements that could be). Instead, the compiler will place a pointer to the array on the stack, that is, the address of the first element of the array. In effect, this amounts to passing the entire array by reference and allows the called function to modify the array. If you do not want to give the called function the ability to modify the array, you must declare the array passed as const.

int findLeast (const int [], int); // prototype

ARRAYS OF OTHER TYPES

So far, we have used examples of character and integer arrays, but any type, whether built-in or user-defined, can be used in arrays. Always remember that arrays can consist only of objects of the same type. So, arrays can consist of:

· Characters

· Integers: short, int, long

· Decimals: float, double, long double

· Strings

· Structures and unions: struct and union

· Classes

· Even arrays themselves (arrays of arrays are multi-dimensional arrays; see below)

STRINGS AND CHARACTER ARRAYS

Recall that C++ makes a distinction between character arrays and strings: string is actually a class. When we open a file we can pass as its name a literalstring, such as: "myTextFile.txt". Or, we can pass a string variable to the open call. But, in order to do so, we must convert the string to a character array.

string myFile = "myTextFile.txt" ... ifstream inFile (myFile.c_str(), ios::in); ...

The c_str() string function converts the string myFile into a traditional C-language character array. In C, character arrays that represent strings are always terminated by a null byte: '\0' (an ASCII character equal to 0).

Most C++ programmers prefer to use the string class instead of the traditional C-language character array, as the string operators, such as ==, !=, and +, are extremely convenient.

TWO-DIMENSIONAL ARRAYS

We mentioned earlier that you can have arrays of arrays. Most often these are 2-dimensional arrays, which we can think of laid out in rows and columns, just like a spreadsheet.

We access these arrays by supplying a row index and a column index. The following is an example of initializing a 2-dimensional array that has 300 rows and 10 columns: 3000 elements altogether. Note that the row number is always first, as it is the primary index. The column number is secondary. Row indices can range from 0 to 299; column indices can range from 0 to 9.

int array2D [300][10]; ... for (int i = 0; i < 300; i++) for (int j = 0 j < 10; j++) array2D[i][j] = 0; ...

When passing two-dimensional arrays to functions you should also pass both dimensions:

void myFunction (int [ ], int, int); // prototype ... int myArray [100] [10]; ... myFunction (myArray, 100, 10);

Two-dimensional arrays will be covered further in the module on matrices and linear systems.

MULTIDIMENSIONAL ARRAYS

We can, of course also have 3-dimensional, 4- dimensional, ... arrays, but these are harder to picture, A 3-dimensional array will have 3 indices. You can think of a 3-dimensional array as a 2-dimensional array in which each cell in that array has many elements. A visual analogy would be a solid in 3-dimensional space (mathematical 3-space does NOT have a finite number of points, whereas arrays in C++ are necessarily finite).

int array3D [2][3][4]; // prototype ... array3D[0][2][1] = 0; ...

Of course, 4-dimensional arrays are even harder to imagine, but an analogy can be made to the 4-dimensional space-time.

REVIEW EXERCISES

1. *The following is a diagram of the memory used by an array of 8 8-bit (1-byte) characters. Do a similar diagram for an array of 8 32-bit integers and 8 64-bit doubles.

2. *What is wrong with the following code snippet?

int myArray [8]; for (int i = 0; i <= 8; i++) myArray [i] = 0;

3. *What is the dimension of the following array, and what is its size? Assuming a double is an 8-byte quantity, how many bytes of memory will the array occupy?

double dArray [2][5][3][4];

4. **C++ has no built-in facility for displaying numbers in binary. The number 45 base 10 is 00101101 base 2. How can you display a int (4 bytes max) in binary using cout? Group the output into 8 blocks of 4 binary digits; that is, 45 should appear as:

0000 0000 0000 0000 0000 0000 0010 1101

5. **Write a program that initializes an array with the first 30 numbers in the Fibonacci series and then prints out the contents of the array. The Fibonacci series is generated by the following rules: both the first and second numbers are 1, every number after that is the sum of the previous two numbers in the series.

6. ***Bubble Sort. A bubble sort is a sorting of a list of numbers. The sort can be in either ascending or descending order. The bubble sort algorithm makes multiple passes through the list and on each pass examines each adjacent pair of members on the list and interchanges then if they are not in the right order. The bubble sort terminates when a pass is made that requires no interchanges. Beginning with the list: 9, 8, 7, 6, 5, 4, 3, 2, 1, sort this list in ascending order using a bubble sort that you implement. Test your program using random orders of the integers 1 to 9.