@[toc]
概要
本篇文章将讲解数据结构的基本概念和术语，这种概念性的东西往往是催人入睡的，当然了，没有谁能把概念讲出花来，概念就是枯燥的。
由于专栏的体系，我有必要讲一讲关于数据结构的基本概念和术语。
数据(data)
数据是指能输入计算机且能被计算机处理的各种符号的集合。
数据是信息的载体，是对客观事物符号化的表示，能够被计算机识别、存储和加工。
数据通常分为两类：
- 数据型：整数、实数等
- 非数值型：文字、图像、声音等
数据元素(data element)
数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。比如下面的一张学生表：
| 学号 | 姓名 | 性别 | 身份证号 |
| :--: | :--: | :--: | :----------------: |
| 001 | 张三 | 男 | 123456789123456781 |
| 002 | 李四 | 男 | 123456789123456782 |
| 003 | 王五 | 女 | 123456789123456783 |
其中的某个学生的信息就为一个数据元素，一个学生的所有信息，包括学号、姓名、性别、身份证号等通常会作为一个整体处理。
数据项(data item)
数据项是构成数据元素的不可分割的最小单位，还是上面的学生表，对于一个数据元素来说，比如学号为002的学生李四，该条数据元素由四个数据项组成，分别是：学号、姓名、性别和身份证号。
数据对象(data object)
数据对象是性质相同的数据元素的集合，是数据的一个子集。
例如整数集合{0，±1，±2，±3，......}，该集合中的所有元素都为整数，所以可以称其为整数数据对象。
又例如字符集合{'A'，'B'，'C'，......}，该集合中的所有元素都为字符，所以可以称其为字符数据对象。
数据结构(data structure)
数据元素不是孤立存在的，它们之间存在着某种关系，数据元素之间的关系称为结构。
数据结构包括以下三个方面的内容：
- 数据元素之间的逻辑关系，也称为逻辑结构
- 数据元素及其关系在计算机内存中的表示，称为数据的物理结构或数据的存储结构
- 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现
下面就来说一说逻辑结构和物理结构的概念。
逻辑结构：
- 描述数据元素之间的逻辑关系
- 与数据的存储无关，独立于计算机
- 是从具体问题抽象出来的数学模型
物理结构：
- 数据元素及其关系在计算机存储器中的结构，即：存储方式
- 是数据结构在计算机中的表示
它们的关系是：存储结构是逻辑关系的映像与元素本身的映像。
逻辑结构的种类
对于逻辑结构，我们通过是否为线性可将其分为线性结构和非线性结构。
线性结构：通常有且仅有一个开始和一个终端结点，并且所有的结点都最多只有一个前驱和一个后继，结点之间是一对一的关系。
典型代表：线性表、栈、队列、串非线性结构：一个结点可能有多个直接前驱和直接后继，结点之间是一对多，或者多对多的关系。
典型代表：树、图
我们还可以通过数据元素之间关系的不同特性，将其分为集合、线性结构、树形结构和图状结构。
- 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系
- 线性结构：结构中的数据元素之间存在着一对一的线性关系
- 树形结构：结构中的数据元素之间存在着一对多的层次关系
- 图状结构：结构中的数据元素之间存在着多对多的任意关系
存储结构的种类
对于存储结构，我们通常将其分为四类：顺序、链式、索引、散列存储结构。
- 顺序存储结构：用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示，在C语言中用数组来实现顺序存储结构
- 链式存储结构：用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用指针表示，在C语言中用指针来实现链式存储结构
- 索引存储结构：在存储结点信息的同时，还建立附加的索引表，比如手机的通讯录，通讯录在联系人信息的基础上建立了字母索引，对联系人进行排序
- 散列存储结构：根据结点的关键字直接计算出该结点的存储地址
数据类型和抽象数据类型
在使用高级程序设计语言编写程序时，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。
何为数据类型？
数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的统称。
那么为何抽象数据类型？
抽象数据类型(Abstract Data Type，简称ADT)是指一个数学模型以及定义在该模型上的一组操作的统称。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。
抽象数据类型的形式定义
抽象数据类型可用三元组(D、S、P)表示，其中：
- D：数据对象
- S：D上的关系集
- P：对D的基本操作集
其定义格式如下；
ADT 抽象数据类型名{
数据对象：<数据对象的定义>
数据关系：<数据关系的定义>
基本操作：<基本操作的定义>
}ADT 抽象数据类型名
其中数据对象、数据关系的定义用伪代码描述。
对于基本操作的定义格式如下：
- 基本操作名(参数表)
- 初始条件：(初始条件描述)
- 操作结果：(操作结果描述)
概念总是晦涩难懂的，下面通过一个具体的例子理解一下抽象数据类型是如何定义的：
ADT Circle{
数据对象：D = {
r,x,y|r,x,y为实数}
数据关系：R = {
<r,x,y>|r为半径,<x,y>为圆心坐标}
基本操作：
Circle(&C,r,x,y)
操作结果：生成一个圆
double Area(C)
初始条件：圆已经生成
操作结果：计算圆的面积
double perimeter(C)
初始条件：圆已经生成
操作结果：计算圆的周长
......
}ADT Circle
这是一个Circle类型的定义。
抽象数据类型如何实现
说完了抽象数据类型的定义，我们来看看该如何实现抽象数据类型。
抽象数据类型可以通过固有的数据类型(如整型、实型、字符型等)来表示和实现。
即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。
下面我们通过C语言作为描述工具来实现一下。
typedef struct{
float r; //半径
int x; //横坐标
int y; //纵坐标
}Circle; //定义抽象数据类型
void Circle(&C,r,x,y); //生成圆
double Area(C) //计算圆的面积
double perimeter(C) //计算圆的周长
这里只是演示，所以并没有实现定义的函数功能。
