Hello 算法教程:数据结构的两大分类维度——逻辑结构、物理结构及其底层源码实现

Hello 算法教程:数据结构的两大分类维度——逻辑结构、物理结构及其底层源码实现

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

本文基于《Hello 算法》仓库的"数据结构分类"一节展开,系统梳理数据结构按"逻辑结构(线性/非线性)"与"物理结构(连续/分散)"两个维度的分类方法,并结合仓库中 Python 栈、哈希表、二叉树、堆、图等多份真实实现源码,验证"所有数据结构都构建于数组、链表或二者的组合之上"这一核心结论。读完后,你将掌握对任意数据结构快速定位其逻辑与物理属性的分析方法,并能看懂项目中各章节实现之间的底层关联。

一、常见的数据结构与两个分类维度

《Hello 算法》中常见的数据结构包括数组、链表、栈、队列、哈希表、树、堆、图。原文档(classification_of_data_structure.md)指出,它们可以从"逻辑结构"和"物理结构"两个维度进行分类:

• 逻辑结构回答的是"数据元素之间有什么逻辑关系";
• 物理结构回答的是"这些数据在计算机内存中到底怎么存放"。

这两个维度正交:同一个逻辑结构(如栈)可以用完全不同的物理结构(数组或链表)实现。仓库的目录结构本身就映射了这套分类体系,例如 chapter_array_and_linkedlist、chapter_stack_and_queue、chapter_hashing、chapter_tree、chapter_heap、chapter_graph 各章节,分别对应基础结构、线性派生结构、散列结构、树形结构与网状结构。

二、逻辑结构:线性与非线性

逻辑结构揭示了数据元素之间的逻辑关系。在数组和链表中,数据按照一定顺序排列,体现了数据之间的线性关系;而在树中,数据从顶部向下按层次排列,表现出"祖先"与"后代"之间的派生关系;图则由节点和边构成,反映了复杂的网络关系。

逻辑结构可分为"线性"和"非线性"两大类。线性结构比较直观,指数据在逻辑关系上呈线性排列;非线性结构则相反,呈非线性排列:

• 线性数据结构:数组、链表、栈、队列、哈希表,元素之间是一对一的顺序关系。
• 非线性数据结构:树、堆、图、哈希表。

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

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

从源码结构看,这个划分在仓库中有直接体现:树与堆的实现都依赖"父节点—子节点"的一对多索引关系(详见第四节),而图的实现 graph_adjacency_list.py 中一条边连接两个顶点、顶点可被多条边共享,正是多对多关系的典型。

三、物理结构:连续与分散

3.1 内存、内存地址与"Excel 表格"类比

当算法程序运行时,正在处理的数据主要存储在内存中。下图展示了一个计算机内存条,其中每个黑色方块都包含一块内存空间。我们可以将内存想象成一个巨大的 Excel 表格,其中每个单元格都可以存储一定大小的数据。

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

值得说明的是,将内存比作 Excel 表格是一个简化的类比,实际内存的工作机制比较复杂,涉及地址空间、内存管理、缓存机制、虚拟内存和物理内存等概念。仓库的 ram_and_cache.md 一篇正是对内存与缓存机制的专门展开,可作为本节类比的延伸阅读。

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

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

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

• 连续空间存储(数组):元素在内存中连续排布,可通过地址 + 偏移量直接寻址,支持 O(1) 随机访问,但中间插入/删除需要整体搬移元素,且初始化后逻辑长度通常固定;
• 分散空间存储(链表):节点在内存中分散存放,靠指针串成链,插入/删除只需修改指针,但访问第 i 个节点需要从头遍历,O(n)。

值得说明的是,所有数据结构都是基于数组、链表或二者的组合实现的。例如,栈和队列既可以使用数组实现,也可以使用链表实现;而哈希表的实现可能同时包含数组和链表。原文档给出的实现清单是:

• 基于数组可实现:栈、队列、哈希表、树、堆、图、矩阵、张量(维度 $\geq 3$ 的数组)等。
• 基于链表可实现:栈、队列、哈希表、树、堆、图等。

链表在初始化后,仍可以在程序运行过程中对其长度进行调整,因此也称"动态数据结构"。数组在初始化后长度不可变,因此也称"静态数据结构"。值得注意的是,数组可通过重新分配内存实现长度变化,从而具备一定的"动态性"。

如果觉得物理结构理解起来有困难,建议先阅读 array.md 与 linked_list.md 两节(仓库下一章),然后再回顾本节内容。

四、源码印证:数组与链表如何拼出所有数据结构

以下逐类对照仓库 Python 实现(路径以 codes/python/ 为根,其他语言在 codes/ 下有同构版本),验证原文档"基于数组可实现 / 基于链表可实现"的清单。

4.1 栈:同一接口的两种物理实现

仓库中栈同时提供了数组版与链表版,接口完全一致(size/is_empty/push/pop/peek),差异仅在底层存储:

• 数组版array_stack.py:内部持有self._stack: list[int],push调用append、pop调用列表pop()、peek取self._stack[-1]——元素在逻辑上连续存放,利用数组下标直接定位栈顶;
• 链表版linkedlist_stack.py:仅持有一个头指针self._peek: ListNode和计数self._size,push是node.next = self._peek后移指针——新节点散落在任意内存位置,靠next指针连接。

队列与双端队列同样成对存在(array_queue.py、linkedlist_queue.py 等),印证了"栈和队列既可用数组实现、也可用链表实现"的论断。

4.2 哈希表:数组 + 链表的组合体

链式地址哈希表 hash_map_chaining.py 是"数组与链表组合"的最典型例证:

class HashMapChaining: """链式地址哈希表""" def __init__(self): self.capacity = 4 # 哈希表容量 self.buckets = [[] for _ in range(self.capacity)] # 桶数组

• self.buckets是一个定长数组(连续空间),负责"哈希值 → 桶下标"的 O(1) 寻址;
• 每个桶内部是一个键值对列表(逻辑上的链表,分散空间),负责串联哈希冲突的同桶元素。

get/put的查找流程都是"先按数组下标定位桶,再在桶内线性遍历",两种物理结构的优缺点在此被组合使用:数组贡献快速定位,链表(列表)贡献动态伸缩。此外,负载因子阈值load_thres = 2.0 / 3.0触发扩容(extend_ratio = 2),正是原文档所说"数组可通过重新分配内存实现长度变化,从而具备一定的动态性"的具体实现。开链法与开放寻址法分别见 hash_map_open_addressing.py 和 array_hash_map.py,后者是纯数组实现的定长哈希表,可对照阅读。

4.3 树:用数组表达层级关系

二叉树的数组表示 array_binary_tree.py 直接印证"树可以基于数组实现":节点i的左子节点在2*i+1、右子节点在2*i+2、父节点在(i-1)//2,树状的"祖先—后代"逻辑关系完全通过数组下标的数学关系表达,层序遍历甚至可以退化为直接顺序扫描数组。相对地,链表(节点指针)表示的二叉树见 binary_tree.py,其增删与遍历操作分散在连续的节点对象之间,是典型的分散空间存储。

4.4 堆:本质上是数组上的完全二叉树

堆的实现 my_heap.py 展示了同样的下标技巧:self.max_heap = nums直接以列表为存储,left(i)=2*i+1、right(i)=2*i+2、parent(i)=(i-1)//2,建堆时对除叶节点外所有节点执行sift_down。从源码结构看,堆是"数组(物理)+ 树(逻辑)"这一组合关系的最紧凑样本——逻辑上是树形的一对多结构,物理上却是一段连续内存。

4.5 图:哈希表 + 数组/列表的组合

无向图的邻接表实现 graph_adjacency_list.py 中,self.adj_list: dict[Vertex, list[Vertex]]为每个顶点维护一个邻接顶点列表:外层哈希表实现"顶点 → 邻接列表"的 O(1) 查找,内层列表承担多对多边的存储。add_edge只需双向append,体现了分散结构增删方便的特点。与之对照,基于二维数组的邻接矩阵见 graph_adjacency_matrix.py,是"同一逻辑结构、不同物理结构"的又一组样本。

4.6 动态与静态:链表长度可变的直观证据

链表 linked_list.py 中的insert(n0, P)与remove(n0)仅通过修改两个指针即可完成增删,节点数量随运行过程自由变化,这是"动态数据结构"定义的最小单元;而数组章节的固定下标访问则对应"静态"一侧。

五、小结:两个维度的速查表

掌握这套分类法后,面对任何数据结构都可以两问定位:逻辑上它是线性、树形还是网状?物理上它落在连续内存、分散内存,还是两者的组合?仓库 chapter_data_structure 一章的 exercises.md 与 summary.md 提供了配套练习与本章小结,可配合上文继续深化;各数据结构的详细操作讲解则分布在前述各chapter_*文档与代码章节中。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo