实验二 抽象数据类型的表示和实现——及编码答案

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

课程名称 数据结构基础 实验项目名称 实验二 抽象数据类型的表示和实现 学生姓名 专业班级 学号

实验成绩 指导老师（签名 ） 日期

一. 实验目的和要求

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

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

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

二. 实验内容

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

（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

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

2.1所示。

TripletElemType

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

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

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

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

图2.2 实现三元组操作的C语言源程序框架图

（2）编写test2_function.h和test2_main.cpp两个文件，其中test2_function.h中包含三元组的各种操作函数的实现，test2_main.cpp中包含三元组存储结构定义与主函数，主函数主要用于验证test2_function.h中各函数的正确性。编译并调试程序，直到正确运行。

说明：

以下给出了若干基本操作（即函数）的实现方法，供参考，其余函数请自行完成。

(a) 头文件test2_function.h中三元组基本操作的实现个例。

I. 初始化操作：

int InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3)

{ // 操作结果：构造三元组T，依次置T的3个元素的初值为v1，v2和v3

// (见图2.3) ，经过此操作，系统将分配给三元组T一个起始地址

if (!(T=(ElemType *) malloc (3*sizeof(ElemType))))

exit(0); // 申请空间失败，退出系统

T[0]=v1; T[1]=v2; T[2]=v3;

return 1; // 若返回值为1，则初始化成功

}

TT[0]

T[1]T[2] 图2.3 构造三元组T

II. 销毁操作：

void DestroyTriplet(Triplet &T)

{ // 操作结果：三元组T被销毁

free(T);

T=NULL;

return;

}

（b) 主文件test2_main.cpp：

# include <iostream.h> // 包含输入（cin）、输出（cout）的头文件， #include <stdio.h> //若采用printf和scanf，则用stdio.h库函数 # include <stdlib.h> //常用函数的头文件

typedef int ElemType; // 定义三元组元素类型ElemType为整型 typedef ElemType *Triplet; //定义动态分配的三元组类型, 指针Triplet

//指向ElemType类型元素的地址。初始化操作分配3个元素的存储空间 # include "test2_function.h" // 包含三元组基本操作的头文件

void main()

{

Triplet T; // ___定义整型指针T _____

ElemType m;

int i;

i=InitTriplet(T, 1, 3, 5); //__以v1, v2, v3值____

printf("调用初始化函数后，i=%d (1：成功；否则：不成功) ", i); printf("\n三元组中三个元素的值分别为：\n");

printf("T[0]=%d, T[1]=%d, T[2]=%d", T[0], T[1], T[2]);

Get(T, 2, m); // ___ printf("\nT的第2个值为：%d", m) ;

Put(T, 2, 6); // ___ printf("\n改变后T的3个值为：%d, %d, %d", T[0], T[1], T[2]) ;

Max(T, m); // ___ printf("\nT中的最大值为：%d", m) ;

Min(T, m); //____用e返回T的三个元素中的最小值______ printf("\nT中的最小值为：%d", m);

..................

DestroyTriplet(T); printf("\n销毁T后，T=%d\n", T);

}

请读懂这个主程序，并把主函数填写完整，体会main() 函数前的“文件包含 (include) ”处理和typedef类型定义作用，并在主函数的划线处填上相应C语句的注释。

3、填写实验报告，实验报告文件取名为report2.doc。

4、上传实验报告文件report2.doc 、源程序文件test2_main.cpp及

test2_function.h到Ftp服务器上（ ）自己的文件夹下。

三. 函数的功能说明及算法思路

（包括每个函数的功能说明，及一些重要函数的算法实现思路）

附属文件test2_function.h:

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

主文件中test2_main.cpp:

先编写开头文件,和调用子函数语句,

# include <iostream.h> // 包含输入（cin）、输出（cout）的头文件， #include <stdio.h> //若采用printf和scanf，则用stdio.h库函数 # include <stdlib.h> //常用函数的头文件

typedef int ElemType; // 定义三元组元素类型ElemType为整型

typedef ElemType *Triplet; //定义动态分配的三元组类型, 指针Triplet //指向ElemType类型元素的地址。初始化操作分配3个元素的存储空间 # include "test2_function.h" // 包含三元组基本操作的头文件

void main()

{

Triplet T; // ________

ElemType m;

int i;

i=InitTriplet(T, 1, 3, 5); //__ printf("调用初始化函数后，i=%d (1：成功；否则：不成功) ", i);

printf("\n三元组中三个元素的值分别为：\n");

printf("T[0]=%d, T[1]=%d, T[2]=%d", T[0], T[1], T[2]);

Get(T, 2, m); // ________

printf("\nT的第2个值为：%d", m) ;

Put(T, 2, 6); // ___ printf("\n改变后T的3个值为：%d, %d, %d", T[0], T[1], T[2]) ;

Max(T, m); // _________

printf("\nT中的最大值为：%d", m) ;

Min(T, m); //__________ printf("\nT中的最小值为：%d", m);

..................再增加判断三元组T是否按顺序排列.

DestroyTriplet(T); printf("\n销毁T后，T=%d\n", T);

}

四. 实验结果与分析

（包括运行结果截图、结果分析等）

五. 心得体会

（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）

感觉程序越编越多,也复杂起来了,多步调用附属文件的子函数,且细节问题频频出现,需多加努力仔细.

【附录----源程序】

Test2_main:

#include<iostream.h> // 包含输入（cin）、输出（cout）的头文件， #include<stdio.h> //若采用printf和scanf，则用stdio.h库函数 #include<stdlib.h> //常用函数的头文件

typedef int ElemType; // 定义三元组元素类型ElemType为整型 typedef ElemType *Triplet; //定义动态分配的三元组类型, 指针Triplet //指向ElemType类型元素的地址。初始化操作分配3个元素的存储空间 # include "test2_function.h" // 包含三元组基本操作的头文件 void main()

{

Triplet T; // __定义整型指针T_______ ElemType m;

int i;

i=InitTriplet(T, 1, 3, 5); //____构造三元组T，元素e1, e2和e3分别被赋以v1, v2, v3值___

printf("调用初始化函数后，i=%d (1：成功；否则：不成功) ", i); printf("\n三元组中三个元素的值分别为：\n");

printf("T[0]=%d, T[1]=%d, T[2]=%d", T[0], T[1], T[2]); Get(T, 2, m); // __用e返回T的第i元的值____ printf("\nT的第2个值为：%d", m) ;

Put(T, 2, 6); // __改变T的第i元的值为e_______ printf("\n改变后T的3个值为：%d, %d, %d", T[0], T[1], T[2]) ; Max(T, m); // __用e返回T的三个元素中的最大值_____ printf("\nT中的最大值为：%d", m) ;

Min(T, m); //___用e返回T的三个元素中的最小值___ printf("\nT中的最小值为：%d", m);

if(IsAscending(T))

printf("\nT的三个元素按升序排列");

else

printf("\nT的三个元素不是按升序排列");

if(IsDecending(T))

printf("\nT的三个元素按降序排列");

else

printf("\nT的三个元素不是按降序排列");

DestroyTriplet(T); //___三元组T被销毁_______ printf("\n销毁T后，T=%d\n", T);

}

Test2_function:

/*初始化操作：*/

int InitTriplet(Triplet &T, ElemType v1, ElemType v2, ElemType v3)

{ // 操作结果：构造三元组T，依次置T的3个元素的初值为v1，v2和v3 // (见图2.3) ，经过此操作，系统将分配给三元组T一个起始地址 if (!(T=(ElemType *) malloc (3*sizeof(ElemType))))

exit(0); // 申请空间失败，退出系统

T[0]=v1; T[1]=v2; T[2]=v3;

return 1; // 若返回值为1，则初始化成功

}

/*用e返回T的第i元的值*/

int Get(ElemType *T,int i,ElemType &e)

{

e=T[i-1];

return e;

}

/*改变T的第i元的值为e*/

int Put(ElemType *T,int i,ElemType e)

{

T[i-1]=e;

return T[i-1];

}

/*如果T的三个元素按升序排列，则返回1，否则返回0*/ int IsAscending(Triplet T)

{

int i;

for(i=0;i<2;i++)

if(T[i]>T[i+1])

return 0;

return 1;

}

/*如果T的三个元素按降序排列，则返回1，否则返回0*/ int IsDecending(Triplet T)

{

int i;

for(i=0;i<2;i++)

if(T[i]<T[i+1])

return 0;

return 1;

}

/*用e返回T的三个元素中的最大值*/

void Max(Triplet T,ElemType &e)

{

int i;

e=T[0];

for(i=1;i<3;i++)

if(e<T[i])

e=T[i];

}

/*用e返回T的三个元素中的最小值*/ void Min(Triplet T,ElemType &e)

{

int i;

e=T[0];

for(i=1;i<3;i++)

if(e>T[i])

e=T[i];

}

/*销毁操作：*/

void DestroyTriplet(Triplet &T)

{ // 操作结果：三元组T被销毁

free(T);

T=NULL;

return;

}

本文来源：https://www.bwwdw.com/article/0ofq.html