📚 IGCSE WJEC Computer Science: Data Structures Key Points | IGCSE WJEC 计算机：数据结构 考点精讲
A solid understanding of data structures is essential for success in the IGCSE WJEC Computer Science exam. Data structures define how data is organised, stored, and manipulated within a program. This article covers the key data structures you need to know: arrays, records, stacks, queues, linked lists, and file organisations, along with practical guidance on choosing the right one for a given scenario.
扎实掌握数据结构对于 IGCSE WJEC 计算机科学考试至关重要。数据结构定义了数据在程序中的组织、存储和操作方式。本文涵盖你需要了解的关键数据结构：数组、记录、栈、队列、链表以及文件组织，并针对不同场景给出选择合适数据结构的实用指导。
1. Introduction to Data Structures | 数据结构简介
A data structure is a particular way of organising related data items so that they can be used efficiently. In programming, choosing the right data structure can make algorithms simpler and faster. At IGCSE level, you will encounter elementary structures such as arrays, records, stacks, queues, and linked lists. You must also understand how files are organised on secondary storage, including sequential, indexed-sequential, and random (direct) access methods. Being able to select and justify an appropriate data structure is a key skill tested in both the theory paper and the practical tasks.
数据结构是一种组织相关数据项以便高效使用的方式。在编程中，选择正确的数据结构可以使算法更简单、更快速。在 IGCSE 级别，你会遇到数组、记录、栈、队列和链表等基本结构。你还需要了解文件在辅助存储器上的组织方式，包括顺序、索引顺序和随机（直接）存取方法。能够选择并证明合适的数据结构是理论考试和实践任务中考查的关键技能。
2. Arrays: One-Dimensional | 数组：一维数组
An array is a collection of elements of the same data type stored under a single identifier. Each element is accessed using an index, typically starting from 0. A one-dimensional array (1D array) can be visualised as a list. For example, the declaration DECLARE scores : ARRAY[0:4] OF INTEGER reserves space for five integers. You can assign values like scores[0] ← 85 and retrieve them using the same notation. Arrays are static, meaning the size is fixed at declaration and cannot change during execution. Common operations include traversal, searching, and finding the maximum or minimum value.
数组是相同数据类型的元素集合，存储在一个标识符下。每个元素通过索引访问，索引通常从 0 开始。一维数组可以看作一个列表。例如，声明 DECLARE scores : ARRAY[0:4] OF INTEGER 为五个整数预留空间。可以使用 scores[0] ← 85 赋值，并用相同符号读取数值。数组是静态的，即大小在声明时确定，执行过程中不能改变。常见操作包括遍历、查找以及寻找最大值或最小值。
3. Arrays: Two-Dimensional | 数组：二维数组
A two-dimensional (2D) array extends the concept into a table with rows and columns. It is declared like ARRAY[1:3, 1:4] OF REAL, representing 3 rows and 4 columns. Each element is accessed with two indices, e.g., grid[2, 3]. 2D arrays are useful for representing grids, matrices, or game boards. You must be able to write algorithms that iterate over 2D arrays using nested loops: an outer loop for rows and an inner loop for columns. Typical exam questions ask you to sum all elements, find a specific value, or swap rows.
二维数组将概念扩展到带有行和列的表格。声明如 ARRAY[1:3, 1:4] OF REAL，表示 3 行 4 列。每个元素使用两个索引访问，例如 grid[2, 3]。二维数组适用于表示网格、矩阵或游戏棋盘。你必须能够编写使用嵌套循环遍历二维数组的算法：外层循环控制行，内层循环控制列。典型的考题要求你对所有元素求和、查找特定值或交换行。
4. Records | 记录
A record is a data structure that can hold items of different data types under one name. Each item is called a field. For example, a student record may contain fields for name (STRING), date of birth (DATE), and average mark (REAL). In pseudocode, you define a record type first: TYPE Student = RECORD name: STRING, dob: DATE, avgMark: REAL ENDRECORD. Then declare a variable DECLARE pupil : Student and access fields using dot notation, e.g., pupil.name ← “Alice”. Records are ideal when you need to group logically related but differently typed data, such as entries in a database. Unlike arrays, records are not designed for iteration over fields.
记录是一种能够在一个名称下存放不同数据类型的数据结构。其中的每一项称为字段。例如，一个学生记录可能包含姓名（字符串）、出生日期（日期）和平均分（实数）字段。在伪代码中，你需要先定义记录类型：TYPE Student = RECORD name: STRING, dob: DATE, avgMark: REAL ENDRECORD。然后声明变量 DECLARE pupil : Student，并使用点号访问字段，如 pupil.name ← “Alice”。记录在需要将逻辑相关但类型不同的数据分组时非常理想，例如数据库中的条目。与数组不同，记录不适用于对字段进行迭代。
5. Stacks (LIFO) | 栈（后进先出）
A stack is a dynamic data structure that follows the Last In First Out (LIFO) principle. Imagine a stack of plates: you can only add or remove from the top. The primary operations are push (add an item) and pop (remove and return the top item). Stacks are used for backtracking (e.g., undo in a text editor), managing function calls (call stack), and evaluating expressions. When a stack is full and a push is attempted, a stack overflow error occurs; attempting to pop from an empty stack causes a stack underflow. A stack can be implemented using an array and a stack pointer (top index). You should be able to trace stack operations step by step and draw the state after each push or pop.
栈是一种遵循后进先出（LIFO）原则的动态数据结构。想象一摞盘子：你只能从顶部添加或移除。主要操作是 push（压入，添加一个项目）和 pop（弹出，移除并返回顶部项目）。栈用于回溯（如文本编辑器中的撤销）、管理函数调用（调用栈）以及表达式求值。当栈满时尝试压入会导致栈溢出错误；尝试从空栈弹出会导致栈下溢。栈可以用数组和栈指针（顶部索引）来实现。你应该能够逐步追踪栈操作，并在每次 push 或 pop 后绘制其状态。
6. Queues (FIFO) | 队列（先进先出）
A queue is a dynamic data structure based on the First In First Out (FIFO) principle, like a line of people waiting to pay. Items are added at the rear (enqueue) and removed from the front (dequeue). Queues are used in print spooling, keyboard buffers, and any system where order must be preserved. A circular queue overcomes the limitation of a simple linear queue by reusing vacant spaces when the rear reaches the end of the array. It uses two pointers – front and rear – and wraps around. You should be able to implement a queue using an array and handle full/empty conditions. In exams, you may be asked to simulate enqueue and dequeue operations or to write algorithms checking if the queue is full or empty.
队列是一种基于先进先出（FIFO）原则的动态数据结构，就像排队等候付款的人群。项目在队尾添加（入队），在队首移除（出队）。队列用于打印后台处理、键盘缓冲区以及任何需要保持顺序的系统。循环队列通过当队尾到达数组末尾时重用空闲空间，克服了简单线性队列的限制。它使用两个指针——队首和队尾——并实现回绕。你应该能够使用数组实现队列并处理满/空状态。考试中可能要求你模拟入队和出队操作，或编写检查队列是否已满或为空的算法。
7. Linked Lists | 链表
A linked list is a dynamic data structure consisting of nodes. Each node contains data and a pointer (link) to the next node. Unlike arrays, linked lists do not require contiguous memory and can grow or shrink during execution. The start of the list is held by a head pointer. To traverse the list, follow the pointers from one node to the next. Inserting or deleting a node only requires updating pointers, making these operations efficient. However, searching requires sequential access because direct indexing is not possible. You should understand singly linked lists and be able to draw diagrams showing nodes, data fields, and pointers (often drawn as arrows). The end of the list is marked by a null pointer (often represented as Ø or –1).
链表是一种由节点组成的动态数据结构。每个节点包含数据和指向下一个节点的指针（链接）。与数组不同，链表不需要连续的内存空间，并且可以在执行时增长或收缩。链表的起始位置由头指针保存。要遍历链表，需要从一个节点跟随指针到下一个节点。插入或删除节点只需更新指针，因此这些操作效率很高。然而，查找需要顺序访问，因为不能直接通过索引访问。你应该理解单向链表，并能够绘制显示节点、数据域和指针（通常用箭头表示）的示意图。链表末尾用空指针标记（通常表示为 Ø 或 –1）。
8. Files: Sequential and Random Access | 文件：顺序与随机存取
File organisation determines how records are stored and accessed on secondary storage. In sequential files, records are stored one after another and can only be read in order. To find a specific record, you must read from the beginning until the desired record is found. This is efficient for batch processing but slow for individual look‑ups. Random (or direct) access files allow any record to be accessed directly using its position or a calculated address (hashing). Indexed‑sequential files combine both: records are stored sequentially, but an index file maps key values to disk addresses, enabling faster retrieval. You should know when each method is appropriate – for example, sequential for bank transactions processed nightly, indexed‑sequential for a library catalogue, and random for a real‑time airline booking system.
文件组织决定了记录在辅助存储器上存储和访问的方式。在顺序文件中，记录一个接一个存储，只能按顺序读取。要查找特定记录，必须从头开始读取直到找到所需的记录。这对批量处理很有效，但对个别查找速度较慢。随机（或直接）存取文件允许使用记录位置或计算出的地址（哈希）直接访问任何记录。索引顺序文件结合了两者：记录按顺序存储，但有一个索引文件将键值映射到磁盘地址，从而实现更快的检索。你应该知道每种方法适用的场景——例如，顺序文件适用于每晚处理的银行交易，索引顺序文件适用于图书馆目录，随机文件适用于实时航空订票系统。
9. String Handling | 字符串处理
Strings are simply sequences of characters. Although often implemented as arrays of characters, they are treated as a distinct data structure in most programming languages. You need to be familiar with common string operations: length (number of characters), substring extraction, concatenation (joining two strings), case conversion, and character‑by‑character traversal. WJEC questions may ask you to write algorithms that count vowels, check for palindromes, or find a pattern within a string. Understanding ASCII and character codes is important because string comparisons are based on these numeric codes. Always remember that indexing a string starts at position 0 for the first character.
字符串简单来说就是字符序列。尽管通常以字符数组的形式实现，但在大多数编程语言中被视为独立的数据结构。你需要熟悉常见的字符串操作：长度（字符数）、子串提取、拼接（连接两个字符串）、大小写转换以及逐字符遍历。WJEC 考题可能要求你编写计算元音数量、检查回文或在字符串中查找模式的算法。理解 ASCII 和字符编码很重要，因为字符串比较是基于这些数字代码的。务必记住，字符串的索引从位置 0 开始表示第一个字符。
10. Choosing Appropriate Data Structures | 选择合适的数据结构
Selecting the right data structure for a problem is a crucial skill. You need to consider the type of data, the operations required, and memory/time constraints. Use a 1D array when you have a fixed‑size collection of identical items and need fast indexing. Use a 2D array for grid‑based data. Use records to group mixed‑type fields into a single entity. Choose a stack when a last‑in‑first‑out order is natural (e.g., reversing a word). Choose a queue for first‑in‑first‑out processing (e.g., a printer spooler). Linked lists are preferable when the number of items is unknown and insertions/deletions are frequent. In the exam, justify your choice clearly: mention the properties of the structure that make it suitable and contrast it with alternatives whose drawbacks would hinder the solution.
为问题选择合适的数据结构是一项关键技能。你需要考虑数据类型、所需的操作以及内存/时间限制。当有一组固定大小且类型相同的项目并需要快速索引时，使用一维数组。对于基于网格的数据，使用二维数组。记录用于将混合类型的字段组合成一个实体。当后进先出的顺序自然合适时选择栈（例如反转一个单词）。对于先进先出处理（如打印机后台处理），选择队列。当项目数量未知且插入/删除频繁时，链表更可取。在考试中，要清晰地说明你的选择：提及该结构的特性如何使其适合，并与替代方案进行对比，指出后者的缺陷会妨碍解决问题。
Published by TutorHao | Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导