计算机数据结构的知识点(10)

他的所有基本操作看作一个整体——称之为模块（model）。我们可以进一步将该模块抽象为数据类型（其中DS的存储结构被表示为私有成员，基本操作被表示为公共方法），称之为ADT（即是抽象数据类型Abstract Data Type，指一个数学模型以及定义在该模型上的一组操作）。

ADT按照其值的不同特性分为下列三种类型：

原子类型（Atomic Data Type）：变量是不带结构的，不可分解的。

固定聚合类型（Fixed-aggregate Data Type）：其值由确定数目的成分按照某种结构组成

可变聚合类型（Variable-Aggregate Data Type）：值的成分的数目不确定

抽象数据类型的描述方法

抽象数据类型可用（D，S，P）三元组表示

其中，D是数据对象，S是D上的关系集，P是对D的基本操作集。

ADT 抽象数据类型名 {

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

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

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

} ADT 抽象数据类型名

其中，数据对象和数据关系的定义用伪码描述，基本操作的定义格式为

基本操作名（参数表）

初始条件：〈初始条件描述〉

操作结果：〈操作结果描述〉

基本操作有两种参数：赋值参数只为操作提供输入值；引用参数以&打头， 除可提供输入值外，还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的条件，若不满足，则操作失败，并返回相应出错信息。“操作结果”说明了操作正常完成之后，数据结构的变化状况和应返回的结果。若初始条件为空，则将其省略。需要注意的是：抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现。

顺便提一句，多形数据类型（Polymorphic Data Type）是指值的成分不确定的数据类型，不过这个不太多见，或者是可以用ADT表示，所以我们在今后的章节再论述。

好的和坏的DS：如果一个DS可以通过某种“线性规则”被转化为线性的DS（例如线性表），则称它为好的DS。好的DS通常对应于好的（高效的）算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如何没有线性化的结构逻辑上是不可计算的。比如对一个图进行操作，要访问图的所有结点，则必须按照某种顺序
来依次访问所有节点（要形成一个偏序），必须通过某种方式将图固有的非线性结构转化为线性结构才能对图进行操作。

树是好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有