《三元组类型定义与实现》由会员分享，可在线阅读，更多相关《三元组类型定义与实现（16页珍藏版）》请在金锄头文库上搜索。
1、【例 1-5】抽象数据类型三元组的表示与实现/ 抽象数据类型三元组 Triplet 的定义ADT Triplet 数据对象：D = e1，e2 ，e3| e1，e2 ，e3ElemType数据关系：R1 = ， 基本操作：InitTriplet(&T,v1,v2,v3)操作结果: 构造三元组 T,依次置 T 的三个元素 e1，e2 ，e3的初值为 v1,v2 和 v3DestroyTriplet(&T)操作结果：三元组 T 被销毁Get(T,i,&e)初始条件：三元组 T 已存在，1i3。操作结果：用 e 返回 T 的第 i 元的值Put(&T,i,e)初始条件：三元组 T 已存在，1i3。操
2、作结果：改变 T 的第 i 元的值为 eIsAscending(T)初始条件：三元组 T 已存在。操作结果：如果 T 的三个元素按升序排列，返回 1，否则返回 0IsDescending(T) 初始条件：三元组 T 已存在。操作结果：如果 T 的三个元素按降序排列，返回 1，否则返回 0Max(T,&e)初始条件：三元组 T 已存在。操作结果：用 e 返回 T 的三个元素中的最大值Min(T,&e)初始条件：三元组 T 已存在。 ADT Triplet/ 定义存储结构/ 采用动态分配的顺序存储结构，由 InitTriplet 分配三个元素存储空间，Triplet 类型是/ ElemType 类
3、型的指针，存放 ElemType类型的地址typedef ElemType *Triplet; / 以下为 vc+6.0 环境下运行，可使用引用参数&/ 定义基本操作的函数原型（8 个基本操作)Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3)Status DestroyTriplet(Triplet &T)Status Get(Triplet T,int i, ElemType &e)Status Put(Triplet &T,int i,ElemType e)Status IsAscending(Triple
4、t T)Status IsDescending(Triplet T)Status Max(Triplet T,ElemType &e)Status Min(Triplet T,ElemType &e)/ 实现函数原型的 8 个基本操作 Triplet.cpp Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3) / 操作结果:构造三元组 T,依次置 T 的三个元素的初值为 v1,v2和 v3if(!(T=(ElemType *)malloc(3*sizeof(ElemType)exit(OVERFLOW);T0=v
5、1,T1=v2,T2=v3;return OK;Status DestroyTriplet(Triplet &T) / 操作结果：三元组 T 被销毁free(T);T=NULL;return OK;Status Get(Triplet T,int i, ElemType &e) / 初始条件：三元组 T 已存在，1i3。操作结果：用 e 返回T 的第 i 元的值if(i3)return ERROR;e=Ti-1;return OK;Status Put(Triplet &T,int i,ElemType e) / 初始条件：三元组 T 已存在，1i3。操作结果：改变 T 的第 i 元的值为 e
6、if(i3)return ERROR;Ti-1=e;return OK;Status IsAscending(Triplet T)/初始条件：三元组 T 已存在。操作结果：若 T 中的元素按升序排列返回 1，否则返回 0return(T0=T1Status Max(Triplet T,ElemType &e) / 初始条件：三元组 T 已存在。操作结果：用 e 返回 T 的三个元素中的最大值e=T0=T1?T0=T2?T0:T2:T1=T2?T1:T2;return OK;Status Min(Triplet T,ElemType &e) / 初始条件：三元组 T 已存在。操作结果：用 e 返
7、回 T 的三个元素中的最小值e=T0#include#include / malloc()等#include / INT_MAX 等#include / EOF(=Z 或 F6),NULL #include / atoi()#include / eof()#include / floor(),ceil(),abs()#include / exit()#include / cout,cin/ 函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1/ #define OVERFLOW
8、 -2 因为在 math.h 中已定义 OVERFLOW 的值为3,故去掉此行typedef int Status; / Status 是函数的类型,其值是函数结果状态代码，如 OK 等typedef int Boolean; / Boolean 是布尔类型,其值是 TRUE 或FALSE/ 定义应用头文件 Triplet.h/ 采用动态分配的顺序存储结构typedef ElemType *Triplet; / 定义基本操作的函数原型（8 个基本操作)Status InitTriplet(Triplet &T,ElemType v1,ElemType v2,ElemType v3)；Statu
9、s DestroyTriplet(Triplet &T)；Status Get(Triplet T,int i, ElemType &e)；Status Put(Triplet &T,int i,ElemType e)；Status IsAscending(Triplet T)；Status IsDescending(Triplet T)；Status Max(Triplet T,ElemType &e)；Status Min(Triplet T,ElemType &e)；/ 定义主函数及实现/ main1-1.cpp 是检验基本操作 Triplet.cpp 的主函数#includecommo
10、n.h. #include Triplet.h#includeTriplet.cpp typedef int ElemType; / 定义抽象数据类型 ElemType 在本程序中为整型void main()Triplet T;ElemType m;Status i; i=InitTriplet(T,5,7,9);printf(调用初始化函数后，i=%d(1:成功) T 的三个值为：,i);cout3)return ERROR;*e=Ti-1;return OK;Status Put(Triplet T,int i,ElemType e)/ 初始条件：三元组 T 已存在，1i3。操作结果：改变
11、 T 的第i 元的值为 e if(i3)return ERROR;Ti-1=e; return OK;Status IsAscending(Triplet T)/初始条件：三元组 T 已存在。操作结果：若 T 中的元素按升序排列，返回 1，否则返回 0 return(T0=T1Status Max(Triplet T,ElemType *e)/ 初始条件：三元组 T 已存在。操作结果：用 e 返回 T 的三个元素中的最大值 *e=T0=T1?T0=T2?T0:T2:T1=T2?T1:T2;return OK;Status Min(Triplet T,ElemType *e)/ 初始条件：三元组
12、 T 已存在。操作结果：用 e 返回 T 的三个元素中的最小值 *e=T0#include#include / malloc()等#include / INT_MAX 等#include / EOF(=Z 或 F6),NULL#include / atoi()#include / eof()#include / floor(),ceil(),abs()#include / exit()#include / cout,cin/ 函数结果状态代码#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1
13、/ #define OVERFLOW -2 因为在 math.h 中已定义 OVERFLOW 的值为3,故去掉此行typedef int Status; / Status 是函数的类型,其值是函数结果状态代码，如 OK 等typedef int Boolean; / Boolean 是布尔类型,其值是 TRUE 或FALSE / 定义应用头文件 Triplet.h/ 采用动态分配的顺序存储结构typedef ElemType *Triplet; / 定义基本操作的函数原型（8 个基本操作)Status InitTriplet(Triplet *T,ElemType v1,ElemType v2
14、,ElemType v3)；Status DestroyTriplet(Triplet *T)；Status Get(Triplet T,int i, ElemType *e)；Status Put(Triplet *T,int i,ElemType e)；Status IsAscending(Triplet T)；Status IsDescending(Triplet T)；Status Max(Triplet T,ElemType *e)；Status Min(Triplet T,ElemType *e)；/ 定义主函数及实现/ main1-1.c 是检验基本操作 Triplet.c 的主
15、函数#includecommon.h. #include Triplet.h#includeTriplet.c typedef int ElemType; / 定义抽象数据类型 ElemType 在本程序中为整型void main()Triplet T;ElemType m;Status i;i=InitTriplet(printf(调用初始化函数后，i=%d(1:成功) T 的三个值为：%d %d %dn,i,T0,T1,T2);i=Get(T,2,if(i=OK)printf(T 的第 2 个值为：%dn,m);i=Put(T,2,6);if(i=OK)printf(将 T 的第 2 个值改为 6 后，T 的三个值为：%d %d %dn,T0,T1,T2);i=IsAscending(T); / 此类函数实参与 ElemType 的类型无关,/ 当 ElemType 的类型变化时,实参不需改变 printf(调用测试升序的函数后，i=%d(0:否 1:是)n,i);i=IsDescending(T); printf(调用测试降序的函数后，i=%d(0:否 1:是)n,i);if(i=Max(T,&m)=OK) /
