C语言中，数据结构，逻辑结构与存储结构的区别..百度谷歌过，但是答案太混杂，不敢确定

Question

我的认为是：
数据结构包含存储结构与逻辑结构。
存储结构包括：链表，数组，集合。
逻辑结构包括：队列。
不知这样理解对否？不对的话可以说明一下

希望有知道的人可以讲解一下，网上的资料太过混乱。
谢谢

Answer 1

1.首先我来说几个概念性的东西：

• 数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。

• 数据对象：是性质相同的数据元素的集合，是数据的子集。

• 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

• 逻辑结构：是指数据对象中的数据元素之间的相互关系。

• 逻辑结构-集合结构：集合结构中的元素除了同属于一个集合外，他们之间是没有关系的。

• 逻辑结构-线性结构：线性结构中的数据元素之间是一对一的关系。

• 逻辑结构-树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。

• 逻辑结构-图形结构：图形结构的数据元素存在多对多的关系

• 物理结构：是指数据的逻辑结构在计算机中的存储形式

• 逻辑存储-顺序存储：是把数据元素放在地址连续的存储单元里，其数据间的逻辑关系和物理关系一直。

• 物理存储-链式存储：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续也可以是不连续的
  接下来就说下线性表，线性表当我们申请的存储的时候是申请了一个数组，数组在计算机里面是连续的存储单元，这样我们就可以把逻辑上的线性结构存储到连续单元的物理结构中去。有不对的地方欢迎讨论。

2.最后推荐你一本书看：《大话数据结构》这本书你值得拥用，讲的通俗易懂，结合了图形来进行讲解。

Answer 2

这幅图的理解正确与否？

Answer 3

我将采用“迂回”的方式来回答题主的问题。

先来说说数据类型和抽象数据类型，先看下面3个例子。

例1，如果我给你一个整数你会获得哪些信息？

• 主要可以得到如下信息：

  1. 该整数应该是$-\infty, \ldots, -1, -2, 0, 1, 2, \ldots +\infty$中的一个

  2. 可对该整数进行加、减、乘、除、取模、开方等操作

  3. 该整数与另一整数的关系

     • 具有相同性质

     • 属于同一个集合 $\left(-\infty, +\infty\right)$的关系

---

例2，如果我给你一个C语句int num;（32位机器）你能获得哪些信息？

• 主要可以得到如下信息

  1. 可对num赋予$\left[-2^{31},2^{31} -1\right]$中的任意值

  2. 可对num执行加、减、乘、除、取模、开方等操作

  3. num与其他int num2;的关系

     • 具有相同性质

     • 同属一于$\left[-2^{31},2^{31} -1\right]$这个集合

---

例3，如果我给你一个队列你会获得哪些信息？

• 主要可以得到如下信息

  1. 队列中可以存放某一种数据集（整数、实数、字符、等等）

  2. 队列支持入队（enqueue）、出队（dequeue）、判空（isEmpty）、队列长度（size/length）等操作

  3. 队列中的数据元素A与数据元素B（假定A先入队、B后入队）的关系

     • 首先，A、B来自同属一个数据集

     • 其次，A在B之前

       • 先进入队列的数据元素一定在后进入队列的数据元素的前面

       • 一对一关系

     • 最后，A先于B出队

       • 先进入队列的数据元素一定比后进入队列的数据元素先离开队列

       • 也就是常说的先进先出FIFO

---

理解了上面的内容，我们来看看教课书上的一些定义。

数据类型的定义(Data Type)：

• 一个数据类型定义了

  1. 数据对象（整数范围内的所有数），也可说成一组值或值的集合或一组元素的集合等

  2. 数据对象上可进行的操作集（加、减、乘、除、取模、开方）

  3. 数据对象中的每个数据元素之间的关系

     • 同属一个集合

     • 一对一

     • 一对多

     • 多对多

• 解释

  • 数据对象：是性质相同的数据元素的集合，是数据的子集

    • 数据对象：可以类比成整数集合

    • 数据元素：可以类比成我给你的那个整数，与其他整数具有相同的性质

    • 是数据的子集：计算机中的数据还有声音、图像等其他数据对象

抽象数据类型(Abstract Data Type, ADT)

• 与数据类型一样需要定义数据对象、操作集、及数据对象中各个数据元素之间的关系。

• 与数据类型的唯一的区别是其对“数据对象”的定义是泛化的可以是任意你想要的类型

  • 如例2中的int就是一个数据类型

    • 其数据对象只能是$\left[-2^{31},2^{31} -1\right]$中的任意值

  • 而列3中的队列其实是抽象数据类型

    • 其数据对象是泛化的某一种数据集

---

什么是数据结构？

业界并无明确定义，算法导论中给出如下定义：

A data structure is a way to store and organize data in order to facilitate
access and modifications.

个人比较喜欢的定义是：数据结构是基于某一编程语言对抽象数据类型进行【高效】的实现。

通常所说线性表、队列、栈等其实说的是抽象数据类型，只给出相应的定义但不涉及具体的实现。

---

什么是逻辑结构？

数据结构这门主要就是教你干三件事：

1. 将现实世界中的事物以计算机能够理解的方式（符号化、离散化）存储到计算机中

   • 编程语言教会你符号化

   • 离散数学教会你离散化

2. 同时存储事物之间的逻辑关系

3. 高效地实现相应的操作

所谓逻辑结构指的是现实世界中事物间的逻辑关系。

• 因现实世界中的事物集已经被存储到了计算机中，所以就给其起了个泛化了的名字叫数据对象

• 所以课本上的定义是逻辑结构：是指数据对象中的数据元素之间的相互关系

  • 现实世界中的某一事物集 => 数据对象

  • 某一事物集合中的某一事物 => 数据元素

---

什么是物理结构/存储结构？

了解了逻辑结构，再来说说物理结构/存储结构。

课本中的定义：

• 物理结构：是指数据的逻辑结构在计算机中的存储形式

  • 翻译过来就是事物A与事物B的逻辑关系，在计算机中是如何表示的

得益于抽象，我们在编程时常常将内存看成是一片连续的存储单元（一个大数组）

• 存储结构：描述的是如何用存储单元之间的物理关系来表示现实世界中事物间的逻辑关系

  • 如果事物A与事物B是一对一关系，或优先关系即A优先于B

    • 用两个连续的存储单元来存储事物A和事物B即可

    • 优先可以通过规定先读取哪个存储单元或存储单元编号的大小来表示

  • 如果事物A与事物B、事物C是一对多关系

    • 可以使用三个连续的存储单元也可以用不连续的

    • 如果用不连续的存储单元，则存储事物A的存储单元需要记录存储B、C的存储单元的地址

    • 如果用连续的存储单元，可以根据存储单元编号的算术运输结构来表示

      • 二叉树根节点A，在数组的0地指处

      • 左子树根节点B，在数组的1地址处

      • 右子树根节点C，在数组的2地址处

全文完
$$