Problems involving arrays are similar, in many ways, to problems involving lists. Lists in Modula 3 have the advantage of being dynamic data structures: they may grow and shrink as the demands of the data being processed require. Arrays, on the other hand, are of fixed size once they are declared or allocated with NEW. This causes certain problems to procedures that process arrays passed as parameters, namely, determining how much of the array is occupied. The end of a list is marked by a NIL pointer at its end, and so its length is easily discovered. An array must either be assumed to be full, in which case FIRST and LAST may be used, or an additional parameter must be passed with the array to say how many items there are in it.
Consider the following specification:
Write a procedure to print out the contents of an array of integers, one per line.
If we can be sure that the array is completely full, then the procedure will take a single input - the array - and return no outputs. Its only action is to print the integers:
PROCEDURE PrintNums(nums : ARRAY OF INTEGER) = BEGIN FOR i := FIRST(nums) TO LAST(nums) DO Put.Int(nums[i]); Put.Char('\n'); END; END PrintNums;
If we cannot be sure that the array is full, then the procedure must take a second input argument:
PROCEDURE PrintNums(nums : ARRAY OF INTEGER; howMany : INTEGER) = BEGIN FOR i := FIRST(nums) TO FIRST(nums)+howMany-1 DO Put.Int(nums[i]); Put.Char('\n'); END; END PrintNums;
Just as we saw with some problems involving lists, we must always be sure that the issue of an empty array is dealt with satisfactorily.
Whereas programs involving linked lists use recursive procedures, those involving arrays often use iteration (loops) instead. This does not have to be the case: recursive procedures can be used with arrays, too, but we will tend to show iterative solutions in this section. Just as we saw with lists, when we choose the sort of loop to use on an array, it will be important to ask, `Do I wish to do something to every element in the array?' If the answer to this is, `Yes', then a FOR-loop might be the right loop to use. If the answer is, `No', then we should not use a FOR-loop. It is a very common mistake to assume that array processing should always utilise a FOR-loop. It is much more usual to need a WHILE-loop with an array, particularly when we know in advance that we might not need to look at every element.
Consider the following:
Write a procedure to find out whether a particular integer is present in an array.
Identifying inputs we note that an array and an integer to find are required. As above, we must determine whether the whole array is occupied or only part.
PROCEDURE IsInList(nums : ARRAY OF INTEGER; value : INTEGER) : BOOLEAN
Should we use a FOR-loop or a WHILE-loop? Do we need to consider every element? It could be argued that we do need to look at every item. However, if we find the number we want before the end, there is no point in looking further, we can return straight away. It takes a little more work, in terms of declaring an index variable and updating it, but a WHILE-loop will produce a better solution than a FOR-loop.
PROCEDURE IsInList(nums : ARRAY OF INTEGER; value : INTEGER) : BOOLEAN = VAR (* Define an index into nums. *) i : INTEGER := FIRST(nums); found : BOOLEAN := FALSE; BEGIN WHILE (NOT found) AND (i <= LAST(nums)) DO IF nums[i] = value THEN found := TRUE; ELSE INC(i) END; END; RETURN found; END IsInList;
This example solves a specific problem, but it has characteristics which are very common in the processing of arrays. Just as we wrote an outline for general recursive processing of a list, we can write something similar for unbounded iteration over an array:
PROCEDURE Iterate(arr : ARRAY OF Something) = VAR i : INTEGER := FIRST(arr); where : INTEGER; terminatingCondition : BOOLEAN := FALSE; BEGIN WHILE (NOT terminatingCondition) AND (i <= LAST(arr)) DO IF arr[i] satisfies the condition we are looking for THEN where := i; terminatingCondition := TRUE; ELSE INC(i) END; END; IF terminatingCondition THEN Possibly do something to or with arr[where]; END END Iterate;
There will be variations on this theme: sometimes we will need to return a result indicating the value of the terminating condition, for instance, but the general structure is one that you should try to understand and learn, because you will find that it proves useful over and over again.
Consider how the following problem differs from that above:
Write a procedure to count the number of times a particular integer is present in an array.
Should we use a FOR-loop or a WHILE-loop? Can we reuse one or more of the examples that we have seen so far to help us?
To Next Page