数据结构原理.pdf

浙江大学城市学院实验报告

课程名称数据结构基础

实验项目名称实验二抽象数据类型的表示和实现

学生姓名丁汀专业班级信管1006学号

实验成绩指导老师（签名）柳俊日期2011/9/22

一.实验目的和要求

1、通过抽象数据类型三元组的表示和实现，了解抽象数据类型的定义方式。

2、掌握抽象数据类型的定义方式和用C语言实现的方法。

3、熟悉如何运用主函数检验各基本操作函数的正确性的具体操作

二.实验内容

1、认真阅读以下有关抽象数据类型的知识：

（1）抽象数据类型的概念

抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。抽象数据

类型的定义仅取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无

关，即不论其内部结构如何变化，只要它的数学特性不变，就不影响其外部的使

用。

一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。抽

象数据类型通常采用以下格式定义：

ADT抽象数据类型名{

数据对象：数据对象的定义

数据关系：数据关系的定义

基本操作：基本操作的定义

}ADT抽象数据类型名

（2）三元组的抽象数据类型定义及表示

我们以抽象数据类型三元组为例，说明抽象数据类型是如何定义的。三元组

实际上就是一个数据对象中有3个数据元素。三元组中元素的数据类型，可以是

整型数，也可以是字符、浮点数或者更复杂的数据类型。

以下是三元组的抽象数据类型定义：

ADTTriplet{

数据对象：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(TripletT);

初始条件:三元组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的三个元素中的最小值

}ADTTriplet

三元组在计算机中的具体存储方式可以采用动态分配的顺序存储结构，如图

2.1所示。

TripletElemType

图2.1动态分配的顺序存储的三元组

2、在计算机中实现上述三元组抽象数据类型。步骤如下：

（1）首先搭好实现该抽象数据类型的整个C语言程序的模块框架结构图，如图

2.2所示。即在一个工程中分别建立两个文件：头文件test2_function.h与源文

件test2_main.cpp。

图2.2实现三元组操作的C