实验02 抽象数据类型的表示与实现

1、浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验二 抽象数据类型的表示和实现 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 一. 实验目的和要求1、通过抽象数据类型三元组的表示和实现，了解抽象数据类型的定义方式。2、掌握抽象数据类型的定义方式和用C语言实现的方法。3、熟悉如何运用主函数检验各基本操作函数的正确性的具体操作。二. 实验内容1、 认真阅读以下有关抽象数据类型的知识：（1）抽象数据类型的概念 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何

2、变化，只要它的数学特性不变，就不影响其外部的使用。一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。抽象数据类型通常采用以下格式定义： ADT抽象数据类型名 数据对象： 数据关系： 基本操作： ADT抽象数据类型名（2）三元组的抽象数据类型定义及表示我们以抽象数据类型三元组为例，说明抽象数据类型是如何定义的。三元组实际上就是一个数据对象中有3个数据元素。三元组中元素的数据类型，可以是整型数，也可以是字符、浮点数或者更复杂的数据类型。以下是三元组的抽象数据类型定义： ADT Triplet 数据对象：D=e1, e2, e3 | e1, e2, e3ElemSet (ElemSet

3、为某个数据对象的集合) 数据关系：R1=, 基本操作： InitTriplet(&T, v1, v2, v3) 操作结果：构造三元组T，元素e1, e2和e3分别被赋以v1, v2, v3值 DestroyTriplet(&T) 操作结果：三元组T被销毁 Get(T, i, &e) 初始条件：三元组T已存在，1i3 操作结果：用e返回T的第i元的值IsAscending(T) 初始条件：三元组T已存在 操作结果：如果T的三个元素按升序排列，则返回1，否则返回0IsDecending(Triplet T); 初始条件: 三元组T已存在 操作结果: 如果T的三个元素按降序排列，则返回1，否则返回0

4、 Put(&T, i, e) 初始条件：三元组T已存在，1i3 操作结果：改变T的第i元的值为e Max(T, &e) 初始条件：三元组T已存在 操作结果：用e返回T的三个元素中的最大值 Min(T, &e) 初始条件：三元组T已存在 操作结果：用e返回T的三个元素中的最小值 ADT Triplet三元组在计算机中的具体存储方式可以采用动态分配的顺序存储结构，如图所示： 动态分配的顺序存储的三元组2、 在计算机中实现上述三元组抽象数据类型。步骤如下：（1）首先搭好实现该抽象数据类型的整个C语言程序的模块框架结构图，即在一个工程中分别建立两个文件：头文件test1_2.h与主程序文件test1_

5、2.cpp。（2）编写test1_2.h和test1_2.cpp两个文件，其中test1_2.h中包含三元组的各种操作函数的实现，test1_2.cpp中包含三元组存储结构定义与主函数，主函数主要用于验证test1_2.h中各函数的正确性。编译并调试程序，直到正确运行。3、填写实验报告，实验报告文件取名为report2.doc。4、上传实验报告文件report2.doc 、源程序文件test1_2.cpp及test1_2.h到Ftp服务器上自己的文件夹下。3. 函数的功能说明及算法思路/*构造三元组T*/int InitTriplet(Triplet &T, ElemType v1,ElemT

6、ype v2,ElemType v3)/*销毁三元组T*/void DestroyTriplet(Triplet &T)/*用e返回三元组T的第i元的值*/void Get(Triplet T,int i,ElemType &e)/*改变三元组T的第i元的值为e*/void Put(Triplet &T,int i,ElemType e)/*求三元组T元素中的最大值*/void Max(Triplet &T,ElemType &e)/*求三元组T元素中的最小值*/void Min(Triplet &T,ElemType &e)/*判断三元组T的元素是否按升序排列，是返回1，否返回0*/int

7、IsAscending(Triplet &T)/*判断三元组T的元素是否按降序排列，是返回1，否返回0*/int IsDecending(Triplet &T)四. 实验结果与分析五. 心得体会【附录-源程序】test1_1.cpp#include#include#includetypedef int ElemType;typedef ElemType *Triplet;#include test1_2.hvoid main()Triplet T;ElemType m;int i,a,b,c,x,y,choice;while(choice!=0)system(cls);printf(*n);p

8、rintf(* 1.InitTriplet *n);printf(* 2.Get *n); printf(* 3.Put *n);printf(* 4.Max & Min *n);printf(* 5.IsSort *n); printf(* 6.DestroyTriplet *n);printf(* 0.Exit *n);printf(*n);printf(nPlease enter: );scanf(%d,&choice);switch(choice)case 1:system(cls);printf(请输入三元组T中的三个元素: );scanf(%d %d %d,&a,&b,&c);i=

9、InitTriplet(T,a,b,c);if(i=1)printf(n调用初始化函数成功！n);printf(n三元组T中三个元素的值分别为: );printf(T0=%d, T1=%d, T2=%dn,T0,T1,T2);printf(nn请按任意键返回菜单！);getchar();getchar();break;case 2:system(cls);while(1)printf(请输入需要查找的三元组T中元素的下标: );scanf(%d,&x);if(x=0|x=1|x=2)Get(T,x,m);printf(n下标为%d的元素 T%d=%dn,x,x,m);break;elsepri

10、ntf(输入错误，请重新输入！nn);printf(nn请按任意键返回菜单！);getchar();getchar();break;case 3:system(cls);printf(三元组T中三个元素的值分别为: );printf(T0=%d, T1=%d, T2=%dnn,T0,T1,T2);while(1)printf(请输入需要改变的三元组T元素的下标及元素值:);scanf(%d%d,&x,&y);if(x=0|x=1|x=2)Put(T,x,y);printf(n改变后三元组T中三个元素的值分别为: );printf(T0=%d, T1=%d, T2=%dn,T0,T1,T2);b

11、reak;elseprintf(输入错误，请重新输入！nn);printf(nn请按任意键返回菜单！);getchar();getchar();break;case 4:system(cls);printf(三元组T中三个元素的值分别为: );printf(T0=%d, T1=%d, T2=%dnn,T0,T1,T2);Max(T,m);printf(三元组T中的最大值为 MAX=%d, ,m);Min(T,m);printf(最小值为 MIN=%dn,m);printf(nn请按任意键返回菜单！);getchar();getchar();break;case 5:system(cls);pr

12、intf(三元组T中三个元素的值分别为: );printf(T0=%d, T1=%d, T2=%dnn,T0,T1,T2);i=IsAscending(T);if(i)printf(三元组T的三个元素是按升序排序,);elseprintf(三元组T的三个元素不是按升序排序,);i=IsDecending(T);if(i)printf(是按降序排序n);elseprintf(不是按降序排序n);printf(nn请按任意键返回菜单！);getchar();getchar();break;case 6:system(cls);printf(三元组T中三个元素的值分别为: );printf(T0=%

13、d, T1=%d, T2=%dnn,T0,T1,T2);DestroyTriplet(T);printf(销毁三元组T后,T=%dn,T);printf(nn请按任意键返回菜单！);getchar();getchar();break;case 0:exit(0);test1_1.hint InitTriplet(Triplet &T, ElemType v1,ElemType v2,ElemType v3)if(!(T=(ElemType*)malloc(3*sizeof(ElemType)exit(0);T0=v1;T1=v2;T2=v3;return 1;void DestroyTriplet(Triplet &T)free(T);T=NULL;return;void Get(Triplet T,int i,ElemType &e)int k;for(k=0;k3;k+)if(k=i)break;e=Tk;void Put(Triplet &T,int i,ElemType e)int k;for(k=0;k3;k+)if(k=i)break;Tk=e;void Max(Triplet &T,ElemType &e)int i;e=T0;for(i=1;i3