注意：以下文字和图片大部分摘选自《大话数据结构》和严老的《数据结构 C语言》第二版

数据结构

数据结构研究的主要问题： 非数值的计算程序设计 中的 操作对象 、以及 它们之间的关系和操作 等相关问题。

程序设计的实质： 对所处理的问题选择一种好的 数据结构 ，在结构基础上加上一种好的 算法 。

数据结构是一个介于 数学、计算机硬件、计算机软件 之间的学科。

数据

数据（Data）： 是描述客观事物的符号， 可以输入到计算机中 ，并且 可以被计算机识别和处理 的符号集合。
数据元素（Data Element）： 是组成数据的基本单位，在计算机中通常作为整体处理，也被称为 记录（record）、结点（node） 。
数据项（Data Item）： 是 组成数据元素 的，具有单独含义，不可分割的 最小单位 （同时也是数据的最小组成单位）。
数据对象（Data Object）： 具有 相同性质 的 数据元素 的集合，是数据的一个子集。
数据结构（Data Structure）： 相互之间存在 一种或多种特定关系 的 数据元素 的集合。

数据

结构

按照不同角度分析，数据结构一般会被分为 逻辑结构 和 存储结构（也称物理结构） 两层次。

数据结构

逻辑结构

逻辑结构： 是指 数据对象中数据元素之间的相互关系 ，也可以看成是从逻辑关系上描述数据元素，与数据的存储无关。
逻辑结构分为 线性结构和非线性结构 （树结构、图结构或网状结构、集合结构）

逻辑结构

逻辑结构层次图

1. 线性结构： 线性结构的数据元素是一对一的关系。
2. 集合结构： 集合结构的数据元素除了同属于一个集合外，它们之间没有其他关系。
3. 树结构： 树结构的数据元素是一对多的关系。
4. 图结构或网状结构： 图结构的数据元素是多对多的关系。

如何用示意图查看逻辑关系：

• 将每一个数据元素看成一个结点，用圆圈表示
• 数据元素之间的逻辑关系用结点之间的连线表示，如果这个关系是有方向的，那么用带箭头的连线表示

物理结构（存储结构）

物理结构： 是指 数据元素 和 数据元素的逻辑关系 在计算机的 存储形式 。

数据元素在计算机中有两种基本的存储结构，分别是 顺序存储结构 和 链式存储结构 。

（1）顺序存储结构

顺序存储结构： 是把数据元素 存储在地址连续的存储单元里 ，其数据间的逻辑结构和物理结构是一致的。是借助 元素在存储器中的相对位置 来表示数据元素之间的逻辑关系，通常借用程序设计语言中的数组类型来描述。

（2）链式存储结构

链式存储结构： 是把 数据元素存储在任意的存储单元 里，这组存储单元 可以是连续 的，也 可以是不连续 的。 无需占用一整块存储空间 。但为了表示数据元素之间的关系，需要 给每个结点附加指针属性，用来存储后继数据元素的存储地址 。

数据类型

数据类型（Data Type）：是指 一组性质相同的值的集合 以及 定义在该集合上的操作 的总称。

抽象： 抽取出实际问题和事物具有的普遍性的本质。

抽象数据类型（Abstract Data Type ，简称 ADT ）： 指 一个数学模型 以及 定义在该模型上的一组操作 。
抽象数据类型的定义只取决于它的逻辑结构，与怎么在计算机中表示和实现无关。

“抽象”的意义在于数据类型的数学抽象特性。

一个数据类型定义了以下三部分：
①一个 数据对象
②数据对象中 各数据元素之间的关系
③ 数据元素的操作 。

抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。

抽象数据类型的标准格式

其中，数据对象和数据关系的定义采用数学符号和自然语言描述，基本操作的定义格式如下：

基本操作的定义格式

注意：
抽象数据类型是在 概念层（又称抽象层） 上描述问题，而类相当于在 实现层 上描述问题。