理论教育 数据结构:数据类型与抽象数据类型

数据结构:数据类型与抽象数据类型

时间:2023-11-01 理论教育 版权反馈
【摘要】:抽象数据类型中的数据对象、数据操作的声明与数据对象的表示、实现相互分离。抽象数据类型有两个重要特征:数据抽象和数据封装。n元组的抽象数据类型定义如下:抽象数据类型可通过基本数据类型来表示和实现,即利用处理器中已经存在的数据类型说明新的结构类型,用已经实现的操作组合实现新的操作。本书采用C++中的类作为抽象数据类型的描述工具。

数据结构:数据类型与抽象数据类型

在程序设计中,数据和运算是两个不可或缺的因素。最初的机器语言汇编语言中的数据没有数据类型的概念。

数据类型是一组值的集合以及定义在该值集上的一组操作的总称。数据类型和数据结构密切相关,它最早出现在高级程序语言中,用来描述程序中操作对象的特性。在用高级程序语言编写的程序中,每个变量、常量或表达式都有确定的数据类型。类型显式或隐式地规定了在程序执行期间变量或表达式所有可能取值的范围,以及在此之上允许进行的操作。例如,整型数据类型是指一组值的集合Z={…,-3,-2,-1,0,1,2,3,…}和定义在该值集上的加、减、乘、除和模运算等算术运算的一组操作。

抽象数据类型(Abstract Data Type,ADT)是用户进行软件设计时从问题的数学模型中抽象出来的逻辑数据结构以及该逻辑数据结构上的一组操作。抽象关注问题的本质特征而忽略非本质的细节,是对具体事务的概括。抽象数据类型中的数据对象、数据操作的声明与数据对象的表示、实现相互分离。

抽象数据类型有两个重要特征:数据抽象和数据封装。数据抽象用ADT描述程序处理的实体时,强调数据的本质特征、所能完成的功能及其与外部用户的接口(外界使用数据的方法)。数据封装将实体的外部特性与其内部的实现细节分离,并且对外部用户隐藏其内部实现细节。

抽象数据类型一般由数据元素、数据关系和基本操作组成,可以表示为三元组

ADT=(D,R,P)其中,D表示数据对象,R表示D上的数据关系集合,P表示D中数据对象的基本操作集合。

抽象数据类型定义的基本格式如下:

ADT抽象数据类型名{

数据对象:数据对象的定义

数据关系:数据关系的定义

基本操作:基本操作的定义}ADT抽象数据类型名

其中,基本操作的定义格式如下:

基本操作名(形式参数表):操作功能描述

例1.1 定义复数的抽象数据类型,对复数进行构造和销毁,并返回复数的实部与虚部,以及两个复数之和。(www.daowen.com)

【解】复数的抽象数据类型定义如下:

ADT Complex{

数据对象:

D={a,b|a,b均为实数}

数据关系:

R={(a,b)|a为复数的实数部分,b为复数的虚数部分}

基本操作:

AssignComplex(&z,x,y):构造复数z,x为实部,y为虚部,&表示返回操作结果

DestroyComplex(&z):销毁复数z

GetReal(z,&real):用real返回z的实部

例1.2 定义n元组的抽象数据类型,实现n元组的构造、销毁,返回和更新指定位置的值,并对n元组进行排序。

【解】n元组的抽象数据类型定义如下:

抽象数据类型可通过基本数据类型来表示和实现,即利用处理器中已经存在的数据类型说明新的结构类型,用已经实现的操作组合实现新的操作。本书采用C++中的类作为抽象数据类型的描述工具。

免责声明:以上内容源自网络,版权归原作者所有,如有侵犯您的原创版权请告知,我们将尽快删除相关内容。

我要反馈