Python数据结构与算法--面向对象

一个分数类

下面来看一个非常普通的例子，用来展示实现抽象数据类型的一个用户自定义类：Fraction（分数）. 我们已经知道 Python 给我们提供了大量的类. 有很多可以适当地帮我们构建分数类型的数据对象.

一个分数比如cd/usr/local/hadoop@Master:/usr/local

 Fraction 类的方法应该能够让 Fraction 对象可以像其他的数值那样进行计算. 我们需要可以进行分数之间的 加, 减, 乘, 和 除 运算. 更进一步, 所有的方法应该返回最简分数.

在 Python中, 我们定义一个类的名字还有一些方法，类似于定义一个函数,例如,

class Fraction:

   #the methods go here

提供了给我们定义方法的框架.第一个方法是所有类都要提供的构造器. 构造函数定义了类创建的方式. 要创建分数对象, 我们需要提供两部分的数据:分子和分母. 在 Python中, 构造函数使用 __init__ (两条下划线包围 init) ，如下所示：

Listing 2

class Fraction:

    def __init__(self,top,bottom):

        self.num = top
        self.den = bottom

注意到参数列表含有三个参数： (self, top, bottom). self 是一个引用对象自身的特殊的参数. 它通常作为第一个参数; 但是, 它从不在调用的时候传值. 之前已经讲过，分数包含两部分（分子和分母）. 记号 self.num 在构造函数中被定义为 fraction 对象具有一个叫num 的内部数据对象. 同理, self.den 也是类似的目的.

要实现 Fraction 类, 我们需要调用构造函数. 接着通过类名传递参数 (注意到我们从不直接调用__init__). 例如：

myfraction = Fraction(3,5)

创建一个分数对象 myfraction 代表分数3/5 .

接着要做的事情就是给抽象数据类型实现方法. 首先, 意识到当我们要输出一个 Fraction 对象.

>>> myf = Fraction(3,5)
>>> print(myf)
<__main__.Fraction instance at 0x409b1acc>

fraction 对象, myf, 并不知道怎样响应输出操作.  print 函数需要对象转换为可输出的字符串格式，这样才能输出. 唯一的选择 myf 必须显示变量实际的地址引用(自身的地址). 这不是我们想要的.

有两种解决问题的办法. 一种是定义一种称为 show 的方法,可以将Fraction 对象作为一个字符串的形式打印. 我们可以实现如 Listing 3所示.假如我们按照前面讲的创建 Fraction 对象, 我们可以让它输出自身, 换句话说, 打印自身按照适当的格式. 不幸的是, 这通常不起作用. 为了使输出工作正常, 我们必须告诉 Fraction 类怎样将自身转换为字符串的格式.

Listing 3

def show(self):
     print(self.num,"/",self.den)
>>> myf = Fraction(3,5)
>>> myf.show()
3 / 5
>>> print(myf)
<__main__.Fraction instance at 0x40bce9ac>

在 Python, 所有的类都提供但不是都适用的标准的方法. 其中之一, __str__,就是一个将对象转换为字符串的方法. 这个方法默认的实现是用来以字符串格式返回类实例的地址. 我们必须为这个方法提供一个“更好的”实现. 我们说这个新的方法重载前面的, 或者说重新定义了方法的行为.

要实现这个,我们简单地定义一个名叫 __str__ 的方法并给出实现 如Listing 4. 这个定义除了使用特殊参数 self以外不需要其他的信息. 注意函数中的不同的实现办法.

Listing 4

def __str__(self):
    return str(self.num)+"/"+str(self.den)
>>> myf = Fraction(3,5)
>>> print(myf)
3/5
>>> print("I ate", myf, "of the pizza")
I ate 3/5 of the pizza
>>> myf.__str__()
'3/5'
>>> str(myf)
'3/5'
>>>

我们可以为我们的新 Fraction 类覆盖很多其他的方法. 其中一些最重要的是一些基础的算术运算操作. 我们可以创建两种 Fraction 对象，同时使用“+” 符号将它们相加 . 这时, 如果我们使两分数相加, 我们得到:

>>> f1 = Fraction(1,4)
>>> f2 = Fraction(1,2)
>>> f1+f2
Traceback (most recent call last):
  File "<pyshell#173>", line 1, in -toplevel-
    f1+f2
TypeError: unsupported operand type(s) for +:
          'instance' and 'instance'

如果你仔细观察错误信息, 你将发现问题是： “+” 操作符不能理解Fraction 操作.

我们可以通过给 Fraction 类提供重载的加法函数来实现. 在 Python, 这种方法称为 __add__ 同时需要两个参数. 第一个参数, self,  第二个参数是另一个操作数. 例如,

f1.__add__(f2)

当 Fraction  f1 加 Fraction f2. 可以写成标准的形式：f1+f2.

两个分数必须有相同的分母才能直接相加. 使它们分母相同最简单的方法是通分： ，具体实现如 Listing 5. 加法函数返回了一个新的 Fraction 对象.

Listing 5

def __add__(self,otherfraction):

     newnum = self.num * otherfraction.den + self.den*otherfraction.num
     newden = self.den * otherfraction.den

     return Fraction(newnum,newden)

>>> f1=Fraction(1,4)
>>> f2=Fraction(1,2)
>>> f3=f1+f2
>>> print(f3)
6/8
>>>

上面的加法函数看起来实现了我们期望的, 但是还可以更完美. 注意到 6/8 是正确的结果，但是却不是以 “最简项” 的形式展示的. 最好的表达式为3/4. 为了使我们的结果为最简项的形式, 我们需要一个辅助函数才化简分数. 这个函数可以求出最大公约数, 或者称为 GCD. 可以通过分子和分母的最大公约数来达到化简分数的目的.

计算最大公约数最著名的算法要数 Euclid算法,原理我就不详细指明了，很简单。实现如下：

>>> def gcd(m, n):
    while m % n != 0:
        oldm = m
        oldn = n
        m = oldn
        n = oldm % oldn
    return n

>>> print gcd(20, 10)
10

这样我们就可以化简任何的分数了，代码如下： (Listing 6).

Listing 6

def __add__(self,otherfraction):
    newnum = self.num*otherfraction.den + self.den*otherfraction.num
    newden = self.den * otherfraction.den
    common = gcd(newnum,newden)
    return Fraction(newnum//common,newden//common)

>>> f1=Fraction(1,4)
>>> f2=Fraction(1,2)
>>> f3=f1+f2
>>> print(f3)
3/4

我们的 Fraction 对象现在有两个非常重要的方法，如上图所示. 一些需要新增进我们的实例类 Fraction 的方法是：允许两个分数进行比较. 假如我们有两个 Fraction 对象, f1 和f2. f1==f2 将得到True 假如他们指向同一个对象. 即使分子分母都相同，但是不满足条件依然将不相等. 这被称为 shallow equality (如下图).

我们可以创建 deep equality (如上图)–通过值相等来判断, 不同于引用–通过覆盖 __eq__ 方法.  __eq__ 是另一个存在于所有类中标准方法. __eq__ 方法比较两个对象当值相等的时候返回 True ,否则返回 False.

在 Fraction 类中, 我们实现了 __eq__ 方法通过常规比较方法来比较分数 (see Listing 7). 值得注意的是还有其他的方法可以覆盖. 例如,  __le__ 方法提供了小于等于功能.

Listing 7

def __eq__(self, other):
    firstnum = self.num * other.den
    secondnum = other.num * self.den

    return firstnum == secondnum

完整的 Fraction 类的代码如下所示：

def gcd(m,n):
    while m%n != 0:
        oldm = m
        oldn = n

        m = oldn
        n = oldm%oldn
    return n

class Fraction:
     def __init__(self,top,bottom):
         self.num = top
         self.den = bottom

     def __str__(self):
         return str(self.num)+"/"+str(self.den)

     def show(self):
         print(self.num,"/",self.den)

     def __add__(self,otherfraction):
         newnum = self.num*otherfraction.den + \
                      self.den*otherfraction.num
         newden = self.den * otherfraction.den
         common = gcd(newnum,newden)
         return Fraction(newnum//common,newden//common)

     def __eq__(self, other):
         firstnum = self.num * other.den
         secondnum = other.num * self.den
         return firstnum == secondnum

x = Fraction(1,2)
y = Fraction(2,3)
print(x+y)
print(x == y)

运行结果：

7/6False