| English | 释义 | 拼音 |
|---|---|---|
| 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ù |
14 排 C 座
- 一家电影院有 300 个座位。它的订票系统没有 300 个叫
Seat1A、Seat1B、Seat1C的变量。它有一个数组(array),你的票是数组里的一个地址:第 14 排,C 座。 - 一个名字,几百个值,每个都靠一个数字找到。加一排座位,代码不用改;循环遍历那些数字,你就检查了每个座位。
- Paper 2 上几乎每个算法都在遍历数组:查找、求和、排序、找最大值。
- 这一课讲术语、声明,以及考官要求用伪代码和文字写出的四个算法。
术语
- 数组是在一个标识符下保存固定数量同一数据类型的元素(element)的数据结构,每个元素通过一个索引(index)访问。
- 下界(lower bound)和上界(upper bound)是第一个和最后一个有效索引。元素个数是上界 − 下界 + 1。
- 维度(dimension)是一个元素需要几个索引:列表一个,表格两个。
- 在
ThisArray[n] ← 42中,数组是一维的,索引是INTEGER变量n,该索引处的元素接收42。

一个标识符,每个元素一个索引,两端各有边界
一个数组存储:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一个数组是相同类型的项的一个有序集合,通过索引访问。(一个记录把不同类型分组。)
一个数组是一个数据结构,在一个名字下保存许多______类型的值。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
每个值通过它的索引到达。
DECLARE Marks : ARRAY[0:99] OF INTEGER 声明了一个有 ____ 个元素的数组。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
上界减下界加一:99 − 0 + 1 = 100。两个边界都是有效索引。
例题:声明任务需要的数组
- 一个声明需要标识符、边界和数据类型。
- 120 个可能带小数的读数:
DECLARE Data : ARRAY[1:120] OF REAL - 150 行两列的文本表:
DECLARE Names : ARRAY[1:150, 1:2] OF STRING - 被问到时说出个数:
[0:99]保存 100 个元素,不是 99 个。
哪个声明保存一张 150 行 2 列的文本表?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
两个维度,各有下界和上界,再加元素类型。第二项是一个长列表;第三项没有类型;第四项没有下界。
处理 1-D 数组
DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
FOR i ← 1 TO 5
OUTPUT Names[i]
NEXT i
- 从下界到上界的
FOR循环把每个元素访问一次。 - 求和、计数、最大值或最小值:在循环前设一个累计变量,在循环内更新它。
2-D 数组
DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99 // row 2, column 3
- 第一个索引是行,第二个是列。嵌套循环(nested loops)访问每个单元:外层循环遍历行,内层遍历列。
- 使用 1-D 表示单个序列,当数据具有两个自然维度(如座位网格或按学生与科目排列的成绩表)时使用 2-D。

Grid[row, column] 在前,顺序不可颠倒
用 [行, 列] 索引一个二维数组
一个二维数组是一个网格。Grid[行, 列] 恰好到达一个单元格——改变行和列,看你落在哪个值上。
在 Grid[2, 3] 中,访问哪个单元格?
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
第一个索引是行,第二个是列——所以行 2,列 3。
例题:能说出"未找到"的线性查找
- 线性查找(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永远不可能是有效索引,所以它表示"未找到"。在循环前初始化它,在循环后测试它。永远不说"未找到"的查找会丢一分。
一个线性搜索这样找到一个值:
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一个线性搜索从开始一个接一个地检查元素,直到它找到目标(或到达末尾)。
在线性查找前把 FoundAt 设为 -1,让程序能在循环后报告"未找到"。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
-1 永远不是有效索引,所以如果循环后它没有改变,目标就不在数组里。
最大值,以及它在哪里
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)对数组反复遍历,比较相邻的每一对并交换顺序错误的,直到某一遍没有交换。
- 每一遍之后,最大的未排序值已经冒到末尾,所以下一遍可以提前一个位置结束。
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

每一遍把剩余的最大值送到末尾
把冒泡排序一遍的步骤及其结束方式按顺序排列。
难度 3/5 · 今日首次完成可获 200 金币及少量额外奖励
重置标志、遍历并交换、缩小上限,当整整一遍没有交换时停止。
例题:冒泡排序的分在哪里
- 外层循环持续运行直到某次遍历未发生任何交换为止;
Swapped标志在每个遍历开始时重置为FALSE,并在IF内部检测到交换时设为TRUE。 - 通过临时变量的三行交换。两行会丢掉一个值。
- 递减的上限,每遍减一,因为最大值已经到了末尾。
- 用文字回答逐步求精题:重复直到有序;每遍比较相邻的对;交换顺序错误的对;每遍之后最大的未排序值在末尾。
高效冒泡排序中哪些特征能得分?选出所有适用的。
难度 2/5 · 今日首次完成可获 140 金币及少量额外奖励
标志、带临时变量的交换、递减的上限:这些是得分点。复制数组不是算法的一部分。
例题:删除和插入
- 删除一项:用线性查找找到它的索引;把后面的每个元素向前移一位,填上空隙;把最后一个元素标为未使用,或减少计数。
- 插入到有序数组:找到第一个元素比它大的索引;把那个元素和后面的每个元素向后移一位,从最后一个开始;把新值存入空隙。
- 开空隙时从末尾开始移,填空隙时从开头开始移,否则你会覆盖掉马上要移的值。
一个数组保存许多通过索引到达的相同类型的项,而一个记录把通过名字到达的(可能)不同类型的字段分组。
难度 1/5 · 今日首次完成可获 100 金币及少量额外奖励
一个二维数组适合一个网格(行 × 列);一个记录适合由几个有名字的字段描述的一件事。
容易丢掉的分
[0:99]保存 100 个元素。两端的边界都要算。- 索引是
INTEGER;声明既要类型也要边界。 Grid[row, column]必须先行。若交换顺序,嵌套循环将读取错误的单元格。- 交换需要临时变量;查找需要"未找到"的路径;冒泡排序在某一遍没有交换时结束,而不是在固定遍数之后。
你掌握了
- 数组在一个标识符下保存固定数量同一类型的元素,通过下界和上界之间的索引访问;个数 = 上界 − 下界 + 1
- 1-D 是列表,2-D 是由嵌套循环遍历的表格
[row, column];声明时需指定边界和类型 - 线性查找:
FoundAt ← -1,循环,存下索引,循环后测试;最大值:从A[1]开始,记住位置 - 冒泡排序:相邻比较并用临时变量交换的多遍、一个
Swapped标志、递减的上限,直到某一遍没有交换