数据结构与算法：探索数据类型的秘密

一开始的坚持总是容易的，因为热血还未退却，激情仍在燃烧，所以趁着这股劲，本系列的第一篇开始了！开始后续真正数据结构和算法的学习之前，需要先弄清楚一些简单的概念，比如数据结构，数据类型及抽象数据类型。

数据结构和数据类型

计算机是处理数据的机器，而数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。

在第 0 篇中提到，根据维基百科：数据结构 (data structure) 是计算机中存储、组织数据的方式。严老师在《数据结构》中阐述的：

1. 数据结构：是相互直接存在一种或多种特定关系的数据元素的集合，包括逻辑结构和物理结构；

1. 数据类型：是一个值的集合和定义在这个值集上的一组操作的总称；

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

数据结构：

是用来反映一个数据的内部构成，即一个数据由哪些成分数据构成，以什么方式构成，呈什么结构。逻辑上的数据结构反映成分数据之间的辑关系，物理上的数据结构反映成分数据在计算机内的存储安排。数据结构是数据存在的形式。

数据结构，分为数据的逻辑结构和物理结构

数据的逻辑结构：数据元素之间的逻辑关系 => 集合结构；线性结构；树形结构；图形结构

数据的物理结构：数据元素在计算机存储器中是如何存储的 => 顺序存储（存放在连续的内存地址中）；链式存储（数据通过指针指向下一存储地址，不一定存储在连续的地址空间）

数据类型：

数据是按照数据结构分类的，具有相同数据结构的数据属同一类。同一类数据的全体称为数据类型。在程序设计高级语言中，数据类型用来明一个数据在数据分类中的归属。它是数据的一种属性。这个属性限定了该数据的变化范围。为了解题的需要，根据数据结构的种类，高级语言定义了一系列的数据类型。不同的高级语言所定义的数据类型不尽相同。

数据类型是一个值的集合和定义在这个值上的一组操作的总称。按照值的不同，高级程序设计语言中数据类型可分为两类：一类是非结构的原子类型，另一类是结构类型。

抽象数据类型

抽象数据类型的含义可理解为数据类型的进一步抽象。即把数据类型和数据类型上的运算捆在一起，进行封装。引入抽象数据类型的目的是把数据类型的表示和数据类型上运算的实现与这些数据类型和运算在程序中的引用隔开，使它们相互独立。

对于抽象数据类型的描述，除了必须描述它的数据结构外，还必须描述定义在它上面的运算（过程或函数）。抽象数据类型上定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。

抽象数据类型实际上就是对该数据结构的定义。因为它定义了一个数据的逻辑结构以及在此结构上的一组算法。

抽象数据类型只是在数据的逻辑结构上讨论问题，与数据的存储结构无关。

计算机科学中有两种常见的抽象：

procedural(functiona) abstraction: 过程抽象，指使用一个函数或方法而忽略它的具体实现。

data abstraction: 数据抽象，指数据类型的属性（值和操作方法）与数据类型的具体实现分离。

简言之，数据结构是数据储存及逻辑的具体表现和实现方式，它的目标是为了高效地储存和检索数据；而抽象数据类型是数据类型的抽象，它是通过其上的可执行的操作以及这些操作的效果的数学约束的间接定义。

数据结构和抽象数据类型的一些典型例子：

作者：crxmai

來源：简书