数据结构与算法的Python实现（一）——抽象数据类型和Python类

文章首发于公众号一件风衣（ID：yijianfengyi）

名人名言强调基础的重要性的句子不胜枚举，数据结构与算法作为计算机专业的必学科目，其重要性不言而喻。

在以往的教学体系中，数据结构与算法通常结合C语言进行教学，而近年来Python的兴起，已经引起了教学上的变化，据我了解，已经有部分大学把C语言和Python同时作为计算机专业的基础编程课了。

这个系列就和大家一起学习数据结构与算法的Python实现，据说找工作面试时特别喜欢问基础的算法问题。

一、抽象数据类型（Abstract Data Type，缩写为ADT）

ADT是计算机领域一种很基础的方法，基本的思想就是数据抽象。围绕抽象出来的数据类型定义各种运算（函数），形成一个完整的模块，提供接口以供调用，这就有了模块化的编程思想。

（一）数据类型和数据构造

在任何编程语言中，都定义了一些基本的数据类型，以Python为例，基本类型有逻辑类型bool、数值类型int、float等、字符串类型str和一些组合数据类型。

对于每一种类型，都定义了相应的运算，比如bool类型的值可以为True或False，运算包括and（与）、or（或）、not（非）这类逻辑运算，int类型的值可以为整数，定义了加减乘除等运算……

但是很多时候基本数据类型是不够用的，比如有理数、复数等，在此以复数为例，数学上复数的形式为a+bi（i为-1的平方根），定义一个复数类型的变量，我们需要两个值，比如写为：

a1 = 2 
b1 = 1

就可以表示复数2+i，同样，可以定义复数上的加法运算函数：

def complex_plus(a1,b1,a2,b2):
    realpart = a1 +a2
    imaginarypart = b1 + b2
    return realpart,imaginarypart

计算2+3i与3-4i的和就可以这么使用：

a3 , b3 = complex_plus(2,3,3,-4)

虽然实现了这个功能，但是用两个独立的数来表示一个复数显然不合适，给后续的使用带来了很大不便，不过我们可以改进一下，用一个二元组来表示复数，约定第一项为实部，第二项为虚部：

c1 = (2,3)
c2 = (3,-4)

那么加法运算函数可以这么写：

def complex_plus(c1,c2):
    realpart = c1[0] + c2[0]
    imaginarypart = c1[1] + c2[1]
    return realpart,imaginarypart

调用就可以直接这么写：

c3 = complex_plus(c1,c2)

虽然改进了使用方式，但是依然有很大的问题：

一是用普通的元组来表示复数，不能和其他的元组相互区分，其他可以用元组表示的类型依然可以进行同样的运算，比如有理数也用(a,b)来表示，那么可以调用复数的加法运算，把一个复数和一个有理数加起来——实部加分子，虚部加分母，这显然不科学；

二是复数的形式还算简洁，只有两个参数，对于很多参数的数据类型还使用元组的话，那可真是太麻烦了。

总的来说，这样的表示方法虽然能实现功能，但造成了很差的可读性，使用和修改起来都会很困难，于是我们需要面向对象的方法来解决这种问题。

（二）抽象数据类型的概念和描述

抽象数据类型把数据定义为抽象的对象集合，只为他们定义可用的操作，而不用暴露具体的实现细节。对一个数据类型的操作分为三类：

1.构造：基于已知的数据类型构造所需要的数据类型，比如基于两个整数表示一个有理数，或是基于两个实数表示一个复数等；

2.解析：通过对象获取需要的信息，比如从一个复数对象中获取实部或者虚部，从一个有理数对象中获取分子或者分母；

3.变动：修改对象的内部信息，比如修改复数的实部大小或虚部大小，对象的名称没变，但是内部的信息发生了变化。

我们通过一个int之类的名字来代表这个数据类型，就可以使用它了。

编程语言的内置数据类型也是这么一种抽象数据类型，构造是必要的，根据是否有变动我们可以把数据类型分为可变数据类型和不变数据类型，Python中，str就是一种不变数据类型，list就是一种可变数据类型。

那么如何描述一个抽象数据类型呢？

以复数为例，有如下伪代码：

ADT ComplexNumber:#定义复数抽象数据类型
    ComplexNumber(float a,float b)# 构造复数a+bi
    +(ComplexNumber c1,ComplexNumber c2)# 求复数c1 + c2
    -(ComplexNumber c1,ComplexNumber c2)# 求复数c1 - c2
    *(ComplexNumber c1,ComplexNumber c2)#求复数c1 * c2
    /(ComplexNumber c1,ComplexNumber c2)#求复数c1 / c2
    getReal(ComplexNumber c1)# 获取c1的实部
    getImaginary(ComplexNumber c1)# 获取c1的虚部

这里用ADT表示这是一个抽象数据类型，ComplexNumber为类型名称，同理我们也可以用类似的方法表示一个有理数，一个日期，一个银行账户的基本信息等。

总的来说，ADT就是围绕某个数据类型定义的模块，接口和实现分离，提供接口完成该数据类型的各种操作。

二、Python类

Python作为面向对象的编程语言，用类（class）定义所有类型，包括内置的数据类型都是类，我们可以这么理解——类是面向对象编程语言的基本类型，一切数据类型都是基于类定义的。

（一）复数的初阶定义

依然以复数为例，我们可以在Python中这么定义一个类：

class ComplexNumber:
    def __init__(self,realpart,imaginarypart=0):
        self.realpart = realpart
        self.imaginarypart = imaginarypart

    def plus(self,another):
        realpart = self.realpart + another.realpart
        imaginarypart = self.imaginarypart + another.imaginarypart
        return ComplexNumber(realpart, imaginarypart)

    def print(self):
        print(str(self.realpart) + “+” +str(self.imaginarypart) + “i”)

class是关键字，表示类定义的开始，ComplexNumber就是这个类的名字。

每个类中我们都会定义__init__函数，称为初始化方法，用于构造一个该类的新对象，我们以类名作为函数创建实例化对象，如：

c1 = ComplexNumber(2,3)

在调用的时候，应当给出除self外的其他参数。

realpart和imaginarypart都是复数类的属性，不用单独声明，即使在初始化中没有，在赋值时也会自动创建，但一般不这么做。

调用其他方法时，也是self表示本实例，应当给出其他参数，比如：

c2 = c1.plus(ComplexNumber(3,-2))

此时c1的值作为plus方法的第一个参数，新构造的复数为第二个。

同理，print函数中只有一个参数self，所以调用的时候这么写：

c2.print()

执行以上语句后我们可以得到如下输出：

（二）复数的高阶定义
对于复数，我们经常使用模的概念，对于z=a+bi，模|z|定义如下：

所以我们需要函数module()，来求取复数的模。可以定义如下

def module():
    return math.sqrt(self.realpart *self.realpart, self.imaginarypart * self.imaginarypart)

调用输出一个复数时直接这么写：

print(c2.module())

其中math.sqrt()是求平方根的函数，需要在程序开头导入math包：
import math

在定义Python的类时，有这样的约定，以下划线开头的属性名或函数名都当作内部使用的名字，不能够在类外使用。此外以两根下划线开头（不以两根下划线结尾）的属性会被特殊处理保护，不得在类外使用。如果我们不希望复数的虚部实部属性被直接修改，初始化方法中我们可以在属性前加下划线，阻止类外的访问：

def __init__(self,realpart,imaginarypart=0):
        self._realpart = realpart
        self._imaginarypart = imaginarypart

然而我们有时又很需要读取这两个属性，于是我们可以定义解析操作：

def realpart(self): return self._realpart
def imaginarypart(self): return self._imaginarypart

这样可以读取受保护的属性了。

我们再考虑新的问题，在数学上我们可以直接用加减乘除的符号来操作复数，按照我们上面的定义，显然调用起来很不方便，要是能直接把方法定义在操作符上，那使用起来也就方便多了。

好消息是Python中可以这么做！Python中为所有的运算符都定义了特殊的方法名，这类特殊方法名都以双下划线开始，双下划线结束，如__add__表示加号，__mul__表示乘号，于是对于复数中的加法，我们可以如下实现：

def __add__(self,another):
    realpart = self._realpart + another.realpart()
    imaginarypart = self._imaginarypart + another.imaginarypart()
    return ComplexNumber(realpart, imaginarypart)

注意这段代码中self和another获取属性的方式的区别。

类似的，我们可以定义其他运算符的操作（包括比较运算符），具体的方法名可以查找Python的文档。但重载运算符时要注意限制条件，比如虚部实部均为0的复数不能作为除数等。

（三）几点总结和提示

1.类定义时格式如下：

class <类名>:
    <语句组>

2.对类中的属性的访问，采用圆点记法；
3.实例对象初始化时自动调用__init__()，第一个参数self表示正在初始化的对象自身；
4.在定义类时，应当避免属性名和方法名相同；
5.静态方法、类方法、作用域、继承等日后再提。

思考：如果要定义一个学生类，属性包括姓名，性别，生日，学号，方法包括计算年龄，修改属性，打印全部属性，初始化时生成学号，规则是年份+顺序五位十进制数，你会怎么实现这个类呢？下一篇中会贴出我的实现方法，欢迎探讨。（提示：类中可定义属性，该属性不属于任何实例，只属于类本身）