本节书摘来自华章出版社《数据结构与算法：Python语言描述》一书中的第2章，第2.2节，作者 裘宗燕，更多章节内容可以访问云栖社区“华章计算机”公众号查看
2.2Python的类
在讨论了抽象数据类型的基本思想和描述技术之后，现在考虑它们在Python语言里的实现。Python语言里没有直接的ADT定义，实现ADT可以采用很多不同的技术。本节介绍最常用也是最自然的一种技术：利用class定义（类定义）实现抽象数据类型。本节假定学习者已有基本的Python编程经验，但不熟悉其中的class定义。熟悉这些内容的读者可以跳过本章下面的内容。本节从例子出发介绍class定义的使用、其结构和主要设施。下一节将进一步讨论Python中基于class的编程技术，称为面向对象技术。
2.2.1有理数类
类（class）定义机制用于定义程序里需要的类型，定义好的一个类就像一个系统内部类型，可以产生该类型的对象（也称为该类的实例），实例对象具有这个类所描述的行为。实际上，Python语言把内置类型都看作类。
在介绍Python类定义的详细情况之前，这里先给出一个类定义的实例。下面代码是一个简化的有理数类的一部分：
class Rational0:
def __init__(self, num, den=1):
self.num = num
self.den = den
def plus(self, another):
den = self.den * another.den
num = (self.num * another.den +
self.den * another.num)
return Rational0(num, den)
def print(self):
print(str(self.num)+"/"+str(self.den))
下面对这段代码做些解释：
class是关键字，表示由这里开始一个类定义。class之后是给定的类名和一个表示类头部结束的冒号。这部分（这一行）称为类定义的头部，随后是类定义的体部分，形式上就是一个语句组。定义一个类，通常是为了创建该类的实例，称为该类的实例对象，简称这个类的对象。例如，上面有理数类的名字是Rational0，定义它就是为了在程序里创建和使用Rational0（一种有理数）对象。
类的体部分通常主要是一批函数定义，所定义的函数称为这个类的方法。最常见的方法是操作本类的实例对象的方法，称为实例方法。这种方法总是从本类的对象出发去调用，其参数表里的第一个参数就表示实际使用时的调用对象，通常以self作为参数名。例如，Rational0类里定义了三个实例方法。下面讨论中简单地说“方法”时，指的总是实例方法，其他情况在后面介绍。
在一个类里，通常都会定义一个名为 init 的方法（其名字是在init的前后各加两个下划线符号），称为初始化方法，其工作是构造本类的新对象。创建实例对象采用函数调用的描述形式，以类名作为函数名，这时系统将建立一个该类的新对象，并自动对这个对象执行 init 方法。例如，下面语句
r1 = Rational0(3, 5)
就是要求创建一个值为3/5的有理数对象，并把这个新对象赋给变量r1。调用式应给出除self之外的其他实际参数。Rational0类的__init__ 方法要求两个实参，上面语句中是3和5。求值表达式时Python系统先建立一个新对象，然后把这个对象作为 __init__方法的self参数去执行方法体。
在Rational0类的__init__方法里有两个语句，要求用实参的值给self.num和self.den赋值。在实例方法的体中，self.fname形式的写法表示本类实例对象的属性，其中fname称为属性名。与Python变量的情况类似，程序里不需要说明对象有哪些属性，赋值时就会创建。上面初始化方法要求给Rational0对象的两个属性赋值，创建本类对象时就会为它建立相应的属性并赋以相应的值。
类里的其他实例方法也应该以self作为第一个参数。对它们的调用需要从本类的实例出发，用圆点形式描述。如果写
r2 = r1.plus(Rational0(7, 15))
赋值右边的表达式调用方法plus，r1的值被称为plus方法的调用对象，方法中self参数将约束于该对象。调用中的实参表达式Rational0(7, 15)创建另一个有理数对象，它将作为plus方法的第二个实参约束到形参another。
上面类定义里的print方法只有一个self参数，其调用形式就应该是r1.print()，不要求其他实参。该方法以字符串形式输出对象r1的内容。
在定义了类Rational0之后，如果送给Python系统下面语句：
r1 = Rational0(3, 5)
r2 = r1.plus(Rational0(7, 15))
r2.print()
解释器将输出80/75。容易看到这个结果没有化简，虽然正确却不是最合适的形式。如果程序里用这样的有理数对象做复杂计算，计算结果的分子和分母都会变得越来越大。虽然Python支持任意大的整数，得到的结果应该是正确的，但存储大的整数需要大的空间，计算也更费时间。所以，实现有理数的计算时应该考虑化简。
下面将考虑一个更完整合理的有理数实现，顺便介绍类定义的更多情况。
2.2.2类定义进阶
如前所述，类定义的一类重要作用是支持创建抽象的数据类型。在建立这种抽象时，人们不希望暴露其实现的内部细节。例如，对于有理数类，不希望暴露这种对象内部是用两个整数分别表示分子和分母。对更复杂的抽象，信息隐藏的意义可能更重要。由于隐藏抽象的内部信息在软件领域意义重大，有些编程语言为此提供了专门机制。Python语言没有专门服务于这种需求的机制，只能依靠一些编程约定。
首先，人们约定，在一个类的定义里，由下划线_开头的属性名（和函数名）都当作内部使用的名字，不应该在这个类之外使用。另外，Python对类定义里以两个下划线开头（但不以两个下划线结尾）的名字做了特殊处理，使得在类定义之外不能直接用这个名字访问。这是另一种保护方式。下面定义更好的有理数类时将遵循这些约定。
上节最后说到有理数的化简问题。在建立有理数时，应该考虑约去其分子和分母的最大公约数，避免无意义的资源浪费。为了完成化简，需要定义一个求最大公约数的函数gcd。这里出现了一个问题：应该在哪里定义这个函数。稍加分析就会发现，现在出现了两个新情况：首先，gcd的参数应该是两个整数，它们不属于被定义的有理数类型。此外，gcd的计算并不依赖任何有理数类的对象，因此其参数表中似乎不应该以表示有理数的self作为第一个参数。但另一方面，这个gcd是为有理数类的实现而需要使用的一种辅助功能，根据信息局部化的原则，局部使用的功能不应该定义为全局函数。综合这两点情况，gcd应该是在有理数类里定义的一个非实例方法。
Python把在类里定义的这种方法称为静态方法（与实例方法不同），描述时需要在函数定义的头部行之前加修饰符 @staticmethod。静态方法的参数表中不应该有self参数，在其他方面没有任何限制。对于静态方法，可以从其定义所在类的名字出发通过圆点形式调用，也可以从该类的对象出发通过圆点形式调用。本质上说，静态方法就是在类里面定义的普通函数，但也是该类的局部函数。
还有一个问题也需要考虑：前面简单有理数类的初始化方法没有检查参数，既没检查参数的类型是否合适（显然，两个实参都应该是整数），也没有检查分母是否为0。此外，人们传送给初始化方法的实参可能有正有负，内部表示应该标准化，例如，保证所有有理数内部的分母为正，用分子的正负表示有理数的正负。这些检查和变换都应该在有理数类的初始化方法里完成，保证构造出的有理数都是合法合规的对象。
考虑了上面这些问题后，可以给出下面的有理数类定义（部分）：
class Rational:
@staticmethod
def _gcd(m, n):
if n == 0:
m, n = n, m
while m != 0:
m, n = n % m, m
return n
def __init__(self, num, den=1):
if not isinstance(num, int) or not isinstance(den, int):
raise TypeError
if den == 0:
raise ZeroDivisionError
sign = 1
if num < 0:
num, sign = -num, -sign
if den < 0:
den, sign = -den, -sign
g = Rational._gcd(num, den)
# call function gcd defined in this class.
self._num = sign * (num//g)
self._den = den//g
在这个类里定义了一个局部使用的求最大公约数的静态方法 _gcd，在初始化方法里使用。初始化函数在开始处检查参数的类型和分母的值，不满足要求抛出适当的异常。随后的if语句提取有理数的符号，几个检查之后sign值为1表示是正数，－1表示是负数。最后用化简后的分子和分母设置有理数的数据属性。
下面考虑Rational类的其他方法。首先，在上面定义中把有理数对象的两个属性都当作内部属性，不应该在类之外去引用它们。但实际计算中有时需要提取有理数的分子或分母。为满足这种需要，应该定义一对解析操作（也是实例方法）：
def num(self): return self._num
def den(self): return self._den
现在考虑有理数的运算。在前面的简单有理数类里定义了名字为plus的方法。对于有理数这种数学类型，人们可能更希望用运算符（＋、－、、/ 等）描述计算过程，写出形式更自然的计算表达式。Python语言支持这种想法，它为所有算术运算符规定了特殊方法名。Python中所有特殊的名字都以两个下划线开始，并以两个下划线结束。例如，与+运算符对应的名字是__add__，与 对应的名字是__mul__。下面是实现有理数运算的几个方法定义，其他运算不难类似地实现：
def __add__(self, another): # mimic + operator
den = self._den * another.den()
num = (self._num * another.den() +
self._den * another.num())
return Rational(num, den)
def __mul__(self, another): # mimic * operator
return Rational(self._num * another.num(),
self._den * another.den())
def __floordiv__(self, another): # mimic // operator
if another.num() == 0:
raise ZeroDivisionError
return Rational(self._num * another.den(),
self._den * another.num())
# ......
# 其他运算符可以类似定义:
# -:__sub__, /:__truediv__, %:__mod__, etc.
这里有几个问题值得提出。首先，通过在每个方法最后用Rational(...,...) 构造新对象，所有构造出的对象都保证能化简为最简形式，不需要在每个建立新有理数的地方考虑化简问题。这种做法很值得提倡。
另外，上面定义除法时用的是整除运算符“//”。在除法方法的开始检查除数并可能抛出异常，也是常规的做法。按照Python的惯例，普通除法“/”的结果应是浮点数，对应方法名是__truediv__，如果需要可以另行定义，实现从有理数到浮点数的转换。
还请注意一个情况：算术运算都要求另一个参数也是有理数对象。如果希望检查这个条件，可以在方法定义的开始加一个条件语句，用内置谓词isinstance(another, Rational) 检查。另外，由于another是另一个有理数对象，上面方法定义中没有直接去访问其成分，而是通过解析函数。
有理数对象经常需要比较相等和不等，有些类的对象需要比较大小。Python为各种关系运算提供了特殊方法名。下面是有理数相等、小于运算的方法定义：
def __eq__(self, another):
return self._num * another.den() == self._den * another.num()
def __lt__(self, other):
return self._num * another.den() < self._den * another.num()
# 其他比较运算符可以类似定义:
# !=:__ne__, <=:__le__, >:__gt__, >=:__ge__
不等、小于、大于等运算可以类似地实现。
为了便于输出等目的，人们经常在类里定义一个把该类的对象转换到字符串的方法。为了保证系统的str类型转换函数能正确使用，这个方法应该采用特殊名字 __str__，内置函数str将调用它。下面是有理数类的字符串转换方法：
def __str__(self):
return str(self._num) + "/" + str(self._den)
def print(self):
print(self._num, "/", self._den)
至此一个简单的有理数类就基本完成了，其中缺少的一些运算的定义情况类似，读者自己完成已经没有实质性困难。
在程序定义好一个类之后，就可以像使用Python系统里的类型一样使用它。首先是创建类的对象，形式是采用类名的函数调用式，前面已经说明：
five = Rational(5) # 初始化方法的默认参数保证用整数直接创建有理数
x = Rational(3, 5)
如果一个变量的值是这个类的对象，就可以用圆点记法调用该类的实例方法：
x.print()
由于有理数类定义了str转换函数，可以直接用标准函数print输出：
print("Two thirds are", Rational(2, 3))
对于有理数，可以使用类中定义的算术运算符和条件运算符：
y = five + x * Rational(5, 17)
if y < Rational(123, 11): ...
还可以获得对象的类型，或者检查对象和类的关系：
t = type(five)
if isinstance(five, Rational): ...
总而言之，从使用的各方面看，用类机制定义的类型与Python系统的内部类型没有什么差别，地位和用法相同。Python标准库的一些类型就是这样定义的。
2.2.3本书采用的ADT描述形式
本书后面章节将主要采用Python的面向对象技术和类结构定义各种数据类型，为了更好地与之对应，这里对ADT的描述形式做一点改动。后面使用的ADT描述将模仿Python类定义的形式，也认为ADT描述的是一个类型，因此：
ADT的基本创建函数将以self为第一个参数，表示被创建的对象，其他参数表示为正确创建对象时需要提供的其他信息。
在ADT描述中的每个操作也都以self作为第一个参数，表示被操作对象。
定义二元运算时也采用同样的形式，其参数表将包括self和另一个同类型对象，操作返回的是运算生成的结果对象。
虽然Python函数定义的参数表里没有描述参数类型的机制，但为了提供更多信息，在下面写ADT定义时，有时还是采用写参数类型的形式，用于说明操作对具体参数的类型要求。在很多情况下，这样写可以省略一些文字说明。
按这种方式描述的有理数对象ADT如下：
