一、基本概念

数据（data）是指所有能输入到计算机中并被计算机程序处理的符号的总和。

数据元素（data element）是数据的基本单位，可由多个数据项组成。

数据项（data item）是数据不可分割的最小单位。

数据对象（data object）是性质相同的数据元素的集合，是数据的一个子集。

数据结构（data structure）是相互子集存在一种或多种特定关系的数据元素的集合。

——《数据结构（C语言版）》

简而言之：

（1）数据（全世界）

（2）数据对象（狗）

（3）数据元素（我家的小白）

（4）数据项（小白的体重）

（5）数据结构（关系 + 数据元素）

---

二、所谓数据结构之一

在任何问题中，数据元素都不是独立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。

根据数据元素之间关系的不同特性，通常有下列4类基本结构：

（1）集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

（2）线性结构：结构中的数据元素之间存在一个对一个的关系。

（3）树形结构：结构中的数据元素之间存在一个对多个的关系。

（4）图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。

——《数据结构（C语言版）》

图1-1

把“连线”设置为发光，是为了强调关系的重要性，数据结构包含两个部分——元素及其关系。

元素无所谓，可以是数字，可以是字符，但是关系是可以事先确定的，是具体的，它不像元素可以泛指，所以在数据结构中关系是更为重要的，《数据结构》这门课主要强调和研究的也是关系。

根据关系的不同，进而延伸出了许多算法，可以这么说，算法和数据结构是密不可分的（虽然有的学校会独立地开设两门课，一门叫数据结构，一门叫算法导论，这其实是为了强调算法的重要）。

很多人都听过这么一句话——“程序设计 = 数据结构 + 算法”，这句话很重要，可以说贯穿了一个计算机专业的学生的一生。

即使参加工作后身边的人总在说“程序设计 = 框架 + 库 + 复制粘贴”，也别放弃了大学时那股“深入底层”的精神。

你是想当一个码农，还是程序员？（我们可以借用别人写好的代码，有现成的为什么不同呢，前提是请先读懂它）。

---

三、所谓数据结构之二

结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。

数据结构在计算机中的表示（又称映射）称为数据的物理结构，又称存储结构。

在计算机中表示信息的最小单位是二进制数的一位，叫做位（bit）。

我们可以用一个由若干为组合起来薪酬的一个位串表示一个数据元素，通常称这个位串为元素（element）或结点（node）。

位串中对应于各个数据项的子位串称为数据域（data field）。

因此，元素或结点可看成是数据元素在计算机中的映射。

——《数据结构（C语言版）》

之前所说的集合、线性结构、树形结构、图状结构都是逻辑结构，也就是所谓的数学模型，我们能在纸上画出来的结构一般来讲就是逻辑结构，逻辑结构只是一种想法、一条思路。

而像pArr->pbase = (int *)malloc(sizeof(int)*length);这种具体的代码执行后计算机内部的存储信息，便是物理结构。

简而言之，画在纸上的是逻辑结构，通过具体代码实现的是物理结构。

一般遇到一个现实中的问题，需要用计算机来解决，则有以下步骤：

（1）分析该问题适合的结构类型（比如公交车线路的设计，就适合用图状结构）

（2）设计该问题的算法（理论上可行的办法）

（3）编写具体代码（将理论转换为实践）

---

四、抽象数据类型

抽象数据类型（abstract data type，简称ADT）是指一个数学模型及其定义在改模型上的一组操作。

——《数据结构（C语言版）》

本来数据结构是由两个部分组成的——元素和关系。

现在呢，它加了一个，加了一个操作。

于是乎，就变成了这个样子（按照C语言里strcut的风格）：

ADT 抽象数据类型名{

数据对象：数据对象的定义

数据关系：数据关系的定义

基本操作：基本操作的定义

}ADT 抽象数据类型

其中基本操作的格式为（按照C语言里function的风格）：

基本操作名（参数表）

初始条件：初始条件的描述

操作结果：操作结果的描述