3.1 数据结构分类¶
常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图,它们可以从“逻辑结构”和“物理结构”两个维度进行分类。
3.1.1 逻辑结构:线性与非线性¶
逻辑结构揭示了数据元素之间的逻辑关系。在数组和链表中,数据按照一定顺序排列,体现了数据之间的线性关系;而在树中,数据从顶部向下按层次排列,表现出“祖先”与“后代”之间的派生关系;图则由节点和边构成,反映了复杂的网络关系。
如图 3-1 所示,逻辑结构可分为“线性”和“非线性”两大类。线性结构比较直观,指数据在逻辑关系上呈线性排列;非线性结构则相反,呈非线性排列。
- 线性数据结构:数组、链表、栈、队列、哈希表,元素之间是一对一的顺序关系。
- 非线性数据结构:树、堆、图、哈希表。
非线性数据结构可以进一步划分为树形结构和网状结构。
- 树形结构:树、堆、哈希表,元素之间是一对多的关系。
- 网状结构:图,元素之间是多对多的关系。
图 3-1 线性数据结构与非线性数据结构
图解 3-1:数据结构的逻辑关系
比较顺序、父子层级、网络连接和键值映射四种逻辑关系。
图左栏为线性数据结构,右栏为非线性数据结构;哈希表位于两栏下方,单独展示键值映射。
| 结构 | 图中分栏 | 图中元素与关系 |
|---|---|---|
| 数组array | 线性 | 按1、3、2、5、4排列 |
| 链表linked list | 线性 | 1→3→2→5→4 |
| 栈stack | 线性 | 从开口端到封闭端为1、3、2、5、4;push入栈与pop出栈同在开口端 |
| 队列queue | 线性 | 从出队端到入队端为1、3、2、5、4;push入队、pop出队在不同端 |
| 树tree | 非线性 | 根1左2右3;2左4右5;3左6右7;7节点三层 |
| 图graph | 非线性 | 5顶点1至5;无向边1—2、1—3、2—3、2—4、2—5、3—5、4—5,共7条 |
| 堆heap | 非线性 | 根1左3右2;3左5右4;5节点三层 |
| 哈希表hash table | 跨两栏单列 | 键a、b、c分别映射值1、2、3 |
线性结构具有先后次序,但对操作位置的限制不同;树与堆组织父子层级,图允许一个顶点有多个邻居。这里比较的是逻辑关系,不等同于底层存储:同类关系可以有不同实现,哈希表也可组合数组、链表或树。
3.1.2 物理结构:连续与分散¶
当算法程序运行时,正在处理的数据主要存储在内存中。图 3-2 展示了一个计算机内存条,其中每个黑色方块都包含一块内存空间。我们可以将内存想象成一个巨大的 Excel 表格,其中每个单元格都可以存储一定大小的数据。
系统通过内存地址来访问目标位置的数据。如图 3-2 所示,计算机根据特定规则为表格中的每个单元格分配编号,确保每个内存空间都有唯一的内存地址。有了这些地址,程序便可以访问内存中的数据。
图 3-2 内存条、内存空间、内存地址
图解 3-2:用地址访问内存
由行起始地址加列偏移定位内存单元,读取其中的数据。
左侧是一条竖直的内存条,其黑色芯片区域通过两条灰线引出右侧的内存空间网格。这些芯片与网格内表示“已用”的深色单元不是同一层级。
网格画出 5 行 8 列:行起始地址为 0x0000、0x0010、0x0020、0x0030、0x0040,列偏移为 00 至 07;右侧和底部的省略号表示还有未画出的单元。浅色是可用空间,深色是已用空间;可用不表示里面存有数值 0。
| 完整地址 | 行起始地址 | 列偏移 | 存储数据 |
|---|---|---|---|
| 0x0012 | 0x0010 | 02 | 1 |
| 0x0024 | 0x0020 | 04 | 2 |
把行起始地址与列偏移相加即可定位。例如 0x0020 加偏移 04,得到 0x0024,读出数据 2。网格下方的两个读取示例与表中两行对应。地址标识位置,数据是该位置存放的内容;网格只作寻址示意,不表示芯片的实际电路布局。
Tip
值得说明的是,将内存比作 Excel 表格是一个简化的类比,实际内存的工作机制比较复杂,涉及地址空间、内存管理、缓存机制、虚拟内存和物理内存等概念。
内存是所有程序的共享资源,当某块内存被某个程序占用时,则通常无法被其他程序同时使用了。因此在数据结构与算法的设计中,内存资源是一个重要的考虑因素。比如,算法所占用的内存峰值不应超过系统剩余空闲内存;如果缺少连续大块的内存空间,那么所选用的数据结构必须能够存储在分散的内存空间内。
如图 3-3 所示,物理结构反映了数据在计算机内存中的存储方式,可分为连续空间存储(数组)和分散空间存储(链表)。物理结构从底层决定了数据的访问、更新、增删等操作方法,两种物理结构在时间效率和空间效率方面呈现出互补的特点。
图 3-3 连续空间存储与分散空间存储
图解 3-3:数组与链表的存储布局
相同的逻辑序列,既可连续存储,也可由分散节点的指针连接。
左右两幅都是 5 行 6 列示意网格,行从上到下、列从左到右,均从 1 起计。左侧数组在第 2 行前 5 格连续存放 1、3、2、5、4;右侧链表节点分散在网格各处,每个节点占相邻的值格和指针格。
浅灰格表示可用空间;数组占用格为绿色,链表的值格为青色、指针格为浅蓝色。下表按链表访问次序列出各节点位置。
| 节点值 | 值格位置 | 指针格位置 | 后继 |
|---|---|---|---|
| 1 | 第2行第2列 | 第2行第3列 | 3 |
| 3 | 第3行第3列 | 第3行第4列 | 2 |
| 2 | 第5行第2列 | 第5行第3列 | 5 |
| 5 | 第5行第5列 | 第5行第6列 | 4 |
| 4 | 第1行第5列 | 第1行第6列 | 未画后续箭头 |
数组的先后次序由相邻位置表达,链表则沿后继指针访问。因此节点 4 虽在最上方,仍位于 1 → 3 → 2 → 5 → 4 的最后。图未注明它的具体指针值。连续存储无须为每个元素另存后继指针;分散节点能利用零散空间,但要额外保存指针。
值得说明的是,所有数据结构都是基于数组、链表或二者的组合实现的。例如,栈和队列既可以使用数组实现,也可以使用链表实现;而哈希表的实现可能同时包含数组和链表。
- 基于数组可实现:栈、队列、哈希表、树、堆、图、矩阵、张量(维度 \(\geq 3\) 的数组)等。
- 基于链表可实现:栈、队列、哈希表、树、堆、图等。
链表在初始化后,仍可以在程序运行过程中对其长度进行调整,因此也称“动态数据结构”。数组在初始化后长度不可变,因此也称“静态数据结构”。值得注意的是,数组可通过重新分配内存实现长度变化,从而具备一定的“动态性”。
Tip
如果你感觉物理结构理解起来有困难,建议先阅读下一章,然后再回顾本节内容。