【数据结构】数据的逻辑结构和物理结构

文章目录

一、引言

  在第一章《绪论》中, 时间复杂度的计算数据结构的辨析 无疑是最重要的两类题型。

  上一篇文章中写了关于数据的几个基本概念,以及它们之间的关系。因此在那的基础上,先写一写关于 数据结构 的定义及辨析。

  该知识点的出题模式相对固定,一般出现在选择题前两道。例如:
《【数据结构】数据的逻辑结构和物理结构》
  事实上,我们只需要理解了 存储结构物理结构 的概念和类别,就能够顺利选出答案。

二、概念

   数据结构的内容可归纳为三个部分:逻辑结构物理结构运算集合

  按某种逻辑关系组织起来的一批数据,按一定的映像方式把它们存放在计算机的存储器中,并在这些数据上定义一个运算的集合,这些是数据结构课程的基本内容。

《【数据结构】数据的逻辑结构和物理结构》

(一)逻辑结构

  数据的逻辑结构是对数据之间关系的描述,它与数据的存储结构无关,同一种逻辑结构可以有多种存储结构这句话是解题的关键)。

   分类:

逻辑结构描述
线性结构一对一的线性关系
非线性结构树形结构一对多的层次关系
图形结构多对多的任意关系
集合结构除了同属于一个集合外,无任何其他关系

   归纳:

逻辑结构包括
线性结构线性表、栈、队列、字符串、数组、广义表
非线性结构树、图、集合

(二)物理结构(存储结构)

   数据的物理结构又称为存储结构,是数据的逻辑结构在计算机中的表示(又称映像)。
  它包括 数据元素的表示关系的表示

存储结构概念一般形式
顺序存储方法把逻辑上相邻的结点存储在物理位置上相邻的存储单元中,结点之间的逻辑关系由存储单元的邻接关系来体现。数组
链式存储方法不要求逻辑上相邻的结点在物理位置上也相邻,结点间的逻辑关系是由附加的指针字段表示的。借助指针
索引存储方法在存储结点信息时除建立存储结点信息外,还建立附加的索引表来标识结点的地址。<关键字,地址>
散列存储方法根据结点的关键字通过散列函数直接计算出该结点的存储地址。数组(是顺序存储的扩展)

三、考研真题解析

《【数据结构】数据的逻辑结构和物理结构》

【C】解析:认真读题好吗!从逻辑上 ,数据结构分为 线性结构非线性结构

《【数据结构】数据的逻辑结构和物理结构》

【D】解析:
  与存储结构(即物理结构)无关的术语。在之后的学习中我们会知道,我们学到的 线性表队列 等,它们都是从逻辑结构上的定义,而具体将它们存放进计算机的存储方法,才是存储结构的范畴。也就是说, 是一种逻辑结构,它可以被存储为 顺序栈链栈,这才是它的存储结构。
  而另一个容易混淆的选项是 A. 循环队列 。在队列的学习中会学到,循环队列 默认是以顺序结构存储,因此已限定其存储方法,可认为是一种存储结构。

《【数据结构】数据的逻辑结构和物理结构》

【D】解析:
   A.广义表 ,表元素可以是原子或者广义表的一种线性表的扩展结构。
   B.二叉树 ,是 非线性结构 中的 树形结构 ,具有一对多的层次关系 。
   C.稀疏矩阵矩阵 明显不是一对一的线性关系。
   D.串 ,是由零个或多个字符组成的有限序列。是限定了元素为字符的线性表。通常用一个 字符数组 来表示。提到由数组来表示,即为线性结构。

《【数据结构】数据的逻辑结构和物理结构》

【A】解析:
  A.栈 是一种逻辑结构,它可以被存储为 顺序栈链栈,这才是它的存储结构。
  B.哈希表 是存储结构中的 散列存储方法
  C.线索树 是在链式存储结构的基础上对树进行线索,与存储结构中的 链式存储结构 有关。
  D.双向链表 也是以链式结构存储的。

    原文作者:SLEEPY_DOG7
    原文地址: https://blog.csdn.net/zjq709918448/article/details/94123530
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系博主进行删除。
点赞