响应式中文网站欣赏,网络管理系统组成,网站首页域名如何设置访问快,中国交通建设监理协网站数据结构之----逻辑结构、物理结构
目前我们常见的数据结构分别有#xff1a; 数组、链表、栈、队列、哈希表、树、堆、图 而它们可以从 逻辑结构和物理结构两个维度进行分类。
什么是逻辑结构#xff1f;
逻辑结构是指数据元素之间的逻辑关系#xff0c;而逻辑结构又分为…数据结构之----逻辑结构、物理结构
目前我们常见的数据结构分别有 数组、链表、栈、队列、哈希表、树、堆、图 而它们可以从 逻辑结构和物理结构两个维度进行分类。
什么是逻辑结构
逻辑结构是指数据元素之间的逻辑关系而逻辑结构又分为线性结构和非线性结构两大类。
什么是线性结构
线性结构比较直观指数据在逻辑关系上呈线性排列 如 在数组和链表中数据按照顺序依次排列体现了数据之间的线性关系。
什么是非线性结构
非线性结构则与线性结构相反指数据在逻辑关系上呈非线性排列 如 在图中数据由节点和边构成反映了复杂的网络关系。 而在树中数据从顶部向下按层次排列表现出祖先与后代之间的派生关系。 而非线性数据结构又可以进一步被划分为树形结构和网状结构。
线性结构数组、链表、队列、栈、哈希表。元素之间是一对一的顺序关系。树形结构树、堆、哈希表。元素之间是一对多的关系。网状结构图。元素之间是多对多的关系。
什么是物理结构
物理结构指的是数据在计算机内存中的存储方式可分为连续空间存储数组和分散空间存储链表。 它从底层决定了数据的访问、更新、增删等操作方法同时在时间效率和空间效率方面呈现出互补的特点。
我们都知道所有数据结构都是基于数组、链表或二者的组合实现的。 如 栈和队列既可以使用数组实现也可以使用链表实现。 而哈希表的实现可能同时包含数组和链表。
基于数组可实现栈、队列、哈希表、树、堆、图、矩阵、张量维度 ≥ 3 的数组等。基于链表可实现栈、队列、哈希表、树、堆、图等。
基于数组实现的数据结构也被称为静态数据结构这意味着此类数据结构在初始化后长度不可变。 相对应地基于链表实现的数据结构被称为动态数据结构这类数据结构在初始化后仍可以在程序运行过程中对其长度进行调整。
QA
为什么哈希表同时包含线性数据结构和非线性数据结构
哈希表底层是数组而为了解决哈希冲突我们会使用链式地址数组中每个桶指向一个链表当链表长度超过一定阈值时又可能被转化为树通常为红黑树。 从存储的角度来看哈希表的底层是数组其中每一个桶槽位可能包含一个值也可能包含一个链表或树。因此哈希表可能同时包含线性数组、链表和非线性树数据结构。
基于数组实现的数据结构也被称为“静态数据结构”是否有歧义因为栈也可以进行出栈和入栈等操作这些操作都是“动态”的。
栈确实可以实现动态的数据操作但数据结构仍然是“静态”长度不可变的。尽管基于数组的数据结构可以动态地添加或删除元素但它们的容量是固定的。如果数据量超出了预分配的大小就需要创建一个新的更大的数组并将老数组的内容复制到新数组中。
在构建栈队列的时候未指定它的大小为什么它们是“静态数据结构”呢
在高级编程语言中我们无须人工指定栈队列的初始容量这个工作是由类内部自动完成的。例如Java 的 ArrayList 的初始容量通常为 10 。另外扩容操作也是自动实现的。
