Lecture Outline
- Array processing
- Initializing the elements of an array
- Searching an array
- Writing out the contents of an array
- Programming examples using arrays
- Two-dimensional arrays
Array Processing
An array is a list of similar items stored under one name.
The class roll sheet is a list of the names of people attending class, or it is an array of names.
Array Processing
Arrays provide the programmer with a way of organising a collection of homogeneous data items (i.e. items that have the same type and the same length) into a single data structure. Elements in an array are referenced by a subscript that indicates the position of an element within the array or list.
If you have a list of names, and you want to see the fourth name on the list, you would ask for: names(4)
Operations on arrays
Here are some things you can do with an array:
1) initialize the elements of the array.
2) process the elements of the array.
3) store results of processing in an array.
4) print the values in an array.
5) search an array for some value.Simple algorithms that manipulate arrays
The following algorithms can be written using either a DO loop or a DOWHILE loop to manipulate the array.
Example 7.1 Find the sum of the elements of an array
In this example, we wish to find the sum of all the values stored in the array. Notice that the variable sum is set to zero before we execute the loop. The assignment:
statement sum = sum + array(index)
takes the value in sum, adds to it the value in array(index) and places the results in sum. Index is varied from 1 to the number_of_elements in the array. Here is the algorithm using the DO loop.
Here is the same algorithm using a DOWHILE loop.
Example 7.2 Find the mean (average) of the elements of an array
This second example is to find the average value in the elements of the array. First we find the sum of the values, then we divide it by the number of elements in the array.
Example 7.3 Find the largest of the elements of an array
This time, we are looking for the largest value in the array. We just set largest to the value of the first element of the array. Then we compare this value to each of the other elements in the array. If one is larger, we replace the value in largest with that value and continue to check the rest of the array.
Example 7.4 Find the smallest of the elements of an array
Now, we want to find the smallest value in the array. We set smallest to the value of the first element of the array and start comparing it to other elements in the array.
Initializing the elements of an array
When you declare an array, its elements have unknown values in them . Before you can use the values of the elements of an array, you have to places values in the elements, or initialize the array.
Loading constant values into an array
Here we have an array of Strings the represent the names of the months of the year. We can initialize these elements one at a time by using 12 assignment statements.
Loading initial values into an array from an input file
We can also use a loop to read in the values for the array from a file.
Arrays of variable size
You may not know how many elements are going to be in an array. In that case you must declare the size of the array as being larger than the largest array you expect. Then you read in and count the number of elements in the array until you see a sentinel value which marks the end of the array.
Paired arrays
You can have parallel arrays, which are two or more arrays with the same number of elements in them. In that case, you can process the array together, using only one loop.
Searching an array
A common array operation is to search the values of an array for a particular value. You may be doing this in order to find and change a value, or to find and process information in a corresponding element of a paired or parallel array.
A linear search of an array
A linear search starts searching for the value with the first element of the array and continues through the array, one element at a time until the wanted value is found or you reach the end of the array. We assume that the program inputs a value (for input_value) and we start the program with element_found is false until the element is really found!
A binary search of an array
A binary search requires that the element values in the array be in order, such as ascending order, from smallest to largest. Now, you can search the array by:
Find the center element value. If this is the wanted value, you are done. Otherwise, if the wanted value is greater than this value, it lays in the top half of the array. Throughout the bottom of the array and find the new center of what is left. Otherwise, if the wanted value is less than this value, it lays in the bottom half of the array. Throughout the top of the array and find the new center of what is left. Keep doing this until you find the value you want or you run out of array.
Writing out the contents of an array
You need to use a loop to print out the values in an array, one element at a time. Here is how to do it with a DO loop.
Here is how to do it with a DOWHILE loop.
Programming examples using arrays
Example 7.6 Process_exam_scores
Design a program to get 18 exams scores, find the average, and print out everything.
A Defining diagram
Here is the IPO chart.
B Control structures required
We need two loops that run 18 times each, an array to hold the scores, an index for the array, and a total accumulator.
C Solution algorithm
Here is a solution algorithm.
Example 7.7 Process integer array
Design a program to get 100 values, find the average, find the number of values greater than the average, display average and count of values larger than average.
A Defining diagram
Here is the IPO chart.
B Control Structures required
We need two loops that run 100 times each, an array to hold the values, a total accumulator, an average holder, a counter for values greater than the average.
C Solution algorithm
Here is the solution algorithm.
Example 7.8 Validate sales number
Design a program to read a file of sales transactions, verify sales numbers and flag any errors.
A Defining diagram
Here is the IPO chart.
B Control structures required
Need two nested loops to read sales file and search for sales number, an array of sales numbers, an index, and an element-found flag.
C Solution algorithm
Here is the algorithm.
Example 7.9 Calculate_freight_charge
A Defining diagram
Read in weight of an item, search for weight and get freight charge.
Here is the weight and fright charge table.
B Control structures required
Need two parallel arrays to hold weights and freight charges, a loop to search the weight and freight arrays, an index.
C Solution algorithm
Here is the algorithm.
Two-dimensional arrays
Multi-dimensional arrays require a subscript for each dimension of the array. A two-dimensional array uses two subscripts, the row subscript and the column subscript. Here is the freight charge problem revisited. The weights are given in the following table.
The freight charges are now based on two factors, weight and zone (distance). This table has rows and columns and is shown below.
So, references are made using the following format.
freight_charges(row_index, column_index)
For example:freight_charges(5, 3)
Refers to the 5th row and 3rd column, which is $20.00
Loading a two-dimensional array
A two-dimensional array is loaded one row at a time. This can be done with nested Do loops.
Searching a two-dimensional array
Searching a two-dimensional array makes use of a DO loop to walk through the rows, and has a fixed column on the field being searched. This is very much like search a one-dimensional array.
This example searches a table, column by column, one row at a time for an employee number.
Pulling out the content of a two-dimensional array
To print the elements of a two-dimensional array, write out the elements, within each row, one column at a time. You might want to use a new line for each row, even though this example doesn't.
Required reading: Simple Program Design - Lesley Anne Robertson - Chapter 7.