《构造数据抽象》PPT课件

《《构造数据抽象》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、构造数据抽象到目前为止，我们操作的都是简单的数值数据，而对我们希望处理的许多问题而言，这种简单数据还不够。许多程序在设计时就是为了模拟复杂的对象，因此他们就常常需要构造起一些计算对象。与我们在前面所做的事情一样，我们将重点转到各种程序设计语言的另一关键方面：讨论他们所提供的，将数据对象组合起来，形成复合数据的方式，并进一步去考查更复杂的数据。同样的我们还将要看到，与过程抽象相对应的，另一种强有力的设计方法学——数据抽象构造数据抽象数据抽象是一种方法学，它使我们能够将一个复合数据对象的使用，与该数据对象怎样由更基本的数据对象构造起来的细节隔离开来。其基本思想，就是设法构造出一些使用复合对象的程序

2、，使它们就像是在“抽象数据”上操作一样。也就是说，我们的程序中使用数据的方式应该是这样的：除了完成当前工作所必要的东西之外，它们不对所用数据做任何多余的假设。与此同时，一种“具体”数据表示的定义，也应该与程序中使用数据的方式无关。我们利用一组称为选择函数和构造函数的过程作为这两个部分之间的界面。构造数据抽象实例研究：有理数的算术运算我们希望能做有理数的加减乘除，比较两个有理数是否相等。我们假定已经有了一种从分子和分母构造有理数的方法。进一步假定，如果有了一个有理数，我们有一种方法取得它的分子和分母。现在再假定有关的构造函数和选择函数都可以做为过程使用：(make-rat)返回一个有

3、理数，其分子是整数，分母是整数(numer)返回有理数的分子(denom)返回有理数的分母这里使用一种称为按愿望思维的策略。现在我们还没有说有理数将如何表示，也没有说过程make-rat，numer和denom应如何实现。利用这三个过程我们就可以实现有理数的运算了构造数据抽象有理数运算过程的实现：加法过程：(define(add-ratxy)(make-rat(+(*(numerx)(denomy))(*(numery)(denomx)))(*(denomx)(denomy))))减法过程：(define(sub-ratxy)(make-rat(-(*(nu

4、merx)(denomy))(*(numery)(denomx)))(*(denomx)(denomy))))构造数据抽象乘法过程：(define(mul-ratxy)(make-rat(*(numerx)(numery))(*(denomx)(denomy))))除法过程：(define(div-ratxy)(make-rat(*(numerx)(denomy))(*(denomx)(numery))))相等判断过程：(define(equal-rat?xy)(=(*(numerx)(denomy))(*(numery)(denomx))))构造数据抽象有理数的表示：我们已经定义了在过程ma

5、ke-rat，numer和denom基础上的各种有理数的运算过程，而这些基础还没有定义。现在需要某种方式，将一个分子和一个分母粘接起来，构成一个有理数。在实现有理数之前我们先来看看我们所用的语言提供的一种称为序对的复合数据。序对为完成这里的有理数系统提供了一种自然的方式，我们可以将有理数简单的表示为两个整数（分子和分母）的序对。构造数据抽象序对：同样我们只关心序对选择函数和构造函数的形式，而实际过程已由解释器实现了(cons),过程cons取两个参数，返回一个包含这两个参数作为其成分的复合数据对象(car)，其序对中的第一个参数(cdr)，其序对中的第二

6、个参数注意一个序对也是一个数据对象，可以像基本数据对象一样给它一个名字且操作它。还可用cons构造其元素本身就是序对的序对，例如：(definex(cons12))(definey(cons34))(definez(consxy))(car(carz))1(car(cdrz))2构造数据抽象基于序对的有理数的表示：(define(make-ratnd)(consnd))(define(numerx)(carx))(define(denomx)(cdrx))为了显示计算结果我们再定义一个打印函数，它以一个有理数作为输入并把它打印出来。(define(print-ratx)(newline)(di

7、splay(numerx))(display"/")(display(denomx)))这里我们用到了两个scheme的基本内置过程display和newline。Display为打印数据的基本过程，newline为随后的打印开始一个新行。构造数据抽象(defineone-half(make-rat12))(print-ratone-half)(defineone-third(make-rat13