山东大学《数据结构》实验指导01抽象数据类型.docx

《数据结构》实验指导
实验一抽象数据类型
一实验任务
抽象数据类型Triplet的表示和实现。
二实验目的
1)理解和掌握抽象数据类型的概念。
2)熟悉数据结构的定义及基本操作。
3)实践系统程序开发的规范步骤。
三实验原理
1.抽象数据类型的定义
抽象数据类型(ADT, Abstract Data Type)由具有一定关系的一组数据和定 义在该组数据上的操作组成。抽象数据类型为我们提供了一个描述数据结构的架 构。
抽象数据类型的定义一般包括数据定义和操作定义两个局部。一个含抽象数 据类型的模块通常包含定义、表示和实现3个局部。
抽象数据类型的形式表示为如下三元组：
(D, S, 0 )
其中：D是数据对象，S是D上的关系集合，。是D上的基本操作集合。
我们习惯上把抽象数据类型表示成如下格式：
ADT抽象数据类型名
{数据对象：〈数据对象的定义,
数据关系：〈数据关系的定义〉基本操作：〈基本操作的定义》
}ADT抽象数据类型名
例如，抽象数据类型Triplet的三元组定义：
ADT Triplet {数显对象：D={el, e2, e3 | el, e2, e3 I ElemSet )
数据关系：Rl= { <E1, e2>, <E2, e3>}基本操作：
InitTriplet ( & Tz vl, v2, v3 )
操作结果：构造了三元组T,元素el,e2和e3分别被赋以参数vl, v2 和v3的值DestroyTriplet ( & T)
操作结果：三元组T被销毁。
Get ( T, i, &e )初始条件：三元组T已存在，l£i£3o
操作结果：用e返回T的第i元的值。
Put(&T, i, e)初始条件：三元组T已经存在，l£i£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
2.抽象数据类型的表示与实现
我们可以通过固有数据类型来表示和实现抽象数据类型，即利用处理器中已 存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。我们约定 以C语言作为数据结果的描述工具。
例如，抽象数据类型Triplet的表示和实现如下：
typedef ElemType * Triplet;
//基本操作的实现
Status InitTriplet ( Triplet & T, ElemType vlz ElemType v2, ElemType v3 ) {
〃构造三元组T,依次设置T的三个元素的初值为vl, v2和v3。
T=(日emType * ) malloc ( 3*sizeof (日emType ));
if ( ! T ) exit ( OVERFLOW );
T[ 0 ] = vl; T[ 1 ] = v2; T[2] = v3; return OK !
}
Status DestroyTriplet ( Triplet & T) {
free (T); T=NULL ; return OK !
}
Status Get ( Triplet T, int i,日emType & e ) {
if (i < 1 11 i > 3 ) return ERROR;
e = T[i-l]; return OK !
}
Status Put ( Triplet & T, int i,日emType e ) {
if (i < 1 11 i > 3 ) return ERROR;
T [ i - 1 ] = e; return OK !
}四实验设备、仪器、工具及资料
微机、VC五实验内容
通过C语言实现一个可无误运行的完整程序，完成抽象数据类型Triplet的 表示和实现。要求：程序运行时显示基本操作的菜单，由用户选择执行相应操作 （如：可利用switch语句等），以此整合Triplet的各基本操作，实现程序设计。 六实验步骤（1）实验预习
1）预习本实验原理中关于抽象数据类型Triplet的定义、表示及实现。
2）熟悉程序运行环境VC的使用。
（2）实验步骤
1）问题分析与系统的结构设计。充分地分析和理解此实验工程，弄清要求 作什么，限制条件是什么。按照以数据结构为中心的原那么划分模块。最后写出每 个子程序（过程或函数）的规格说明，列出它们之间的调用关系，可以使用调用 关系图表示那么更加清晰，这样便完成了系统结构设计。
2）详细设计和编码。详细设计的目的是对子程序（过程或函数）的进一步 求精。用IF、WHILE和赋值语句等，以及自然语言写出算法的框架。利用自然 语言的目的是防止陷入细节。在编码时，可以对详细设计的结果进一步求精，用 高级语言表示出来。
3）在VC环境下调试程序。
七实验报告要求
实验报告包含程序开发过程所形成的所有文档资料，包括如下内容：
1）需求分析及规格说明：问题描述，求解的问题是什么。
2）概要设计：本程序所用的数据类型定义；主程序流程；程序模块及相互 关系。
3）详细设计：采用C语言定义的数据结构；各模块的伪码算法；各函数调 用关系。
4）调试报告。
5）本实验工程的程序清单及运行结果。
八思考题
为什么用抽象数据类型描述数据结构？