배열(Data arrays)

Seat 14C

• A cinema has 300 seats. Its booking system does not have 300 variables called Seat1A, Seat1B, Seat1C. It has one array 数组, and your ticket is an address into it: row 14, seat C.
• One name, hundreds of values, each found by a number. Add a row and the code does not change; loop over the numbers and you have checked every seat.
• Almost every Paper 2 algorithm walks an array: searching it, summing it, sorting it, finding its largest value.
• This lesson is the vocabulary, the declarations, and the four algorithms the examiner asks for in pseudocode and in words.

The vocabulary

• An array is a data structure holding a fixed number of elements 元素 of the same data type under one identifier, each reached by an index 索引.
• The lower bound 下界 and upper bound 上界 are the first and last valid index. The number of elements is upper bound − lower bound + 1.
• The dimension 维度 is how many indices an element needs: one for a list, two for a table.
• In ThisArray[n] ← 42 the array has one dimension, the index is the INTEGER variable n, and the element at that index receives 42.

One identifier, an index for each element, bounds at both ends

Worked example: declaring the array a task needs

Processing a 1-D array

DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"

FOR i ← 1 TO 5
    OUTPUT Names[i]
NEXT i

• A FOR loop from the lower bound to the upper bound visits every element once.
• For a sum, count, maximum or minimum, set a running variable before the loop and update it inside.

2-D arrays

DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99      // row 2, column 3

• The first index is the row, the second the column. Nested loops 嵌套循环 visit every cell: the outer loop over rows, the inner over columns.
• Use 1-D for a single sequence and 2-D when the data has two natural dimensions, such as a grid of seats or a table of marks by student and subject.

Grid[row, column], always in that order

Worked example: a linear search that can say "not found"

FoundAt ← -1
FOR i ← 1 TO n
    IF A[i] = Target THEN
        FoundAt ← i
    ENDIF
NEXT i
IF FoundAt = -1 THEN
    OUTPUT "Not found"
ELSE
    OUTPUT "Found at ", FoundAt
ENDIF

Largest value, and where it is

Largest ← A[1]
Position ← 1
FOR i ← 2 TO n
    IF A[i] > Largest THEN
        Largest ← A[i]
        Position ← i
    ENDIF
NEXT i
OUTPUT Largest, " at ", Position

• Start Largest at the first element, never at 0: the array might be all negative.
• The same shape counts or outputs the non-blank elements: compare each with the marker for unused, "" or -1, and count only those that differ.

Bubble sort

• A bubble sort 冒泡排序 makes repeated passes through the array comparing adjacent pairs and swapping those out of order, until a pass makes no swaps.
• After each pass the largest unsorted value has bubbled to the end, so the next pass can stop one place earlier.

REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO Limit - 1
        IF Data[Index] > Data[Index + 1] THEN
            Temp ← Data[Index]
            Data[Index] ← Data[Index + 1]
            Data[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Limit ← Limit - 1
UNTIL Swapped = FALSE

Each pass carries the largest remaining value to the end

Worked example: where the bubble-sort marks are

Worked example: removing and inserting

Marks that slip away

You've got it