weixin_43812286
min三岁
2019-08-15 21:18
采纳率: 0%
浏览 2.1k

顺序表、链表和数组是逻辑结构还是物理(存储)结构?或者这两种结构都有描述?

数据结构中的线性结构也就是“线性表”是逻辑结构,现在可以肯定栈与队列都是存储结构,栈与队列都是线性表,顺序表和链表也是线性表,一维数组和顺序表又基本上是一回事,那么顺序表和链表也是存储结构吗?

主要是在网上看了很多人的回答,各种说法都有,所以想确认一下。

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

  • caozhy

    顺序表的存储方式一般用数组,数组是物理上连续的,顺序表是逻辑结构。链表是非连续结构。当然这里说的物理,实际上对于实际的内存硬件也未必连续,应为操作系统中使用虚拟地址。

    点赞 评论
  • zongxian5219
    铁血乳娃娃 2019-08-21 21:25

    顺序表的意思就是表内各个元素的地址空间是连续的,属于一个统称,数组、栈和队列都可以包括在顺序表里。你可以这样进行判断:如果一个数据结构你可以通过下标任意访问里面的元素那么它就可以叫顺序表。因为地址空间是连续的,比如你访问第五个元素,只需要将第一个元素的地址加4就可以得到第五个元素的地址。
    所以顺序表应该是一类数据结构的统称
    而链表的地址空间不是连续的,而是通过一个指针指向下一个元素,所以你访问链表里的元素时必须从头开始一个一个找。
    链表是一种数据结构
    线性表就是指像一条线一样的数据结构,数组、栈、队列、链表这些都是线性表,都是一个维度的。而二叉树这种因为会产生分支所以就不是线性表
    线性表也是一类数据结构的统称
    还有一个概念需要知道 如果一个数据结构是顺序表,它不一定是线性的;其实没必要纠结物理存储结构,因为底层的实现是复杂而多样的,数据可以在内存物理地址上不连续存储,但是在上层也可以获得类似数组一样的操作。同样反过来即便在底层用连续的地址空间进行存储但是你读取的时候也不能像数组那样读。比如最大堆和最小堆理论上是一种二叉树,但是底层可以用数组进行实现

    点赞 评论
  • m0_46588308
    m0_46588308 2020-08-19 12:15

    最近我也有这个问题,就是搞不清楚数组和链表是属于逻辑结构层面的还是存储结构层面的 还是二者都有涉及。依照我所了解的,存储结构有四种:顺序存储,链式存储,索引存储和哈希存储。其中,前两者应该是对应数组和链表的思想。另外,栈和队列这些是属于逻辑结构层面的,举个例子简单说,所谓“先进先出”“后进先出”这些思想只是逻辑上的原理,计算机实际存储并没有这样的结构,而通常说栈和队列可以由数组和链表实现(一般是数组),所以按照这个关系来讲,其实数组和链表就可能是对应存储结构的顺序存储和链式存储,而大多数编程语言都实现了基本的数组结构,除此之外,基于这些存储结构,再加上逻辑结构,就可以得出不同的数据结构了,例如java集合中的list,有分别基于数组和链表实现的arraylist和linkedlist

    点赞 评论

相关推荐