Data Structures, Strings and Files
Arrays and records, every string operation AQA can ask for, reading and writing text files, and generating random numbers, with the traps that cost marks in each.
Arrays and records
An array is a data structure holding many values of the same type under one identifier, with each value found by its index.
scores ← [14, 9, 21, 6, 18]
OUTPUT scores[0]
scores[3] ← 11Indexing starts at 0, so the five items above are at positions 0, 1, 2, 3 and 4. There is no position 5, and asking for one is an out of range error.
Why arrays exist
Without an array, thirty scores means thirty separately named variables and thirty near identical lines of code. With an array, one loop handles any number of items and nothing breaks when the number changes.
total ← 0
FOR i ← 0 TO LEN(scores) - 1
total ← total + scores[i]
ENDFORA five item array has LEN 5 and a last index of 4. Looping TO LEN(scores) runs one step too far. This single mistake accounts for a large share of runtime errors in exam code.
Two dimensional arrays
A two dimensional array is an array of arrays, useful for anything grid shaped: a seating plan, a game board, a table of results.
board ← [[1, 0, 0], [0, 1, 0], [0, 0, 1]]
OUTPUT board[1][2]The first index selects the row, the second selects the position within it, so board[1][2] is 0.
Records
A record holds several values of different types that belong together, each with its own field name.
student.name ← 'Amira'
student.year ← 10
student.average ← 68.4An array holds many of the same thing. A record holds the several different things that describe one thing. A common structure is an array of records: one entry per student, each with a name, a year and an average.
- A one dimensional array: values in a row, reached by one index.
- A two dimensional array: rows and columns, reached by two.
- grid[1][2] means row 1, then column 2. Row always comes first.
- A record holds fields of different types, reached by name.
String handling
AQA names a specific set of string operations, and the exam expects you to use them by name.
| Operation | Meaning | Example on "Computing" |
|---|---|---|
LEN(s) | Length in characters | 9 |
POSITION(s, c) | Index of the first occurrence of a character | POSITION('Computing', 'p') gives 3 |
SUBSTRING(a, b, s) | The characters from index a to index b inclusive | SUBSTRING(0, 2, 'Computing') gives 'Com' |
| Concatenation | Joining strings together | 'Comp' + 'uting' gives 'Computing' |
STRING_TO_INT | Converts a string to an integer | '25' becomes 25 |
INT_TO_STRING | Converts an integer to a string | 25 becomes '25' |
CHAR_TO_CODE | The character set code for a character | 'A' becomes 65 |
CODE_TO_CHAR | The character for a code | 65 becomes 'A' |
String indexes also start at 0, so in "Computing" the C is at index 0 and the g is at index 8.
Converting case with character codes
Because the codes for the letters are in order and the gap between an upper case letter and its lower case partner is always 32, you can change case with arithmetic alone.
code ← CHAR_TO_CODE(letter)
IF code ≥ 65 AND code ≤ 90 THEN
letter ← CODE_TO_CHAR(code + 32)
ENDIFThat is not a curiosity. It is the sort of question AQA sets to check you understand that characters are numbers underneath.
- Every character has an index. The first is 0, and negative indexes count back from the end.
- A slice [a:b] runs from index a up to, but not including, b. Leave b out to go to the end.
- [-1] is the last character.
- Functions and methods build and search strings, and each one gives back a new string.
- upper() makes every letter a capital.
- strip() removes spaces from both ends.
- replace() swaps every match for something else.
- split() breaks a string into a list.
- join() builds a string from a list.
- find() gives the position of the first match, or -1 if there is none.
- A method returns a new string. The original is never changed unless you assign the result.
Files and random numbers
Reading and writing text files
A program that forgets everything when it closes is of limited use. Writing to a file makes data persist.
scores ← OPEN('results.txt')
line ← scores.readLine()
WHILE NOT scores.endOfFile()
OUTPUT line
line ← scores.readLine()
ENDWHILE
scores.close()Three points get marks:
- A file must be opened before use and closed afterwards. Not closing it can leave data unwritten, because output is often buffered.
- Reading past the end of a file is an error, which is why a loop must test for the end of file.
- Everything read from a text file arrives as a string, so numbers have to be converted before arithmetic.
Random numbers
roll ← RANDOM_INT(1, 6)Computers cannot produce genuinely random numbers. They produce pseudo-random numbers from an algorithm and a starting value called a seed, which means the same seed gives the same sequence every time.
For a dice game it does not matter. For anything security related it matters enormously, because a predictable sequence means predictable keys. That is the reason AQA distinguishes the two words.
- r reads. The file is only looked at, and it must already exist.
- w writes. Everything already in the file is erased first.
- a appends. New lines go on the end and the old ones are kept.
- with closes the file for you, and \n ends a line.
Key terms you must be able to define
- Array
- A data structure holding multiple values of the same data type under one identifier, accessed by index.
- Index
- The position of an item within an array or string, counted from zero.
- Two dimensional array
- An array whose elements are themselves arrays, used to represent grids and tables.
- Record
- A data structure holding several related values of different data types, each in a named field.
- Concatenation
- Joining two strings together end to end.
- SUBSTRING
- An operation returning the characters of a string between two given positions.
- Casting
- Converting a value from one data type to another, such as a string to an integer.
- End of file
- The marker showing that there is no more data to read from a file.
- Pseudo-random
- Generated by an algorithm so that it appears random, but is fully determined by the starting seed.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
The strongest answers here are the ones that keep types straight.
They say where data came from. Anything read from a file or from the user is a string until it is cast. Saying so explicitly is what turns a partially correct answer into a full one.
They count indexes carefully. Off by one errors are the single most common fault in exam code, and an answer that writes LEN(x) - 1 where it belongs shows the examiner that you understand indexing rather than remembering a pattern.
They choose the structure and justify it. "An array of records, because each student has several different pieces of information but every student has the same fields" is a complete answer. "An array" is half of one.
Mistakes that cost marks here
- Looping FOR i to LEN(array) rather than LEN(array) - 1, which reads past the end.
- Using an array for values of different types. That is a record's job.
- Forgetting that data read from a file is a string and must be converted before arithmetic.
- Forgetting to close a file, which can leave buffered output unwritten.
- Saying computers generate random numbers. They generate pseudo-random numbers from a seed.
Almost every programming language counts array positions from zero rather than one. The reason is historical: early languages stored an index as an offset from the start of the block, and the first item sits zero places along.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LAn array stores values that are all of the same data type
- LA record stores values of different data types in named fields
An array holds many values that must all be of the same data type, accessed by an index. A record holds several values of different data types that belong to one thing, each stored in its own named field.
- LSets a starting highest value, for example the first element
- LLoops through the array using the correct index range
- LCompares each element with the current highest
- LUpdates the highest and outputs it at the end
Set highest to scores[0], then loop i from 1 to LEN(scores) minus 1. Inside the loop, if scores[i] is greater than highest then set highest to scores[i]. After the loop finishes, output highest. Starting from the first element rather than from zero matters, because a list of negative scores would otherwise report zero as the highest.
- LA text file stores characters, so the value read is a string
- LArithmetic operators do not behave as intended on strings
- LCasting converts the string into an integer or real so the calculation works
A text file holds characters, so a line read from it is a string even when every character in it is a digit. Applying an arithmetic operator to a string either causes an error or joins values together rather than adding them, so the result is wrong. Casting the string to an integer or a real converts it into a numeric value, after which the calculation behaves as intended.
- LUses records to hold the three fields for one member
- LJustifies the record because the fields have different data types
- LUses an array to hold the 200 records
- LJustifies the array because every member has the same set of fields and a loop can process them all
The right structure is an array of records. Each member is one record with three named fields: name as a string, age as an integer and email as a string. A record is needed rather than an array for the individual member because the three values have different data types and belong together as a description of one person. The two hundred records are then held in an array, because every member has exactly the same set of fields, which means one loop can process all of them and the program does not have to change if the club gains or loses members.
- LThey are produced by an algorithm from a seed value
- LThe same seed always produces the same sequence, so the numbers are predictable
- LAn attacker who works out or guesses the seed can reproduce the keys
Pseudo-random numbers come from a deterministic algorithm applied to a starting seed, so they only appear random. Give the algorithm the same seed and it produces exactly the same sequence every time. If an attacker can work out or guess the seed, perhaps because it was taken from the system clock, they can regenerate the whole sequence and therefore every key the program produced. Cryptographic use requires a source of genuine unpredictability rather than a repeatable formula.