数据结构

基本概念

一、数据

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

通俗点来说，一个字符，一段文字，一段音频，甚至一部电影，都可以说是数据。而站在计算机的角度来看，数据就是一串0101二进制字符。

二、数据元素、数据项

数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素由若干个数据项组成。数据项是构成数据元素不可分割的最小单位。例如：这张中国富豪排行榜上，每一行的信息看做一个整体，就是一个数据元素；数据项就是每一行对应的中国排名、世界排名、名字、财富来源、年龄。

2021中国富豪排行榜

三、数据结构、数据对象

所谓“结构”，就是用来描述元素之间的逻辑关系的。那顾名思义，数据结构指的是数据之间的相互关系；数据对象的是具有相同性质的数据元素之集合。还说富豪榜的例子，按财富从高到低排名，钱多的在前，钱少的在后，这样的先后关系就是数据之间的结构。具有这样结构的数据元素放在一起，就组成了一个数据对象。数据对象是数据的子集。

总结来说，数据对象是具有相同性质的数据元素的集合，是数据的一个子集；数据结构是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构关心的是各个数据元素之间的逻辑关系，以及对数据的各种操作，而不在意数据的内容是什么样的。那么当我们在设计一个数据结构的时候，应该注意数据节结构的哪些方面呢？

数据结构的三要素

一、逻辑结构

逻辑结构
1.集合结构

集合结构

这个概念和数学里的逻辑集合是一样的。例如：中国最有钱的10个人中就可以构成一个集合，而你我这样的普通人是不属于这个集合的。

线性结构

线性结构

数据元素之间是一对一的关系，除了第一个元素和最后一个元素之外，任何一个元素都有惟一的前驱和惟一的后继。比如：富豪排行榜中除了排行第一个的和排行最后一个的人，中间的每一个人都有一个人在他的前面，也总有一个人在他的后面。说的专业一点儿，除了首部和尾部，每一个元素都有自己的前驱和自己的后继。拥有这种唯一前驱和唯一后记结构的数据的结构，称为线性结构。
树形结构

树形结构

数据元素是一对多的关系。例如我们的磁盘文件夹的层层包含的关系，就是一个树形结构。
图结构

图结构

数据元素是多对多的关系。这种结构在生活中也很常见，比如我们在描述两个城市或者几个城市之间互相是否存在一条道路，也就是地图。用到的就是这种图结构。

二、数据的运算

针对某一种逻辑结构，结合实际需求定义出来的基本运算。例如：2021中国富豪排行榜（我们已经知道这是一个线性结构），我们就针对这一线性逻辑结构，结合和实际需求，定义如下几种运算：

来查找第i个数据元素
在第i个位置插入新的数据元素
删除第i个位置的元素
这是一个特例，只针对这一个富豪排行榜的操作，但是我们完全可以把这些运算扩展到其他的拥有线性结构的数据结构上去。
从确定逻辑结构，到定义几种运算，我们就相当于定义出来了一种数据结构。接下来我们要用计算机去实现这一数据结构，那么就要考虑数据结构的第三个要素了物理结构了。

三、物理结构

物理结构由叫做存储结构，这里我们要讨论的是如何用计算机表示数据元素的逻辑关系。一般来说存储结构分为四种：顺序存储、链式存储、索引存储和散列存储。接下来，我们以线性逻辑结构为例，来探讨如何用计算机表示出这种关系：

顺序存储：
把逻辑上相邻的的元素存储在物理上也相邻的存储单元中，元素之间的关系由单元之间的邻接关系来体现。

顺序存储
链式存储
逻辑上相邻的元素在物理位置上是可以不相邻的，借助元素存储地址的指针来表示元素之间的顺序关系。

链式存储.png
索引存储
在存储元素信息的同时，还建立一个附加的索引表。索引表中的每一项称为索引项，索引项的一般形式是(关键字，地址)。所谓关键字就是可以区分这些数据元素的数据项，例如：我们每一个人都有唯一的身份证号码，那么这个身份证号码就可以作为区分的关键字。再例如，富豪排行榜中的姓名，就可以作为关键字(我们假设没有重名的情况)，当我们需要查询某一个数据元素时，可以姓名作为关键字。

索引存储
散列存储
散列存储又叫哈希(Hash)存储，会根据元素的关键字直接算出元素的存储地址。这里先不多说，后面会单独介绍。

除了顺序存储之外，其他的存储方式在实际的物理内存空间中都是不相邻的，因此我们把链式存储、索引存储、散列存储都通称为非顺序存储。

若采用顺序存储，则各个元素之间在物理内存上必须是连续的；若采用非顺序存储，则各个数据元素的物理空间可以是离散的。

数据的存储会结构会影响存储空间的方便程度。例如：我们要采用顺序存储的方式存放一百万条数据，这就必须要求实际的物理内存空间有足够大的而且是连续的空间，否则是不能进行存储的。而采用其他存储方式则不然，即使没有那么大的一块连续空间，也可以进行数据的存储。

数据存储结构会影响对数据的运算速度。如过我们是按照顺序存储的方式存储数据，想要插入一个数据，就必须对数据进行大量的移动操作才能保持这种顺序关系。这是十分耗时的事情。但是如果我们采用链式存储的方式，只需要修改指针的指向即可。其中的细节会在线性表中介绍。同时，这里要指出的是运算的定义是针对逻辑结构的，其目的在于指出运算的功能。而运算的实现是针对存储结构的，其目的在于指出具体的操作步骤。

补充：数据类型与抽象数据类型

数据类型

数据类型是一个值的集合和在此集合上的一组操作的总称。数据类型分为原子类型和结构类型。

原子类型，其值不可再分割的数据类型。例如bool类型，值的范围为true和false，可以进行的操作是与、或、非等。int 类型，值的范围是-2147483648~2147483647，可以进行的操作是加、减、乘、除、模运算等等。
结构类型，其值可以再分解为若干成分（分量）的数据类型。在C语言里面常见的就是结构体：

//定义一个“人”结构体
struct Person
{
   char * name;  //姓名
   int age;     //年龄
};

那么对于这个Person数据类型，我们也可以定义出来一些基本的操作。比如修改姓名，计算与另一个人的年龄差值等等。只不过我们不能使用C语言里面的那些符号运算符，但是我们完全可以把这些运算封装成一个一个的函数。

抽象数据类型（Abstract Data Type，ADT）

抽象数据类型是抽象的数据组织以及与之相关的操作。当我们定义出来一个抽象数据类型的时候，就是定义出来了一个完整的数据结构。

上文列出的结构体就可以看成一个抽象数据类型。我们以struct Person结构体为例来做一些解释以加深理解：它的数据组织就是一个char* 数据类型和一个int 数据类型的一个组合。我们知道，int类型的数据可以被这样定义出来: int a。同样的，我们定义出来一个变量：struct Person p。int数据类型可以进行加、减、乘、除的运算。而Person类型的数据也可以有自己的运算，只不过这里我们没有定义出来罢了，而这些运算正是需要这个数据结构的实现者来完成的。

数据结构的使用者只需要知道它的逻辑结构和与之相关的操作即可。而这个数据结构的实现者，还应该要知道如何存储这些数据元素，以及如何实现这些相应的运算。可以这么说，抽象数据类型就是对一个数据结构的逻辑特性的描述。