讲解在线视频

这一节，我们来学习数据结构相关的概念和术语

第一个概念：数据。数据

是指计算机能够处理的任何信息

它是一种符号

在我们这门课当中

提到数据，都是在计算机的语境下来说的

第二

数据元素

它是指数据的基本组成单元。数据

实际上是由若干个数据元素构成的有限集

比如，刚才遇到的学生表当中的每一行，构成了学生表当中的一个数据元素

而学生表

就是由多个数据元素构成的。数据元素

简称为元素

第三个概念：数据项。数据元素

实际上还可以再分

数据元素的基本组成单元就是数据项

比如，刚才学生表当中的每一行

它实际上可以继续分为很多的列

比如，学生的编号、

学生的姓名、

年纪等等

这些列

往往是不能继续再去划分的

所以数据项具有原子性

意味着不能再去划分

第四个概念：数据结构。数据结构

是具有一种或多种关系的数据元素的集合

这里强调了两个方面

就是数据元素以及关系

所以

我们经常把数据结构用形式化的语言描述成两个部分

第一个部分是D，第二个部分是R

它们分别代表数据元素和元素之间的关系

下一个概念：逻辑结构

所谓逻辑结构

是站在真实世界

站在现实世界，去观察数据元素以及它们之间的关系

注意，是数据元素在真实世界当中所体现出来的关系

我们把它叫逻辑结构。意味着，逻辑结构

跟计算机没有任何关系

有四种逻辑结构。第一种

是集合结构

在集合结构当中

若干个元素同属于一个集合

除此之外

它们之间再没有其他明显的关系

在集合这种离散的数据结构当中

因为元素间没有其他明显的关系

所以，我们在这门课当中，就不关注

集合这种数据结构了

第二种

是线性结构

在线性结构当中

元素之间存在着一对一的关系

比如，图当中的圆圈代表着数据元素

圆圈之间的连线代表着元素之间的关系

至于这里的连线具体代表什么关系

取决于你的应用

我们这里就把关系抽象成连线，元素

抽象成圆圈

第三种是树形结构

树形结构实际上就来源于现实世界当中的树。一个结点

有多个子结点——从上往下看的话

那么从下往上看，一个结点

它有唯一的一个父结点

元素之间是呈一对多关系的

最后一种

叫图形结构，或者说网状结构

在这种结构当中

任何两个元素之间都可能具有关系

所以，元素之间的关系是多对多的关系

我们刚才讲的文件系统

实际上就是树形的结构。互联网的拓扑架构

实际上就是图形的结构

再来看

物理结构

物理结构跟逻辑结构相对应

逻辑结构站在现实世界当中来观察数据结构，物理结构呢

是站在计算机的世界来观察数据结构

这里的计算机，我们前面在课程介绍的时候

曾经提到过：在数据结构这门课当中

凡是提到计算机，提到硬件

都是指内存

也就是站在内存的角度来观察数据结构

数据元素

在内存当中

如何存储、

元素之间的关系在内存当中如何实现

这就是物理结构

有两种物理结构

分别是顺序结构和链式结构。顺序结构

也称为顺序存储，链式结构也称为链式存储

现在，我们来看第一种物理结构：顺序结构。顺序结构

是用一段连续的内存来存放元素。元素之间的关系

实际上就是用元素在内存上所占的位置来表达的

那些逻辑上相邻的元素

它们在

内存上、在存储单元当中也是相邻的

究其本质

顺序结构就是用元素在物理位置

也就是内存上的相邻来表示

这些元素在真实世界、在逻辑上的相邻

我们可以来了解一下内存的结构

内存

实际上是由若干个字节线性排列构成的

这里每一个横向的格子都代表一个字节

八位的

它里面可以存八个比特、八位的二进制数

每一个字节

都有一个唯一的编号

这个编号

我们写在格子的外面

通常我们是用16进制

来描述每一个字节的编号

因为如果用二进制的话，太长了

字节的编号是连续的

每一个字节都有一个唯一的编号

通常

我们在纸上、在图上画内存的时候

我们一般上小下大

什么意思呢

就是：画在上面的字节

它的编号要小一些

画在下面的字节，编号要大一些

这只是一种约定

这就是内存的结构

如果我们用顺序结构来表示

数学上、线性代数当中的向量

向量中的元素是有位序之分的

比如[1, 2, 3]

它跟[1, 3, 2]是不等价的

所以，我们在存储1、2、3的同时，必须保持1、2、3之间的这种位序关系

我们用顺序存储，那些逻辑上相邻的元素

它们在内存上也相邻

这就是顺序存储

你看1和2

它们在逻辑上是相邻的

那么，它们在内存上也是相邻的

它们占据的存储单元是相邻的

这就是顺序结构

的本质

再看第二种物理结构：链式结构。链式结构

不要求元素占据的内存单元是连续的

这时候，元素可以占任意的内存单元。既然元素

占任意的内存单元

那如何还原出这些元素

在真实世界当中的逻辑关系呢

所以，链式结构除了存放元素本身的值之外

还需要存放元素之间的

关系，这个关系

就是以与当前元素有关系的那个元素

它的存储位置来实现的。这个位置

实际上就是C语言当中的指针

或者说是链

我们在记录每一个元素

自身的信息之外，还需要记录与这个元素有关系的下一个元素

它的存放位置

这样我们才能通过内存

找到元素的值以及与这个值相关联的下一个元素

它在哪

还是刚才存储向量的例子

如果我们用链式方式来存

那可能是这样

现在，1、2、3

这些元素它们占的内存是任意

不一定连续

比如，1存放在这里

1这个值我们存放下了

那它的下一个元素2，假设存放在这里

只存放值，很明显

无法还原1和2之间的逻辑关系

除了存放值之外

我们在1的后面，紧接着存放2这个值所在的内存单元的地址

假设2是存放在2019H

注意这里是16进制数，它是地址

那我们在1的后面

就存放一个2019H

当然

2019H是4位的16进制数

可能占据的是两个字节

那这时候呢

我们就不

细分这两个字节了

1的后面存放了一个地址

CPU

在找到1之后

它能根据1后面的2019H这个地址，寻址到相关的字节单元

从而找到2这个元素

2后面可能存放的是3019H

而3这个元素

就存放在编号为3019H的这个字节里。那3019H里面的3是向量的最后一个元素

它没有下一个元素了

那我们就用空来表示。在图当中呢

我们一般用这样的符号来表示空地址

实际上，在内存当中

就是一个16进制的0

就是八位的0

我们来对比一下逻辑结构和物理结构

逻辑结构关注的是元素及其关系

在真实世界、在自然世界当中的呈现

也就是说

只用描述出：元素有哪些、

这些元素之间的关系是什么

逻辑结构跟计算机是没有任何关系的

而物理结构

是站在内存的角度，来观察这些元素

如何组织、元素之间的关系

在内存当中如何实现

我们可以从四个维度，来比较一下逻辑结构和物理结构。第一个维度：关注点

如果用英文单词

那么逻辑结构

它强调的

是Representation——呈现，这个呈现都是向外部世界呈现

而物理结构

关注的是实现(Implementation)——元素和关系

在计算机当中如何真正的实现

如果我们从软件的使用

这个维度来看

那么，逻辑结构实际上是对应着软件的用户、软件的使用者。软件的用户

通常都是不懂技术的

他们无需知道一个软件是怎么开发出来

他们只需要知道这个软件怎么用、提供了哪些功能、

怎么用这些功能就可以了

而物理结构

是对于软件开发者

来说的

开发者

程序员必须知道一个功能

真正怎么来实现、怎么编程来实现这个功能

如果我们从编程语言、从面向过程的编程语言这个维度来看

逻辑结构实际上对应着函数的原型声明。大家学过C语言，都知道

如果函数调用语句出现在了函数定义之前

需要在调用之前

加上被调函数的原型声明

原型声明是没有函数体的

只用告诉计算机：一个函数它的名字叫什么

它的返回值类型是什么

它有哪些参数

每个参数的类型是什么，就可以了

而物理结构

对应的函数的定义，也就是带函数体的常规函数

一个函数

它的功能是如何实现的

必须在函数体当中，用语句

来实现

第四个维度

如果我们从面向对象的编程语言来看，逻辑结构

实际上代表的一些接口

我们知道，接口里面

都是抽象方法

抽象方法也是没有函数体、

没有方法体的。抽象方法实际上就是告诉计算机：一个方法

名字叫什么

返回值类型是什么

有什么样的参数

有这些信息就可以了

而物理结构呢，就是接口对应的实现类

接口的实现类必须去重写

接口里面的抽象方法，是必须带方法体的

你必须告诉计算机：一个函数的功能

它是具体如何来实现的。四种逻辑结构

各自都可以以两种物理结构来表示

比如刚才的集合

线性结构

树形结构和图

它们各自都可以用顺序结构和链式结构来实现

两种物理结构具有完全不同的操作特性

那么，用哪种物理结构来实现，完全取决于你的需求

看你看重哪一方面的需求

比如，如果要经常对一些数据进行增加、删除的操作

这时候采用链式结构比较合适

我们后面会讲到，在链式结构当中，元素的删除和增加

是不需要移动元素的

而与之对应的顺序存储是需要移动元素的

反过来说

如果你看中的是找元素比较快

很少对元素进行增加和删除

这时候采用顺序结构比较合适

因为它支持随机存取

我们后面都会讲到