1、基本概念

1.1 数据-data

数据是能输入计算机且能被计算机处理的各种符号的集合。数据是信息的载体，是对客观事物符号化的表示，数据能被计算机识别，存储和加工。

数据包括数值型数据：整数、实数等；和非数值型数据：文字，图像，图形和声音等。

1.2 数据元素-data element

数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素也简称为元素，或者称为记录，节点或者顶点。

1.3 数据项

    数据项是构成数据元素的不可分割的最小单位。综上介绍可知，数据由数据元素组成，数据元素又由数据项组成。

1.4 数据对象-data object

\qquad 数据对象是性质相同的数据元素的集合，是数据的一个子集。例如，整数数据对象是集合N={0,−1,+1,−2,+2,...}。

2、数据结构-data structure

数据结构是指相互之间存在一种或者多种特定关系的数据元素的集合，或者说是带结构的数据元素的集合。

数据结构包括以下三个方面的内容：(1)数据元素之间的逻辑结构；(2) 数据元素及其关系在计算机内存中的表示(映像)，称为数据结构的物理结构或者存储结构；(3) 数据的运算和实现，即对数据元素可以施加的操作以及这些操作在相应的存储结构上的实现。

2.1 逻辑结构的种类

划分方法一可以划分为：线性结构和非线性结构。

线性结构：有且仅有一个开始和一个终端结点，并且所有节点都最多之后一个直接前趋个一个直接后继。例如：线性表，栈，队列，串。

非线性结构：一个节点可能有多个直接前趋和直接后继。例如：树，图。

划分方法二可以划分为：四类基本逻辑结构。

集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其他关系；

线性结构：结构中的数据元素之间存在着一对一的线性关系；

树型结构：结构中的数据元素存在着一对多的层次关系；

图状结构或者网状结构：结构中的数据元素之间存在着多对多的任意关系。

2.2 存储结构的种类

有以下四种基本的存储结构：顺序存储结构；链式存储结构；索引存储结构和散列表存储结构。

2.2.1 顺序存储结构

用一组连续的存储单元依次存储数据元素，数据元素之间的逻辑关系由元素的存储位置来表示。C语言中用数组来实现顺序存储结构。

2.2.2 链式存储结构

 用一组任意的存储单元存储数据元素，数据元素之间的逻辑关系用用指针来表示。C语言中用指针实现链式存储结构。

2.2.3 索引存储结构

在存储节点信息的同时，还建立附加的索引表。

索引表中的每一项称为一个索引项，索引项的一般形式是：(关键字，地址)；关键字是能唯一标识一个节点的那些数据项；若每个节点在索引表中都有一个索引项，则该索引表称之为稠密索引(Dense Index)。若一组节点在索引表中只对应一个索引项，则该索引表称之为系数索引(Sparse Index)。

2.2.4 散列存储结构

根据节点的关键字直接计算出该节点的存储地址。如下图所示：

3、数据类型和抽象数据类型

C语言中提供了int, char flaot, double等基本数据类型；数组、结构，公用体，枚举等构造数据类型；还有指针，空类型。一些最基本的数据结构可以用数据类型来实现，如数组、字符串等；而另一些常用的数据结构，如栈，队列，树，图等，不能直接用数据类型来表示。

数据类型是一组性质相同的值的集合以及定义于这个值集合上的一组操作的总称。

数据类型=值的集合+值集合上的一组操作

抽象数据类型可以用(D，S，P)三元组表示。其中：D是数据对象；S是D上的关系集；P是对D的基本操作集。其中基本操作的定义格式为：基本操作名(参数表)；初始条件(初始条件描述)；操作结果：(操作结果描述)。

抽象数据类型的定义举例：Circle 的定义：