数据结构chap001.ppt

6. 抽象数据类型 (Abstract Data Type 简称ADT) 抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作。其定义仅取决于数据的逻辑特性，而与机内表示和实现无关。 抽象数据类型和数据类型实质上是一个概念。 例如，抽象数据类型复数的定义： 数据对象： D＝{e1,e2｜e1,e2∈RealSet } 数据关系： R1＝{e1,e2 | e1是复数的实数部分 | e2 是复数的虚数部分 } 基本操作： AssignComplex( Z, v1, v2 ) 操作结果：构造复数 Z,其实部和虚部分别被赋以 参数 v1 和 v2 的值。 ADT Complex { DestroyComplex( Z) 操作结果：复数Z被销毁。 GetReal( Z, realPart ) 初始条件：复数已存在。 操作结果：用realPart返回复数Z的实部值。 GetImag( Z, ImagPart ) 初始条件：复数已存在。 操作结果：用ImagPart返回复数Z的虚部值。 Add( z1,z2, sum ) 初始条件：z1, z2是复数。 操作结果：用sum返回两个复数z1, z2 的 和值。 } ADT Complex 假设:z1和z2是上述定义的复数 则 Add(z1, z2, z3) 操作的结果 z3 = z1 + z2 即为用户企求的结果 ADT 有两个重要特征: 数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）。 数据封装 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。 抽象数据类型的描述方法 抽象数据类型可用（D，S，P）三元组表示。 其中：D 是数据对象； S 是 D 上的关系集； P 是对 D 的基本操作集。 ADT 抽象数据类型名 { 数据对象：〈数据对象的定义〉 数据关系：〈数据关系的定义〉 基本操作：〈基本操作的定义〉 } ADT 抽象数据类型名 其中基本操作的定义格式为: 基本操作名（参数表） 初始条件：〈初始条件描述〉 操作结果：〈操作结果描述〉 参数表： 赋值参数 只为操作提供输入值。 引用参数 以打头，除可提供输入值外，还将返 回操作结果。 初始条件：描述了操作执行之前数据结构和参数应 满足的条件，若不满足，则操作失败， 并返回相应出错信息。若初始条件为空， 则省略之。 操作结果：说明了操作正常完成之后，数据结构的 变化状况和应返回的结果。 1.5 算法、算法的描述 1. 算法 算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性： (1)．有穷性 (2)．确定性 (3)．可行性 (4)．输入 (5)．输出 1. 有穷性：当执行一个算法时，不论是何种情况下，有限步骤后，这个算法一定要终止。 2.确定性：算法中的每条指令都必须是确定的，无二义性。 3.可行性：算法中的所有操作都必须足够基本，都可以通过已经实现的基本操作运算有限次实现之。 4.输入：具有0个或0个以上由外界提供的量。 5.输出：产生1个或多个结果。 算法与数据结构的关系 算法和数据结构有着紧密的联系，它们是一个统一体，没有一方另一方就没有意义。 Wirth有一句名言： “算法+数据结构=程序” 2. 算法的描述 一个算法可以用自然语言、约定的符号（如流程图等）来描述，也可以用计算机高级程序语言来描述，如Pascal语言、C语言或伪代码等。本书选用类C语言作为描述算法的工具。现简单说明类C语言的语法结构如下： (1)．预定义常量和类型： # define TRUE 1； # define FALSE 0； # define OK 1； # define ERROR 0； # define INFEASIBLE -1； # define OVERFLOW