CS7Arrays and Records

A data structure is an organised collection of values kept together under one name. You need two kinds: arrays and records.

• Without a data structure, 30 test scores would need 30 variables (score1, score2…). Adding a 31st score means changing the code.
• With an array, all 30 scores share one identifier. Each one is reached by its position number, the index.
• Because the index is just a number, a loop can visit every element. The same few lines then work for 5 scores or 500.
• AQA's definition of an array: “A data structure that stores a collection of elements of the same data type under a single variable name and is accessed through an index.”
• In AQA exams every element of an array has the same data type (all integers, all strings…). A record groups values of different types.
• Python has no arrays as such. It uses lists, which work the same way for this course.
• Only one-dimensional and two-dimensional arrays are on the course.
• Adding up five scores in Python with a list and a loop:

  scores = [14, 9, 17, 12, 20]
  total = 0
  for score in scores:
      total = total + score
  print(total)

Data structure

An organised collection of values stored together under one name, such as an array or a record.

Array

A data structure that stores a collection of elements of the same data type under a single variable name and is accessed through an index.

Element

One value stored in an array.

Index

The position number used to reach one element of an array. It starts at 0 unless a question says otherwise.

• Create an array by listing its elements in square brackets. In pseudo-code: temps ← [12, 15, 9, 11, 14]. In Python: temps = [12, 15, 9, 11, 14].
• Indexes start at 0. temps[0] is 12 and temps[4] is 14. AQA's papers count from 0 unless a question says otherwise.
• Update one element by assigning to it: temps[2] ← 10 (Python: temps[2] = 10). The other elements don't change.
• LEN(temps) (Python len(temps)) gives the number of elements, 5. It is not the last index.
• So the last index is always LEN − 1: temps[LEN(temps) − 1] is the last element. (len() works on strings too: see String handling.)
• The same in Python, with each output as a comment:

  temps = [12, 15, 9, 11, 14]
  print(temps[0])                 # 12
  temps[2] = 10
  print(temps)                    # [12, 15, 10, 11, 14]
  print(len(temps))               # 5
  print(temps[len(temps) - 1])    # 14, the last element

• Python lists can also grow with .append(). AQA's pseudo-code has no equivalent, so exam questions give you arrays of a fixed size.

Each element has an index. The first is 0, so the last is LEN − 1.

LEN / len()

Returns the number of elements in an array (or characters in a string).

Zero-based indexing

Counting positions from 0, so the first element is at index 0 and the last at LEN − 1.

• By index: FOR i ← 0 TO LEN(rain) − 1 in pseudo-code, or for i in range(len(rain)): in Python. Use this when you need the position, or need to change elements.
• By element: FOR day IN rain in pseudo-code, or for day in rain: in Python. Each pass gives the next value. It can't change the array's elements.
• Total and mean: start a total at 0, add each element, then divide by the number of elements.

  rain ← [4, 0, 7, 2, 5]
  total ← 0
  FOR i ← 0 TO LEN(rain) - 1
      total ← total + rain[i]
  ENDFOR
  OUTPUT total / LEN(rain)

• Counting: start a counter at 0 and add 1 each time an element matches a condition.
• Largest or smallest: start with the first element, then compare every element with the best so far.

  rain = [4, 0, 7, 2, 5]
  wettest = rain[0]
  dryDays = 0
  for day in rain:
      if day > wettest:
          wettest = day
      if day == 0:
          dryDays = dryDays + 1
  print(wettest)    # 7
  print(dryDays)    # 1

• Starting the largest at 0 fails if every value is negative. Starting the smallest at 0 fails if every value is positive. Starting at the first element always works.

FOR-IN loop

A loop that takes each element of an array in turn. In AQA pseudo-code it can't be used to change the elements.

Running total

A variable that starts at 0 and has each value added to it inside a loop.

A two-dimensional (2D) array is an array of arrays. Think of it as a table with rows and columns.

• Write it as a list of rows. This one holds a café's cake sales: 3 days (rows) and 4 cakes (columns).

  sales ← [[3, 5, 2, 8],
           [6, 1, 4, 0],
           [2, 7, 3, 5]]

• sales[1][2] means row 1, then column 2, which is 4. AQA always puts the row index first.
• Update one element the same way: sales[2][0] ← 9 (Python sales[2][0] = 9).
• LEN(sales) is the number of rows (3). LEN(sales[0]) is the number of columns in row 0 (4).
• sales[1] on its own is a whole row: [6, 1, 4, 0].
• To visit every element, use nested loops: the outer loop picks a row and the inner loop goes along it.

  sales = [[3, 5, 2, 8],
           [6, 1, 4, 0],
           [2, 7, 3, 5]]
  total = 0
  for row in range(len(sales)):
      for col in range(len(sales[row])):
          total = total + sales[row][col]
  print(total)    # 46

• The inner statement runs rows × columns times: 3 × 4 = 12 here.

Row first, then column.

Two-dimensional array

An array whose elements are themselves arrays, used like a table of rows and columns.

Nested loop

A loop inside another loop. For a 2D array, the outer loop picks the row and the inner loop picks the column.

• Valid indexes run from 0 to LEN − 1. Using any other index is an error: the element doesn't exist.
• In Python the program stops with IndexError: list index out of range.

  marks = [56, 71, 48]
  print(marks[3])    # IndexError: there is no element at index 3

• Commonest cause: a loop that goes one too far, such as FOR i ← 0 TO LEN(a) or range(len(a) + 1).
• Comparing neighbours: if the loop uses a[i + 1], it must stop at LEN − 2. In Python, range(len(a) - 1) does this.

  heights = [150, 152, 151, 155]
  for i in range(len(heights) - 1):
      if heights[i + 1] > heights[i]:
          print(f"Taller after position {i}")

• Four values have only three neighbouring pairs, so the loop runs three times.
• Indexes from the user: check the number is from 0 to LEN − 1 before using it.

  marks = [56, 71, 48]
  pos = int(input("Position: "))
  if pos >= 0 and pos < len(marks):
      print(marks[pos])
  else:
      print("No such position")

• Python treats marks[-1] as the last element, but AQA's pseudo-code and other languages don't. Don't rely on negative indexes in exam answers.

Out of range (index) error

An error caused by using an index that is less than 0 or greater than LEN − 1.

A record groups related values that can have different data types. Each value is stored in a named field.

• AQA's pseudo-code defines a record type with RECORD … ENDRECORD. Each field has a name and a data type.

  RECORD Plant
      name : String
      height : Real
      potSize : Integer
      inFlower : Boolean
  ENDRECORD

• The definition is only a template. It doesn't store any data.
• Create a record (an instance) by giving the values in the same order as the fields.

  p1 ← Plant('Fern', 32.5, 15, False)
  p2 ← Plant('Geranium', 24.0, 12, True)

• Each value must match its field's type: 'Fern' is a String, 32.5 a Real, 15 an Integer, False a Boolean.
• The record type's name starts with a capital letter (Plant). Each record you create is a variable (p1, p2).
• Data types you can use for fields: String, Integer, Real, Boolean and Character.

One record holds several named fields, each with its own type.

Record

A data structure that groups related values, possibly of different data types, into named fields.

Field

One named item of data inside a record, with its own data type.

Instance

One record created from a record definition, such as p1 created from Plant.

• Reach a field with the record's name, a dot and the field name: p1.name.
• Output a field: OUTPUT p1.name outputs Fern.
• Update just one field by assigning to it. The other fields keep their values.

  p1.height ← 34.0
  p2.inFlower ← False
  p1.height ← p1.height + 1.5

• Don't create a new record to change one value. p1 ← Plant('Fern', 34.0, 15, False) retypes every field and risks mistakes.
• Fields work in expressions and conditions like ordinary variables.

  IF p1.height > p2.height THEN
      OUTPUT p1.name, ' is taller'
  ENDIF

• Writing p1 on its own means the whole record. If you want one value, you need the field: p1.height.

Dot notation

Writing record.field (such as p1.height) to read or change one field of a record.

Python has no RECORD keyword. AQA's papers write records as classes with an __init__ subroutine.

• The same Plant record in Python:

  class Plant:
      def __init__(self, nm, ht, ps, fl):
          self.name = nm
          self.height = ht
          self.potSize = ps
          self.inFlower = fl
  
  p1 = Plant("Fern", 32.5, 15, False)
  p2 = Plant("Geranium", 24.0, 12, True)
  print(p1.name)              # Fern
  p1.height = 34.0
  p2.inFlower = False
  print(p1.height, p2.inFlower)    # 34.0 False

• __init__ has two underscores before and after init. It runs when a record is created.
• self is the first parameter. Each field is made by writing self. before its name.
• The other parameters (nm, ht…) receive the values in order, then are copied into the fields.
• The class name starts with a capital letter. Python doesn't state the fields' data types: the values you pass decide them.
• You only need classes as a way to write records. Methods and other object-oriented ideas aren't on the course.

__init__

The Python subroutine that runs when a record (an object of a class) is created; it sets up the fields.

self

The first parameter of __init__: it stands for the record being created, so self.name is a field.

Records of the same type can go in an array. Then a loop can process many records, such as every plant in a garden centre.

• Put records in an array: plants ← [p1, p2, Plant('Cactus', 8.5, 9, True)].
• The index picks the record and the field picks the value: plants[2].name is Cactus.
• Update a field of one record in the array: plants[1].potSize ← 15.
• Mean height in pseudo-code:

  total ← 0
  FOR i ← 0 TO LEN(plants) - 1
      total ← total + plants[i].height
  ENDFOR
  OUTPUT total / LEN(plants)

• Finding the tallest plant in Python. Keep the whole record so you can output any field of the winner.

  class Plant:
      def __init__(self, nm, ht, ps, fl):
          self.name = nm
          self.height = ht
          self.potSize = ps
          self.inFlower = fl
  
  plants = [Plant("Fern", 32.5, 15, False),
            Plant("Geranium", 24.0, 12, True),
            Plant("Cactus", 8.5, 9, True)]
  tallest = plants[0]
  for p in plants:
      if p.height > tallest.height:
          tallest = p
  print(tallest.name)    # Fern

• To change a field in every record, use an index loop: plants[i].height ← plants[i].height + 1. That works in pseudo-code and Python alike.

plants[1].height: index first, then the field.

Array of records

An array whose elements are all records of the same type, reached as array[index].field.