数据结构专题——那些难以理解的数据结构基本概念

不知有没有人和博主一样，在上大学的时候最头疼的一门课就是数据结构与算法了，其中枯燥的概念、冗长的伪代码都让博主昏昏欲睡。

尤其是严大妈在《数据结构》中开篇讲述的数据结构、数据类型与抽象数据类型的概念，让博主完美地将这三个概念混淆了很久(这里没有黑严大妈的意思……但是数据结构确实给当时没有认真听课的博主留下了深刻的印象)。

博主希望在这个系列的博文中将自己眼中的数据结构与各位同学进行分享，希望大牛们能不吝赐教或是对初学者能有一点帮助。

在本篇博文中我主要谈谈我对以下三个概念的理解，欢迎大家与我一起讨论。

• 数据结构
• 数据类型
• 抽象数据类型

首先来看数据结构的概念：

数据结构: 是相互之间存在一种或多种特定关系的数据元素的集合。这种结构可以是逻辑结构或者是物理结构。

逻辑结构是指数据之间的逻辑关系，比如

• 当所有数据都属于一个集合，而彼此之间没有别的关系时，这就是逻辑上的集合关系，如下图；

• 当数据之间有下图所展示的一一对应的关系时，就属于线性结构
  

• 当数据之间有下图所展示的一对多的关系时，就属于树形结构
  

• 当数据之间有下图所展示的多对多的关系时，就属于图形结构
  

物理结构是指数据如何计算机中存储的形式

若数据被存放在连续的存储单元中，则属于顺序存储结构,这种数据结构中数据间的逻辑关系和物理关系是一致的。这种数据结构很简单，最常见的例子就是数组。当我们向计算机申请创建一个装有 10 个整型元素的数组时，计算机会在内存中找一块连续的空间，按照一个整型元素所需的内存大小乘以 10，为这个数组开辟所需的内存空间，其中第一个元素放在第一个位置，第二个元素放在第二个位置，依次摆放，如下图所示。

若数据被存放在任意的存储单元中，则属于链式存储结构,这种数据结构中的数据存放位置可以是连续的，也可以是不连续的。数据间的存储关系并不能反应它的逻辑关系，因此需要指针来存放元素的位置，这样通过地址就可以找到相关联元素的位置了，如下图所示。

根据上述的概念来看，我们平常所说的树(Tree)、线性表(List)、图(Graph)都属于数据结构，因为它们的元素满足逻辑结构中元素的特定逻辑关系。

同样，以 Java 语言为例，ArrayList(基于数组实现的线性表)、LinkedList(链表)也属于数据结构，因为他们的元素在计算机中是以顺序与链式的物理结构来存储的。

逻辑结构是面向逻辑关系的结构，而物理结构是面向计算机存储的结构。对于我们程序员来说我们更倾向于关注物理结构，因此我们更习惯叫 ArrayList 这种线性表的实现为数据结构。

接下来我们来看数据类型的概念：

数据类型：是指一组性质相同的值的集合及在此集合上的一些操作的总称。

同样以 Java 语言为例，每一个变量在被声明的时候我们都需要指明它的数据类型。因为内存需要知道你这个数据应该被分配多大的空间。

同样的一个变量 i=12， 如果它被声明为 byte 类型就会被分配 8 bits 的空间，而被声明为 int 类型就会被分配 32 bits 的空间。

通常来说，数据类型分为原子类型和结构类型。

原子类型就是不可再分的基本类型：整型、浮点型等等

结构类型就是由若干个原子类型组成符合类型。

以 Java 为例，原子类型就是 8 个基本数据类型，而结构类型就是引用类型。对于 C 语言、或是 C++ 而言，原子类型就是基本类型，结构类型就是 struct。

但是不同的硬件系统在将这些数据类型转换为底层语言时肯定会有不同。这点对于 C 语言来说尤为明显，比如 int 类型没有固定的取值范围，而是依赖于硬件系统来决定。

因此这些我们人为为数据划定的“类型”就有硬件的局限性了。

这也是抽象数据类型出现的原因。

抽象数据类型：是指一个数据模型及定义在该模型上的一组操作

抽象数据类型可以解决上述 int 类型在不同硬件上有不同取值的问题。

比如说，我们可以抽象出一个数据类型叫做整型。那么在任何硬件系统中需要用到的整数类型以及整数的操作都可以在这个抽象类型中声明。至于在某种编程语言中将它实现为 32 位的 int 类型还是 16 位的 int 类型抽象类型都不需要关心。

以 Java 语言为例，线性表 List 是一个抽象数据类型；但 ArrayList 与 LinkedList 就不是抽象数据类型，因为这两种具体的数据结构已经是线性表的具体实现了，并不具有抽象性。

三者的关系总结

• 数据结构与数据类型的关系

数据结构是由一个个的数据元素组成的，而这些数据在声明的时候都会属于某一种数据类型。

• 数据结构与抽象数据类型的关系

逻辑数据结构一般也可以看作抽象数据类型；但物理数据结构不是抽象数据类型，而是抽象数据类型的具体实现。

• 数据类型与抽象数据类型的关系

数据类型是人为规定的平台相关的类型；而抽象数据类型是将数学模型和模型的相关操作抽象出来

注：本文图片来源于程杰老师的《大话数据结构》