数据结构

数据结构的分类

常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图等，它们可以从 “逻辑结构” 和 “物理结构” 两个维度进行分类。

逻辑结构：线性与非线性

**逻辑结构揭示了数据元素之间的逻辑关系。**在数组和链表中，数据按照顺序依次排列，体现了数据之间的线性关系；而在树中，数据从顶部向下按层次排列，表现出父节点与子节点之间的派生关系；图则由节点和边构成，反映了复杂的网络关系。

如下图所示，逻辑结构可以被分为 “线性” 和 “非线性” 两大类。线性结构与非线性结构本质区别为数据是否在逻辑结构上呈线性排列。

• **线性数据结构：**数组、链表、栈、队列、哈希表。
• **非线性数据结构：**树、堆、图、哈希表。

非线性数据结构可以进一步被划分为树形结构和网状结构。

• 树形结构：树、堆、哈希表，元素之间是一对多的关系。
• 网状结构：图，元素之间是多对多的关系。

线性与非线性数据结构

物理结构：连续与分散

在计算机中，内存和硬盘是两种主要的存储硬件设备。硬盘主要用于长期存储数据，容量较大（通常可达到 TB 级别）、速度较慢。内存用于运行程序时暂存数据，速度较快，但容量较小（通常为 GB 级别）。

在算法运行过程中，相关数据都存储在内存中。下图展示了一个计算机内存条，其中每个黑色方块都包含一块内存空间。我们可以将内存想象成一个巨大的表格，其中每个单元格都可以存储一定大小的数据，在算法运行时，所有数据都被存储在这些单元格中。

系统通过内存地址来访问目标位置的数据。如下图所示，计算机根据特定规则为表格中的每个单元格分配编号，确保每个内存空间都有唯一的内存地址。有了这些地址，程序便可以访问内存中的数据。

内存条、内存空间、内存地址

内存是所有程序的共享资源，当某块内存被某个程序占用时，则无法被其他程序同时使用了。因此在数据结构与算法的设计中，内存资源是一个重要的考虑因素。比如，算法所占用的内存峰值不应超过系统剩余空闲内存；如果缺少连续大块的内存空间，那么所选用的数据结构必须能够存储在分散的内存空间内。

如下所示，物理结构反映了数据在计算机内存中的存储方式，可分为连续空间存储（数组）和分散空间存储（链表）。物理结构从底层决定了数据的访问、更新、增删等操作方法，同时在时间效率和空间效率方面呈现出互补的特点（即最优的时间效率或最优的空间效率不可兼得）。

连续空间存储与分散空间存储

值得说明的是，**所有的数据结构都是基于数组、链表或者二者的组合实现的。**例如，栈和队列既可以使用数组实现，也可以使用链表实现；而哈希表的实现可能同时包含数组和链表。

• 基于数组可实现：栈、队列、哈希表、树、堆、图、矩阵、张量（维度 ≥3 的数组）等。
• 基于链表可实现：栈、队列、哈希表、树、堆、图等。

基于数组实现的数据结构也被称为 “静态数据结构”，这意味着此类数据结构在初始化后长度不可变。相对应地，基于链表实现的数据结构被称为 “动态数据结构”，这类数据结构在初始化后，仍可以在程序运行过程中对其长度进行调整。

基本数据类型

基本数据类型是 CPU 可以直接进行计算的类型，在算法中被直接使用，主要包括以下几种类型。

• 整数类型 byte、short、int、long。
• 浮点数类型 float、double ，用于表示小数。
• 字符类型 char ，用于表示各种语言的字母、标点符号、甚至表情符号等。
• 布尔类型 bool ，用于表示“是”与“否”判断。

基本数据类型以二进制的形式存储在计算机中。一个二进制位即为 1 比特。在绝大多数现代操作系统中，1 字节（byte）由 8（bits）组成。

基本数据类型的取值范围取决于其所占用的空间大小。下面以 Java 为例。

• 整数类型 byte 占用 1 byte = 8 bits，可以表示 $2^8$ 个数字
• 整数类型 int 占用 4 bytes = 32 bits，可以表示 $2^32$ 个数字

下表列举了各种基本数据类型的占用空间、取值范围和默认值。

基本数据类型的占用空间和取值范围

类型	符号	占用空间	最小值	最大值	默认值
整数	byte	1 byte	$-2^7$ ($-128$)	$2^7 - 1$ ($127$)	$0$
	short	2 bytes	$-2^{15}$	$2^{15} - 1$	$0$
	int	4 bytes	$-2^{31}$	$2^{31} - 1$	$0$
	long	8 bytes	$-2^{63}$	$2^{63} - 1$	$0$
浮点数	float	4 bytes	$1.175 \times 10^{-38}$	$3.403 \times 10^{38}$	$0.0 f$
	double	8 bytes	$2.225 \times 10^{-308}$	$1.798 \times 10^{308}$	$0.0$
字符	char	2 bytes / 1 byte	$0$	$2^{16} - 1$	$0$
布尔	bool	1 byte	$\text{false}$	$\text{true}$	$\text{false}$

注意

字符 char 的大小在 C 和 C++ 中为 1 字节，在大多数编程语言中取决于特定的字符编码方法，详见“字符编码”章节。

即使表示布尔量仅需 1 位（0 或 1)，但它在内存中通常被存储为 1 字节。这是因为现代计算机 CPU 通常将 1 字节作为最小寻址内存单元。

我们知道，数据结构是在计算机中组织与存储数据的方式，侧重点是结构。基本数据类型与数据结构之间的联系简单来说就是，基本数据类型提供了数据的“内容类型”，而数据结构提供了数据的“组织方式”。

数字编码 *