📚 Data Structures for IGCSE CIE Computer Science | IGCSE CIE 计算机：数据结构 考点精讲
Data structures are the fundamental building blocks that allow programs to organise, store, and manage data efficiently. In the IGCSE CIE Computer Science syllabus (0984/0478), you need to understand how arrays, records, files, stacks, and queues work – and, more importantly, be able to choose the right structure for a given problem. This revision guide walks you through every key concept with clear explanations and practical examples.
数据结构是让程序能够高效地组织、存储和管理数据的基础构件。在IGCSE CIE计算机科学大纲（0984/0478）中，你需要理解数组、记录、文件、栈和队列的工作原理，更重要的是，能够根据具体问题选择合适的结构。这份精讲将通过清晰的解释和实用示例带你逐一攻克每个关键概念。
1. What are Data Structures? | 什么是数据结构？
A data structure is a specialised format for organising, processing, retrieving and storing data. Choosing the right data structure can make a program faster and more memory-efficient. The IGCSE syllabus focuses on static structures (arrays), composite structures (records), persistent storage using files, and two dynamic structures – stacks and queues.
数据结构是一种用于组织、处理、检索和存储数据的专用格式。选择合适的数据结构可以使程序运行更快、内存利用更高效。IGCSE大纲主要关注静态结构（数组）、复合结构（记录）、使用文件的持久化存储，以及两种动态结构——栈和队列。
- Key terms: element, field, index, key, static vs dynamic.
- 关键术语：元素、字段、索引、键、静态与动态。
2. Arrays – Fixed-Size Collections | 数组 – 固定大小集合
An array is a collection of elements of the same data type, stored in contiguous memory locations. Each element can be accessed directly using an index, which normally starts from 0 or 1. The size of an array is fixed when it is declared, so it is a static data structure.
数组是相同数据类型的元素的集合，存储在连续的内存位置中。每个元素可以通过索引直接访问，索引通常从0或1开始。数组的大小在声明时就固定了，因此它是一种静态数据结构。
- Declaration example:
DECLARE scores : ARRAY[0:9] OF INTEGER(10 elements, indices 0–9). - 声明示例：
DECLARE scores : ARRAY[0:9] OF INTEGER（10个元素，索引0至9）。 - Elements are accessed as
scores[3] ← 85; the time to access any element is constant – O(1). - 访问元素如
scores[3] ← 85；访问任意元素的时间是常数级——O(1)。 - Arrays can be one-dimensional (list), two-dimensional (table), or multi-dimensional.
- 数组可以是一维（列表）、二维（表格）或多维。
Example: Exam marks stored in a 1D array
示例：存储在1D数组中的考试成绩
| Index 索引 | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Mark 分数 | 78 | 65 | 92 | 56 | 88 |
Advantages: fast access, simple to implement. Disadvantages: fixed size, inserting/deleting items in the middle is inefficient because elements must be shifted.
优点：访问快速，实现简单。缺点：大小固定，在中间插入或删除元素效率低，因为需要移动其他元素。
3. Records – Grouping Related Data | 记录 – 组合相关数据
A record is a composite data structure that groups together variables of different data types under one name. Each variable is called a field. Records are used to represent entities like a student, a product, or a car – where each entity has several attributes.
记录是一种复合数据结构，它将不同数据类型的变量组合在一起，统一命名。每个变量称为一个字段。记录用于表示诸如学生、产品或汽车等实体，每个实体具有多个属性。
- Example declaration:
TYPE StudentRecordwith fieldsname: STRING,grade: CHAR,age: INTEGER. - 示例声明：
TYPE StudentRecord包含字段name: STRING、grade: CHAR、age: INTEGER。 - Access:
Student1.name ← "Alice"– using dot notation. - 访问：
Student1.name ← "Alice"——使用点号表示法。
Records can be stored in arrays to create a table of data, e.g. an array of StudentRecord to store a class register. They are fundamental in file handling, where each record represents a row in a sequential or random-access file.
记录可以存储在数组中，形成数据表，例如一个 StudentRecord 数组用来存储班级名册。记录是文件处理的基础，在顺序或随机存取文件中，每条记录代表文件中的一行。
4. Sequential Files – One After Another | 顺序文件 – 前后存取
A sequential file stores records one after the other in the order they are added. To read the 100th record, the program must read through the first 99 records – there is no way to jump directly to a specific record. Sequential files are simple to implement and efficient when the entire file needs to be processed.
顺序文件按照记录添加的顺序逐个存储。要读取第100条记录，程序必须先读前99条记录——无法直接跳转到特定记录。顺序文件实现简单，当需要处理整个文件时效率很高。
- Typical operations: open, read next, write to end, close. No insert in the middle without rewriting the file.
- 典型操作：打开、读取下一条、写入末尾、关闭。无法在中间插入而不重写整个文件。
- Used for: log files, transaction history, text files, batch processing.
- 适用于：日志文件、交易历史记录、文本文件、批处理。
Searching a sequential file for a record with a specific key requires a linear search, which takes on average n/2 comparisons. Updates often require creating a new file and copying records.
在顺序文件中搜索具有特定键的记录需要线性搜索，平均需要 n/2 次比较。更新通常需要创建新文件并复制记录。
5. Random Access Files – Direct Access to Data | 随机存取文件 – 直接存取数据
A random-access file (or direct-access file) allows individual records to be read or written in any order without processing the entire file. Each record is stored at a known position, calculated from a key using a hashing algorithm or an index. This gives constant-time access – O(1).
随机存取文件（或直接存取文件）允许以任意顺序读取或写入单个记录，而无需处理整个文件。每条记录存储在已知位置，该位置通过键和哈希算法或索引计算得出。这实现了常数时间的访问——O(1)。
- Uses a hashing algorithm, e.g.
address = key MOD file_sizeto determine the record's location. - 使用哈希算法，例如
address = key MOD file_size来确定记录的位置。 - Collision handling is required when two keys produce the same address (e.g. using overflow areas).
- 当两个键产生相同地址时，需要进行碰撞处理（例如使用溢出区）。
Random-access files are essential for real-time systems like airline booking, banking, and databases where fast retrieval of a single record is required. The main disadvantage is that storage may be wasted if the file is sparsely populated.
随机存取文件对于实时系统（如机票预订、银行和数据库）至关重要，这些系统需要快速检索单条记录。主要缺点是，如果文件填充稀疏，可能会浪费存储空间。
6. Stacks – Last In, First Out (LIFO) | 栈 – 后进先出 (LIFO)
A stack is a dynamic data structure that works on the Last In, First Out principle. You can imagine a stack like a pile of plates – the last plate placed on top is the first one taken off. Stacks are used extensively in programming for managing subroutine calls, undo features, and expression evaluation.
栈是一种动态数据结构，遵循后进先出的原则。你可以把栈想象成一叠盘子——最后放上去的盘子最先被取走。栈在编程中广泛用于管理子程序调用、撤销功能和表达式求值。
- Two main operations: push (add an item to the top) and pop (remove and return the top item).
- 两个主要操作：push（将一个项添加到栈顶）和pop（移除并返回栈顶项）。
- Both operations are O(1) when implemented with an array or linked list.
- 使用数组或链表实现时，这两个操作的时间复杂度都是 O(1)。
- Stacks can be implemented using a 1D array and a pointer (e.g.
stackPointer). - 栈可以用一维数组和指针（例如
stackPointer）来实现。
Stack trace example for a subroutine call:
子程序调用的栈跟踪示例：
- Main program calls Sub_A → push return address onto stack.
- 主程序调用 Sub_A → 将返回地址压入栈。
- Sub_A calls Sub_B → push another return address.
- Sub_A 调用 Sub_B → 再压入一个返回地址。
- Sub_B finishes → pop address and return to Sub_A.
- Sub_B 结束 → 弹出地址，返回 Sub_A。
7. Queues – First In, First Out (FIFO) | 队列 – 先进先出 (FIFO)
A queue is a dynamic data structure operating on the First In, First Out principle – just like a line of people waiting for a bus. Items join at the rear (enqueue) and leave from the front (dequeue). Queues are used in print spooling, keyboard buffers, and breadth-first search algorithms.
队列是一种动态数据结构，遵循先进先出的原则——就像人们排队等公交车。项从队尾加入（入队），从队头离开（出队）。队列用于打印假脱机、键盘缓冲区和广度优先搜索算法。
- Operations: enqueue(item) – adds to rear; dequeue() – removes from front.
- 操作：enqueue(item) – 加入队尾；dequeue() – 从队头移除。
- Both are O(1) when implemented efficiently with a circular array.
- 使用循环数组高效实现时，两个操作均为 O(1)。
- A linear array implementation can suffer from 'drifting' where the front moves forward, wasting space; a circular queue overcomes this.
- 线性数组实现可能会出现“漂移”问题，队头前移导致空间浪费；循环队列解决了这个问题。
Circular queue pointers: front points to the first item, rear points to the last item. When incrementing, use (current + 1) MOD size to wrap around.
循环队列指针：front 指向第一个项，rear 指向最后一个项。递增时使用 (current + 1) MOD size 实现回绕。
8. Choosing the Right Data Structure | 选择合适的数据结构
For the exam, you must be able to justify the choice of one data structure over another based on the requirements of the problem. Consider: access pattern (random vs sequential), frequency of insertions/deletions, memory constraints, and whether the size is known in advance.
在考试中，你必须能够根据问题的需求，论证为何选择一种数据结构而非另一种。需要考虑的因素包括：访问模式（随机还是顺序）、插入/删除的频率、内存限制以及大小是否预先已知。
| Scenario 场景 | Recommended Structure 推荐结构 | Reason 原因 |
|---|---|---|
| Storing high scores in a game that always shows top 10 | Array | Fixed size, fast direct access, simple to sort. |
| 存储游戏中始终显示前10名的最高分 | 数组 | 固定大小，快速直接访问，易于排序。 |
| Customer database requiring instant look-up by ID | Random-access file | Direct access via hashing – O(1) retrieval. |
| 需要按ID即时查询的客户数据库 | 随机存取文件 | 通过哈希直接访问——O(1)检索。 |
| Managing function calls in a compiler | Stack | LIFO perfectly matches call-return sequence. |
| 在编译器中管理函数调用 | 栈 | LIFO 完美匹配调用-返回顺序。 |
| Printer spooler processing jobs in order received | Queue | FIFO ensures fairness and correct order. |
| 打印机假脱机按接收顺序处理作业 | 队列 | FIFO 保证公平性和正确顺序。 |
| Processing a large transaction log overnight | Sequential file | Entire file is read from start to end; no need for random access. |
| 夜间处理大型事务日志 | 顺序文件 | 整个文件从头读到尾；无需随机访问。 |
Always link your justification to the characteristics discussed: access speed, memory usage, ease of insertion/deletion, and whether the data size fluctuates.
始终将你的理由与所讨论的特性联系起来：访问速度、内存使用、插入/删除的便捷性以及数据大小是否波动。
Published by TutorHao | IGCSE CIE Computer Science Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图