本章主要总结了数据结构的基本概念和定义。

数据结构三要素：逻辑结构、存储结构（物理结构）以及数据的运算（算法）。

数据结构的存储结构有四种，分别是顺序存储、链式存储、索引存储以及散列存储。本节主要介绍前两种。

数据的运算定义是基于逻辑结构的，而运算实现是基于存储结构的。同一逻辑结构的不同存储结构的运算的实现是不同的

基本概念

数据是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素是数据的基本单位，在计算机程序中通常作为一个整体来进行考虑和处理。

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

逻辑结构

数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 这里说的是逻辑结构而非存储结构。

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

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

  1. 集合：结构中的数据元素除了同属一个集合外，别无其他关系。
  2. 线性结构：结构中的数据元素之间存在一对一的关系。（线性表、栈、队列等）
  3. 树形结构：结构中的数据元素之间存在这一对多的关系。
  4. 图状结构或网状结构：结构中的数据元素之间存在多对多的关系。

数据结构的形式定义为：

数据结构是一个二元组 $Data_Structure = (D,S)$ ，其中 $D$是数据元素的有限集，$S$ 是 $D$ 上关系的有限集。

上述数据结构的定义仅是对操作对象的一种数学描述，是从操作对象抽象出来的数学模型。

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

存储结构

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

它包含数据元素的表示和关系的表示。

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

在计算机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。

当数据元素由若干项组成时，位串中对应于各个数据项的子位串成为数据域。

元素或结点可看成数据元素在计算机中的映像。

数据元素之间的关系在计算机中有两种不同的表示方法：顺序映像和非顺序影像，由此有两种不同的存储结构：顺序存储结构和链式存储结构。

顺序影像的特点是借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。

数据类型

数据类型是和数据结构密切相关的一个概念，用以刻画操作对象的特性。类型明显或隐含的规定了在程序运行期间变量或表达式所有可能的取值范围，以及在这些值上允许的操作。

数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 例如C语言中的整数，其值集为某个区间上的整数（区间大小依赖于不同的机器），定义在其值集上的操作有加减乘除以及取模等算术运算。

按值的不同特性，高级程序语言中的数据类型可分为两类：

  1. 非结构的原子类型。原子类型的值是不可分解的，例如C语言中的基本类型（整型、浮点型、字符型和枚举类型）、指针类型、空类型。
  2. 结构类型。结构类型的值是由若个成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的。

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响外部的使用。

抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。按其值的不同特性分为以下3类：

  1. 原子类型，属于原子类型的变量的值是不可分解的。这类抽象数据类型较少，因为一般情况下，已有的故有数据类型足以满足需求。
  2. 固定聚合类型，属于该类型的变量，其值由确定树木的成分按某种结构组成。例如复数是由两个实数依确定的次序关系组成。
  3. 可变聚合类型，构成可变聚合类型的值的成分的数目是不固定的。

后两种类型统称为结构类型。

抽象数据类型可由三元组表示 $(D,S,P)$ ，其中 $D$ 是数据对象， $S$ 是 $D$ 上的关系集， $P$ 是对 $D$的基本操作集。

ADT 抽象数据类型名{
        数据对象: {数据对象的定义}
        数据关系: {数据关系的定义}
        基本操作: {基本操作的定义}
}ADT 抽象数据类型名

其中，数据对象和数据关系的定义用伪码表示，基本操作的定义格式如下：

基本操作名(参数表)
	初始条件: <初始条件描述>
	操作结果: <操作结果描述>

抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已实现的操作来组合新的操作。

算法

算法是对特定问题求解步骤的一种描述，是指令的有限序列。

算法具有以下5中特性：

  1. 有穷性，一个算法必须总是在执行有穷步之后结束，且每一步都可在有穷时间内结束。
  2. 确定性，算法中每条指令必须有确切的含义，不会产生二义性。并且在任何条件下，算法只有唯一的一条执行路径，即对于相同输入只能的到相同输出。
  3. 可行性，算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。
  4. 输入
  5. 输出

算法设计要求：

  1. 正确性，算法应当满足具体问题的需求。
  2. 可读性
  3. 健壮性，当输入数据非法时，算法也能够作出处理，而不会产生名莫名其妙的结果。