# 数据类型与结构

> CIE A-Level 计算机科学 · 9618
> 来源: https://www.owlsprep.com/zh/study/cie-9618-u10-overview/
> 占比: n/a

本单元介绍编程中的核心数据类型和常见数据结构，讲解如何组织、存储和操作数据以高效解决计算问题。

**先修:** 基础编程知识：变量、算法和控制流

## 学习目标

- 区分编程中使用的原始数据类型和复合数据类型
- 在不同问题场景中实现并应用常见的线性和非线性数据结构
- 分析不同数据结构之间的时间与空间权衡
- 选择合适的数据结构高效解决给定的计算问题

## 单元概览

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

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

以下是本单元涵盖的所有子主题，按从基础到进阶排序：
- [原始数据类型](https://www.owlsprep.com/study/cie-9618-u10-primitive-data-types/) — 大多数编程语言内置的基础单值原子数据类型。
- [数组](https://www.owlsprep.com/study/cie-9618-u10-arrays/) — 同构数据的线性集合，支持静态或动态大小。
- [记录](https://www.owlsprep.com/study/cie-9618-u10-records/) — 将异构相关数据字段分组的复合数据类型。
- [链表](https://www.owlsprep.com/study/cie-9618-u10-linked-lists/) — 由通过指针/引用连接的节点组成的动态线性结构。
- [栈](https://www.owlsprep.com/study/cie-9618-u10-stacks/) — 后进先出（LIFO）线性结构，有广泛的实际应用。
- [队列](https://www.owlsprep.com/study/cie-9618-u10-queues/) — 先进先出（FIFO）线性结构，用于有序处理数据。
- [树](https://www.owlsprep.com/study/cie-9618-u10-trees/) — 用于对嵌套数据关系建模的分层非线性结构。
- [图](https://www.owlsprep.com/study/cie-9618-u10-graphs/) — 用于对网络和节点间连接建模的非线性结构。
- [哈希表](https://www.owlsprep.com/study/cie-9618-u10-hash-tables/) — 利用哈希函数实现高效键值查找的结构。

## 常见错误

- **错误做法:** 混淆栈和队列的操作顺序
  - 原因: 混淆LIFO和FIFO会导致表达式求值等常见问题的解决方案出错。
  - 正确做法: 记住：栈 = 后进先出（就像一摞盘子），队列 = 先进先出（就像结账排队）。
- **错误做法:** 不权衡利弊就选择数据结构
  - 原因: 数组访问快但插入慢，链表则相反，这会导致解决方案效率低下。
  - 正确做法: 选择数据结构前，务必确认你最常执行的操作是什么。
- **错误做法:** 将所有数据结构都视为线性结构
  - 原因: 对树和图的错误分类会导致遍历逻辑和性质解答出错。
  - 正确做法: 分析数据结构的特性时，务必先将其分类为线性或非线性。

## 速查表

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

## 下一步

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

- [原始数据类型（本单元第一个子主题）](https://www.owlsprep.com/zh/study/cie-9618-u10-primitive-data-types/)
- [数组](https://www.owlsprep.com/zh/study/cie-9618-u10-arrays/)
- [记录](https://www.owlsprep.com/zh/study/cie-9618-u10-records/)

---

来自 [OwlsPrep](https://www.owlsprep.com) —— A-Level / IB / AP / IGCSE 免费学习指南，依据官方考纲编写。原页面：https://www.owlsprep.com/zh/study/cie-9618-u10-overview/