跳转至

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。

图中两个已用内存单元
完整地址行起始地址列偏移存储数据
0x00120x0010021
0x00240x0020042

把行起始地址与列偏移相加即可定位。例如 0x0020 加偏移 04,得到 0x0024,读出数据 2。网格下方的两个读取示例与表中两行对应。地址标识位置,数据是该位置存放的内容;网格只作寻址示意,不表示芯片的实际电路布局。

Tip

值得说明的是,将内存比作 Excel 表格是一个简化的类比,实际内存的工作机制比较复杂,涉及地址空间、内存管理、缓存机制、虚拟内存和物理内存等概念。

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

如图 3-3 所示,物理结构反映了数据在计算机内存中的存储方式,可分为连续空间存储(数组)和分散空间存储(链表)。物理结构从底层决定了数据的访问、更新、增删等操作方法,两种物理结构在时间效率和空间效率方面呈现出互补的特点。

图 3-3   连续空间存储与分散空间存储

图解 3-3:数组与链表的存储布局

相同的逻辑序列,既可连续存储,也可由分散节点的指针连接。

左右两幅都是 5 行 6 列示意网格,行从上到下、列从左到右,均从 1 起计。左侧数组在第 2 行前 5 格连续存放 1、3、2、5、4;右侧链表节点分散在网格各处,每个节点占相邻的值格和指针格。

浅灰格表示可用空间;数组占用格为绿色,链表的值格为青色、指针格为浅蓝色。下表按链表访问次序列出各节点位置。

链表节点的示意位置与后继;行列从1起
节点值值格位置指针格位置后继
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

如果你感觉物理结构理解起来有困难,建议先阅读下一章,然后再回顾本节内容。

欢迎在评论区留下你的见解、问题或建议