型是一个抽象数据类型,尽管它们在不同处理器上实现的方法可以不同,但由于其定义的 数学特性相同,在用户看来都是相同的。因此,“抽象”的意义在于数据类型的数学抽象特 性。 另一方面抽象数据类型的范畴更广,它不再局限于前述各处理器中已定义并实现的 数据类型(也可称这类数据类型为固有数据类型),还包括形户在设计软件系统时自已定 义的数据类型。为了提高软件的复用率在近代程序设计方法学中指出,个软件系统的 框架应建立在数据之上,而不是建立在操作之上(后者是传统的软件设计方法所为)。即 在构成软件系统的每个相对独立的模块上,定义一组数据和施于这些数据上的一组操作, 并在模块内部给出这些数据的表示及其操作的细节,而在模块外部使用的只是抽象的数 据和抽象的操作。显然,所定义的数据类型的抽象层次越高,含有该抽象数据类型的软件 模块的复用程度也就越高。 个含抽象数据类型的软件模块通常应包含定义、表示和实现三个部分 如前所述,抽象数据类型的定义由一个值域和定义在该值域上的一组操作组成。若 按其值的不同特性,可细分为下列三种类型: 原子类型 Atomic Data Type)属原子类型的变量的值是不可分解的。这类抽象数 据类型较少,因为一般情况下,已有的固有数据类型足以满足需求。但有时也有必要定义 新的原子数据类型例如数位为100的整数。 团定聚合类型(Fxe4 aggregate Data Type)属该类型的变量,其值由确定数目的成 分按某种结构组成。例如复数是由两个实数依确定的次序关系构成。 可变聚合类型( Variable-Aggregate Data Type)和固定聚合类型相比较构成可变聚 合类型“值”的成分的数目不确定。例如可定义一个“有序整数序列的抽象数据类型,其 中序列的长度是可变的。 显然后两种类型可统称为结构类型。 和数据结构的形式定义相对应抽象数据类型可用以下三元组表示 (D, S, P) (14) 其中D是数据对象,S是D上的关系集P是对D的基本操作梟。本书采用以下格式定 义抽象数据类型: 抽微类型名 数据对康:(数据对象的定义 数据关系:(数据关系的定义 基本操作:〈基本操作的定义 }抽象数据类型名 其中,数据对象和数据关系的定义用伪码描述,基本操作的定义格式为 基本操作名(参数表) 初始条件:〈初始条件描述 操作结果:《操作结果描述〉 基本操作有两种参数:赋值参数只为操作提供输入值;引用参数以&打头,除可提供输
入值外还将返回操作结果。“初始条件”描述了操作执行之前数据结构和参数应满足的 条件,若不满足则操作失败,并返回相应出错信息。“操作结果”说明了操作正常完成之 后,数据结构的变化状况和应返回的结果。若初始条件为空则省略之 例1-6抽象数据类型三元组的定义 数据对象:D={e,e2,e3|el,e2,e3∈ Genset(定义了关系运算的某个集合) 数据关系R=|<el,e2>,<e2,e3> 基本操作 InitTriplet( &T, v1, v2, v3 操作结果:构造了三元组T元素el,e2和e3分别被赋以参数v,v和的值。 DestroyTriplet( &T) 操作结果:三元组T被销毀 Get( T, 1, &e) 初始条件:三元组T已存在,1≤还3 操作结果:用e返回T的第i元的值。 Put( &T, i, e) 初始条件:三元组T已存在1≤还3 操作结果政变T的第i元的值为e IsAscending( T) 初始条件:三元组T已存在。 操作结果:如果T的三个元素按升序排列则返回1,否则返回0 IsDescending( T 初始条件:三元组T已存在。 操作结果:如果T的三个元素按降序排列,则返回1,否则返回0。 Max( t, &e 初始条件:三元组T已存在。 操作结果:用e返回T的三个元素中的最大值 Min( t, &e) 初始条件:三元组T已存在。 操作结果:用e返回T的三个元素中的最小值。 ADT Triplet 多形数据类型( Polymorphic data Type)是指其值的成分不确定的数据类型。例 如,例16中定义的抽象数据类型 Triplet,其元素el、e2和6可以是整数或字符或字符 串甚至更复杂地由多种成分构成(只要能进行关系运算即可)。然而不论其元素具有何 种特性,元素之间的关系相同,基本操作亦相同。从抽象数据类型的角度看,具有相同的 数学抽象特性故称之为多形数据类型。显然,需借助面向对象的程序设计语言如C+ 等实现之。本书中讨论的各种数据类型大多是多形数据类型,限于本书采用类C语言作 为描述工具,故只讨论含有确定成分的数据元素的情况。如例16中的 Elem Set是某个 确定的将由用户自行定义的含某个关系运算的数据对象。 13抽象数据类型的表示与实现 抽象数据类型可通过固有数据类型来表示和实现即利用处理器中已存在的数据类 型来说明新的结构用已经实现的操作来组合新的操作。由于本书在高级程序设计语言 的虚拟层次上讨论抽象数据类型的表示和实现,并且讨论的数据结构及其算法主要是面
向读者故采用介于伪码和C语言之间的类C语言作为描述工具,有时也用伪码描述 些只含抽象操作的抽象箅法。这使得数据结构和算法的描述和讨论简明清晰,不拘泥于 C语言的细节,又能容易转换成C或者C++程序。 本书采用的类C语言精选了C语言的一个核心子集,同时作了若干扩充修改,增强 了语言的描述功能。以下对其作简要说明。 (1)预定义常量和类型: ∥/函数结果状态代码 define TRUE #define FAISE 0 t define ERROR i define INFEASIBLE -I #define OVERELOR-2 ∥ Status是函数的类型其值是函数结果状态代码 int status (2)数据结构的表示(存储结构)用类型定义( typedef描述。数据元素类型约定为 Elem Type,由用户在使用该数据类型时自行定义。 (3)基本操作的算法都用以下形式的函数描述 函数类型函数名(函数参数表) ∥算法说明 语句序列 ↓∥函数名 除了函数的参数需要说明类型外,算法中使用的辅助变量可以不作变量说明,必要时对其 作用给予注释。一般而言,a、b、c、de等用作数据元素名, j,k,h,m,n等用作整型变量 名,p、qr等用作指针变量名。当函数返回值为函数结果状态代码时,函数定义为 Status 类型。为了便于算法描述,除了值调用方式外,增添了C++语言的引用调用的参数传 递方式。在形参表中以&打头的参数即为引用参数。 (4)赋值语句有 简单赋值变量名=表达式; 串联赋值变量名1=变量名2=…=变量名k=表达式; 成组赋值(变量名1,…,变量名k)=(表达式1,…,表达式k); 结构名=结构名; 结构名=(值1,…,值x); 变量名[]=表达式 变量名起始下标终止下标]=变量名起始下标终止下标]; 交换赋值变量名←→变量名; 条件赋值变量名=条件表达式?表达式T表达式F; (5)选择语句有 条件语句1迁(表达式)语句; 条件语句2近(表达式)语句; 4l语句; 开关语句1itch(表达式)
cB值1:语句序列1; break c為值n:语句序列n;rak; default:语句序列n+1; 开关语句2 switch ca·条件1:语句I;rk; cae条件n:语句n; break; default:语句n+1 (6)循环语句有 for语句fox(赋初值表达式序列;条件;修改表达式序列)语句 h·语句mhi]l(条件)语句 语句序列; 咖hi1l(条件); (7)结束语句有 函数结束语句 ru表达式; returm; case结束语句 异常结束语句 erit(异常代码); (8)输入和输出语句有 输入语句atf([格式串],变量1,…变量n); 输出语句rf([格式串]】表达式1,,表达式n) 通常省略格式串。 (9)注释 单行注释∥文字序列 (10)基本函数有 求最大值 x(表达式1,…,表达式n) 求最小值-n(表达式1,…,表达式n) 求绝对值 aha(表达式) 求不足整数值o(表达式) 求进位整数值c1(表达式) 判定文件结柬·(文件变量)或of 判定行结束·n(文件变量)或ola ()逻辑运算约定 与运算&&:对于A&&B,当A的值为0时,不再对B求值。 或运算|:对于&|l,当A的值为非0时,不再对B求值。 例17抽象数据类型 Triplet的表示和实现
∥ 采用动态分配的顺序存储结构 pede Blem Type+ Triplet;∥由 InitTriplet分配三个元素存储空间 基本操作的函数原型说明 Status InitTriplet(Triplet &T, Blea Type vl, ElenType v2, Elen Type v3); ∥操作结果:构造了三元组T,元素el,e和e3分别被赋以参数v,v和v3的值。 Status DestroyTriplet(Triplet &T); ∥操作结果:三元组T被销毁。 Status Get(Triplet T, int 1, EleaType &e); ∥初始条件:三元组T已存在1≤≤3 ∥操作结果:用e返回置的第元的值 Status Put(Triplet &T, int i, Elem Type e); ∥初始条件:三元组T已存在,1≤还3 ∥操作结果:改变T的第i元的值为e 就 tug IsAscendin(TtT); ∥初始条件:三元组T已存在。 ∥操作结果:如果T的三个元素按升序排列,则返回1,否则返回0 Status IsDescendiog(Triplet T); ∥初始条件:三元组T已存在。 ∥操作结果:如果T的三个元素按降序排列,则返回1,否则返回0。 Status Max(Triplet T, Elee type &e); ∥初始条件:三元组T已存在。 ∥操作结果:用e返回T的三个元素中的最大值。 Status Min (Triplet T, Blen Type &e); ∥初始条件:三元组T已存在。 ∥操作结果:用e返回T的三个元素中的最小值。 ∥-----基本操作的实现 Status InitTriplet(Triplet &T, Elem'l'ype v1, BleaType v2, Elemtype 13) ∥构造三元组T依次置T的三个元素的初值为,2和3 =( ElenType)甽llc(3普 sizeof( ElemType);∥分配3个元素的存储空间 进(!T)ait(OWRF);∥分配存储空向失败 r[0]vl;r[1=v2;r[2] return OK; ∥ InitTripl Status DestroyTriplet(Triplet &r) ∥销毁三元组T return OK t∥ DestroyIriplet Status Get(triplet T, int i, Elem'lype &e)I ∥1≤还3,用e返回T的第i元的值。 (ⅸ1‖i>3)su邳RQR; Ti-1] t∥et Status Put(Triplet &T, int i, Elem Type e)I ∥1≤还≤3,置T的第i元的值为e (i<1‖i>3)rOR; [-1] return ∥t Status IsAscending(Triplet T)