Data Types and Structures

Programs work with data, and choosing the right way to store it makes a solution simpler and more reliable. This chapter covers the basic data types, then the structures that hold collections of data: records, arrays, files, and the abstract data types stack, queue and linked list. Paper 2 expects you to write pseudocode for all of them.

10.1 Data types and records

Data types

A data type says what kind of value a variable holds, how much space it needs and which operations are allowed.

Choosing a data type for a problem:

• Use INTEGER for counts and whole-number quantities, and REAL for measurements and money (when decimal values are needed).
• Use STRING for data that is not used in calculations, even if it contains digits, such as a telephone number, postcode or ID number (they may start with 0, and adding two phone numbers has no meaning).
• Use BOOLEAN for yes/no states such as "has paid" or "is a member".
• Use CHAR for a single letter, such as a menu choice 'Y' or 'N'.

In pseudocode, variables are declared with DECLARE, constants with CONSTANT:

DECLARE Age : INTEGER
DECLARE Name : STRING
DECLARE IsMember : BOOLEAN
CONSTANT VATRate = 0.2

Records

A record is a data structure that holds a set of related items of different data types under one name. Each item is a field. A record is useful because a single record groups everything about one thing (a student, a product) and can be passed around as one item. In pseudocode, a record is declared as a user-defined type:

TYPE TStudent
    DECLARE StudentID : INTEGER
    DECLARE Name      : STRING
    DECLARE DateOfBirth : DATE
    DECLARE Paid      : BOOLEAN
ENDTYPE

DECLARE Pupil : TStudent
Pupil.StudentID ← 1012
Pupil.Name ← "Amina Khan"
Pupil.Paid ← FALSE
OUTPUT Pupil.Name

A field is accessed by writing the record's name, a dot, and the field's name. Records are often put in an array (an array of records) to hold many students (see the next section), and are stored as the rows of a file or a database table.

10.2 Arrays

An array is a data structure that holds a fixed number of items of the same data type under one identifier, with each item reached by its index (position number). A one-dimensional (1D) array is a list. Arrays make it possible to store and process many values using loops, instead of many separate variables.

Terms: the index identifies the element; upper and lower bounds are the first and last index (in Cambridge pseudocode, arrays usually start at 1); an element is one item.

1D arrays

DECLARE Marks : ARRAY[1:5] OF INTEGER

Marks[1] ← 72
Marks[2] ← 55

FOR Index ← 1 TO 5          // read in five marks
    INPUT Marks[Index]
NEXT Index

Total ← 0
FOR Index ← 1 TO 5          // total them
    Total ← Total + Marks[Index]
NEXT Index
OUTPUT "Average ", Total / 5

2D arrays

A two-dimensional (2D) array is a table with rows and columns, accessed with two indexes: Table[Row, Column]. It is used for a grid of values (a game board, a table of results).

DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER    // 3 rows, 4 columns

FOR Row ← 1 TO 3
    FOR Column ← 1 TO 4
        Grid[Row, Column] ← 0
    NEXT Column
NEXT Row

Two nested loops are needed to visit every element: the outer loop moves through the rows and the inner loop through the columns.

Linear search

A linear search checks each element in turn from the start until the item is found or the end of the list is reached. It works on unsorted data. In the worst case, every element is looked at.

DECLARE Found : BOOLEAN
Found ← FALSE
Index ← 1
WHILE Index <= 100 AND Found = FALSE
    IF Names[Index] = SearchName THEN
        Found ← TRUE
    ELSE
        Index ← Index + 1
    ENDIF
ENDWHILE
IF Found = TRUE THEN
    OUTPUT "Found at position ", Index
ELSE
    OUTPUT "Not found"
ENDIF

Bubble sort

A bubble sort repeatedly compares adjacent pairs and swaps them if they are in the wrong order. After each pass the largest remaining value has "bubbled" to the end, so the next pass can be one element shorter. A flag stops it as soon as a pass makes no swaps.

DECLARE Swapped : BOOLEAN
DECLARE Temp, Last : INTEGER
Last ← 10                          // number of items still to check
REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO Last - 1
        IF Scores[Index] > Scores[Index + 1] THEN
            Temp ← Scores[Index]
            Scores[Index] ← Scores[Index + 1]
            Scores[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Last ← Last - 1
UNTIL Swapped = FALSE

The three assignments that swap two elements need a temporary variable. Bubble sort is simple, but slow for large lists, since it makes many passes.

10.3 Files

A file stores data permanently on secondary storage, so it is kept when the program ends and can be used by other programs. A text file holds data as lines of text. Programs use files to keep data between runs (high scores, records of orders) and to read in large amounts of data.

Steps for using a file: open it (stating the mode), read or write it, then close it.

OPENFILE "Scores.txt" FOR WRITE
FOR Index ← 1 TO 3
    WRITEFILE "Scores.txt", Names[Index] & "," & Scores[Index]   // one line each
NEXT Index
CLOSEFILE "Scores.txt"

OPENFILE "Scores.txt" FOR READ
WHILE NOT EOF("Scores.txt")
    READFILE "Scores.txt", Line       // reads the next line into Line
    OUTPUT Line
ENDWHILE
CLOSEFILE "Scores.txt"

EOF(filename) returns TRUE when the end of the file has been reached, so the loop reads every line. Always close a file: otherwise data may not be written, and the file may be locked.

10.4 Abstract data types (ADT)

An abstract data type (ADT) is a collection of data together with the operations that can be carried out on it, described without saying how it is stored or implemented. The programmer uses the operations and does not need to know the details. Three ADTs are needed.

Stack

A stack is a last in, first out (LIFO) structure: items are added and removed at the same end (the top), like a pile of plates. Operations:

• push: add an item to the top
• pop: remove and return the item at the top
• possibly peek (look at the top) and is empty / is full checks.

Uses: the undo feature, the call stack (return addresses when subroutines are called), storing registers during an interrupt, evaluating expressions in Reverse Polish Notation, and backtracking.

Tap to enlarge

A stack of up to five items in five stages: empty, push 5, push 8, pop which returns 8, and push 3, with the top-of-stack pointer moving up and down as items are added and removed at the top

Close

Implemented with a 1D array and a top-of-stack pointer (TopOfStack, which is 0 when the stack is empty):

CONSTANT MaxSize = 10
DECLARE Stack : ARRAY[1:MaxSize] OF INTEGER
DECLARE TopOfStack : INTEGER
TopOfStack ← 0

PROCEDURE Push(Item : INTEGER)
    IF TopOfStack = MaxSize THEN
        OUTPUT "Stack is full"
    ELSE
        TopOfStack ← TopOfStack + 1
        Stack[TopOfStack] ← Item
    ENDIF
ENDPROCEDURE

FUNCTION Pop() RETURNS INTEGER
    IF TopOfStack = 0 THEN
        OUTPUT "Stack is empty"
        RETURN -1
    ELSE
        Item ← Stack[TopOfStack]
        TopOfStack ← TopOfStack - 1
        RETURN Item
    ENDIF
ENDFUNCTION

Queue

A queue is a first in, first out (FIFO) structure: items are added at the rear and removed from the front, like people waiting in a line. Operations: enqueue (add at the rear) and dequeue (remove from the front), plus checks for empty or full.

Uses: a print queue, the order in which processes wait for the processor, keyboard and buffers, and messages waiting to be handled.

Tap to enlarge

A circular queue held in an array of eight places drawn as a ring, holding the items C, D, E and F in places 6, 7, 8 and 1 with the front pointer at place 6 and the rear pointer at place 1, so the queue has wrapped round the end of the array

Close

A queue is implemented with an array and two pointers, FrontPointer and RearPointer, and a count of the items. A circular queue wraps the pointers back to the start of the array when they reach the end, so that space made empty at the front is reused.

// enqueue in a circular queue of MaxSize items
IF NumberOfItems = MaxSize THEN
    OUTPUT "Queue is full"
ELSE
    RearPointer ← RearPointer + 1
    IF RearPointer > MaxSize THEN RearPointer ← 1 ENDIF
    Queue[RearPointer] ← Item
    NumberOfItems ← NumberOfItems + 1
ENDIF

Linked list

A linked list is a list in which each item (node) holds the data and a pointer to the next node. The items need not be stored next to each other in memory. A start pointer gives the first node, and the pointer of the last node is null (written -1 or 0). A pool of unused nodes is the free list, with its own free pointer.

Tap to enlarge

A linked list of nodes holding 1018, 1034 and 1056, each with a pointer to the next; below it the list after inserting 1020, where only two pointers change; and the same kind of list stored in two arrays of data and pointers with a start pointer and a free list

Close

Implemented with two parallel arrays: one for the data and one for the pointers.

With StartPointer = 2, the list in order follows the pointers: 1007, 1010, 1018, 1034, 1056, 1062, 1092, and the last pointer is -1.

Inserting a node: take a node from the free list, put the data in it, set its pointer to the node that should come after it, and change the previous node's pointer to point to the new one. Deleting: change the previous node's pointer to skip the node, and add the freed node to the free list. Nothing needs to be moved, which is the main advantage over an array, where inserting means shifting everything along. The drawbacks are the extra memory for the pointers and the fact that you cannot jump directly to the n-th item: you must follow the links from the start.

Editing an item. In a stack only the top item can be read and changed directly, and in a queue only the front item; to change any other item the items in front of it must be removed first. In a linked list, follow the pointers from the start until the node is found, then change its data.

Justifying the choice of structure. Use a stack when the last item added must be dealt with first (undo, return addresses). Use a queue when items must be handled in the order they arrive (print jobs). Use a linked list when items are often inserted or deleted in the middle and the number of items changes.