如果链表和数组是基本的数据结构，那么树、哈希表、堆等是什么类型的数据结构？

Question

我正在学习数据结构在线课程，上面提到链表和数组是基本的数据结构，所以我的问题是关于哈希表，堆，树和图是不是基本的数据结构，如果不是，它们是从任何其他数据结构派生的吗？

谢谢。

Answer 1

列表和数组可以被认为是基本的，因为几乎每个单一的数据结构都是由这些原始数据结构的片段组成的。

例如，图可以是数组支持的，也可以是列表支持的(通常用于稀疏图)。

但是，正如计算机科学中的许多事情一样，AFIAK在数学上并没有形式化地表示什么是“基本数据结构”。

Answer 2

您可以考虑数组和链表的基本原理，因为基本上只有一种方法来实现它们(数组的连续对象序列，链表的线性对象链(单链或双链))。

更高级的数据结构可以被认为是“派生的”，因为它们可以以多种方式实现，并且本质上返回到最低级别的数组和链表。示例：

-n元树通常实现为一系列链接节点(如列表)，但每个节点包含一个子链接数组。对于二叉树，您通常不会公开地看到该数组，因为子对象通常会被命名为left和right。

-哈希表有多种实现方式。对于链式哈希表，它被实现为链表的(稀疏)数组。对于被探测或开放地址的哈希表，它只是一个带有冲突逻辑的大数组。

-集合通常是树或哈希表，因此以数组和列表的形式进行传递定义

-堆栈、队列、向量等只是施加了特殊语义的数组。

我同意其他人的观点，即CS实际上并没有基本数据结构的“教科书”定义，但你可以很容易地看出这是“事实上”的事实。

顺便提个有趣的问题..。

Answer 3

在Lisp (总之是well Scheme )中，唯一的基本数据结构是对。其他所有东西都是从这个类型构造的。

您必须指定您的语言，以找出该语言的基本数据结构。

编辑: Ok，Java和C++。我设想所有的C++库容器，如向量和队列，都将基于简单的数组，但在Java语言中可能内置更多的类型。我想这取决于你如何定义“基础”。