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

浙江大学城市学院实验报告 课程名称 数据结构基础 实验项目名称 实验二 抽象数据类型的表示和实现 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 实验目的和要求 1、通过抽象数据类型三元组的表示和实现，了解抽象数据类型的定义方式。 2、掌握抽象数据类型的定义方式和用C语言实现的方法。 3、熟悉如何运用主函数检验各基本操作函数的正确性的具体操作。 实验内容 认真阅读以下有关抽象数据类型的知识： （1）抽象数据类型的概念 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，就不影响其外部的使用。 一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。抽象数据类型通常采用以下格式定义： ADT抽象数据类型名 { 数据对象：数据对象的定义 数据关系：数据关系的定义 基本操作：基本操作的定义 } ADT抽象数据类型名 （2）三元组的抽象数据类型定义及表示 我们以抽象数据类型三元组为例，说明抽象数据类型是如何定义的。三元组实际上就是一个数据对象中有3个数据元素。三元组中元素的数据类型，可以是整型数，也可以是字符、浮点数或者更复杂的数据类型。 以下是三元组的抽象数据类型定义： ADT Triplet{ 数据对象：D={e1, e2, e3 | e1, e2, e3∈ElemSet (ElemSet为某个数据对象的集合)} 数据关系：R1={e1, e2, e2, e3} 基本操作： InitTriplet(T, v1, v2, v3) 操作结果：构造三元组T，元素e1, e2和e3分别被赋以v1, v2, v3值 DestroyTriplet(T) 操作结果：三元组T被销毁 Get(T, i, e) 初始条件：三元组T已存在，1≤i≤3 操作结果：用e返回T的第i元的值 IsAscending(T) 初始条件：三元组T已存在 操作结果：如果T的三个元素按升序排列，则返回1，否则返回0 IsDecending(Triplet T); 初始条件: 三元组T已存在 操作结果: 如果T的三个元素按降序排列，则返回1，否则返回0 Put(T, i, e) 初始条件：三元组T已存在，1≤i≤3 操作结果：改变T的第i元的值为e Max(T, e) 初始条件：三元组T已存在 操作结果：用e返回T的三个元素中的最大值 Min(T, e) 初始条件：三元组T已存在 操作结果：用e返回T的三个元素中的最小值 } ADT Triplet 三元组在计算机中的具体存储方式可以采用动态分配的顺序存储结构，如图所示： 动态分配的顺序存储的三元组 在计算机中实现上述三元组抽象数据类型。步骤如下： （1）首先搭好实现该抽象数据类型的整个C语言程序的模块框架结构图即在一个工程中分别建立两个文件：头文件test1_2.h与文件test1_2.cpp。 （2）编写test1_2.h和test1_2.cpp两个文件，其中test1_2.h中包含三元组的各种操作函数的实现，test1_2.cpp中包含三元组存储结构定义与主函数，主函数主要用于验证test1_2.h中各函数的正确性。编译并调试程序，直到正确运行。、、report2.doc 、int InitTriplet(Triplet T, ElemType v1,ElemType 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) /