Data types, arrays, files and abstract data types

Data types and how to choose one

Every value in a program is declared with a data type, and the type fixes what the value can be and which operations are allowed on it. Cambridge pseudocode uses six simple data types, INTEGER, REAL, CHAR, STRING, BOOLEAN and DATE, plus the structured types ARRAY and FILE. Choosing the type is not decoration: it decides whether arithmetic will work, whether a leading zero survives, and whether the value can be validated at all.

INTEGER holds whole numbers, positive, negative or zero, and is used for counting: a quantity, a year group, the number of seats sold. REAL holds a number with a fractional part, such as a price, an average or a measurement, and it must be used whenever the result of a calculation can have a decimal part. Money is sometimes stored as an INTEGER number of pence rather than a REAL number of pounds, because binary floating point cannot store every decimal fraction exactly, so repeated additions of 0.10 can drift.

CHAR holds exactly one character, such as a grade letter or a single initial. STRING holds zero or more characters: a name, an address, a postcode, a telephone number. A telephone number and a postcode look numeric but must be STRING, because a postcode contains letters and spaces and a telephone number beginning with 0 would lose that zero if it were stored as an INTEGER.

BOOLEAN holds only TRUE or FALSE, and it is the right type for anything with two states: whether a pupil is registered, whether a book is on loan, whether a password has been entered correctly. DATE holds a calendar date, and it exists so that dates can be compared and used in calculations. The number of days between two DATE values can be calculated, which is how an age or an overdue charge is worked out; a date stored as a STRING can be displayed but cannot be treated as a date without being converted first.

• Ask four questions of the data: is it counted (INTEGER), measured or money with a fractional part (REAL), a single character (CHAR), text (STRING), one of two states (BOOLEAN) or a calendar date (DATE)?
• Use STRING, not INTEGER, for anything with a leading zero or with letters in it: telephone numbers, postcodes, product codes such as 0071.
• Use REAL only where a fractional part is genuinely possible, and INTEGER where it never is, because the type tells the reader what the value means.
• A value that is only ever compared with another date, or used to work out an interval, should be DATE rather than STRING.

Records: different data types under one identifier

A record is a structure that holds a set of related data of different data types under one identifier. One pupil's record might hold a last name (STRING), a date of birth (DATE), a year group (INTEGER) and whether the fees are paid (BOOLEAN). Without records you would need four separate variables for every pupil and a naming scheme to keep them together; with a record the four fields travel as one item, which can be passed to a procedure or written to a file in one go.

The structure is defined once, and the definition is a type, not a variable. TYPE names the record type and lists each field with its data type, and ENDTYPE closes the definition. A variable of that type is then declared in the usual way, and each field is reached using the variable name, a dot and the field name, for example Pupil.YearGroup.

This dot notation is accepted anywhere a variable is accepted: INPUT Pupil.LastName reads a value into the field, an assignment stores one, and OUTPUT displays one. Because a field is just a named storage location with a type, it behaves like any other variable: LastName can be compared with another STRING, DateOfBirth can be compared with today's date, and FeePaid can be used directly as a condition. A whole record can also be read from a file or written to a file in one statement when the file stores records, which is why records and files are taught together.

Records combine naturally with arrays. DECLARE Pupils : ARRAY[1:200] OF StudentRecord gives 200 records, and Pupils[7].LastName is the surname of the seventh pupil. Parallel arrays, one array of names and a separate array of marks, also work, but they can drift out of step the moment a pupil is deleted from one array and not the other; an array of records cannot drift, because element 7 holds every field belonging to pupil 7.

1D arrays: index, bounds and processing

An array is a fixed number of elements of the same data type, held under one identifier and selected by an index (also called a subscript). The lower bound is the first index the array allows and the upper bound is the last, so ARRAY[1:30] has 30 elements and ARRAY[0:9] has 10. The number of elements is the upper bound minus the lower bound plus one.

Declaring an array reserves all of its storage at once: DECLARE Scores : ARRAY[1:30] OF INTEGER creates 30 integer locations, all initially undefined. An element is used exactly like a variable, with the index in square brackets, so Scores[4] <- 67 stores a mark and OUTPUT Scores[4] displays it. The index may be a variable or an expression, and that is what makes an array worth having: Scores[Index] inside a loop reaches every element in turn with a single statement.

Most array processing is one pass from the lower bound to the upper bound. A FOR loop reads the values, and a second pass totals, counts, finds the largest or works out an average. A running total must be set to 0 before the loop, never inside it, and a maximum must be initialised to the first element or to a value below any possible element, otherwise it stays at 0 and no mark is ever larger than it.

Indexing outside the declared bounds is an error. Some languages stop the program with an index error, others silently write over another variable, which is far worse because the fault appears somewhere else. Arrays are also fixed in size, so when the number of items is not known in advance the array is declared generously and a separate variable counts how many elements are actually in use.

2D arrays: data in a grid

A 2D array needs two indices to select an element, and it is the natural structure for anything laid out in rows and columns. DECLARE Seats : ARRAY[1:5, 1:3] OF BOOLEAN declares 5 rows of 3 columns, which is 15 elements, and Seats[2, 3] is the element in row 2, column 3. The first index is always the row and the second is the column, and that order has to be kept the same everywhere in the program, because Seats[3, 2] is a different element.

Reading or processing the whole array takes two loops, one inside the other. The outer loop steps through the rows and the inner loop steps through every column of the current row, so the inner loop finishes before the row changes. Reading a value into each element therefore takes one INPUT inside the inner loop, with both indices written in the brackets, and a total over the grid is a sum accumulated in the inner loop.

A 2D array is the right choice when each item is described by two facts: a seat by its row and its number, a mark by the pupil and the subject, a pixel by its x and y coordinates, a square on a board by its row and column. A 1D array is right when one index is enough, as with a list of 30 names, even though each name is itself a string of characters.

Two errors are common. The first is mixing the order of the indices so that the program reads columns where it means rows; the second is declaring an array far larger than the data, which wastes storage and makes the loops harder to follow. Decide which index is the row before writing a single line, and use the same meaning throughout.

Searching an array with a linear search

A linear search (serial search) checks the elements one at a time, starting at the lower bound, until it finds the value it is looking for or runs past the last element. It makes no demand that the data be in order, which is its great strength: it is the only one of the two searches in this syllabus that works on unsorted data, and it can be used the moment a value is stored.

The algorithm needs four things: the array, the value being searched for, an index that steps through the elements, and a Boolean flag that records whether the value has been found. The index and the flag are both initialised before the loop, and the loop continues while the value has not been found and the index is still inside the array. Missing either half of that condition breaks the algorithm: without the flag it never stops when the value is found, and without the bounds check it runs past the end of the array for a value that is not there.

Inside the loop the element is compared with the search value; if they are equal the flag is set to TRUE, otherwise the index moves on by one. When the loop ends, the flag is tested to decide what to output. If the flag is TRUE the value was found at the current index; if it is FALSE the value is not in the array and the index has ended one beyond the upper bound, which is why the flag rather than the index decides what is reported.

A linear search is easy to write and needs no ordering, but it is slow on large arrays. A successful search takes between 1 comparison, if the value happens to be first, and n comparisons, if it is last; an unsuccessful search always takes n comparisons because every element must be checked. Doubling the amount of data doubles the work, so for a large amount of sorted data an algorithm that uses the order to discard half the data at a time is dramatically faster.

Sorting an array with a bubble sort

A bubble sort steps through the array comparing each element with the one after it, and swaps the pair whenever they are in the wrong order. On each pass the largest remaining value moves steadily towards the end of the array and stays there, which is where the name comes from. Sorting into descending order needs no change to the algorithm beyond reversing the comparison.

After the first pass the largest value is in place, after the second the second largest is in place, so n elements need at most n-1 passes. In practice the sort usually finishes sooner: if a complete pass makes no swaps then nothing was out of order, so the array must already be sorted. A Boolean flag set to FALSE at the start of every pass and to TRUE whenever a swap happens lets a REPEAT loop stop as soon as a pass is clean, which makes the algorithm much quicker on data that is nearly in order already.

Swapping two elements needs three statements and a temporary variable: copy the first value into the temporary, copy the second value into the first element, then copy the temporary into the second element. The classic mistake is two assignments without the temporary, which ends with both elements holding the same value and one value lost for ever.

A bubble sort is short, needs only one extra variable, and is simple to check by hand, but it is inefficient. With n elements the first pass makes n-1 comparisons, the next n-2, and so on, giving roughly n(n-1)/2 comparisons in the worst case, so the work grows with the square of the number of items and a large array becomes very slow. It is a sensible choice for a few dozen items, or for data that is almost sorted, and a poor choice for a file of thousands of records.

Files: why they are needed and how they are handled

Why files are needed. Variables and arrays live in main memory, and main memory is volatile: its contents are lost when the program ends, when the computer is switched off or when the power fails. A file is held on secondary storage, so the data survives between runs, can be read back by the same program next time or by a different program, and can be copied, transferred to another computer, backed up or sent to a printer. Files also hold collections of data far too large to fit in memory at once, which can be processed one line at a time.

A text file is a sequence of characters divided into lines, and the program reads it one line at a time from the beginning to the end. Each line normally holds one record or one field, so the structure of the file has to match the structure of the program that reads it. The program has no way of knowing how many lines there are except by reaching the end, so it tests EOF, end of file, before every read; reading when the end has been reached is an error.

A file is opened before it is used and closed afterwards. OPENFILE with FOR READ opens an existing file for reading, FOR WRITE creates a new file or empties an existing one, and FOR APPEND adds new data to the end of an existing file without destroying what is already there.

READFILE reads one line into a variable, WRITEFILE writes one line, and CLOSEFILE writes any buffered data to the disk and releases the file. A program that forgets to close a file can lose the last few records it wrote.

Reading a file therefore follows a fixed pattern: open it, test EOF, read one line, process that line, and repeat until EOF is true, then close it. If the lines are records, each line is read into a record or split into fields; if the program needs to keep all of the data, each line is copied into the next element of an array as it is read, which is how a file of records becomes an array of records in memory.

Stacks and queues as abstract data types

An abstract data type (ADT) is a collection of data together with the set of operations that can be performed on that data. It is abstract because the user of the ADT knows what each operation does but not how the data is stored or how the operations are implemented. A stack can be built from an array or from a linked list, and the program that uses the stack does not need to know which, because the operations behave the same way in both cases.

This is the same idea as abstraction elsewhere in the course: keep the essential behaviour and hide the detail. A stack is a last in, first out (LIFO) structure. Data is added with push and removed with pop, and both operations work at one end only, the top; a peek (or top) operation reads the top value without removing it.

Because only the top is accessible, the item that was pushed most recently is the first one out. Pushing onto a full stack causes overflow, and popping from an empty stack causes underflow, so a well-written implementation tests for both.

A queue is a first in, first out (FIFO) structure. Data is added at one end, the rear, with enqueue, and removed from the other end, the front, with dequeue, so items leave in exactly the order they arrived. A queue is the right structure whenever fairness or arrival order matters: a print spooler, a keyboard buffer, a queue of customers, or a set of processes waiting for the processor are all queues.

Choosing between them is a question about which item must be handled next: the most recent item first means a stack, and the oldest item first means a queue. Say which operation is used and why that order gives the behaviour the situation needs, because a description of the structure without the justification does not answer a justify question.

Linked lists, and implementing all three with arrays

A linked list stores each item in a node. A node holds the data and a pointer to the next node, the last node's pointer holds a null value to show the list has ended, and a separate start (or head) pointer gives the position of the first node. The nodes need not be next to one another in memory, which is what makes a linked list different from an array: the list can grow and shrink while the program runs, and no maximum size has to be declared in advance.

To traverse a linked list the program starts at the start pointer and follows the pointers node by node until it reaches null; the nth item cannot be reached directly, so a linked list is slower than an array for reading a particular item but much faster for inserting and deleting.

To insert a node, the new node's pointer is set to the node it will come before and the previous node's pointer is set to the new node. To delete a node, the previous node's pointer is set to skip over it. Neither operation moves any of the other items, whereas inserting into the middle of an array means shifting every later element up one place.

All three ADTs can be implemented using arrays, which is how they are usually examined. A stack uses a 1D array and a single integer, Top, which holds the index of the current top element and is 0 when the stack is empty: push tests that Top is below the upper bound, then increments Top and stores the value; pop tests that Top is above 0, reads the value and decrements Top. Top equal to the upper bound means the stack is full, and Top equal to 0 means it is empty.

A queue uses a 1D array with two integers, Front and Rear, which mark the two ends; enqueue increments Rear and stores, dequeue reads the element at Front and increments Front. In a simple array implementation the space at the front is never reused, so the queue creeps towards the end of the array and reports itself full while most of the array is empty; a circular queue solves this by making Rear wrap round to the start with MOD, reusing the vacated space. A linked list uses two parallel arrays, one holding the data and one holding the index of the next node, plus a start pointer and a list of free positions, so that inserting and deleting only ever changes the integer pointers.