CAIE AS and A Level CS revision - Unit 10 (2nd)
如遇到公式加载异常，请刷新页面！
Unit 10 Data Types and structures 数据类型和结构
10.1 Data Types and Records 数据类型和记录
- 大纲要求
10.1.1 Select and use appropriate data types for a problem solution 为问题解决方案选择和使用适当的数据类型
including integer, real, char, string, Boolean, date (pseudocode will use the following data types: INTEGER, REAL, CHAR, STRING, BOOLEAN, DATE, ARRAY, FILE) 包括整数、实数、字符、字符串、布尔值、日期（伪代码将使用以下数据类型：INTEGER、REAL、CHAR、STRING、BOOLEAN、DATE、ARRAY、FILE）
- 常见数据类型：
- Integer：整型，指整数的数据。
- Real：实数型，指实数的数据。
- Char：字符型，指单个字符数据。
- String：字符串型，指多个字符组成的字符序列，也可能是empty string空字符串。
- Boolean：布尔型，指TRUE或FALSE。
- Date：日期型，包括年月日，也可能包括时分秒。
10.1.2 Show understanding of the purpose of a record structure to hold a set of data of different data types under one identifier 理解记录结构的目的是在一个标识符下保存一组不同数据类型的数据
Write pseudocode to define a record structure. 编写伪代码定义记录结构。
Write pseudocode to read data from a record structure and save data to a record structure 编写伪代码从记录结构中读取数据并将数据保存到记录结构中
- Record：记录，指一种用户自定义的数据类型，能够在一个标识符下保存若干有着不同数据类型的数据。
- 定义record type：
TYPE 记录名
DECLARE 类别名 : 数据类型
DECLARE 类别名 : 数据类型
…
ENDTYPE
- 将变量声明为record这种数据类型：
DECLARE 变量名 : 记录名
- 为record数据类型的变量进行赋值：
变量名.类别名 ← 数值
- 输出record数据类型的变量的数值：
OUTPUT 变量名.类别名
10.2 Arrays 数组
- 大纲要求
10.2.1 Use the technical terms associated with arrays 使用与数组相关的技术术语
Including index, upper and lower bound 包括索引、上下界
- Array：数组，指一组有序的数据项。它们具有相同的数据结构，通过数组标识符和数组索引来引用其中的指定元素。
- Array index：数组索引，即数据在数组中的位置。通过索引可以定位到指定数据的存储位置，以便在程序中使用和存储该数据。
- Upper bound：上限，指array dimension数组维度中的最大值。
- Lower bound：下限，指array dimension数组维度中的最小值。
10.2.2 Select a suitable data structure (1D or 2D array) to use for a given task 为给定任务选择合适的数据结构（一维或二维数组）
- One-dimensional array（1D）：一维数组，指以列表形式出现的、只有一个数组索引数字的数组。
- Two-dimensional array（2D）：二维数组，指以表格或矩阵形式出现的、有两个数组索引数字的数组。
10.2.3 Write pseudocode for 1D and 2D arrays 为一维和二维数组编写伪代码
- 关于一维数组（1D）的各种操作代码：
- 定义一维数组：
DECLARE 数组名 : ARRAY[下限:上限] OF 数据类型
- 为一维数组赋值：
数组名[数组索引] ← 值
- 引用一维数组的值：
变量 = 数组名[数组索引]
- 输入值并存入一维数组：
FOR 变量 ← 值 TO 值
INPUT 数组名[变量]
NEXT 变量
- 输出一维数组的所有值：
FOR 变量 ← 值 TO 值
OUTPUT 数组名[变量]
NEXT 变量
- 线性搜索一维数组：【参考10.2.4】。
- 一维数组的冒泡排序：【参考10.2.4】。
- 数据类型为record记录的数组：
- 定义数据类型为record记录的一维数组：
DECLARE 数组名 : ARRAY[下限:上限] OF 记录名
- 为数据类型为record记录的数组赋值：
数组名[数组索引].类别名 ← 值
- 关于二维数组（2D）的各种操作代码：
- 定义二维数组：
DECLARE 数组名 : ARRAY[下限1:上限1, 下限2:上限2] OF 数据类型
- 为二维数组赋值：
数组名[数组索引1, 数据索引2] ← 值
- 引用二维数组的值：
变量 = 数组名[数组索引1, 数据索引2]
- 输入值并存入二维数组：
FOR 行变量 ← 值 TO 值
FOR 列变量 ← 值 TO 值
INPUT 数组名[行变量, 列变量]
NEXT 列变量
NEXT 行变量
- 输出二维数组的所有值：
FOR 行变量 ← 值 TO 值
FOR 列变量 ← 值 TO 值
OUTPUT 数组名[行变量, 列变量]
NEXT 列变量
NEXT 行变量
10.2.4 Write pseudocode to process array data 编写伪代码处理数组数据
Sort using a bubble sort 使用冒泡排序
Search using a linear search 使用线性搜索进行搜索
- 线性搜索一维数组：
MaxIndex ← 最大值
INPUT SearchValue //输入需要搜索的数值
Found ← FALSE //用于标记是否找到。初始值设定为FALSE
Index ← –1 //数组索引值。根据下面使用的REPEAT循环需求，设定初始值为-1
REPEAT
Index ← Index + 1
IF MyList[Index] = SearchValue
THEN
Found ← TRUE //如果找到了（条件成立），则将标记改为TRUE
ENDIF
UNTIL FOUND = TRUE OR Index >= MaxIndex //如果发现标记为TRUE或已经完成数组列表遍历，则结束循环
IF Found = TRUE //如果找到位置则输入位置，如果没找到则输出未发现
THEN
OUTPUT "Value found at location: " Index
ELSE
OUTPUT "Value not found"
ENDIF
- 一维数组的冒泡排序：
（最常规易懂的代码）
n ← MaxIndex – 1
FOR i ← 0 TO MaxIndex – 1 //外循环，控制交换轮次，完成全部排序需要交换maxindex-1轮
FOR j ← 0 TO n //内循环，作为数组索引使用
IF MyList[j] > MyList[j + 1] //如果前面的数值大于后面的数值，则进行交换
THEN
Temp ← MyList[j] //交换数值时，需要引入临时存储用变量
MyList[j] ← MyList[j + 1]
MyList[j + 1] ← Temp
ENDIF
NEXT j
n ← n – 1 //因为本轮次结束后会把本轮检查范围内最大的数值排到最后，因此后面的部分已经按顺序排好，无需再进行检查，只需检查前n-1项即可
NEXT i
（优化后的代码）
n ← MaxIndex – 1
REPEAT
NoMoreSwaps ← TRUE //引入标记来表示数组内是否发生了数值的交换。初始值为TRUE，如果发生了交换则改为FALSE
FOR j ← 0 TO n //内循环，作为数组索引使用
IF MyList[j] > MyList[j + 1]
THEN
Temp ← MyList[j]
MyList[j] ← MyList[j + 1]
MyList[j + 1] ← Temp
NoMoreSwaps ← FALSE //因为数组内发生了数值的交换，将标记改为FALSE
ENDIF
NEXT j
n ← n – 1 //因为本轮次结束后会把本轮检查范围内最大的数值排到最后，因此后面的部分已经按顺序排好，无需再进行检查，只需检查前n-1项即可
UNTIL NoMoreSwaps = TRUE //如果标记为TRUE，说明数组在本轮次的检查后，前面的数值没有发生交换。这意味着前面的数值已经按照顺序排好了，而后面的数值也已经调整完毕，所以此时排序实际上已经完成，无需再进行后续循环。条件得到满足，从而跳出循环。
10.3 Files 文件
- 大纲要求
10.3.1 Show understanding of why files are needed 了解为什么需要文件
- File：文件，是独立于程序的数据存储形式。
- 当程序结束时，存放在数组等集合中的数据将自动清除。如果需要永久存储相关数据，需要使用file文件类型。
10.3.2 Write pseudocode to handle text files that consist of one or more lines 编写伪代码来处理包含一行或多行的文本文件
- 从文件中读取数据：
OPENFILE 文件名 FOR READ //以读取形式打开文件
READFILE 文件名, 变量 //读取值并赋值给变量
CLOSEFILE 文件名 //关闭文件
- 将数据写入文件：
OPENFILE 文件名 FOR WRITE //以写入形式打开文件
WRITEFILE 文件名, 变量（或值） //将变量或值输出到文件
CLOSEFILE 文件名 //关闭文件
- 将数据添加到现有文件：
OPENFILE 文件名 FOR APPEND //以扩展形式打开文件
WRITEFILE 文件名, 变量（或值） //将变量或值输出到文件
CLOSEFILE 文件名 //关闭文件
- 以循环形式读取文件中的数据：
OPENFILE 文件名 FOR READ //文件名可以用“文件名或路径”的形式
WHILE NOT EOF(文件名) DO //引入EOF()函数，用于判断文件是否到结尾。到尾部则函数返回TRUE，未到尾部则函数返回FALSE
READFILE 文件名, 变量
ENDWHILE
CLOSEFILE 文件名
10.4 Introduction to Abstract Data Types (ADT) 抽象数据类型（ADT）简介
- 大纲要求
10.4.1 Show understanding that an ADT is a collection of data and a set of operations on those data 理解 ADT 是数据的集合和对这些数据的一组操作
- Abstract Data Types (ADT)：抽象数据类型，指数据的集合和对这些数据一系列的操作，如创建数据结构中的新实例，在数据结构中查找、插入、删除数据等。
- 常见的ADT包括：stack栈、queue队列和linked list链表。
10.4.2 Show understanding that a stack, queue and linked list are examples of ADTs 理解堆栈、队列和链表是 ADT 的示例
Describe the key features of a stack, queue and linked list and justify their use for a given situation 描述堆栈、队列和链表的关键特性，并证明它们在特定情况下的用途
- stack：栈，指先进后出的数组。Base pointer基数指针始终指向栈的底部，而top pointer栈指针则在加入和移出数据时发生变化。如下图所示：
- queue：队列，指先进先出的数组。Front pointer头指针在移出数据时会下移，end pointer尾指针在加入数据时会下移。如下图所示：
- 因为头指针在移出数据时下移，这会浪费数组中的很多存储空间，因此可以考虑circular queue循环队列，即可以使用头指针前方的空白单元存储新加入队列的数据，使其首尾相接。如下图所示：
- 注意：头指针之前的A、B、C、D、E这五个数据已经移出队列，当加入到H数据时，数组已经填满。再加入I、J、K数据时，无需扩展数组，只需要使用前方已经闲置的存储单元，将尾指针指向这些单元，把数据存放进去即可。
- linked list：链表，指一系列通过pointer指针联系起来的数据集合，每个数据可以存储在任何位置，而不需要像栈或队列一样存储在连续的位置。
- node：节点，指链表中的每个元素，包括值和pointer指针两部分。值是存储的数据，指针是存储的地址。
- null pointer：空指针，即不指向任何位置的指针，写作“∅”。
- start pointer：起始指针，即首个元素中保存的指针。
- 链表的存储形式：每个节点中的指针保存的是下一个节点的位置，链表通过指针将每个节点联系在一起，无需连续存储。链表以起始指针开始，以空指针结束，如下图所示：
- 链表在最开始插入一个节点：将新节点A的指针指向原来的第一个节点B，将起始指针的指针指向A。如下图所示：
- 链表在最后插入一个节点：将原来的尾指针指向新节点P，将节点P的指针赋为空指针。如下图所示：
- 链表中删除第一个数据：将起始指针的指针指向删除节点B原本指向的节点D。（绕过节点B）如下图所示：
- 链表中删除最后一个数据：将倒数第二个节点D的指针赋为空指针。（断开和L的联系）如下图所示：
- 链表中间插入一个数据：将新节点C的指针指向后方节点D，将前方节点B的指针指向新节点C。如下图所示：
- 链表中间删除一个数据：将前方节点B的指针指向删除节点D原本指向的节点L。（绕过节点D）如下图所示：
- 链表与数组的比较：
- 链表进行排序等操作时只需要更改节点的指针指向即可，简洁且快速。而数组则需要挪动数据项，耗时较长。
- 链表需要为指针额外提供存储空间，而数组不需要。
10.4.3 Use a stack, queue and linked list to store data 使用栈、队列和链表存储数据
Candidates will not be required to write pseudocode for these structures, but they should be able to add, edit and delete data from these structures 考生不需要为这些结构编写伪代码，但他们应该能够从这些结构中添加、编辑和删除数据
- 【参考10.4.2】。
10.4.4 Describe how a queue, stack and linked list can be implemented using arrays 描述如何使用数组实现队列、栈和链表
- 队列和栈的数组表示【参考10.4.2】。
- 链表的数组表示：使用两个数组来分别存储节点当中的数值与指针。
- 链表的存储形式：如下图所示，图中链表为B-D-L。
- 起始指针指向Data[1]，即下一个节点为Data[1]，对应数值B。
- B所在节点的指针指向Data[2]，即连接到Data[2]，对应数值D。以此类推。
- 最后一个节点的指针设置为-1，表示空指针（无对应）。
- 链表的存储形式：如下图所示，图中链表为B-D-L。
- 链表在最开始插入一个节点：插入节点A，如下图所示。插入后的链表为A-B-D-L。
- 在数组中新加入一个节点，存入Data[3]，值为A，指针指向起始指针原来指向的位置Data[1]。
- 将起始指针改为指向Data[3]。
- 链表在最开始插入一个节点：插入节点A，如下图所示。插入后的链表为A-B-D-L。
- 链表在最后插入一个节点：插入节点P，如下图所示。插入后的链表为B-D-L-P。
- 在数组中新加入一个节点，存入Data[3]，值为P，指针为-1（空指针）。
- 将原来最后一个节点Data[0]的指针指向新节点Data[3]。
- 链表在最后插入一个节点：插入节点P，如下图所示。插入后的链表为B-D-L-P。
- 链表中删除第一个数据：删除节点B，如下图所示，删除后的链表为D-L。
- 将起始指针指向原来的第二个节点Data[2]。（即绕过第一个节点）
- 链表中删除第一个数据：删除节点B，如下图所示，删除后的链表为D-L。
- 链表中删除最后一个数据：删除节点L，如下图所示。删除后的链表为B-D。
- 将倒数第二个节点的指针改为-1（空指针）。（即绕过最后一个节点）
- 链表中删除最后一个数据：删除节点L，如下图所示。删除后的链表为B-D。
- 链表中间插入一个数据：插入节点C，如下图所示。插入后的链表为B-C-D-L。
- 在数组中新加入一个节点，存入Data[3]，值为C，指针指向前一节点原来指向的位置Data[2]。（即指针指向其后一节点）
- 将前一节点的指针指向新节点Data[3]。
- 链表中间插入一个数据：插入节点C，如下图所示。插入后的链表为B-C-D-L。
- 链表中间删除一个数据：删除节点D，如下图所示。删除后的链表为B-L。
- 将删除节点的前一节点指针指向删除节点的后一节点Data[0]。（即绕过删除节点）
- 链表中间删除一个数据：删除节点D，如下图所示。删除后的链表为B-L。
- Free list：自由链表。在链表结构中，空余的节点可以串在一起，以备今后使用。这些空余的节点串成的链表被称为free list。
- 初始化的free list：如下图所示。所有数值均为空，指针按照顺序排列（最后为空指针）。起始指针指向空指针（-1），自由链表指针FreeListPtr指向第一个数组位置（0）。
- 读入数据后的free list：如下图所示。自由链表指针FreeListPtr不断下移，指向目前还空着的首个节点Data[3]。
- 节点增减后的free list：如下图所示。
- 当节点Data[2]被删除后，其前一个节点Data[1]的指针指向其后一个节点Data[0]。
- 被删除的节点Data[2]的指针指向自由链表指针FreeListPtr原本指向的节点Data[3]。
- 自由链表指针FreeListPtr指向被删除的节点Data[2]。
- 节点增减后的free list：如下图所示。
