单元总览

数据类型与结构

CIE A-Level 计算机科学· 5 分钟阅读 📊 n/a

1. 单元概览

本单元从最基础的数据构建块（原始类型）开始，逐步讲解用于解决实际计算问题的越来越复杂的复合结构。我们首先介绍基础线性结构，然后转向可对数据间更复杂关系建模的非线性结构。

掌握本主题对编写高效代码、解答整个CIE 9618考纲中的问题求解题目至关重要。数据结构的选择会直接影响你实现的任何算法的效率。

以下是本单元涵盖的所有子主题，按从基础到进阶排序：

原始数据类型

大多数编程语言内置的基础单值原子数据类型。

★⏱ 5 min

数组

同构数据的线性集合，支持静态或动态大小。

★★⏱ 7 min

记录

将异构相关数据字段分组的复合数据类型。

★★⏱ 5 min

链表

由通过指针/引用连接的节点组成的动态线性结构。

★★★⏱ 8 min

栈

后进先出（LIFO）线性结构，有广泛的实际应用。

★★★⏱ 6 min

队列

先进先出（FIFO）线性结构，用于有序处理数据。

★★★⏱ 6 min

树

用于对嵌套数据关系建模的分层非线性结构。

★★★★⏱ 10 min

图

用于对网络和节点间连接建模的非线性结构。

★★★★⏱ 10 min

哈希表

利用哈希函数实现高效键值查找的结构。

★★★★⏱ 9 min

2. 常见陷阱

错误做法:

混淆栈和队列的操作顺序

原因:

混淆LIFO和FIFO会导致表达式求值等常见问题的解决方案出错。

正确做法:

记住：栈 = 后进先出（就像一摞盘子），队列 = 先进先出（就像结账排队）。

错误做法:

不权衡利弊就选择数据结构

原因:

数组访问快但插入慢，链表则相反，这会导致解决方案效率低下。

正确做法:

选择数据结构前，务必确认你最常执行的操作是什么。

错误做法:

将所有数据结构都视为线性结构

原因:

对树和图的错误分类会导致遍历逻辑和性质解答出错。

正确做法:

分析数据结构的特性时，务必先将其分类为线性或非线性。

3. 速查表

概念	核心规则 / 定义
原始数据类型	原子单值类型：整数、浮点数、布尔值、字符
静态数组访问	任意元素的随机访问时间复杂度为 $O (1)$
链表插入	已知节点处的插入/删除时间复杂度为 $O (1)$
栈的性质	遵循后进先出（LIFO）访问顺序
队列的性质	遵循先进先出（FIFO）访问顺序
二叉树规则	每个节点最多可拥有2个子节点（左和右）
图的存储	通常存储为邻接矩阵或邻接表
哈希表平均查找	平均情况下键查找的时间复杂度为 $O (1)$
记录定义	存储多个异构相关字段的复合类型

下一步

从本单元的第一个子主题开始学习，它讲解原始数据类型——这是你在本单元将学到的所有其他数据结构的基础构建块。完成这里所有子主题后，就可以进入下一单元（算法），学习这些数据结构如何用于解决常见计算问题。