Arrays · 数组
| English | 中文 | Pinyin · 拼音 |
|---|---|---|
| array/əˈreɪ/ | 数组 | shù zǔ |
| element/ˈelɪmənt/ | 元素 | yuán sù |
| index/ˈɪndeks/ | 索引 | suǒ yǐn |
| lower bound/ˈləʊə baʊnd/ | 下界 | xià jiè |
| upper bound/ˈʌpə baʊnd/ | 上界 | shàng jiè |
| dimension/daɪˈmenʃn/ | 维度 | wéi dù |
| nested loops/ˈnestɪd luːps/ | 嵌套循环 | qiàn tào xún huán |
| linear search/ˈlɪnɪə sɜːtʃ/ | 线性查找 | xiàn xìng chá zhǎo |
| bubble sort/ˈbʌbl sɔːt/ | 冒泡排序 | mào pào pái xù |
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.
14 排 C 座
- 一家电影院有 300 个座位。它的订票系统没有 300 个叫
Seat1A、Seat1B、Seat1C的变量。它有一个数组(array),你的票是数组里的一个地址:第 14 排,C 座。 - 一个名字,几百个值,每个都靠一个数字找到。加一排座位,代码不用改;循环遍历那些数字,你就检查了每个座位。
- Paper 2 上几乎每个算法都在遍历数组:查找、求和、排序、找最大值。
- 这一课讲术语、声明,以及考官要求用伪代码和文字写出的四个算法。
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] ← 42the array has one dimension, the index is theINTEGERvariablen, and the element at that index receives42.
One identifier, an index for each element, bounds at both ends
术语
- 数组是在一个标识符下保存固定数量同一数据类型的元素(element)的数据结构,每个元素通过一个索引(index)访问。
- 下界(lower bound)和上界(upper bound)是第一个和最后一个有效索引。元素个数是上界 − 下界 + 1。
- 维度(dimension)是一个元素需要几个索引:列表一个,表格两个。
- 在
ThisArray[n] ← 42中,数组是一维的,索引是INTEGER变量n,该索引处的元素接收42。
一个标识符,每个元素一个索引,两端各有边界
An array stores: · 一个数组存储:
An array is an ordered collection of same-type items accessed by index. (A record groups different types.) · 一个数组是相同类型的项的一个有序集合,通过索引访问。(一个记录把不同类型分组。)
An array is a data structure holding many values of the ______ type under one name. · 一个数组是一个数据结构,在一个名字下保存许多______类型的值。
Each value is reached by its index. · 每个值通过它的索引到达。
DECLARE Marks : ARRAY[0:99] OF INTEGER declares an array of ____ elements. · DECLARE Marks : ARRAY[0:99] OF INTEGER 声明了一个有 ____ 个元素的数组。
Upper bound minus lower bound plus one: 99 − 0 + 1 = 100. Both bounds are valid indices. · 上界减下界加一:99 − 0 + 1 = 100。两个边界都是有效索引。
Worked example: declaring the array a task needs
- A declaration needs the identifier, the bounds and the data type.
- 120 readings that may have a decimal place:
DECLARE Data : ARRAY[1:120] OF REAL - A table of 150 rows and two columns of text:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - Say the count if asked:
[0:99]holds 100 elements, not 99.
例题:声明任务需要的数组
- 一个声明需要标识符、边界和数据类型。
- 120 个可能带小数的读数:
DECLARE Data : ARRAY[1:120] OF REAL - 150 行两列的文本表:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - 被问到时说出个数:
[0:99]保存 100 个元素,不是 99 个。
Which declaration holds a table of 150 rows and 2 columns of text? · 哪个声明保存一张 150 行 2 列的文本表?
Two dimensions, each with a lower and upper bound, and the element type. The second option is one long list; the third has no type; the fourth has no lower bounds. · 两个维度,各有下界和上界,再加元素类型。第二项是一个长列表;第三项没有类型;第四项没有下界。
Processing a 1-D array
- A
FORloop 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.
处理一维数组
DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
FOR i ← 1 TO 5
OUTPUT Names[i]
NEXT i
- 从下界到上界的
FOR循环把每个元素访问一次。 - 求和、计数、最大值或最小值:在循环前设一个累计变量,在循环内更新它。
2-D arrays
- 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
二维数组
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // 第 2 行,第 3 列
- 第一个索引是行,第二个是列。嵌套循环(nested loops)访问每个单元:外层循环遍历行,内层遍历列。
- 单一序列用一维;数据有两个天然维度时用二维,比如座位网格,或按学生和科目排列的成绩表。
Grid[行, 列],永远是这个顺序
Index a 2-D array by [row, column] · 用 [行, 列] 索引一个二维数组
A 2-D array is a grid. Grid[row, column] reaches exactly one cell — change the row and column to see which value you land on. · 一个二维数组是一个网格。Grid[行, 列] 恰好到达一个单元格——改变行和列,看你落在哪个值上。
In Grid[2, 3], which cell is accessed? · 在 Grid[2, 3] 中,访问哪个单元格?
The first index is the row, the second the column — so row 2, column 3. · 第一个索引是行,第二个是列——所以行 2,列 3。
Worked example: a linear search that can say "not found"
- A linear search 线性查找 checks each element in turn from the first until the target is found or the end is reached.
-1can never be a valid index, so it means "not found". Initialise it before the loop and test it after. A search that never says "not found" loses a mark.
例题:能说出"未找到"的线性查找
- 线性查找(linear search)从第一个元素起依次检查,直到找到目标或到达末尾。
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
-1永远不可能是有效索引,所以它表示"未找到"。在循环前初始化它,在循环后测试它。永远不说"未找到"的查找会丢一分。
A linear search finds a value by: · 一个线性搜索这样找到一个值:
A linear search examines elements one by one from the start until it finds the target (or reaches the end). · 一个线性搜索从开始一个接一个地检查元素,直到它找到目标(或到达末尾)。
Setting FoundAt to -1 before a linear search lets the program report "not found" after the loop. · 在线性查找前把 FoundAt 设为 -1,让程序能在循环后报告"未找到"。
-1 is never a valid index, so if it is unchanged after the loop the target was not in the array. · -1 永远不是有效索引,所以如果循环后它没有改变,目标就不在数组里。
Largest value, and where it is
- Start
Largestat 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.
最大值,以及它在哪里
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
Largest从第一个元素开始,绝不从 0 开始:数组可能全是负数。- 同样的结构可以计数或输出非空元素:把每个元素与未使用标记(
""或-1)比较,只计那些不同的。
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.
Each pass carries the largest remaining value to the end
冒泡排序
- 冒泡排序(bubble sort)对数组反复遍历,比较相邻的每一对并交换顺序错误的,直到某一遍没有交换。
- 每一遍之后,最大的未排序值已经冒到末尾,所以下一遍可以提前一个位置结束。
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
每一遍把剩余的最大值送到末尾
Put the steps of one bubble-sort pass, and its ending, in order. · 把冒泡排序一遍的步骤及其结束方式按顺序排列。
Reset the flag, sweep and swap, shrink the limit, stop when a whole pass made no swap. · 重置标志、遍历并交换、缩小上限,当整整一遍没有交换时停止。
Worked example: where the bubble-sort marks are
- The outer loop that repeats until a pass makes no swaps; the
Swappedflag reset toFALSEat the start of each pass and setTRUEinside theIF. - The three-line swap through a temporary variable. Two lines lose a value.
- The shrinking limit, one less each pass, because the largest value has already reached the end.
- In words, for a stepwise-refinement question: repeat until sorted; on each pass compare adjacent pairs; swap any pair out of order; after each pass the largest unsorted value is at the end.
例题:冒泡排序的分在哪里
- 重复到某一遍没有交换才结束的外层循环;
Swapped标志在每遍开始时重置为FALSE,在IF内设为TRUE。 - 通过临时变量的三行交换。两行会丢掉一个值。
- 递减的上限,每遍减一,因为最大值已经到了末尾。
- 用文字回答逐步求精题:重复直到有序;每遍比较相邻的对;交换顺序错误的对;每遍之后最大的未排序值在末尾。
Which features earn marks in an efficient bubble sort? Select all · 所有 that apply. · 高效冒泡排序中哪些特征能得分?选出所有适用的。
Flag, swap with a temporary, shrinking limit: those are the marks. Copying the array is not part of the algorithm. · 标志、带临时变量的交换、递减的上限:这些是得分点。复制数组不是算法的一部分。
Worked example: removing and inserting
- Remove an item: find its index with a linear search; move every later element one place towards the start so the gap closes; mark the last element as unused, or reduce the count.
- Insert into a sorted array: find the first index whose element is larger; move that element and every later one one place towards the end, starting from the last; store the new value in the gap.
- Move from the end when opening a gap and from the start when closing one, or you overwrite the value you are about to move.
例题:删除和插入
- 删除一项:用线性查找找到它的索引;把后面的每个元素向前移一位,填上空隙;把最后一个元素标为未使用,或减少计数。
- 插入到有序数组:找到第一个元素比它大的索引;把那个元素和后面的每个元素向后移一位,从最后一个开始;把新值存入空隙。
- 开空隙时从末尾开始移,填空隙时从开头开始移,否则你会覆盖掉马上要移的值。
An array holds many items of the SAME type reached by index, while a record groups fields of (possibly) DIFFERENT types reached by name. · 一个数组保存许多通过索引到达的相同类型的项,而一个记录把通过名字到达的(可能)不同类型的字段分组。
A 2-D array suits a grid (rows × columns); a record suits one thing described by several named fields. · 一个二维数组适合一个网格(行 × 列);一个记录适合由几个有名字的字段描述的一件事。
Marks that slip away
[0:99]holds 100 elements. Count both bounds.- An index is an
INTEGER; a declaration needs the type as well as the bounds. Grid[row, column]: row first. Swapping them reads the wrong cell in every nested loop.- A swap needs a temporary variable; a search needs a "not found" path; a bubble sort ends when a pass makes no swaps, not after a fixed number of passes.
容易丢掉的分
[0:99]保存 100 个元素。两端的边界都要算。- 索引是
INTEGER;声明既要类型也要边界。 Grid[行, 列]:先行。互换它们会在每个嵌套循环里读错单元。- 交换需要临时变量;查找需要"未找到"的路径;冒泡排序在某一遍没有交换时结束,而不是在固定遍数之后。
You've got it
- an array holds a fixed number of same-type elements under one identifier, reached by an index between the lower and upper bound; count = upper − lower + 1
- 1-D is a list, 2-D is a table
[row, column]walked by nested loops; declare with bounds and type - linear search:
FoundAt ← -1, loop, store the index, test after the loop; largest value: start atA[1], keep the position - bubble sort: passes of adjacent compare-and-swap with a temporary, a
Swappedflag, a shrinking limit, until a pass makes no swaps
你掌握了
- 数组在一个标识符下保存固定数量同一类型的元素,通过下界和上界之间的索引访问;个数 = 上界 − 下界 + 1
- 一维是列表,二维是表格
[行, 列],用嵌套循环遍历;声明要有边界和类型 - 线性查找:
FoundAt ← -1,循环,存下索引,循环后测试;最大值:从A[1]开始,记住位置 - 冒泡排序:相邻比较并用临时变量交换的多遍、一个
Swapped标志、递减的上限,直到某一遍没有交换