1. Data Abstraction

Data Abstraction

大多数值都是复合值，由多种对象组成

抽象数据类型可以让我们将符合对象作为一个单元操作，允许我们隔离使用数据的程序的两个部分：

数据的表示
数据的操作

即在数据的表示与操作之间建立一个抽象屏障

Example——Rational Numbers

表示

任何有理数可以表示为一个最简分数

这为小数提供了更精确的表示方法

故我们需要分开分子分母，作为一个复合数据类型：

rational(n,d)返回一个有理数x
numer(x)返回有理数x的分子
denom(x)返回有理数的分母

第一个函数称为构造函数（constructor），它用于构造一个新值作为抽象数据类型的实例（instance）

第二、三个函数称为选择器（selectors），它们返回得到的有理数的整数部分

这三个函数作为有理数的抽象数据类型使用，用它们进行数字操作

算术

根据小学二年级知识，我们根据分数来执行有理数加乘，公式如下

def mul_rational(x,y):
    return rational(numer(x)*numer(y),denom(x)*denom(y))

def add_rational(x,y):
    nx, dx = numer(x), denom(y)
    ny, dy = numer(y), denom(y)
    return rational(nx*dy+ny*dx, dx*dy)

def equal_rational(x,y):
    return numer(x)*denom(y)==numer(y)*denom(x)

Abstraction Barriers

拿上方的有理数函数作为例子

抽象屏障表示使用由有理数计算时使用的函数只能是对应相关的，而不能越界表示

用有理数计算时只需要使用计算相关函数
用来表示有理数和进行操作时只需要使用对应构造函数与选择器
用来构建构造函数与选择器时需要用到列表与元素选择

一种跨越了抽象屏障的反例：

add_rational([1,2],[1,4])

def divide_rational(x,y):
    return [x[0]*y[1], x[1]*y[0]]

Pair

创建与访问

通常使用列表表示一个pair

1
2
3

>>> pair = [1,2]
>>> pair
[1,2]

通过序列解包或列表下标获得pair中的两个值

>>> x,y=pair
>>> x
1
>>> y
2
>>> pair[0]
1

还可以用getitem函数获得值，在operator库中

用法：getitem(<list>, <index>)

>>> getitem(pair, 0)
1
>>> getitem(pair, 1)
2

用pair表示有理数

1
2
3

def rational(n,d):
    """Construct a rational number that represents N/D"""
    return [n, d]

返回一个列表，记录分子分母用来表示有理数

def numer(x):
    """Return the numerator of rational number x"""
    return x[0]

def denom(x):
    """Return the denominator of rational number x"""
    return x[1]

通过访问列表中的元素返回分子分母

应用

分数通分

有理数的分子分母应互质，故我们可以用gcd获取它们的最大公因数来同时除以分子分母以确保获得互质的分子分母

from fractions import gcd
def rational(n,d):
    g = gcd(n,d)
    return [n//g, d//g]

Data Representation

数据抽象的基本思想：通过它的行为来识别该抽象数据类型

改变有理数的表现形式

def rational(n,d):
    def select(name):
        if name == 'n':
            return n
        elif name == 'd':
            return d
    return select
def numer(x):
    """Return the numerator of rational number x"""
    return x('n')

def denom(x):
    """Return the denominator of rational number x"""
    return x('d')

这里使x成为一个函数，这样就可以不需要内置的列表数据类型了

此时rational是一个高阶函数，返回一个表示有理数的函数

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

红魔咖啡馆

【CS61A】CS61A——Data Abstraction

Data Abstraction