摘要：一抽象數(shù)據(jù)類型，縮寫為是計算機領(lǐng)域一種很基礎(chǔ)的方法，基本的思想就是數(shù)據(jù)抽象。二抽象數(shù)據(jù)類型的概念和描述抽象數(shù)據(jù)類型把數(shù)據(jù)定義為抽象的對象集合，只為他們定義可用的操作，而不用暴露具體的實現(xiàn)細(xì)節(jié)。

文章首發(fā)于公眾號一件風(fēng)衣（ID：yijianfengyi）

名人名言強調(diào)基礎(chǔ)的重要性的句子不勝枚舉，數(shù)據(jù)結(jié)構(gòu)與算法作為計算機專業(yè)的必學(xué)科目，其重要性不言而喻。

在以往的教學(xué)體系中，數(shù)據(jù)結(jié)構(gòu)與算法通常結(jié)合C語言進(jìn)行教學(xué)，而近年來Python的興起，已經(jīng)引起了教學(xué)上的變化，據(jù)我了解，已經(jīng)有部分大學(xué)把C語言和Python同時作為計算機專業(yè)的基礎(chǔ)編程課了。

這個系列就和大家一起學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法的Python實現(xiàn)，據(jù)說找工作面試時特別喜歡問基礎(chǔ)的算法問題。

一、抽象數(shù)據(jù)類型（Abstract Data Type，縮寫為ADT）

ADT是計算機領(lǐng)域一種很基礎(chǔ)的方法，基本的思想就是數(shù)據(jù)抽象。圍繞抽象出來的數(shù)據(jù)類型定義各種運算（函數(shù)），形成一個完整的模塊，提供接口以供調(diào)用，這就有了模塊化的編程思想。

（一）數(shù)據(jù)類型和數(shù)據(jù)構(gòu)造

在任何編程語言中，都定義了一些基本的數(shù)據(jù)類型，以Python為例，基本類型有邏輯類型bool、數(shù)值類型int、float等、字符串類型str和一些組合數(shù)據(jù)類型。

對于每一種類型，都定義了相應(yīng)的運算，比如bool類型的值可以為True或False，運算包括and（與）、or（或）、not（非）這類邏輯運算，int類型的值可以為整數(shù)，定義了加減乘除等運算……

但是很多時候基本數(shù)據(jù)類型是不夠用的，比如有理數(shù)、復(fù)數(shù)等，在此以復(fù)數(shù)為例，數(shù)學(xué)上復(fù)數(shù)的形式為a+bi（i為-1的平方根），定義一個復(fù)數(shù)類型的變量，我們需要兩個值，比如寫為：

a1 = 2 
b1 = 1

就可以表示復(fù)數(shù)2+i，同樣，可以定義復(fù)數(shù)上的加法運算函數(shù)：

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)

雖然實現(xiàn)了這個功能，但是用兩個獨立的數(shù)來表示一個復(fù)數(shù)顯然不合適，給后續(xù)的使用帶來了很大不便，不過我們可以改進(jìn)一下，用一個二元組來表示復(fù)數(shù)，約定第一項為實部，第二項為虛部：

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

那么加法運算函數(shù)可以這么寫：

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

調(diào)用就可以直接這么寫：

c3 = complex_plus(c1,c2)

雖然改進(jìn)了使用方式，但是依然有很大的問題：

一是用普通的元組來表示復(fù)數(shù)，不能和其他的元組相互區(qū)分，其他可以用元組表示的類型依然可以進(jìn)行同樣的運算，比如有理數(shù)也用(a,b)來表示，那么可以調(diào)用復(fù)數(shù)的加法運算，把一個復(fù)數(shù)和一個有理數(shù)加起來——實部加分子，虛部加分母，這顯然不科學(xué)；

二是復(fù)數(shù)的形式還算簡潔，只有兩個參數(shù)，對于很多參數(shù)的數(shù)據(jù)類型還使用元組的話，那可真是太麻煩了。

總的來說，這樣的表示方法雖然能實現(xiàn)功能，但造成了很差的可讀性，使用和修改起來都會很困難，于是我們需要面向?qū)ο蟮姆椒▉斫鉀Q這種問題。

（二）抽象數(shù)據(jù)類型的概念和描述

抽象數(shù)據(jù)類型把數(shù)據(jù)定義為抽象的對象集合，只為他們定義可用的操作，而不用暴露具體的實現(xiàn)細(xì)節(jié)。對一個數(shù)據(jù)類型的操作分為三類：

1.構(gòu)造：基于已知的數(shù)據(jù)類型構(gòu)造所需要的數(shù)據(jù)類型，比如基于兩個整數(shù)表示一個有理數(shù)，或是基于兩個實數(shù)表示一個復(fù)數(shù)等；

2.解析：通過對象獲取需要的信息，比如從一個復(fù)數(shù)對象中獲取實部或者虛部，從一個有理數(shù)對象中獲取分子或者分母；

3.變動：修改對象的內(nèi)部信息，比如修改復(fù)數(shù)的實部大小或虛部大小，對象的名稱沒變，但是內(nèi)部的信息發(fā)生了變化。

我們通過一個int之類的名字來代表這個數(shù)據(jù)類型，就可以使用它了。

編程語言的內(nèi)置數(shù)據(jù)類型也是這么一種抽象數(shù)據(jù)類型，構(gòu)造是必要的，根據(jù)是否有變動我們可以把數(shù)據(jù)類型分為可變數(shù)據(jù)類型和不變數(shù)據(jù)類型，Python中，str就是一種不變數(shù)據(jù)類型，list就是一種可變數(shù)據(jù)類型。

那么如何描述一個抽象數(shù)據(jù)類型呢？

以復(fù)數(shù)為例，有如下偽代碼：

ADT ComplexNumber:#定義復(fù)數(shù)抽象數(shù)據(jù)類型
    ComplexNumber(float a,float b)# 構(gòu)造復(fù)數(shù)a+bi
    +(ComplexNumber c1,ComplexNumber c2)# 求復(fù)數(shù)c1 + c2
    -(ComplexNumber c1,ComplexNumber c2)# 求復(fù)數(shù)c1 - c2
    *(ComplexNumber c1,ComplexNumber c2)#求復(fù)數(shù)c1 * c2
    /(ComplexNumber c1,ComplexNumber c2)#求復(fù)數(shù)c1 / c2
    getReal(ComplexNumber c1)# 獲取c1的實部
    getImaginary(ComplexNumber c1)# 獲取c1的虛部

這里用ADT表示這是一個抽象數(shù)據(jù)類型，ComplexNumber為類型名稱，同理我們也可以用類似的方法表示一個有理數(shù)，一個日期，一個銀行賬戶的基本信息等。

總的來說，ADT就是圍繞某個數(shù)據(jù)類型定義的模塊，接口和實現(xiàn)分離，提供接口完成該數(shù)據(jù)類型的各種操作。

二、Python類

Python作為面向?qū)ο蟮木幊陶Z言，用類（class）定義所有類型，包括內(nèi)置的數(shù)據(jù)類型都是類，我們可以這么理解——類是面向?qū)ο缶幊陶Z言的基本類型，一切數(shù)據(jù)類型都是基于類定義的。

（一）復(fù)數(shù)的初階定義

依然以復(fù)數(shù)為例，我們可以在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是關(guān)鍵字，表示類定義的開始，ComplexNumber就是這個類的名字。

每個類中我們都會定義__init__函數(shù)，稱為初始化方法，用于構(gòu)造一個該類的新對象，我們以類名作為函數(shù)創(chuàng)建實例化對象，如：

c1 = ComplexNumber(2,3)

在調(diào)用的時候，應(yīng)當(dāng)給出除self外的其他參數(shù)。

realpart和imaginarypart都是復(fù)數(shù)類的屬性，不用多帶帶聲明，即使在初始化中沒有，在賦值時也會自動創(chuàng)建，但一般不這么做。

調(diào)用其他方法時，也是self表示本實例，應(yīng)當(dāng)給出其他參數(shù)，比如：

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

此時c1的值作為plus方法的第一個參數(shù)，新構(gòu)造的復(fù)數(shù)為第二個。

同理，print函數(shù)中只有一個參數(shù)self，所以調(diào)用的時候這么寫：

c2.print()

執(zhí)行以上語句后我們可以得到如下輸出：

（二）復(fù)數(shù)的高階定義
對于復(fù)數(shù)，我們經(jīng)常使用模的概念，對于z=a+bi，模|z|定義如下：

所以我們需要函數(shù)module()，來求取復(fù)數(shù)的模。可以定義如下

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

調(diào)用輸出一個復(fù)數(shù)時直接這么寫：

print(c2.module())

其中math.sqrt()是求平方根的函數(shù)，需要在程序開頭導(dǎo)入math包：
import math

在定義Python的類時，有這樣的約定，以下劃線開頭的屬性名或函數(shù)名都當(dāng)作內(nèi)部使用的名字，不能夠在類外使用。此外以兩根下劃線開頭（不以兩根下劃線結(jié)尾）的屬性會被特殊處理保護(hù)，不得在類外使用。如果我們不希望復(fù)數(shù)的虛部實部屬性被直接修改，初始化方法中我們可以在屬性前加下劃線，阻止類外的訪問：

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

然而我們有時又很需要讀取這兩個屬性，于是我們可以定義解析操作：

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

這樣可以讀取受保護(hù)的屬性了。

我們再考慮新的問題，在數(shù)學(xué)上我們可以直接用加減乘除的符號來操作復(fù)數(shù)，按照我們上面的定義，顯然調(diào)用起來很不方便，要是能直接把方法定義在操作符上，那使用起來也就方便多了。

好消息是Python中可以這么做！Python中為所有的運算符都定義了特殊的方法名，這類特殊方法名都以雙下劃線開始，雙下劃線結(jié)束，如__add__表示加號，__mul__表示乘號，于是對于復(fù)數(shù)中的加法，我們可以如下實現(xiàn)：

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

注意這段代碼中self和another獲取屬性的方式的區(qū)別。

類似的，我們可以定義其他運算符的操作（包括比較運算符），具體的方法名可以查找Python的文檔。但重載運算符時要注意限制條件，比如虛部實部均為0的復(fù)數(shù)不能作為除數(shù)等。

（三）幾點總結(jié)和提示

1.類定義時格式如下：

class <類名>:
    <語句組>

2.對類中的屬性的訪問，采用圓點記法；
3.實例對象初始化時自動調(diào)用__init__()，第一個參數(shù)self表示正在初始化的對象自身；
4.在定義類時，應(yīng)當(dāng)避免屬性名和方法名相同；
5.靜態(tài)方法、類方法、作用域、繼承等日后再提。

思考：如果要定義一個學(xué)生類，屬性包括姓名，性別，生日，學(xué)號，方法包括計算年齡，修改屬性，打印全部屬性，初始化時生成學(xué)號，規(guī)則是年份+順序五位十進(jìn)制數(shù)，你會怎么實現(xiàn)這個類呢？下一篇中會貼出我的實現(xiàn)方法，歡迎探討。（提示：類中可定義屬性，該屬性不屬于任何實例，只屬于類本身）